note
	description: "Multiple purpose array which is linear, extendable, sortable and iterable"
	author: "Mark Howard"
	date: "$Date$"
	revision: "$Revision$"
	path: "$File: //rose/source/kernel/infrastructure/containers/rose_linear_array.e $"

class LINEAR_ARRAY [G]

inherit
	SORTABLE_ARRAY [G]
		redefine
			binary_search,
			linear_search
		end

create
	make, make_empty, make_from_array, make_from_linear, make_from_array_reversed, make_with_default_value

convert
	make_from_array({ARRAY[G]})

feature {NONE} -- Correction

--	correct_mismatch is
--			-- Attempt to correct object mismatch using `mismatch_information'.
--		local
--			l_mismatch: MISMATCH_INFORMATION
--		do
--			l_mismatch := mismatch_information
--		end

feature -- Access

	plus alias "+" (a_other: LINEAR [G]): like Current
			-- Union of 'Current' and 'a_other'
		require
			valid_other: a_other /= Void
		do
			Result := twin
			if a_other /= Void  then
				from a_other.start until a_other.off loop
					Result.extend (a_other.item)
					a_other.forth
				end
			end
		end

	subset (a_indices: ARRAY [INTEGER]): like Current
			-- Subset composed of items at 'a_indices' from this array
		local
			i, j, k, l_lower: INTEGER
		do
			k := a_indices.count
			l_lower := a_indices.lower
			create Result.make (1,k)
			from i := 1 until i > k loop
				j := a_indices.item (l_lower + i - 1)
				if not valid_index (j) then
					(create {EXCEPTIONS}).raise ("Invalid index given to LINEAR_ARRAY.subset")
				end
				Result.put (item (j),i)
				i := i + 1
			end
		end

	subset3 (a_indices: ARRAY [INTEGER]): like Current
			-- Subset composed of items at 'a_indices' from this array
			-- compare to subset feature, subset3 has loose requirement. If a_indices[i] is invalid, put null in position i.
		local
			i, j, k, l_lower: INTEGER
		do
			k := a_indices.count
			l_lower := a_indices.lower
			create Result.make (1,k)
			from i := 1 until i > k loop
				j := a_indices.item (l_lower + i - 1)
				if not valid_index (j) then
					print ("%NInvalid index given to LINEAR_ARRAY.subset%N")
				else
					Result.put (item (j),i)
				end
				i := i + 1
			end
		end

	subarray_by_flags(a_flags : ARRAY[BOOLEAN]) : like Current
		-- sub array by a valid flag array
		do
			create Result.make_empty
			if a_flags /= Void then
				from start until off loop
					if a_flags.valid_index (index) and then a_flags[index] then
						Result.extend(current_item)
					end
					forth
				end
			end
		end

--	random_subarray (a_count: INTEGER) : like Current is
--			-- a random subarray of size `a_count'
--			-- empty is `a_count' <= 0, the entire array is `a_count' >= `count'
--		local
--			l_needed, l_remaining, l_found, l_seed, i : INTEGER
--			l_date : ROSE_DATE
--			l_random : RANDOM
--			l_random_double : DOUBLE
--		do
--			if a_count <= 0 then
--				l_needed := 0
--			elseif a_count >= count then
--				l_needed := count
--			else
--				l_needed := a_count
--			end

