note
	description: "[
		Hash tables, used to store items identified by string keys that are compared with or without case sensitivity.
	]"
	legal: "See notice at end of class."
	status: "See notice at end of class."
	warning: "[
		Modifying an object used as a key by an item present in a table will
		cause incorrect behavior. If you will be modifying key objects,
		pass a clone, not the object itself, or an immutable object, as key argument to
		put and replace_key.
	]"
	date: "$Date: 2016-12-08 10:30:24 +0000 (Thu, 08 Dec 2016) $"
	revision: "$Revision: 99662 $"

class 
	STRING_TABLE [G]

create 
	make,
	make_equal,
	make_caseless,
	make_equal_caseless

feature {NONE} -- Initialization

	default_create
			-- Process instances of classes with no creation clause.
			-- (Default: do nothing.)
			-- (from ANY)
		do
		end

	make_caseless (n: INTEGER_32)
			-- Allocate hash table for at least n items.
			-- The table will be resized automatically
			-- if more than n items are inserted.
			-- Keys will be compared caseless.
		require
			n_non_negative: n >= 0
		do
			is_case_insensitive := True
			make (n)
		ensure
			breathing_space: n < capacity
			more_than_minimum: capacity > Minimum_capacity
			no_status: not special_status
			is_case_insensitive: is_case_insensitive
		end

	make_equal_caseless (n: INTEGER_32)
			-- Allocate hash table for at least n items.
			-- The table will be resized automatically
			-- if more than n items are inserted.
			-- Keys will be compared caseless.
			-- Items will be compared using ~.
		require
			n_non_negative: n >= 0
		do
			is_case_insensitive := True
			make_equal (n)
		ensure
			breathing_space: n < capacity
			more_than_minimum: capacity > Minimum_capacity
			no_status: not special_status
			is_case_insensitive: is_case_insensitive
			compare_objects: object_comparison
		end
	
feature -- Initialization

	accommodate (n: INTEGER_32)
			-- Reallocate table with enough space for n items;
			-- keep all current items.
			-- (from HASH_TABLE)
		require -- from HASH_TABLE
				n >= 0
		local
			i, nb: INTEGER_32
			new_table: STRING_TABLE [G]
			l_content: like content
			l_keys: like keys
		do
			from
				new_table := empty_duplicate (keys.count.max (n))
				l_content := content
				l_keys := keys
				nb := l_keys.count
			until
				i = nb
			loop
				if occupied (i) then
					new_table.put (l_content.item (i), l_keys.item (i))
				end
				i := i + 1
			end
			if has_default then
				i := indexes_map.item (capacity);
				new_table.put (l_content.item (i), keys.item (i))
			end
			set_content (new_table.content)
			set_keys (new_table.keys)
			set_deleted_marks (new_table.deleted_marks)
			set_indexes_map (new_table.indexes_map)
			capacity := new_table.capacity
			iteration_position := new_table.iteration_position
		ensure -- from HASH_TABLE
			count_not_changed: count = old count
			breathing_space: count < capacity
		end

	make (n: INTEGER_32)
			-- Allocate hash table for at least n items.
			-- The table will be resized automatically
			-- if more than n items are inserted.
			-- (from HASH_TABLE)
		require -- from HASH_TABLE
			n_non_negative: n >= 0
		local
			clever: PRIMES
			l_default_value: detachable G
			l_default_key: detachable READABLE_STRING_GENERAL
			l_size: INTEGER_32
		do
			create clever
			l_size := n.max (Minimum_capacity)
			l_size := l_size + l_size // 2 + 1
			l_size := clever.higher_prime (l_size)
			capacity := l_size
			create content.make_empty (n + 1)
			create keys.make_empty (n + 1)
			create deleted_marks.make_filled (False, n + 1)
			create indexes_map.make_filled (Ht_impossible_position, l_size + 1)
			iteration_position := n + 1
			count := 0
			deleted_item_position := Ht_impossible_position
			control := 0
			found_item := l_default_value
			has_default := False
			item_position := 0
			ht_lowest_deleted_position := Ht_max_position
			ht_deleted_item := l_default_value
			ht_deleted_key := l_default_key
		ensure -- from HASH_TABLE
			breathing_space: n < capacity
			more_than_minimum: capacity > Minimum_capacity
			no_status: not special_status
		end

	make_equal (n: INTEGER_32)
			-- Allocate hash table for at least n items.
			-- The table will be resized automatically
			-- if more than n items are inserted.
			-- Use ~ to compare items.
			-- (from HASH_TABLE)
		require -- from HASH_TABLE
			n_non_negative: n >= 0
		do
			make (n)
			compare_objects
		ensure -- from HASH_TABLE
			breathing_space: n < capacity
			more_than_minimum: capacity > Minimum_capacity
			no_status: not special_status
			compare_objects: object_comparison
		end
	
