class
	EL_HASH_SET [H -> HASHABLE]

inherit
	EL_HASH_SET_BASE [H]
		export
			{EL_HASH_SET, EL_HASH_SET_ITERATION_CURSOR}
				append_to, comparison_method, content, key_tester, position_default_key
			{ANY} set_key_tester
		redefine
			copy, is_equal, is_subset, intersect, subtract
		end

	EL_CONTAINER_STRUCTURE [H]
		rename
			current_container as current_table,
			intersection as intersection_query
		undefine
			count, copy, is_equal, object_comparison
		end

	ITERABLE [H]
		undefine
			copy, is_equal
		end

	TRAVERSABLE [H]
		rename
			item as iteration_item
		undefine
			copy, changeable_comparison_criterion, compare_objects, compare_references,
			is_equal
		end

	EL_SET [H]
		undefine
			copy, is_equal
		end

create
	make_equal, make, make_equal_array, make_from, make_from_special

convert
	make_equal_array ({ARRAY [H]})

feature {NONE} -- Initialization

	make (n: INTEGER)
		-- Allocate hash table for at least `n' items using `=' for comparison.
		-- The table will be resized automatically if more than `n' items are inserted.
		require
			n_non_negative: n >= 0
		do
			make_with_key_tester (n, new_key_tester)
			compare_references
			set_comparison_method
		ensure
			capacity_big_enough: capacity >= n
			reference_comparison: reference_comparison
		end

	make_equal (n: INTEGER)
		-- Allocate hash table for at least `n' items using `~' for comparison.
		-- The table will be resized automatically if more than `n' items are inserted.
		require
			n_non_negative: n >= 0
		do
			make_with_key_tester (n, new_key_tester)
			compare_objects
			set_comparison_method
		ensure
			capacity_big_enough: capacity >= n
		end

	make_equal_array (array: ARRAY [H])
		do
			make_equal (array.count)
			array.do_all (agent put)
		end

	make_from (container: CONTAINER [H]; a_object_comparison: BOOLEAN)
		do
			if attached as_structure (container) as structure then
				make (structure.count)

			-- May `object_comparison' be changed ?
			-- (Answer: only if set empty; otherwise insertions might
			-- introduce duplicates, destroying the set property.)
				object_comparison := a_object_comparison

				structure.do_for_all (create {EL_PUT_IN_COLLECTION_ACTION [H]}.make (Current))
			else
				make (0)
				object_comparison := a_object_comparison
			end
			set_comparison_method
		end

	make_from_special (area: SPECIAL [H]; a_object_comparison: BOOLEAN)
		local
			i: INTEGER
		do
			make (area.count)
			object_comparison := a_object_comparison
			set_comparison_method
			from i := 0 until i = area.count loop
				put (area [i])
				i := i + 1
			end
		end

