From: Mathieu Bouchard <matju@...>
Date: 2001-01-23T10:35:18+09:00
Subject: [ruby-talk:9743] Write Ruby's Array in Ruby


Here is a _rough_ sketch of the ArrayInterface / ArrayMixin modules. See
introduction at the top of the file.

I invite people on this list to contribute missing methods, bug fixing,
performance improvements, etc.

Future versions will be posted on my webpage instead (and announced here
of course)

ArrayMixin.rb:
----------------8<--------cut-here--------8<----------------

=begin

ArrayMixin 0.1

Purpose of this document:

	* To describe a minimal but vaguely efficient interface for
	interacting with Array-like objects. 

	* To implement a set of default replacements for methods provided
	in Array but not declared in the Array interface.

This is split in two parts:

	ArrayInterface
	ArrayMixin

Warning:

	This software is not tested at all.
	It contains a billion bugs (roughly)

Author(s):

	Mathieu Bouchard <matju@cam.org>

	Copyright (c) 2001 by Mathieu Bouchard
	Licensed under the same license as Ruby.

=end

module ArrayInterface
	def length
		# must return the number of elements in the array.
		raise NotImplementedError
	end
	def get(i)
		# i is in 0...length
		# returns contents of cell i
		raise NotImplementedError
	end
	def put(i,v)
		# i is in 0...length
		# sets cell i to value v
		# returns nil
		# note: never changes the array length
		raise NotImplementedError
	end
	def get_many(i,n)
		# i is in 0...length
		# i+n is in 0..length
		# returns plain Array of elements i...(i+n)
		raise NotImplementedError
	end
	def splice(i,n,*v)
		# i is in 0..length
		# i+n is in 0..length
		# deletes elements in i...(i+n)
		# inserts *v elements at i
		# returns nil
		raise NotImplementedError
	end

	# Exceptions:
	# NotImplementedError: abstract method not overloaded
	# ArgumentError: argument precondition failed

	#! and dup ?
end

module ArrayMixin
	include ArrayInterface
	include Enumerable

	# def ArrayMixin.[](*v); end

	def initialize(length,value)
		# presuming the array is created by the implementor,
		# and is empty.

		if (len < 0)
			raise ArgumentError "negative array size"
		end

		(0...length).each {|i| put i,value }
	end

	def [](i,l=nil)
		#! handle the Range case
		#! handle the length case
		#! handle number of args errors
		if i < 0 then i = length - 1 - i end
		if i < 0 || i >= length then nil else get i end
	end
	def []=(i,v,w=nil)
		#! handle the Range case
		#! handle the length case
		#! handle number of args errors
		if i < 0 then i += length end
		if i < 0 then
			nil
		else
			if i >= length
				splice length,0,*Array.new(i-length+1)
			end
			put i,v
			v
		end
	end

	def +(other)
		foo = dup
		foo.splice length,0,*other
		foo
	end
	def -(other)
		t = {}
		each {|x| t[x]=1 }
		other.each {|x| t.delete x }
		r
	end
	# as seen in [ruby-talk:6756]
	def &(other)
		t = {}
		r = []
		other.each {|x| t[x]=1 }
		uniq.each  {|x| r<<x if t.has_key? x }
		r
	end
	# as seen in [ruby-talk:6756]
	def |(other)
		t = {}
		r = []
		(self+other).each {|x| r<<x unless t.has_key?(x); t[x]=1 }
		r
	end

	def *(n)
		foo = []
		n.times { foo.splice length,0,*self }
	end

	def <<(v)
		foo.splice length,0,v
		self
	end

	def <=>(other)
		#! write me
	end

	def assoc(key)
		#! write me
	end

	def clear
		splice 0,length
	end

	def concat(other)
                splice length,0,*other
		self
	end		

	def compact!
		#! write me
	end
	def compact
		dup.compact!
	end

	def delete(v,&proc)
		#! write me
	end
	def delete_at(i)
		splice(i,1)
	end

	def delete_if(i)
		#! write me
	end

	def each(&proc)
		#! write me
	end

	def each_index(&proc)
		(0...length).each {}
	end

	def empty?
		length == 0
	end

	def fill(v,start=0,length=nil)
		#! write me / fix me
	end

	def filter(&proc)
		(0...length).each {|i| put i, proc.call(get i) }
	end
	def flatten
		dup.flatten!
	end
	def flatten!
		#! write me
	end
	def freeze
		#! write me
	end
	def frozen
		#! write me
	end
	def include?(v)
		[] != find_all {|x| x == v }
	end
	def index(v)
		#! write me
	end
	def indexes(*i)
		#! write me
	end
	def indices(*i)
		#! write me
	end
	def join(sep=$,)
		#! write me
	end
	def size
		length
	end
	def nitems
		find_all {|x| x != nil }.length
	end
	def pack(template)
		#! write me (?)
		get_many(0,length).pack(template)
	end
	def pop
		splice length-1,1
	end
	def push(v)
		splice length,0,v
	end
	def rassoc(v)
		#! write me
	end

	def reject(i,&proc); delete_if(i,&proc); end

	def replace(other)
		splice 0,length,*other
	end
	def reverse
		dup.reverse!
	end
	def reverse!
		#! write me
	end
	def reverse_each(&proc)
		reverse.each(&proc)
	end
	def rindex(v)
		#! write me
	end
	def shift
		splice 0,1
	end
	def sort(&proc)
		dup.sort!
	end
#	def sort!(&proc=proc{|a,b|a<=>b})
	def sort!(&proc)
		proc ||= proc{|a,b|a<=>b}
		#! write me
	end

	# as seen in [ruby-talk:6756]
	def uniq; self|[] end
	def uniq!; replace self|[]; end

	def unshift(v)
		splice 0,0,v
	end
end

----------------8<--------cut-here--------8<----------------

matju