feature -- Access

	at alias "@" (key: READABLE_STRING_GENERAL): detachable G assign force
			-- Item associated with key, if present
			-- otherwise default value of type G.
			-- Was declared in HASH_TABLE as synonym of item.
			-- (from HASH_TABLE)
		note
			option: stable
		local
			l_default_key: detachable READABLE_STRING_GENERAL
			hash_value, increment, l_pos, l_item_pos, l_capacity: INTEGER_32
			l_first_deleted_position: INTEGER_32
			stop: INTEGER_32
			l_keys: like keys
			l_indexes: like indexes_map
			l_deleted_marks: like deleted_marks
			l_key: READABLE_STRING_GENERAL
		do
			l_first_deleted_position := Ht_impossible_position
			if key = l_default_key or key = Void then
				if has_default then
					Result := content.item (indexes_map.item (capacity))
				end
			else
				from
					l_keys := keys
					l_indexes := indexes_map
					l_deleted_marks := deleted_marks
					l_capacity := capacity
					stop := l_capacity
					hash_value := hash_code_of (key)
					increment := 1 + hash_value \\ (l_capacity - 1)
					l_item_pos := (hash_value \\ l_capacity) - increment
				until
					stop = 0
				loop
					l_item_pos := (l_item_pos + increment) \\ l_capacity
					l_pos := l_indexes [l_item_pos]
					if l_pos >= 0 then
						l_key := l_keys.item (l_pos)
						debug ("detect_hash_table_catcall")
							check
								catcall_detected: l_key /= Void and then l_key.same_type (key)
							end
						end
						if same_keys (l_key, key) then
							stop := 1
							Result := content.item (l_pos)
						end
					elseif l_pos = Ht_impossible_position then
						stop := 1
					elseif l_first_deleted_position = Ht_impossible_position then
						l_pos := - l_pos + Ht_deleted_position
						check
							l_pos_valid: l_pos < l_deleted_marks.count
						end
						if not l_deleted_marks [l_pos] then
							stop := 1
						else
							l_first_deleted_position := l_item_pos
						end
					end
					stop := stop - 1
				end
			end
		ensure then -- from HASH_TABLE
			default_value_if_not_present: (not has (key)) implies (Result = computed_default_value)
		end

	current_keys: ARRAY [READABLE_STRING_GENERAL]
			-- New array containing actually used keys, from 1 to count
			-- (from HASH_TABLE)
		local
			j: INTEGER_32
			old_iteration_position: INTEGER_32
		do
			if is_empty then
				create Result.make_empty
			else
				old_iteration_position := iteration_position
				from
					start
					create Result.make_filled (key_for_iteration, 1, count)
					j := 1
					forth
				until
					off
				loop
					j := j + 1;
					Result.put (key_for_iteration, j)
					forth
				end
				iteration_position := old_iteration_position
			end
		ensure -- from HASH_TABLE
			good_count: Result.count = count
		end

	cursor: CURSOR
			-- Current cursor position
			-- (from HASH_TABLE)
		do
			create {HASH_TABLE_CURSOR} Result.make (iteration_position)
		ensure -- from HASH_TABLE
			cursor_not_void: Result /= Void
		end

	definite_item (key: READABLE_STRING_GENERAL): G
			-- Entry of key k.
			-- (from HASH_TABLE)
		require -- from TABLE
			valid_key: has (key)
		require -- from TABLE
			valid_key: has (key)
		local
			old_position: like item_position
			old_control: like control
		do
			old_position := item_position
			old_control := control
			internal_search (key)
			Result := content.item (position)
			control := old_control
			item_position := old_position
		end

	found_item: detachable G
			-- Item, if any, yielded by last search operation
			-- (from HASH_TABLE)

	generating_type: TYPE [detachable STRING_TABLE [G]]
			-- Type of current object
			-- (type of which it is a direct instance)
			-- (from ANY)
		external
			"built_in"
		ensure -- from ANY
			generating_type_not_void: Result /= Void
		end

	generator: STRING_8
			-- Name of current object's generating class
			-- (base class of the type of which it is a direct instance)
			-- (from ANY)
		external
			"built_in"
		ensure -- from ANY
			generator_not_void: Result /= Void
			generator_not_empty: not Result.is_empty
		end

	has (key: READABLE_STRING_GENERAL): BOOLEAN
			-- Is there an item in the table with key key?
			-- (from HASH_TABLE)
		require -- from  TABLE
			True
		local
			l_default_key: detachable READABLE_STRING_GENERAL
			hash_value, increment, l_pos, l_item_pos, l_capacity: INTEGER_32
			l_first_deleted_position: INTEGER_32
			stop: INTEGER_32
			l_keys: like keys
			l_indexes: like indexes_map
			l_deleted_marks: like deleted_marks
			l_key: READABLE_STRING_GENERAL
		do
			l_first_deleted_position := Ht_impossible_position
			if key = l_default_key or key = Void then
				if has_default then
					Result := True
				end
			else
				from
					l_keys := keys
					l_indexes := indexes_map
					l_deleted_marks := deleted_marks
					l_capacity := capacity
					stop := l_capacity
					hash_value := hash_code_of (key)
					increment := 1 + hash_value \\ (l_capacity - 1)
					l_item_pos := (hash_value \\ l_capacity) - increment
				until
					stop = 0
				loop
					l_item_pos := (l_item_pos + increment) \\ l_capacity
					l_pos := l_indexes [l_item_pos]
					if l_pos >= 0 then
						l_key := l_keys.item (l_pos)
						debug ("detect_hash_table_catcall")
							check
								catcall_detected: l_key /= Void and then l_key.same_type (key)
							end
						end
						if same_keys (l_key, key) then
							stop := 1
							Result := True
						end
					elseif l_pos = Ht_impossible_position then
						stop := 1
					elseif l_first_deleted_position = Ht_impossible_position then
						l_pos := - l_pos + Ht_deleted_position
						check
							l_pos_valid: l_pos < l_deleted_marks.count
						end
						if not l_deleted_marks [l_pos] then
							stop := 1
						else
							l_first_deleted_position := l_item_pos
						end
					end
					stop := stop - 1
				end
			end
		ensure then -- from HASH_TABLE
			default_case: (key = computed_default_key) implies (Result = has_default)
		end

	has_item (v: G): BOOLEAN
			-- Does structure include v?
			-- (Reference or object equality, based on object_comparison.)
			-- (from HASH_TABLE)
		local
			i, nb: INTEGER_32
			l_content: like content
		do
			if has_default then
				Result := v = content.item (indexes_map.item (capacity))
			end
			if not Result then
				l_content := content
				nb := l_content.count
				if object_comparison then
					from
					until
						i = nb or else Result
					loop
						Result := occupied (i) and then (v ~ l_content.item (i))
						i := i + 1
					end
				else
					from
					until
						i = nb or else Result
					loop
						Result := occupied (i) and then (v = l_content.item (i))
						i := i + 1
					end
				end
			end
		ensure -- from CONTAINER
			not_found_in_empty: Result implies not is_empty
		end

	has_key (key: READABLE_STRING_GENERAL): BOOLEAN
			-- Is there an item in the table with key key?
			-- Set found_item to the found item.
			-- (from HASH_TABLE)
		local
			old_position: INTEGER_32
			l_default_value: detachable G
		do
			old_position := item_position
			internal_search (key)
			Result := found
			if Result then
				found_item := content.item (position)
			else
				found_item := l_default_value
			end
			item_position := old_position
		ensure then -- from HASH_TABLE
			default_case: (key = computed_default_key) implies (Result = has_default)
			found: Result = found
			item_if_found: found implies (found_item = item (key))
		end

	item alias "[]" (key: READABLE_STRING_GENERAL): detachable G assign force
			-- Item associated with key, if present
			-- otherwise default value of type G.
			-- Was declared in HASH_TABLE as synonym of at.
			-- (from HASH_TABLE)
		note
			option: stable
		local
			l_default_key: detachable READABLE_STRING_GENERAL
			hash_value, increment, l_pos, l_item_pos, l_capacity: INTEGER_32
			l_first_deleted_position: INTEGER_32
			stop: INTEGER_32
			l_keys: like keys
			l_indexes: like indexes_map
			l_deleted_marks: like deleted_marks
			l_key: READABLE_STRING_GENERAL
		do
			l_first_deleted_position := Ht_impossible_position
			if key = l_default_key or key = Void then
				if has_default then
					Result := content.item (indexes_map.item (capacity))
				end
			else
				from
					l_keys := keys
					l_indexes := indexes_map
					l_deleted_marks := deleted_marks
					l_capacity := capacity
					stop := l_capacity
					hash_value := hash_code_of (key)
					increment := 1 + hash_value \\ (l_capacity - 1)
					l_item_pos := (hash_value \\ l_capacity) - increment
				until
					stop = 0
				loop
					l_item_pos := (l_item_pos + increment) \\ l_capacity
					l_pos := l_indexes [l_item_pos]
					if l_pos >= 0 then
						l_key := l_keys.item (l_pos)
						debug ("detect_hash_table_catcall")
							check
								catcall_detected: l_key /= Void and then l_key.same_type (key)
							end
						end
						if same_keys (l_key, key) then
							stop := 1
							Result := content.item (l_pos)
						end
					elseif l_pos = Ht_impossible_position then
						stop := 1
					elseif l_first_deleted_position = Ht_impossible_position then
						l_pos := - l_pos + Ht_deleted_position
						check
							l_pos_valid: l_pos < l_deleted_marks.count
						end
						if not l_deleted_marks [l_pos] then
							stop := 1
						else
							l_first_deleted_position := l_item_pos
						end
					end
					stop := stop - 1
				end
			end
		ensure then -- from HASH_TABLE
			default_value_if_not_present: (not has (key)) implies (Result = computed_default_value)
		end

	item_for_iteration: G
			-- Element at current iteration position
			-- (from HASH_TABLE)
		require -- from HASH_TABLE
			not_off: not off
		do
			Result := content.item (iteration_position)
		end

	iteration_item (i: INTEGER_32): G
			-- Entry at position i.
			-- (from HASH_TABLE)
		require -- from READABLE_INDEXABLE
			valid_index: valid_iteration_index (i)
		do
			Result := content.item (i)
		end

	key_for_iteration: READABLE_STRING_GENERAL
			-- Key at current iteration position
			-- (from HASH_TABLE)
		require -- from HASH_TABLE
			not_off: not off
		do
			Result := keys.item (iteration_position)
		end

	new_cursor: HASH_TABLE_ITERATION_CURSOR [G, READABLE_STRING_GENERAL]
			-- Fresh cursor associated with current structure
			-- (from HASH_TABLE)
		require -- from  ITERABLE
			True
		do
			create Result.make (Current);
			Result.start
		ensure -- from ITERABLE
			result_attached: Result /= Void
		end
	
feature -- Measurement

	capacity: INTEGER_32
			-- Number of items that may be stored.
			-- (from HASH_TABLE)

	count: INTEGER_32
			-- Number of items in table
			-- (from HASH_TABLE)

	index_set: INTEGER_INTERVAL
		obsolete "Use `lower' and `upper' instead. [2017-05-31]"
			-- Range of acceptable indexes.
			-- (from READABLE_INDEXABLE)
		do
			create Result.make (iteration_lower, iteration_upper)
		ensure -- from READABLE_INDEXABLE
			not_void: Result /= Void
			empty_if_not_in_order: (iteration_lower > iteration_upper) implies Result.is_empty
			same_lower_if_not_empty: (iteration_lower <= iteration_upper) implies Result.lower = iteration_lower
			same_upper_if_not_empty: (iteration_lower <= iteration_upper) implies Result.upper = iteration_upper
		end

	iteration_lower: INTEGER_32
			-- Minimum index.
			-- (from HASH_TABLE)
		do
			Result := next_iteration_position (-1)
		end

	iteration_upper: INTEGER_32
			-- Maximum index.
			-- (from HASH_TABLE)
		do
			Result := previous_iteration_position (keys.count)
		end

	occurrences (v: G): INTEGER_32
			-- Number of table items equal to v.
			-- (from HASH_TABLE)
		local
			old_iteration_position: INTEGER_32
		do
			old_iteration_position := iteration_position
			if object_comparison then
				from
					start
				until
					off
				loop
					if item_for_iteration ~ v then
						Result := Result + 1
					end
					forth
				end
			else
				from
					start
				until
					off
				loop
					if item_for_iteration = v then
						Result := Result + 1
					end
					forth
				end
			end
			iteration_position := old_iteration_position
		ensure -- from BAG
			non_negative_occurrences: Result >= 0
		end
	