feature -- Access

	new_cursor: EL_HASH_SET_ITERATION_CURSOR [H]
		-- <Precursor>
		do
			create Result.make (Current)
		end

	subset (is_member: PREDICATE [H]; inverse: BOOLEAN): like Current
		local
			include: BOOLEAN; subset_area: SPECIAL [H]
			index, last_index: INTEGER; break: BOOLEAN
			area_item: H
		do
			create subset_area.make_empty (capacity)
			if attached content as area and then attached deleted_marks as deleted then
				last_index := capacity - 1
				from index := -1 until break loop
					index := next_iteration_index (index, last_index, area, deleted)
					if index > last_index then
						break := True
					else
						area_item := area [index]
						include := is_member (area_item)
						if inverse then
							include := not include
						end
						if include then
							subset_area.extend (area_item)
						end
					end
				end
			end
			create Result.make_from_special (subset_area, object_comparison)
		end

	subset_exclude (is_member: PREDICATE [H]): like Current
		do
			Result := subset (is_member, True)
		end

	subset_include (is_member: PREDICATE [H]): like Current
		do
			Result := subset (is_member, False)
		end

	to_list, linear_representation: EL_ARRAYED_LIST [H]
		local
			index, last_index: INTEGER; break: BOOLEAN
			list_area: SPECIAL [H]
		do
			create list_area.make_empty (count)
			if attached content as area and then attached deleted_marks as deleted then
				last_index := capacity - 1
				from index := -1 until break loop
					index := next_iteration_index (index, last_index, area, deleted)
					if index > last_index then
						break := True
					else
						list_area.extend (area [index])
					end
				end
			end
			create Result.make_from_special (list_area)
		end

	to_representation: EL_HASH_SET_REPRESENTATION [H]
		-- to representation applied to reflected field of type `H'
		do
			create Result.make (Current)
		end

feature -- Comparison

	is_equal (other: like Current): BOOLEAN
		-- Does table contain the same information as `other'?
		local
			index, last_index: INTEGER; break: BOOLEAN
		do
			if Current = other then
				Result := True

			elseif count = other.count and then object_comparison = other.object_comparison
				and then key_tester ~ other.key_tester
			then
				if attached content as area and then attached deleted_marks as deleted then
					last_index := capacity - 1
					Result := True
					from index := -1 until not Result or break loop
						index := next_iteration_index (index, last_index, area, deleted)
						if index > last_index then
							break := True
						else
							Result := other.has (area [index])
						end
					end
				end
			end
		end

	is_subset (other: TRAVERSABLE_SUBSET [H]): BOOLEAN
		-- Is `Current' set a subset of `other' ?
		local
			index, last_index: INTEGER; break: BOOLEAN
		do
			if is_empty then
				Result := True

			elseif not other.is_empty and then count <= other.count
				and then attached content as area and then attached deleted_marks as deleted
			then
				last_index := capacity - 1; Result := True
				from index := -1 until break or not Result loop
					index := next_iteration_index (index, last_index, area, deleted)
					if index > last_index then
						break := True
					else
						Result := other.has (area [index])
					end
				end
			end
		end

feature -- Duplication

	copy (other: like Current)
		-- Re-initialize from `other'.
		do
			standard_copy (other)
			content := other.content.twin
			deleted_marks := other.deleted_marks.twin
		end

	duplicate (n: INTEGER): like Current
		do
			create Result.make (0)
			Result.copy (Current)
		end

feature -- Basic operations

	accommodate (n: INTEGER)
		-- Reallocate table with enough space for `n' items;
		-- keep all current items.
		do
			resize (n.max (count))
		end

	intersect (other: TRAVERSABLE_SUBSET [H])
		-- Remove all items not in `other'.
		-- No effect if `other' `is_empty'.
		do
			if not other.is_empty then
				query_not_in (other).do_all (agent prune)
			else
				wipe_out
			end
		end

	resize (n: INTEGER)
		-- Resize table to accommodate `n' elements.
		do
			if (content.count * Size_threshold <= 100 * n) and then attached empty_duplicate (n) as new then
				append_to (new)
				standard_copy (new)
			end
		end

	search (key: H)
		-- Search for item of key `key'
		-- If found, set `found' to True, and set
		-- `found_item' to item associated with `key'.
		local
			default_value: H
		do
			if attached content as area and then attached deleted_marks as deleted then
				set_position (key, area, deleted)
				inspect control
					when Found_constant then
						found_item := area [position]
				else
					found_item := default_value
				end
			end
		end

feature -- Removal

	prune (key: H)
		-- Remove item associated with `key', if present.
		-- Set `control' to `Removed' or `Not_found_constant'.
		local
			default_key: H
		do
			if attached content as area and then attached deleted_marks as deleted then
				set_position (key, area, deleted)
				inspect control
					when Found_constant then
						area.put (default_key, position)
						deleted.put (True, position)
						set_position_default_key (key, -1)
						count := count - 1
				else
				end
			end
		end

	remove_item
		do
			prune (key_for_iteration)
		end

	subtract (other: TRAVERSABLE_SUBSET [H])
		-- Remove all items also in `other'.
		do
			if not (other.is_empty or is_empty) then
				intersection_query (other).do_all (agent prune)
			end
		end

	wipe_out
		-- Reset all items to default values.
		local
			default_key: H
		do
			content.fill_with_default (0, capacity - 1)
			deleted_marks.fill_with_default (0, capacity - 1)
			count := 0
			control := 0
			position := 0
			position_default_key := -1
			found_item := default_key
		end

