#!/usr/bin/env ruby

=begin
ArrayMixin 0.2

AUTHOR(S)

	Mathieu Bouchard <matju@cam.org>

LICENSING

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

PURPOSE

1. To describe a minimal but reasonably efficient interface for
interacting with Array-like objects. 

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

3. In short this can be seen as equivalent to Perl's tie.

4. This is also can be seen as a small part of an upcoming Ruby-in-Ruby. I
am not aware of anyone who is seriously involved in that sort of thing,
but who knows.

STRUCTURE

the ArrayMixin file contains several components:

1. module ArrayInterface

2. module ArrayMixin

WARNING

	This software is not tested at all.
	It contains a billion bugs (roughly)
	Call it pre-alpha.

TO DO

1. Fix all the things marked with #!@#$

2. Try it and write a useful program with it

3. Adapt Dave Thomas' test suite to work on these classes

4. Ensure conformance with that test suite.

5. Categorize ArrayMixin methods.

6. Fix the possibly many bugs with the return values in ArrayMixin.

7. Fix the return types of methods that return a new Array. (decide
between the basic Array and self.type and other...)

8. Tune performance

=end

# Minimal interface for using Arrays. Some new methods have been added
# because the equivalent in the Array class are too complex to be elegantly
# and simply defined by any Array provider.
module ArrayInterface

	# length() returns the number of elements in the array.
	def length
		raise NotImplementedError
	end

	# get(i) returns contents of cell i.
	# i is the number of a cell. Such a number is always in the
	# range 0...length.
	# should raise IndexError when i is invalid.
	def get(i)
		raise NotImplementedError
	end

	# i is like in get(i). put(i,v) sets cell i to v's value.
	# the return value should not be used; but it should be nil.
	# note: never should change the array length.
	def put(i,v)
		raise NotImplementedError
	end

	# returns plain Array of elements i...(i+n)
	# i is like in get(i).
	# n.type <= Integer and n >= 0
	# i+n should be in 0..length
	def get_many(i,n)
		raise NotImplementedError
	end

	# deletes a range and inserts elements at a same point.
	# i is the insertion point.
	# i is in range 0..length
	# i+n is in range 0..length
	# deletes elements in i...(i+n)
	# inserts *v elements at i
	# the return value should not be used; but it should be nil.
	def put_many(i,n,*v)
		raise NotImplementedError
	end

	# Exceptions:
	# NotImplementedError: abstract method not overloaded
	# IndexError: invalid index
	#	(element index or insertion point or range length)
	# ArgumentError: other argument error, if applicable
	# May throw other exceptions when it makes sense.

	#!@#$ what do I do with 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

# category: [] and []=

	# this whole category of methods is possibly a mess.

	def range_to_i_n(r)
		i,j = r.begin,r.end
		i += length if i < 0
		return nil if i < 0
		j += length if j < 0
		n = j-i + (r.exclude_end? ? 0 : 1)
		return (if n < 0 then nil else [i,n] end)
	end
	# private :range_to_i_n

	def subseq(i,n)
		if i > length || i < 0 || n < 0 then return nil end
		if i+n > length then n = length - i end
		if n > 0 then get_many(i,n) else [] end
	end
	# private :subseq

	def [](i,*args)
		if args.length > 1 then
			raise ArgumentError,
				"wrong # of arguments (%d for 2)" % args.length
		elsif args.length == 0 && ! i <= Range then
			if i < 0 then i += length end
			return(if i < 0 || i >= length then nil else get i end)
		elsif args.length == 1 then
			return subseq(i,args[0])
		end

		foo = range_to_i_n(i)
		return (if foo.nil? then nil else subseq foo[0],foo[1] end)
	end

	def []=(i,*args)
		if args.length == 0 then
			raise ArgumentError,
				"wrong # of arguments (1 for 2)" % args.length
		end
		v = args.pop

		#!@#$ return values are wrong here
		#!@#$ bugful

		if args.length > 1 then
			raise ArgumentError,
				"wrong # of arguments (%d for 3)" % args.length
		elsif args.length == 0 && ! i <= Range then
			if i < 0 then i += length end
			return(if i < 0 || i >= length then nil else put i,v end)
		elsif args.length == 1 then
			return put_many(i,args[0],*v)
		end

		foo = range_to_i_n(i)
		return (if foo.nil? then nil else put_many foo[0],foo[1],*v end)
	end