feature {NONE} -- Measurement

	estimated_count_of (other: ITERABLE [G]): INTEGER_32
			-- Estimated number of elements in other.
			-- (from CONTAINER)
		do
			if attached {FINITE [G]} other as f then
				Result := f.count
			elseif attached {READABLE_INDEXABLE [G]} other as r then
				Result := r.upper - r.lower + 1
			end
		ensure -- from CONTAINER
			instance_free: class
			non_negative_result: Result >= 0
		end
	
feature -- Comparison

	frozen deep_equal (a: detachable ANY; b: like arg #1): BOOLEAN
			-- Are a and b either both void
			-- or attached to isomorphic object structures?
			-- (from ANY)
		do
			if a = Void then
				Result := b = Void
			else
				Result := b /= Void and then a.is_deep_equal (b)
			end
		ensure -- from ANY
			instance_free: class
			shallow_implies_deep: standard_equal (a, b) implies Result
			both_or_none_void: (a = Void) implies (Result = (b = Void))
			same_type: (Result and (a /= Void)) implies (b /= Void and then a.same_type (b))
			symmetric: Result implies deep_equal (b, a)
		end

	disjoint (other: HASH_TABLE [G, READABLE_STRING_GENERAL]): BOOLEAN
			-- Is Current and other disjoint on their keys?
			-- Use same_keys for comparison.
			-- (from HASH_TABLE)
		do
			Result := is_empty or else other.is_empty or else not across
				other as o
			some
				has (o.key)
			end
		end

	frozen equal (a: detachable ANY; b: like arg #1): BOOLEAN
			-- Are a and b either both void or attached
			-- to objects considered equal?
			-- (from ANY)
		do
			if a = Void then
				Result := b = Void
			else
				Result := b /= Void and then a.is_equal (b)
			end
		ensure -- from ANY
			instance_free: class
			definition: Result = (a = Void and b = Void) or else ((a /= Void and b /= Void) and then a.is_equal (b))
		end

	frozen is_deep_equal alias "≡≡≡" (other: STRING_TABLE [G]): BOOLEAN
			-- Are Current and other attached to isomorphic object structures?
			-- (from ANY)
		require -- from ANY
			other_not_void: other /= Void
		external
			"built_in"
		ensure -- from ANY
			shallow_implies_deep: standard_is_equal (other) implies Result
			same_type: Result implies same_type (other)
			symmetric: Result implies other.is_deep_equal (Current)
		end

	is_equal (other: like Current): BOOLEAN
			-- Does table contain the same information as other?
		require -- from ANY
			other_not_void: other /= Void
		do
			if is_case_insensitive = other.is_case_insensitive then
				Result := Precursor (other)
			end
		ensure -- from ANY
			symmetric: Result implies other ~ Current
			consistent: standard_is_equal (other) implies Result
		end

	same_keys (a_search_key, a_key: READABLE_STRING_GENERAL): BOOLEAN
			-- Is a_search_key the same key as a_key ?
		do
			if is_case_insensitive then
				Result := a_search_key.is_case_insensitive_equal (a_key)
			else
				Result := a_search_key.same_string (a_key)
			end
		end

	frozen standard_equal (a: detachable ANY; b: like arg #1): BOOLEAN
			-- Are a and b either both void or attached to
			-- field-by-field identical objects of the same type?
			-- Always uses default object comparison criterion.
			-- (from ANY)
		do
			if a = Void then
				Result := b = Void
			else
				Result := b /= Void and then a.standard_is_equal (b)
			end
		ensure -- from ANY
			instance_free: class
			definition: Result = (a = Void and b = Void) or else ((a /= Void and b /= Void) and then a.standard_is_equal (b))
		end

	frozen standard_is_equal alias "≜" (other: STRING_TABLE [G]): BOOLEAN
			-- Is other attached to an object of the same type
			-- as current object, and field-by-field identical to it?
			-- (from ANY)
		require -- from ANY
			other_not_void: other /= Void
		external
			"built_in"
		ensure -- from ANY
			same_type: Result implies same_type (other)
			symmetric: Result implies other.standard_is_equal (Current)
		end
	
feature -- Status report

	after: BOOLEAN
			-- Is cursor past last item?
			-- Was declared in HASH_TABLE as synonym of off.
			-- (from HASH_TABLE)
		do
			Result := is_off_position (iteration_position)
		end

	changeable_comparison_criterion: BOOLEAN
			-- May object_comparison be changed?
			-- (Answer: yes by default.)
			-- (from CONTAINER)
		do
			Result := True
		end

	conflict: BOOLEAN
			-- Did last operation cause a conflict?
			-- (from HASH_TABLE)
		do
			Result := control = Conflict_constant
		end

	conforms_to (other: ANY): BOOLEAN
			-- Does type of current object conform to type
			-- of other (as per Eiffel: The Language, chapter 13)?
			-- (from ANY)
		require -- from ANY
			other_not_void: other /= Void
		external
			"built_in"
		end

	empty: BOOLEAN
		obsolete "ELKS 2000: Use `is_empty' instead. [2017-05-31]"
			-- Is there no element?
			-- (from CONTAINER)
		do
			Result := is_empty
		end

	Extendible: BOOLEAN = False
			-- May new items be added?
			-- (from HASH_TABLE)

	found: BOOLEAN
			-- Did last operation find the item sought?
			-- (from HASH_TABLE)
		do
			Result := control = Found_constant
		end

	Full: BOOLEAN = False
			-- Is structure filled to capacity?
			-- (from HASH_TABLE)

	inserted: BOOLEAN
			-- Did last operation insert an item?
			-- (from HASH_TABLE)
		do
			Result := control = Inserted_constant
		end

	is_case_insensitive: BOOLEAN
			-- Ignoring case when comparing keys?
			-- (Default: False)

	is_empty: BOOLEAN
			-- Is structure empty?
			-- (from FINITE)
		require -- from  CONTAINER
			True
		do
			Result := count = 0
		end

	is_inserted (v: G): BOOLEAN
			-- Has v been inserted by the most recent insertion?
			-- (By default, the value returned is equivalent to calling 
			-- has (v). However, descendants might be able to provide more
			-- efficient implementations.)
			-- (from COLLECTION)
		do
			Result := has_item (v)
		end

	not_found: BOOLEAN
			-- Did last operation fail to find the item sought?
			-- (from HASH_TABLE)
		do
			Result := control = Not_found_constant
		end

	object_comparison: BOOLEAN
			-- Must search operations use equal rather than =
			-- for comparing references? (Default: no, use =.)
			-- (from CONTAINER)

	off: BOOLEAN
			-- Is cursor past last item?
			-- Was declared in HASH_TABLE as synonym of after.
			-- (from HASH_TABLE)
		do
			Result := is_off_position (iteration_position)
		end

	prunable: BOOLEAN
			-- May items be removed? (Answer: yes.)
			-- (from DYNAMIC_TABLE)
		do
			Result := True
		end

	removed: BOOLEAN
			-- Did last operation remove an item?
			-- (from HASH_TABLE)
		do
			Result := control = Removed_constant
		end

	replaced: BOOLEAN
			-- Did last operation replace an item?
			-- (from HASH_TABLE)
		do
			Result := control = Replaced_constant
		end

	same_type (other: ANY): BOOLEAN
			-- Is type of current object identical to type of other?
			-- (from ANY)
		require -- from ANY
			other_not_void: other /= Void
		external
			"built_in"
		ensure -- from ANY
			definition: Result = (conforms_to (other) and other.conforms_to (Current))
		end

	valid_cursor (c: CURSOR): BOOLEAN
			-- Can cursor be moved to position c?
			-- (from HASH_TABLE)
		require -- from HASH_TABLE
			c_not_void: c /= Void
		local
			i: INTEGER_32
		do
			if attached {HASH_TABLE_CURSOR} c as ht_cursor then
				i := ht_cursor.position
				Result := is_off_position (i) or else truly_occupied (i)
			end
		end

	valid_iteration_index (i: INTEGER_32): BOOLEAN
			-- Is i a valid index?
			-- (from HASH_TABLE)
		do
			Result := truly_occupied (i)
		ensure -- from READABLE_INDEXABLE
			only_if_in_index_set: Result implies (iteration_lower <= i and i <= iteration_upper)
		end

	valid_key (k: READABLE_STRING_GENERAL): BOOLEAN
		obsolete "Remove the call to this feature or use `has` instead. [2018-11-30]"
			-- Is k a valid key?
			-- (from HASH_TABLE)
		do
			Result := True
			debug ("prevent_hash_table_catcall")
				if not ({READABLE_STRING_GENERAL}).is_expanded and then attached k then
					Result := k.generating_type ~ {detachable READABLE_STRING_GENERAL}
				end
			end
		end
	
feature -- Status setting

	compare_objects
			-- Ensure that future search operations will use equal
			-- rather than = for comparing references.
			-- (from CONTAINER)
		require -- from CONTAINER
			changeable_comparison_criterion: changeable_comparison_criterion
		do
			object_comparison := True
		ensure -- from CONTAINER
				object_comparison
		end

	compare_references
			-- Ensure that future search operations will use =
			-- rather than equal for comparing references.
			-- (from CONTAINER)
		require -- from CONTAINER
			changeable_comparison_criterion: changeable_comparison_criterion
		do
			object_comparison := False
		ensure -- from CONTAINER
			reference_comparison: not object_comparison
		end
	
feature -- Cursor movement

	forth
			-- Advance cursor to next occupied position,
			-- or off if no such position remains.
			-- (from HASH_TABLE)
		require -- from HASH_TABLE
			not_off: not off
		do
			iteration_position := next_iteration_position (iteration_position)
		end

	go_to (c: CURSOR)
			-- Move to position c.
			-- (from HASH_TABLE)
		require -- from HASH_TABLE
			c_not_void: c /= Void
			valid_cursor: valid_cursor (c)
		do
			if attached {HASH_TABLE_CURSOR} c as ht_cursor then
				iteration_position := ht_cursor.position
			end
		end

	search (key: READABLE_STRING_GENERAL)
			-- Search for item of key key.
			-- If found, set found to true, and set
			-- found_item to item associated with key.
			-- (from HASH_TABLE)
		local
			old_position: INTEGER_32
			l_default_value: detachable G
		do
			old_position := item_position
			internal_search (key)
			if found then
				found_item := content.item (position)
			else
				found_item := l_default_value
			end
			item_position := old_position
		ensure -- from HASH_TABLE
			found_or_not_found: found or not_found
			item_if_found: found implies (found_item = item (key))
		end

	search_item: detachable G
		obsolete "Use `found_item` instead. [2017-05-31]"
			-- (from HASH_TABLE)
		do
			Result := found_item
		end

	start
			-- Bring cursor to first position.
			-- (from HASH_TABLE)
		do
			iteration_position := next_iteration_position (-1)
		end
	
feature {HASH_TABLE_ITERATION_CURSOR} -- Cursor movement

	next_iteration_position (a_position: like iteration_position): like iteration_position
			-- Given an iteration position, advanced to the next one taking into account deleted
			-- slots in the content and keys structures.
			-- (from HASH_TABLE)
		require -- from HASH_TABLE
			a_position_big_enough: a_position >= -1
			a_position_small_enough: a_position < keys.count
		local
			l_deleted_marks: like deleted_marks
			l_table_size: INTEGER_32
		do
			l_deleted_marks := deleted_marks
			l_table_size := content.count
			from
				Result := a_position + 1
			until
				Result >= l_table_size or else not l_deleted_marks.item (Result)
			loop
				Result := Result + 1
			end
		ensure -- from HASH_TABLE
			is_increased: Result > a_position
			is_below_upper_bound: Result <= keys.count
		end

	previous_iteration_position (a_position: like iteration_position): like iteration_position
			-- Given an iteration position, go to the previous one taking into account deleted
			-- slots in the content and keys structures.
			-- (from HASH_TABLE)
		require -- from HASH_TABLE
			a_position_big_enough: a_position >= 0
			a_position_small_enough: a_position <= keys.count
		local
			l_deleted_marks: like deleted_marks
		do
			l_deleted_marks := deleted_marks
			from
				Result := a_position - 1
			until
				Result <= -1 or else not l_deleted_marks.item (Result)
			loop
				Result := Result - 1
			end
		ensure -- from HASH_TABLE
			is_decreased: Result < a_position
			is_above_lower_bound: Result >= -1
		end
	
feature -- Element change

	extend (new: G; key: READABLE_STRING_GENERAL)
			-- Assuming there is no item of key key,
			-- insert new with key.
			-- Set inserted.
			--
			-- To choose between various insert/replace procedures,
			-- see instructions in the Indexing clause.
			-- (from HASH_TABLE)
		require -- from HASH_TABLE
			not_present: not has (key)
		local
			l_default_key: detachable READABLE_STRING_GENERAL
			l_new_pos, l_new_index_pos: like position
		do
			search_for_insertion (key)
			if soon_full then
				add_space
				search_for_insertion (key)
			end
			if deleted_item_position = Ht_impossible_position then
				l_new_pos := keys.count
				l_new_index_pos := item_position
			else
				l_new_pos := deleted_position (deleted_item_position)
				l_new_index_pos := deleted_item_position;
				deleted_marks.force (False, l_new_pos)
			end;
			indexes_map.put (l_new_pos, l_new_index_pos);
			content.force (new, l_new_pos);
			keys.force (key, l_new_pos)
			if key = l_default_key then
				has_default := True
			end
			count := count + 1
			control := Inserted_constant
		ensure -- from HASH_TABLE
			inserted: inserted
			insertion_done: item (key) = new
			one_more: count = old count + 1
			default_property: has_default = ((key = computed_default_key) or (old has_default))
		end

	fill (other: CONTAINER [G])
			-- Fill with as many items of other as possible.
			-- The representations of other and current structure
			-- need not be the same.
			-- (from COLLECTION)
		require -- from COLLECTION
			other_not_void: other /= Void
			extendible: Extendible
		local
			lin_rep: LINEAR [G]
		do
			lin_rep := other.linear_representation
			from
				lin_rep.start
			until
				not Extendible or else lin_rep.off
			loop
				collection_extend (lin_rep.item);
				lin_rep.forth
			end
		end

	force (new: G; key: READABLE_STRING_GENERAL)
			-- Update table so that new will be the item associated
			-- with key.
			-- If there was an item for that key, set found
			-- and set found_item to that item.
			-- If there was none, set not_found and set
			-- found_item to the default value.
			--
			-- To choose between various insert/replace procedures,
			-- see instructions in the Indexing clause.
			-- (from HASH_TABLE)
		require -- from TABLE
			valid_key: has (key)
		require else -- from HASH_TABLE
				True
		local
			l_default_key: detachable READABLE_STRING_GENERAL
			l_default_value: detachable G
			l_new_pos, l_new_index_pos: like position
		do
			internal_search (key)
			if not_found then
				if soon_full then
					add_space
					internal_search (key)
				end
				if deleted_item_position = Ht_impossible_position then
					l_new_pos := keys.count
					l_new_index_pos := item_position
				else
					l_new_pos := deleted_position (deleted_item_position)
					l_new_index_pos := deleted_item_position;
					deleted_marks.force (False, l_new_pos)
				end;
				indexes_map.put (l_new_pos, l_new_index_pos);
				keys.force (key, l_new_pos)
				if key = l_default_key then
					has_default := True
				end
				count := count + 1
				found_item := l_default_value
			else
				l_new_pos := position
				found_item := content.item (l_new_pos)
			end;
			content.force (new, l_new_pos)
		ensure -- from TABLE
			inserted: definite_item (key) = new
		ensure then -- from HASH_TABLE
			insertion_done: item (key) = new
			now_present: has (key)
			found_or_not_found: found or not_found
			not_found_if_was_not_present: not_found = not (old has (key))
			same_count_or_one_more: (count = old count) or (count = old count + 1)
			found_item_is_old_item: found implies (found_item = old (item (key)))
			default_value_if_not_found: not_found implies (found_item = computed_default_value)
			default_property: has_default = ((key = computed_default_key) or ((key /= computed_default_key) and (old has_default)))
		end

	merge (other: HASH_TABLE [G, READABLE_STRING_GENERAL])
			-- Merge other into Current. If other has some elements
			-- with same key as in Current, replace them by one from
			-- other.
			-- (from HASH_TABLE)
		require -- from HASH_TABLE
			other_not_void: other /= Void
		do
			across
				other as other_cursor
			loop
				force (other_cursor.item, other_cursor.key)
			end
		ensure -- from HASH_TABLE
			inserted: across
					other as other_cursor
				all
					has (other_cursor.key)
				end
		end

	put (new: G; key: READABLE_STRING_GENERAL)
			-- Insert new with key if there is no other item
			-- associated with the same key.
			-- Set inserted if and only if an insertion has
			-- been made (i.e. key was not present).
			-- If so, set position to the insertion position.
			-- If not, set conflict.
			-- In either case, set found_item to the item
			-- now associated with key (previous item if
			-- there was one, new otherwise).
			--
			-- To choose between various insert/replace procedures,
			-- see instructions in the Indexing clause.
			-- (from HASH_TABLE)
		require -- from TABLE
			valid_key: has (key)
		require else -- from HASH_TABLE
				True
		local
			l_default_key: detachable READABLE_STRING_GENERAL
			l_new_pos, l_new_index_pos: like position
		do
			internal_search (key)
			if found then
				set_conflict
				found_item := content.item (position)
			else
				if soon_full then
					add_space
					internal_search (key)
					check
						not_present: not found
					end
				end
				if deleted_item_position = Ht_impossible_position then
					l_new_pos := keys.count
					l_new_index_pos := item_position
				else
					l_new_pos := deleted_position (deleted_item_position)
					l_new_index_pos := deleted_item_position;
					deleted_marks.force (False, l_new_pos)
				end;
				indexes_map.put (l_new_pos, l_new_index_pos);
				content.force (new, l_new_pos);
				keys.force (key, l_new_pos)
				if key = l_default_key then
					has_default := True
				end
				count := count + 1
				found_item := new
				control := Inserted_constant
			end
		ensure then -- from HASH_TABLE
			conflict_or_inserted: conflict or inserted
			insertion_done: inserted implies item (key) = new
			now_present: inserted implies has (key)
			one_more_if_inserted: inserted implies (count = old count + 1)
			unchanged_if_conflict: conflict implies (count = old count)
			same_item_if_conflict: conflict implies (item (key) = old (item (key)))
			found_item_associated_with_key: found_item = item (key)
			new_item_if_inserted: inserted implies (found_item = new)
			old_item_if_conflict: conflict implies (found_item = old (item (key)))
			default_property: has_default = ((inserted and (key = computed_default_key)) or ((conflict or (key /= computed_default_key)) and (old has_default)))
		end

	replace (new: G; key: READABLE_STRING_GENERAL)
			-- Replace item at key, if present,
			-- with new; do not change associated key.
			-- Set replaced if and only if a replacement has been made
			-- (i.e. key was present); otherwise set not_found.
			-- Set found_item to the item previously associated
			-- with key (default value if there was none).
			--
			-- To choose between various insert/replace procedures,
			-- see instructions in the Indexing clause.
			-- (from HASH_TABLE)
		local
			l_default_item: detachable G
		do
			internal_search (key)
			if found then
				found_item := content.item (position);
				content.put (new, position)
				control := Replaced_constant
			else
				found_item := l_default_item
			end
		ensure -- from HASH_TABLE
			replaced_or_not_found: replaced or not_found
			insertion_done: replaced implies item (key) = new
			no_change_if_not_found: not_found implies item (key) = old item (key)
			found_item_is_old_item: found_item = old item (key)
		end

	replace_key (new_key: READABLE_STRING_GENERAL; old_key: READABLE_STRING_GENERAL)
			-- If there is an item of key old_key and no item of key
			-- new_key, replace the former's key by new_key,
			-- set replaced, and set found_item to the item
			-- previously associated with old_key.
			-- Otherwise set not_found or conflict respectively.
			-- If conflict, set found_item to the item previously
			-- associated with new_key.
			--
			-- To choose between various insert/replace procedures,
			-- see instructions in the Indexing clause.
			-- (from HASH_TABLE)
		local
			l_item: G
		do
			internal_search (new_key)
			if not found then
				internal_search (old_key)
				if found then
					l_item := content.item (position)
					remove (old_key)
					put (l_item, new_key)
					control := Replaced_constant
				end
			else
				set_conflict
				found_item := content.item (position)
			end
		ensure -- from HASH_TABLE
			same_count: count = old count
			replaced_or_conflict_or_not_found: replaced or conflict or not_found
			old_absent: (replaced and not same_keys (new_key, old_key)) implies (not has (old_key))
			new_present: (replaced or conflict) = has (new_key)
			new_item: replaced implies (item (new_key) = old (item (old_key)))
			not_found_implies_no_old_key: not_found implies old (not has (old_key))
			conflict_iff_already_present: conflict = old has (new_key)
			not_inserted_if_conflict: conflict implies (item (new_key) = old item (new_key))
		end
	
feature -- Removal

	clear_all
		obsolete "Use `wipe_out' instead. [2017-05-31]"
			-- (from HASH_TABLE)
		do
			wipe_out
		end

	prune (v: G)
			-- Remove first occurrence of v, if any,
			-- after cursor position.
			-- Move cursor to right neighbor.
			-- (or after if no right neighbor or v does not occur)
			-- (from HASH_TABLE)
		require -- from COLLECTION
			prunable: prunable
		do
			if object_comparison then
				from
				until
					after or else item_for_iteration ~ v
				loop
					forth
				end
			else
				from
				until
					after or else item_for_iteration = v
				loop
					forth
				end
			end
			if not after then
				remove (key_for_iteration)
			end
		end

	prune_all (v: G)
			-- Remove all occurrences of v.
			-- (Reference or object equality,
			-- based on object_comparison.)
			-- (from COLLECTION)
		require -- from COLLECTION
			prunable: prunable
		do
			from
			until
				not has_item (v)
			loop
				prune (v)
			end
		ensure -- from COLLECTION
			no_more_occurrences: not has_item (v)
		end

	remove (key: READABLE_STRING_GENERAL)
			-- Remove item associated with key, if present.
			-- Set removed if and only if an item has been
			-- removed (i.e. key was present);
			-- if so, set position to index of removed element.
			-- If not, set not_found.
			-- Reset found_item to its default value if removed.
			-- (from HASH_TABLE)
		require -- from DYNAMIC_TABLE
			prunable: prunable
			valid_key: has (key)
		require else -- from HASH_TABLE
				prunable
		local
			l_default_key: detachable READABLE_STRING_GENERAL
			l_default_value: detachable G
			l_pos: like position
			l_nb_removed_items: INTEGER_32
		do
			internal_search (key)
			if found then
				l_pos := position
				if key = l_default_key then
					has_default := False
				end;
				deleted_marks.put (True, l_pos);
				indexes_map.put (- l_pos + Ht_deleted_position, item_position)
				if iteration_position = l_pos then
					forth
				end
				count := count - 1
				ht_lowest_deleted_position := l_pos.min (ht_lowest_deleted_position)
				if ht_lowest_deleted_position = count then
					l_nb_removed_items := content.count - ht_lowest_deleted_position;
					content.remove_tail (l_nb_removed_items);
					keys.remove_tail (l_nb_removed_items);
					deleted_marks.fill_with (False, ht_lowest_deleted_position, deleted_marks.count - 1)
					ht_deleted_item := l_default_value
					ht_deleted_key := l_default_key
					ht_lowest_deleted_position := Ht_max_position
				elseif attached ht_deleted_item as l_item and attached ht_deleted_key as l_key then
					content.put (l_item, l_pos);
					keys.put (l_key, l_pos)
				else
					ht_deleted_item := content.item (l_pos)
					ht_deleted_key := keys.item (l_pos)
				end
				control := Removed_constant
				found_item := l_default_value
			end
		ensure then -- from HASH_TABLE
			removed_or_not_found: removed or not_found
			not_present: not has (key)
			one_less: found implies (count = old count - 1)
			default_case: (key = computed_default_key) implies (not has_default)
			non_default_case: (key /= computed_default_key) implies (has_default = old has_default)
		end

	wipe_out
			-- Reset all items to default values; reset status.
			-- (from HASH_TABLE)
		require -- from COLLECTION
			prunable: prunable
		local
			l_default_value: detachable G
		do
			content.wipe_out;
			keys.wipe_out;
			deleted_marks.fill_with (False, 0, deleted_marks.upper);
			indexes_map.fill_with (Ht_impossible_position, 0, capacity)
			found_item := l_default_value
			count := 0
			item_position := 0
			iteration_position := keys.count
			control := 0
			has_default := False
		ensure -- from COLLECTION
			wiped_out: is_empty
		ensure then -- from HASH_TABLE
			position_equal_to_zero: item_position = 0
			count_equal_to_zero: count = 0
			has_default_set: not has_default
			no_status: not special_status
		end
	
feature -- Transformation

	correct_mismatch
			-- Attempt to correct object mismatch during retrieve using Mismatch_information.
			-- (from HASH_TABLE)
		local
			l_old_deleted_marks: detachable SPECIAL [BOOLEAN]
			i, l_capacity, l_count: INTEGER_32
			l_new_table: STRING_TABLE [G]
			l_default_item: like ht_deleted_item
			l_default_key: like ht_deleted_key
		do
			if not Mismatch_information.has ("hash_table_version_64") then
				if attached {ARRAY [G]} Mismatch_information.item ("content") as array_content then
					content := array_content.area
				end
				if attached {ARRAY [READABLE_STRING_GENERAL]} Mismatch_information.item ("keys") as array_keys then
					keys := array_keys.area
				end
				if attached {ARRAY [BOOLEAN]} Mismatch_information.item ("deleted_marks") as array_marks then
					deleted_marks := array_marks.area
				end
				if deleted_marks /= Void and keys /= Void and then not Mismatch_information.has ("hash_table_version_57") and then deleted_marks.count /= keys.count then
					l_old_deleted_marks := deleted_marks
					create deleted_marks.make_empty (keys.count);
					deleted_marks.copy_data (l_old_deleted_marks, 0, 0, l_old_deleted_marks.count)
				end
				if attached {INTEGER_32} Mismatch_information.item ("count") as l_retrieved_count then
					l_count := l_retrieved_count
				end
				if content = Void or keys = Void or deleted_marks = Void then
					Precursor {MISMATCH_CORRECTOR}
				else
					from
						l_capacity := keys.count
						l_new_table := empty_duplicate (l_count)
					until
						i = l_capacity
					loop
						if attached keys.item (i) as l_key_item and then l_key_item /= l_default_key then
							l_new_table.put (content.item (i), l_key_item)
						end
						i := i + 1
					end
					if attached {BOOLEAN} Mismatch_information.item ("has_default") as l_bool and then l_bool then
						l_new_table.put (content.item (content.capacity - 1), keys.item (l_capacity - 1))
					end
					set_content (l_new_table.content)
					set_keys (l_new_table.keys)
					set_deleted_marks (l_new_table.deleted_marks)
					set_indexes_map (l_new_table.indexes_map)
					capacity := l_new_table.capacity
					iteration_position := l_new_table.iteration_position
					deleted_item_position := l_new_table.deleted_item_position
					item_position := l_new_table.item_position
					ht_lowest_deleted_position := Ht_max_position
					ht_deleted_item := l_default_item
					ht_deleted_key := l_default_key
				end
				control := 0
			end
		end
	
feature {NONE} -- Transformation

	hash_table_version_64: BOOLEAN
			-- Fake attribute for versioning purposes. Used in correct_mismatch.
			-- (from HASH_TABLE)
	
feature -- Conversion

	linear_representation: ARRAYED_LIST [G]
			-- Representation as a linear structure
			-- (from HASH_TABLE)
		require -- from  CONTAINER
			True
		local
			old_iteration_position: INTEGER_32
		do
			old_iteration_position := iteration_position
			from
				create Result.make (count)
				start
			until
				off
			loop
				Result.extend (item_for_iteration)
				forth
			end
			iteration_position := old_iteration_position
		ensure then -- from HASH_TABLE
			result_exists: Result /= Void
			good_count: Result.count = count
		end
	
feature {NONE} -- Duplication

	empty_duplicate (n: INTEGER_32): like Current
			-- Create an empty copy of Current that can accommodate n items
		require -- from HASH_TABLE
			n_non_negative: n >= 0
		do
			if is_case_insensitive then
				create Result.make_caseless (n)
			else
				create Result.make (n)
			end
			if object_comparison then
				Result.compare_objects
			end
		ensure -- from HASH_TABLE
			empty_duplicate_attached: Result /= Void
		end
	
feature -- Duplication

	frozen clone (other: detachable ANY): like other
		obsolete "Use `twin' instead. [2017-05-31]"
			-- Void if other is void; otherwise new object
			-- equal to other
			--
			-- For non-void other, clone calls copy;
			-- to change copying/cloning semantics, redefine copy.
			-- (from ANY)
		do
			if other /= Void then
				Result := other.twin
			end
		ensure -- from ANY
			instance_free: class
			equal: Result ~ other
		end

	copy (other: STRING_TABLE [G])
			-- Re-initialize from other.
			-- (from HASH_TABLE)
		require -- from ANY
			other_not_void: other /= Void
			type_identity: same_type (other)
		do
			if other /= Current then
				standard_copy (other)
				set_content (other.content.twin)
				set_keys (other.keys.twin)
				set_deleted_marks (other.deleted_marks.twin)
				set_indexes_map (other.indexes_map.twin)
			end
		ensure -- from ANY
			is_equal: Current ~ other
		end

	frozen deep_clone (other: detachable ANY): like other
		obsolete "Use `deep_twin' instead. [2017-05-31]"
			-- Void if other is void: otherwise, new object structure
			-- recursively duplicated from the one attached to other
			-- (from ANY)
		do
			if other /= Void then
				Result := other.deep_twin
			end
		ensure -- from ANY
			instance_free: class
			deep_equal: deep_equal (other, Result)
		end

	frozen deep_copy (other: STRING_TABLE [G])
			-- Effect equivalent to that of:
			--		copy (other . deep_twin)
			-- (from ANY)
		require -- from ANY
			other_not_void: other /= Void
		do
			copy (other.deep_twin)
		ensure -- from ANY
			deep_equal: deep_equal (Current, other)
		end

	frozen deep_twin: STRING_TABLE [G]
			-- New object structure recursively duplicated from Current.
			-- (from ANY)
		external
			"built_in"
		ensure -- from ANY
			deep_twin_not_void: Result /= Void
			deep_equal: deep_equal (Current, Result)
		end

	frozen standard_clone (other: detachable ANY): like other
		obsolete "Use `standard_twin' instead. [2017-05-31]"
			-- Void if other is void; otherwise new object
			-- field-by-field identical to other.
			-- Always uses default copying semantics.
			-- (from ANY)
		do
			if other /= Void then
				Result := other.standard_twin
			end
		ensure -- from ANY
			instance_free: class
			equal: standard_equal (Result, other)
		end

	frozen standard_copy (other: STRING_TABLE [G])
			-- Copy every field of other onto corresponding field
			-- of current object.
			-- (from ANY)
		require -- from ANY
			other_not_void: other /= Void
			type_identity: same_type (other)
		external
			"built_in"
		ensure -- from ANY
			is_standard_equal: standard_is_equal (other)
		end

	frozen standard_twin: STRING_TABLE [G]
			-- New object field-by-field identical to other.
			-- Always uses default copying semantics.
			-- (from ANY)
		external
			"built_in"
		ensure -- from ANY
			standard_twin_not_void: Result /= Void
			equal: standard_equal (Result, Current)
		end

	frozen twin: STRING_TABLE [G]
			-- New object equal to Current
			-- twin calls copy; to change copying/twinning semantics, redefine copy.
			-- (from ANY)
		external
			"built_in"
		ensure -- from ANY
			twin_not_void: Result /= Void
			is_equal: Result ~ Current
		end
	
feature -- Basic operations

	frozen as_attached: attached STRING_TABLE [G]
		obsolete "Remove calls to this feature. [2017-05-31]"
			-- Attached version of Current.
			-- (Can be used during transitional period to convert
			-- non-void-safe classes to void-safe ones.)
			-- (from ANY)
		do
			Result := Current
		end

	frozen default: detachable STRING_TABLE [G]
			-- Default value of object's type
			-- (from ANY)
		do
		end

	frozen default_pointer: POINTER
			-- Default value of type POINTER
			-- (Avoid the need to write p.default for
			-- some p of type POINTER.)
			-- (from ANY)
		do
		ensure -- from ANY
			instance_free: class
		end

	default_rescue
			-- Process exception for routines with no Rescue clause.
			-- (Default: do nothing.)
			-- (from ANY)
		do
		end

	frozen do_nothing
			-- Execute a null action.
			-- (from ANY)
		do
		ensure -- from ANY
			instance_free: class
		end
	
feature -- Inapplicable

	bag_put (v: G)
			-- Ensure that structure includes v.
			-- (from TABLE)
		require -- from COLLECTION
			extendible: Extendible
		do
		ensure -- from COLLECTION
			item_inserted: is_inserted (v)
		end

	collection_extend (v: G)
			-- Insert a new occurrence of v.
			-- (from HASH_TABLE)
		require -- from COLLECTION
			extendible: Extendible
		do
		ensure -- from COLLECTION
			item_inserted: is_inserted (v)
		end
	
feature {NONE} -- Implementation

	add_space
			-- Increase capacity.
			-- (from HASH_TABLE)
		do
			accommodate (count + count // 2)
		ensure -- from HASH_TABLE
			count_not_changed: count = old count
			breathing_space: count < capacity
		end

	computed_default_key: detachable READABLE_STRING_GENERAL
			-- Default key
			-- (For performance reasons, used only in assertions;
			-- elsewhere, see use of local entity l_default_key.)
			-- (from HASH_TABLE)
		do
		end

	computed_default_value: detachable G
			-- Default value of type G
			-- (For performance reasons, used only in assertions;
			-- elsewhere, see use of local entity l_default_value.)
			-- (from HASH_TABLE)
		do
		end

	Conflict_constant: INTEGER_32 = 1
			-- Could not insert an already existing key
			-- (from HASH_TABLE)

	default_key_value: G
			-- Value associated with the default key, if any
			-- (from HASH_TABLE)
		require -- from HASH_TABLE
			has_default: has_default
		do
			Result := content [indexes_map [capacity]]
		end

	deleted (i: INTEGER_32): BOOLEAN
			-- Is position i that of a deleted item?
			-- (from HASH_TABLE)
		require -- from HASH_TABLE
			in_bounds: i >= 0 and i <= capacity
		do
			Result := indexes_map.item (i) <= Ht_deleted_position
		end

	deleted_position (a_pos: INTEGER_32): INTEGER_32
			-- Given the position of a deleted item at a_pos gives the associated position
			-- in content/keys.
			-- (from HASH_TABLE)
		require -- from HASH_TABLE
			deleted: deleted (a_pos)
		do
			Result := - indexes_map.item (a_pos) + Ht_deleted_position
			Result := Result.min (keys.count)
		ensure -- from HASH_TABLE
			deleted_position_non_negative: Result >= 0
			deleted_position_valid: Result <= keys.count and Result <= content.count
		end

	Found_constant: INTEGER_32 = 2
			-- Key found
			-- (from HASH_TABLE)

	ht_deleted_item: detachable G
			-- (from HASH_TABLE)

	ht_deleted_key: detachable READABLE_STRING_GENERAL
			-- Store the item and key that will be used to replace an element of the HASH_TABLE
			-- that will be removed. If elements being removed are at the end of content or keys
			-- then they are both Void. It is only used when removing an element at a position strictly
			-- less than count.
			-- (from HASH_TABLE)

	Ht_deleted_position: INTEGER_32 = -2
			-- Marked a deleted position.
			-- (from HASH_TABLE)

	Ht_impossible_position: INTEGER_32 = -1
			-- Position outside the array indices.
			-- (from HASH_TABLE)

	ht_lowest_deleted_position: INTEGER_32
			-- Index of the lowest deleted position thus far.
			-- (from HASH_TABLE)

	Ht_max_position: INTEGER_32 = 2147483645
			-- Maximum possible position
			-- (from HASH_TABLE)

	initial_position (hash_value: INTEGER_32): INTEGER_32
			-- Initial position for an item of hash code hash_value
			-- (from HASH_TABLE)
		do
			Result := hash_value \\ capacity
		end

	Inserted_constant: INTEGER_32 = 4
			-- Insertion successful
			-- (from HASH_TABLE)

	internal_search (key: READABLE_STRING_GENERAL)
			-- Search for item of key key.
			-- If successful, set position to index
			-- of item with this key (the same index as the key's index).
			-- If not, set position to possible position for insertion,
			-- and set status to found or not_found.
			-- (from HASH_TABLE)
		local
			l_default_key: detachable READABLE_STRING_GENERAL
			hash_value, increment, l_pos, l_item_pos, l_capacity: INTEGER_32
			l_first_deleted_position: INTEGER_32
			stop: INTEGER_32
			l_keys: like keys
			l_indexes: like indexes_map
			l_deleted_marks: like deleted_marks
			l_key: READABLE_STRING_GENERAL
		do
			l_first_deleted_position := Ht_impossible_position
			if key = l_default_key or key = Void then
				item_position := capacity
				if has_default then
					control := Found_constant
				else
					control := Not_found_constant
				end
			else
				from
					l_keys := keys
					l_indexes := indexes_map
					l_deleted_marks := deleted_marks
					l_capacity := capacity
					stop := l_capacity
					hash_value := hash_code_of (key)
					increment := 1 + hash_value \\ (l_capacity - 1)
					l_item_pos := (hash_value \\ l_capacity) - increment
					control := Not_found_constant
				until
					stop = 0
				loop
					l_item_pos := (l_item_pos + increment) \\ l_capacity
					l_pos := l_indexes [l_item_pos]
					if l_pos >= 0 then
						l_key := l_keys.item (l_pos)
						debug ("detect_hash_table_catcall")
							check
								catcall_detected: l_key /= Void and then l_key.same_type (key)
							end
						end
						if same_keys (l_key, key) then
							stop := 1
							control := Found_constant
						end
					elseif l_pos = Ht_impossible_position then
						stop := 1
					elseif l_first_deleted_position = Ht_impossible_position then
						l_pos := - l_pos + Ht_deleted_position
						check
							l_pos_valid: l_pos < l_deleted_marks.count
						end
						if not l_deleted_marks [l_pos] then
							stop := 1
						else
							l_first_deleted_position := l_item_pos
						end
					end
					stop := stop - 1
				end
				item_position := l_item_pos
			end
			deleted_item_position := l_first_deleted_position
		ensure -- from HASH_TABLE
			found_or_not_found: found or not_found
			deleted_item_at_deleted_position: (deleted_item_position /= Ht_impossible_position) implies deleted (deleted_item_position)
			default_iff_at_capacity: (item_position = capacity) = (key = computed_default_key)
		end

	is_off_position (pos: INTEGER_32): BOOLEAN
			-- Is pos a cursor position outside the authorized range?
			-- (from HASH_TABLE)
		do
			Result := pos < 0 or pos >= keys.count
		end

	key_at (n: INTEGER_32): detachable READABLE_STRING_GENERAL
			-- Key at position n
			-- (from HASH_TABLE)
		do
			if keys.valid_index (n) then
				Result := keys.item (n)
			end
		end

	Minimum_capacity: INTEGER_32 = 2
			-- (from HASH_TABLE)

	Not_found_constant: INTEGER_32 = 8
			-- Key not found
			-- (from HASH_TABLE)

	occupied (i: INTEGER_32): BOOLEAN
			-- Is position i occupied by a non-default key and a value?
			-- (from HASH_TABLE)
		require -- from HASH_TABLE
			in_bounds: deleted_marks.valid_index (i)
		do
			if has_default then
				Result := i /= indexes_map.item (capacity) and then not deleted_marks.item (i)
			else
				Result := not deleted_marks.item (i)
			end
		end

	position_increment (hash_value: INTEGER_32): INTEGER_32
			-- Distance between successive positions for hash code
			-- hash_value (computed for no cycle: capacity is prime)
			-- (from HASH_TABLE)
		do
			Result := 1 + hash_value \\ (capacity - 1)
		end

	Removed_constant: INTEGER_32 = 16
			-- Remove successful
			-- (from HASH_TABLE)

	Replaced_constant: INTEGER_32 = 32
			-- Replaced value
			-- (from HASH_TABLE)

	search_for_insertion (key: READABLE_STRING_GENERAL)
			-- Assuming there is no item of key key, compute
			-- position at which to insert such an item.
			-- (from HASH_TABLE)
		require -- from HASH_TABLE
			not_present: not has (key)
		local
			l_default_key: detachable READABLE_STRING_GENERAL
			hash_value, increment, l_pos, l_item_pos, l_capacity: INTEGER_32
			l_first_deleted_position: INTEGER_32
			stop: INTEGER_32
			l_indexes: like indexes_map
			l_deleted_marks: like deleted_marks
		do
			l_first_deleted_position := Ht_impossible_position
			if key = l_default_key or key = Void then
				check
						not has_default
				end
				item_position := capacity
			else
				from
					l_indexes := indexes_map
					l_deleted_marks := deleted_marks
					l_capacity := capacity
					stop := l_capacity
					hash_value := hash_code_of (key)
					increment := 1 + hash_value \\ (l_capacity - 1)
					l_item_pos := (hash_value \\ l_capacity) - increment
				until
					stop = 0
				loop
					l_item_pos := (l_item_pos + increment) \\ l_capacity
					l_pos := l_indexes [l_item_pos]
					if l_pos >= 0 then
					elseif l_pos = Ht_impossible_position then
						stop := 1
					elseif l_first_deleted_position = Ht_impossible_position then
						l_pos := - l_pos + Ht_deleted_position
						check
							l_pos_valid: l_pos < l_deleted_marks.count
						end
						if not l_deleted_marks [l_pos] then
							stop := 1
						else
							l_first_deleted_position := l_item_pos
						end
					end
					stop := stop - 1
				end
				item_position := l_item_pos
			end
			deleted_item_position := l_first_deleted_position
		ensure -- from HASH_TABLE
			deleted_item_at_deleted_position: (deleted_item_position /= Ht_impossible_position) implies deleted (deleted_item_position)
			default_iff_at_capacity: (item_position = capacity) = (key = computed_default_key)
		end

	set_conflict
			-- Set status to conflict.
			-- (from HASH_TABLE)
		do
			control := Conflict_constant
		ensure -- from HASH_TABLE
			conflict: conflict
		end

	set_content (c: like content)
			-- Assign c to content.
			-- (from HASH_TABLE)
		require -- from HASH_TABLE
			c_attached: c /= Void
		do
			content := c
		ensure -- from HASH_TABLE
			content_set: content = c
		end

	set_deleted_marks (d: like deleted_marks)
			-- Assign c to content.
			-- (from HASH_TABLE)
		require -- from HASH_TABLE
			d_attached: d /= Void
		do
			deleted_marks := d
		ensure -- from HASH_TABLE
			deleted_marks_set: deleted_marks = d
		end

	set_found
			-- Set status to found.
			-- (from HASH_TABLE)
		do
			control := Found_constant
		ensure -- from HASH_TABLE
			found: found
		end

	set_indexes_map (v: like indexes_map)
			-- Assign v to indexes_map.
			-- (from HASH_TABLE)
		do
			indexes_map := v
		ensure -- from HASH_TABLE
			indexes_map_set: indexes_map = v
		end

	set_inserted
			-- Set status to inserted.
			-- (from HASH_TABLE)
		do
			control := Inserted_constant
		ensure -- from HASH_TABLE
			inserted: inserted
		end

	set_keys (c: like keys)
			-- Assign c to keys.
			-- (from HASH_TABLE)
		require -- from HASH_TABLE
			c_attached: c /= Void
		do
			keys := c
		ensure -- from HASH_TABLE
			keys_set: keys = c
		end

	set_no_status
			-- Set status to normal.
			-- (from HASH_TABLE)
		do
			control := 0
		ensure -- from HASH_TABLE
			default_status: not special_status
		end

	set_not_found
			-- Set status to not found.
			-- (from HASH_TABLE)
		do
			control := Not_found_constant
		ensure -- from HASH_TABLE
			not_found: not_found
		end

	set_removed
			-- Set status to removed.
			-- (from HASH_TABLE)
		do
			control := Removed_constant
		ensure -- from HASH_TABLE
			removed: removed
		end

	set_replaced
			-- Set status to replaced.
			-- (from HASH_TABLE)
		do
			control := Replaced_constant
		ensure -- from HASH_TABLE
			replaced: replaced
		end

	special_status: BOOLEAN
			-- Has status been set to some non-default value?
			-- (from HASH_TABLE)
		do
			Result := control > 0
		ensure -- from HASH_TABLE
				Result = (control > 0)
		end

	truly_occupied (i: INTEGER_32): BOOLEAN
			-- Is position i occupied by a key and a value?
			-- (from HASH_TABLE)
		do
			if i >= 0 and i < keys.count then
				Result := (has_default and i = indexes_map.item (capacity)) or else occupied (i)
			end
		ensure -- from HASH_TABLE
			normal_key: (i >= 0 and i < keys.count and i /= indexes_map.item (capacity)) implies (occupied (i) implies Result)
			default_key: (i = indexes_map.item (capacity)) implies (Result = has_default)
		end
	
feature -- Correction

	Mismatch_information: MISMATCH_INFORMATION
			-- Original attribute values of mismatched object
			-- (from MISMATCH_CORRECTOR)
		once
			create Result
		end
	
feature -- Hash code

	hash_code_of (a_key: READABLE_STRING_GENERAL): INTEGER_32
			-- Hash code value
		do
			if is_case_insensitive then
				Result := a_key.case_insensitive_hash_code
			else
				Result := a_key.hash_code
			end
		ensure -- from HASH_TABLE
			non_negative: Result >= 0
		end
	
feature {HASH_TABLE, HASH_TABLE_ITERATION_CURSOR} -- Implementation: content attributes and preservation

	content: SPECIAL [G]
			-- Array of contents
			-- (from HASH_TABLE)

	keys: SPECIAL [READABLE_STRING_GENERAL]
			-- Array of keys
			-- (from HASH_TABLE)
	
feature {HASH_TABLE} -- Implementation: content attributes and preservation

	deleted_marks: SPECIAL [BOOLEAN]
			-- Indexes of deleted positions in content and keys.
			-- (from HASH_TABLE)

	has_default: BOOLEAN
			-- Is the default key present?
			-- (from HASH_TABLE)

	indexes_map: SPECIAL [INTEGER_32]
			-- Indexes of items in content, and keys.
			-- If item is not present, then it has Ht_impossible_position.
			-- If item is deleted, then it has Ht_deleted_position.
			-- (from HASH_TABLE)

	item_position: INTEGER_32
			-- Position in indexes_map for item at position position. Set by internal_search.
			-- (from HASH_TABLE)
	
feature {HASH_TABLE} -- Implementation: search attributes

	control: INTEGER_32
			-- Control code set by operations that may produce
			-- several possible conditions.
			-- (from HASH_TABLE)

	deleted_item_position: INTEGER_32
			-- Place where a deleted element was found during a search
			-- (from HASH_TABLE)

	iteration_position: INTEGER_32
			-- Cursor for iteration primitives
			-- (from HASH_TABLE)

	position: INTEGER_32
			-- Hash table cursor, updated after each operation:
			-- put, remove, has, replace, force, change_key...
			-- (from HASH_TABLE)
		do
			Result := indexes_map.item (item_position)
		end

	soon_full: BOOLEAN
			-- Is table close to being filled to current capacity?
			-- (from HASH_TABLE)
		do
			Result := keys.count = keys.capacity
		ensure -- from HASH_TABLE
				Result = (keys.count = keys.capacity)
		end
	
feature -- Output

	Io: STD_FILES
			-- Handle to standard file setup
			-- (from ANY)
		once
			create Result;
			Result.set_output_default
		ensure -- from ANY
			instance_free: class
			io_not_void: Result /= Void
		end

	out: STRING_8
			-- New string containing terse printable representation
			-- of current object
			-- (from ANY)
		do
			Result := tagged_out
		ensure -- from ANY
			out_not_void: Result /= Void
		end

	print (o: detachable ANY)
			-- Write terse external representation of o
			-- on standard output.
			-- (from ANY)
		local
			s: READABLE_STRING_8
		do
			if attached o then
				s := o.out
				if attached {READABLE_STRING_32} s as s32 then
					Io.put_string_32 (s32)
				elseif attached {READABLE_STRING_8} s as s8 then
					Io.put_string (s8)
				else
					Io.put_string_32 (s.as_string_32)
				end
			end
		ensure -- from ANY
			instance_free: class
		end

	frozen tagged_out: STRING_8
			-- New string containing terse printable representation
			-- of current object
			-- (from ANY)
		external
			"built_in"
		ensure -- from ANY
			tagged_out_not_void: Result /= Void
		end
	
feature -- Platform

	Operating_environment: OPERATING_ENVIRONMENT
			-- Objects available from the operating system
			-- (from ANY)
		once
			create Result
		ensure -- from ANY
			instance_free: class
			operating_environment_not_void: Result /= Void
		end
	
feature {NONE} -- Retrieval

	frozen internal_correct_mismatch
			-- Called from runtime to perform a proper dynamic dispatch on correct_mismatch
			-- from MISMATCH_CORRECTOR.
			-- (from ANY)
		local
			l_msg: STRING_32
			l_exc: EXCEPTIONS
		do
			if attached {MISMATCH_CORRECTOR} Current as l_corrector then
				l_corrector.correct_mismatch
			else
				create l_msg.make_from_string ("Mismatch: ".as_string_32)
				create l_exc;
				l_msg.append (generating_type.name_32);
				l_exc.raise_retrieval_exception (l_msg)
			end
		end
	
invariant
		-- from HASH_TABLE
	keys_not_void: keys /= Void
	content_not_void: content /= Void
	keys_enough_capacity: keys.count <= capacity + 1
	content_enough_capacity: content.count <= capacity + 1
	valid_iteration_position: off or truly_occupied (iteration_position)
	control_non_negative: control >= 0
	special_status: special_status = (conflict or inserted or replaced or removed or found or not_found)
	count_big_enough: 0 <= count
	count_small_enough: count <= capacity
	slot_count_big_enough: 0 <= count

		-- from FINITE
	empty_definition: is_empty = (count = 0)

		-- from ANY
	reflexive_equality: standard_is_equal (Current)
	reflexive_conformance: conforms_to (Current)

		-- from READABLE_INDEXABLE
	consistent_boundaries: iteration_lower <= iteration_upper or else iteration_lower = iteration_upper + 1

note
	copyright: "Copyright (c) 1984-2016, Eiffel Software and others"
	license: "Eiffel Forum License v2 (see http://www.eiffel.com/licensing/forum.txt)"
	source: "[
		Eiffel Software
		5949 Hollister Ave., Goleta, CA 93117 USA
		Telephone 805-685-1006, Fax 805-685-6869
		Website http://www.eiffel.com
		Customer support http://support.eiffel.com
	]"

end -- class STRING_TABLE