--			if l_needed = 0 then
--				create Result.make_empty
--			else
--				l_remaining := count
--				l_found := 0
--				create Result.make(1,l_needed)
--				create l_random.make
--				create l_date.make_now
--				l_seed := l_date.second
--				l_random.set_seed (l_seed)
--				from i := 1 until i > count or l_needed = 0 loop
--					l_random.forth
--					l_random_double := l_random.double_item
--					if l_random_double <= l_needed/l_remaining then
--						-- add this to the array
--						l_found := l_found + 1
--						l_needed := l_needed - 1
--						Result[l_found] := item(i)
--					end
--					i := i + 1
--					l_remaining := l_remaining - 1
--				end
--			end
--		end

	valid_subarray(a_valid : FUNCTION[G, BOOLEAN]) : like Current
		-- sub array by a agent
		local
			i : INTEGER
		do
			create Result.make_empty
			if a_valid /= Void then
				from i := lower until i > upper loop
					if a_valid.item([item(i)]) then
						Result.extend(item(i))
					end
					i := i + 1
				end
			end
		end

	valid_flags(a_valid : FUNCTION[G, BOOLEAN]) : LINEAR_ARRAY[BOOLEAN]
		-- valid data item flags
		local
			i : INTEGER
		do
			create Result.make(lower, upper)
			if a_valid /= Void then
				from i := lower until i > upper loop
					Result.put(a_valid.item([item(i)]), i)
					i := i + 1
				end
			else
				from i := lower until i > upper loop
					Result.put(True, i)
					i := i + 1
				end
			end
		end

	values_intersect (a_linear: LINEAR [G]): BOOLEAN
			--do the elements of a_linear intersect our elements?
		do
			from a_linear.start until Result or else a_linear.off loop
				Result := has_value (a_linear.item)
				a_linear.forth
			end
		end

	references_intersect (a_linear: LINEAR [G]): BOOLEAN
		do
			from a_linear.start until Result or else a_linear.off loop
				Result := has_reference (a_linear.item)
				a_linear.forth
			end
		end

	min_max (a_comparison: FUNCTION [G, G, BOOLEAN]): PAIR [G,G]
		do
			if not is_empty then
				from
					start
					create Result.make (item (lower),item (lower))
				until
					off
				loop
					if a_comparison.item ([current_item,Result.first]) then
						Result.set_first (current_item)
					end
					if a_comparison.item ([Result.second,current_item]) then
						Result.set_second (current_item)
					end
					forth
				end
			end
		end

	equivalent_from_order (a_order: FUNCTION [G,G,BOOLEAN]; a_1: G; a_2: G): BOOLEAN
			-- determine if two items are the same using just a less_than function
		do
			Result := (not a_order.item ([a_1, a_2])) and (not a_order.item ([a_2, a_1]))
		end

	quotient_with_less_than_function (a_order : FUNCTION [G,G,BOOLEAN]): LINEAR_ARRAY [LINEAR_ARRAY [G]]
			-- create a quotient, just using less than function
		do
			Result := ordered_quotient (a_order, agent equivalent_from_order (a_order, ?, ?))
		end

	ordered_quotient (a_order : FUNCTION [G,G,BOOLEAN]; a_equivalent: FUNCTION [G,G,BOOLEAN]): LINEAR_ARRAY [LINEAR_ARRAY [G]]
			-- create ordered quotient
		local
			l_array : LINEAR_ARRAY [G]
		do
			create l_array.make_from_array (Current)
			l_array.sort_by (a_order)
			Result := l_array.quotient (a_equivalent)
		end

	quotient (a_equivalent: FUNCTION [G,G,BOOLEAN]): LINEAR_ARRAY [LINEAR_ARRAY [G]]
			-- create quotient; assumes you have sorted the array
		local
			l_last: G
			l_array: LINEAR_ARRAY [G]
		do
			create Result.make_empty
			from start until off loop
				if index = lower then
					create l_array.make_empty
					l_array.extend (current_item)
					Result.extend (l_array)
				else
					if a_equivalent.item ([current_item,l_last]) then
						l_array.extend (current_item)
					else
						create l_array.make_empty
						Result.extend (l_array)
						l_array.extend (current_item)
					end
				end
				l_last := current_item
				forth
			end
		end

	is_sorted: BOOLEAN
			-- Is `Current' sorted?
		require
			comparison_not_void: comparison /= Void
		local
			i: INTEGER
			l_last_item, l_current_item: like item
		do
			Result := True
			if count > 1 then
				from
					i := lower + 1
					l_last_item := item (lower)
				until
					i > upper or not Result
				loop
					l_current_item := item (i)
					comparison.call ([l_last_item, l_current_item])
					Result := comparison.last_result
					l_last_item := l_current_item
					i := i + 1
				end
			end
		end

feature -- Basic operations

	subarray (a_start_pos, a_end_pos: INTEGER): like Current
		require
			valid_start_pos: valid_index (a_start_pos)
			valid_end_pos: a_end_pos <= upper
			valid_bounds: (a_start_pos <= a_end_pos) or (a_start_pos = a_end_pos + 1)
		do
			create Result.make_from_array(array_subarray(a_start_pos, a_end_pos))
		ensure
			lower: Result.lower = 1
			upper: Result.count = a_end_pos - a_start_pos + 1
		end

	reversed: like Current
			-- Reversed array from current (last swapped with first etc.)
		local
			i: INTEGER
		do
			create Result.make_empty
			from
				i := count
			until
				i < 1
			loop
				Result.extend (item (i))
				i := i - 1
			end
		end

	comparison: FUNCTION [G, G, BOOLEAN]

	sort_by (a_comparison: FUNCTION [G, G, BOOLEAN])
			-- Sort this array using 'a_comparison'.
		do
			comparison := a_comparison
			sort
			comparison := Void
		end

	sort_by_and_remember (a_routine: FUNCTION [G, G, BOOLEAN])
			-- Sort this array using 'a_comparison', and remember 'a_comparison' for further searching
		require
			need_comparison: a_routine /= Void or comparison /= Void
		do
			if a_routine /= Void then
				comparison := a_routine
			end
			sort
		end

	set_comparison (a_comparison : like comparison)
			-- Assign `a_comparison' to `comparison'.
		do
			comparison := a_comparison
		ensure
			comparison_set : comparison = a_comparison
		end

	binary_search (a_g: G)
			-- binary search for item `a_g'
			-- current better be sorted ...
		do
			Precursor (a_g)
			index := found_index
		end

	linear_search (a_g: G)
			-- linear search (look at every item) for item `a_g'
		do
			Precursor (a_g)
			index := found_index
		end

	concatenate (a_linear: LINEAR [G])
			-- Appends each element of 'a_linear' to the end of this array.
		do
			if a_linear /= Void then
				from a_linear.start until a_linear.off loop
					extend (a_linear.item)
					a_linear.forth
				end
			end
		end

	merge_values (a_linear: LINEAR [G])
		do
			from a_linear.start until a_linear.off loop
				if not has_value (a_linear.item) then
					extend (a_linear.item)
				end
				a_linear.forth
			end
		end

	merge_references (a_linear: LINEAR [G])
		do
			from a_linear.start until a_linear.off loop
				if not has_reference (a_linear.item) then
					extend (a_linear.item)
				end
				a_linear.forth
			end
		end

	union_values (a_linear: LINEAR [G]): like Current
		do
			Result := twin
			Result.merge_values (a_linear)
		end

	union_references (a_linear: LINEAR [G]): like Current
		do
			Result := twin
			Result.merge_references (a_linear)
		end

	union_values_is_equal (a_linear: LINEAR [G]): like Current
		do
			Result := twin
			from a_linear.start until a_linear.off loop
				if not has(a_linear.item) then
					Result.extend(a_linear.item)
				end
				a_linear.forth
			end
		end

	intersection_values(a_linear: LINEAR [G]): like Current
			-- Intersection of current and argument array values, uses is_equal
		do
			create Result.make_empty
			from a_linear.start until a_linear.off loop
				if has(a_linear.item) then
					Result.extend(a_linear.item)
				end
				a_linear.forth
			end
		end

	ordered_union_values (a_other: like Current; a_comparison: like comparison; a_distinct: BOOLEAN): like Current
			-- Current and other must already been in the order specified by comparison
			-- Perform a full linear merge to get an ordered union of the two sets
		require
			a_other_not_void: a_other /= Void
		local
			i, j: INTEGER
		do
			if count = 0 then
				Result := a_other.twin
			elseif a_other.count = 0 then
				Result := twin
			else
				create Result.make_empty
				from i := lower; j := a_other.lower
				until i > upper and j > a_other.upper
				loop
					if j > a_other.upper or else (i <= upper and a_comparison.item ([item (i), a_other.item (j)])) then
						Result.extend (item (i))
						i := i + 1
					elseif i > upper or else a_comparison.item ([a_other.item (j), item (i)]) then
						Result.extend (a_other.item (j))
						j := j + 1
					else
						Result.extend (item (i))
						if not a_distinct then
							Result.extend (a_other.item (j))
						end
						i := i + 1
						j := j + 1
					end
				end
			end
		end

	selected_items(a_ixs : ARRAY[INTEGER]) : like Current
		local
			i, l_ix : INTEGER
		do
			if a_ixs /= Void then
				create Result.make(1, a_ixs.count)
				from i := 1 until i > a_ixs.count loop
					l_ix := a_ixs.item(i)
					if valid_index(l_ix) then
						Result.put(item(l_ix), i)
					end
					i := i + 1
				end
			end
		end

feature {NONE} -- Comparison

	less_than (a, b: G): BOOLEAN
		do
			if a /= Void and b /= Void then
				Result := comparison.item ([a,b])
			elseif a /= Void and b = Void then
				Result := True
			else
				Result := False
			end
		end

end -- class LINEAR_ARRAY