# category: miscellaneous operations

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

	def <=>(other)
		length.times {|i|
			c = self.get(i) <=> other.get(i)
			return c if c != 0
		}
		0
	end

	def clear
		put_many 0,length
		self
	end

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

	def delete(v)
		delete_if {|x| x == v}
	end

	def delete_at(i)
		foo = get(i)
		put_many(i,1)
		foo
	end

	#!@#$ alias?
	def reject(i,&proc); delete_if(i,&proc); end

	def delete_if(i,&proc)
		foo = []
		each {|x|
			foo << x unless proc.call(x)
		}
		replace foo
	end

	def each(&proc)
		length.times {|i|
			proc.call get(i)
		}
	end

	def each_index(&proc)
		(0...length).each(&proc)
	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

	# there is strange (?) behaviour involving recursive arrays.
	# I think #flatten and #flatten! do not behave the same.
	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)
		each_with_index {|x,i|
			return i if x==v
		}
		nil
	end

	#!@#$ alias?
	def indexes(*i); indices(*i); end

	# this may be a good candidate for adding to ArrayInterface
	def indices(*i)
		i.collect {|x| get x }
	end

	#!@#$ this is O(n**2). Make it O(n log n)
	def join(sep=$,)
		return "" if length==0
		foo = get 0
		(1...length).each {|i|
			foo += sep
			foo += get(i)
		}
		foo
	end

	#!@#$ alias?
	def size
		length
	end

	def pack(template)
		#!@#$ write me (?)
		get_many(0,length).pack(template)
	end

	def replace(other)
		put_many 0,length,*other
		self
	end

	def reverse!
		#!@#$ write me
	end

	def reverse_each(&proc)
		reverse.each(&proc)
	end

	def rindex(v)
		#!@#$ write me
	end

#	def slice(*args)
#		#!@#$ write me
#	end

#	def slice!(*args)
#		#!@#$ write me
#		replace slice(*args)
#	end

# category: stack/queue

	#!@#$ alias?
	def push(v); put_many length,0,v; self; end
	def <<(v);   put_many length,0,v; self; end

	def pop; foo = get(length-1); put_many length-1,1; foo; end
	def shift; foo = get(0); put_many 0,1; foo; end
	def unshift(v); put_many 0,0,v; end

# category: dup wrappers for some methods

	def compact; dup.compact!; end
	def flatten; dup.flatten!; end
	def reverse; dup.reverse!; end
	def sort(&proc); dup.sort!(&proc); end

# category: shortcuts involving nil

	def compact!; delete_if {|x| x.nil? }; end
	def nitems; find_all {|x| x != nil }.length; end

# category: array of [key,value] arrays

	def assoc(key)
		#!@#$ write me
	end

	def rassoc(v)
		#!@#$ write me
	end

# category: sorting

	# &proc must be present
	# range.exclude_end? == false
	def sort_partition_range!(range,&proc)
		pivot = get(range.end)
		foo = get_many(start,end+1-start)
		bar = find_all {|x| x < pivot }
		pivot_pos = bar.length
		bar << find_all {|x| x == pivot }
		bar << find_all {|x| x  > pivot }
		put_many start,end+1-start,*bar
		return pivot_pos
	end

	# &proc must be present
	# range.exclude_end? == false
	def sort_range!(range,&proc)
		if range.end - range.start < 0 then return nil end
		pivot = sort_partition_range!(range,&proc)
		a = sort_range!(range.start .. pivot-1)
		b = sort_range!(pivot+1 .. range_end)
		a || b
	end

	# private :sort_partition_range!
	# private :sort_range!

	def sort!(&proc)
		proc ||= proc{|a,b|a<=>b}
		sort_range!(0..length-1,&proc)
	end

# category: set operations

	def +(other)
		foo = dup
		foo.put_many 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

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

	def uniq!; replace self|[]; end

end

class ArrayUsingArray
	include ArrayMixin
	def initialize
		#!@#$ write me
		@array = []
	end
	def length
		@array.length
	end
	def get(i)
		@array[i]
	end
	def put(i,v)
		@array[i]=v
		nil
	end
	def get_many(i,n)
		@array[i,n]
	end
	def put_many(i,n,*v)
		@array[i,n]=v
		nil
	end
end