feature -- Insertion

	force (key: H)
		-- If `key' is present, replace corresponding item by `new',
		-- if not, insert item `new' with key `key'.
		-- Set `control' to `Insertion_ok'.
		local
			area: like content; deleted: like deleted_marks
		do
			area := content; deleted := deleted_marks
			set_position (key, area, deleted)
			inspect control
				when Found_constant then
			else
				if soon_full then
					expand_size
					area := content; deleted := deleted_marks
					set_position (key, area, deleted)
				end
				count := count + 1
			end
			area.put (key, position)
			if deleted [position] then
				deleted [position] := False
			end
			set_position_default_key (key, position)
			control := Insertion_ok
		ensure then
			insertion_done: item (key) = key
		end

	merge_other (other: EL_HASH_SET [H])
		-- Merge two search_tables
		do
			if other.count /= 0 then
				resize (count + other.count)
				other.append_to (Current)
			end
		end

	put (key: H)
		-- Attempt to insert `new' with `key'.
		-- Set `control' to `Insertion_ok' or `Insertion_conflict'.
		-- No insertion if conflict.
		local
			area: like content; deleted: like deleted_marks
		do
			area := content; deleted := deleted_marks
			set_position (key, area, deleted)
			inspect control
				when Found_constant then
					control := Insertion_conflict
					found_item := area [position]
					inserted := False
			else
				if soon_full then
					expand_size
					area := content; deleted := deleted_marks
					set_position (key, area, deleted)
				end
				area.put (key, position)
				if deleted [position] then
					deleted [position] := False
				end
				set_position_default_key (key, position)
				count := count + 1
				control := Insertion_ok
				found_item := key
				inserted := True
			end
		ensure then
			insertion_done: control = Insertion_ok implies item (key) = key
			item_if_found: found implies found_item = content [position]
		end

	put_copy (key: H)
		-- put a copy of `key' if not found
		-- In either case, set `found_item' to the item
		-- now associated with `key' (previous item if
		-- there was one, `new' otherwise).
		-- Attempt to insert `new' with `key'.
		-- Set `control' to `Inserted_constant' or `Conflict_constant'.
		-- No insertion if `conflict' is `True'.
		do
			put (key)
			if inserted then
				found_item := key.twin
				content.put (found_item, position)
			end
		ensure then
			insertion_done: inserted implies item (key) ~ key and item (key) /= key
			item_if_found: found_item = content [position]
		end

feature -- Cursor movement

	after, off: BOOLEAN
		-- Is the iteration cursor off ?
		do
			Result := iteration_position > capacity - 1
		end

	forth
		-- Advance cursor to next occupied position,
		-- or `off' if no such position remains.
		do
			iteration_position := next_iteration_position (iteration_position)
		end

	go_to (pos: like cursor)
		-- Move to position `pos'.
		require
			valid_cursor: valid_cursor (pos)
		do
			iteration_position := pos
		end

	start
		-- Iteration initialization
		do
			iteration_position := next_iteration_position (-1)
		end

feature -- Contract Support

	valid_cursor (index: like cursor): BOOLEAN
		-- Can cursor be moved to position `index'?
		do
			if index >= capacity or else (index >= 0 and index <= capacity) then
				Result := valid_key (index, content, deleted_marks)
			end
		end

feature {NONE} -- Implementation

	current_table: like Current
		do
			Result := Current
		end

	empty_duplicate (n: INTEGER): like Current
		-- Create an empty copy of Current that can accommodate `n' items
		require
			n_non_negative: n >= 0
		local
			tester: like key_tester
		do
			tester := key_tester
			if object_comparison then
				create Result.make_equal (n)
			else
				create Result.make (n)
			end
			Result.set_key_tester (tester)
		ensure
			same_key_tester: Result.key_tester = key_tester
		end

	set_position_default_key (key: H; index: INTEGER)
		local
			default_key: H
		do
			inspect comparison_method
				when Compare_expanded then
					if key = default_key then
						position_default_key := index
					end
			else
			end
		end

	subset_strategy_selection (v: H; other: EL_HASH_SET [H]): SUBSET_STRATEGY_HASHABLE [H]
		-- Strategy to calculate several subset features selected depending
		-- on the dynamic type of `v' and `other'
		do
			create Result
		end

end