note
	description: "Original values of the attributes of a mismatched object."
	instructions: "[
		This object will contain the original values of the attributes
		of a retrieved object for which a mismatched was detected at
		retrieval time. The value are indexed by the name of the attribute
		in the stored object. One extra entry is provided to contain the
		original name of the class in the storing system, indexed by the
		string 'class'. This allows correct_mismatch to determine the
		original name of its generating class in case class-name
		translation is in effect.
	]"
	library: "Free implementation of ELKS library"
	status: "See notice at end of class."
	legal: "See notice at end of class."
	date: "$Date: 2020-05-19 14:29:33 +0000 (Tue, 19 May 2020) $"
	revision: "$Revision: 104259 $"

class 
	MISMATCH_INFORMATION

create {MISMATCH_CORRECTOR}
	default_create


create 
	make

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: MISMATCH_INFORMATION
			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

	default_create
			-- Make container with default size
		do
			make (5)
			Set_callback_pointers
		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 ANY
			l_default_key: detachable STRING_8
			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: STRING_8): detachable ANY 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 STRING_8
			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: STRING_8
		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

	class_name: STRING_8
			-- Name of generating class which held attribute values
		do
			check
				has_class_entry: has (Type_name_key)
			end
			check
					attached {STRING_8} item (Type_name_key) as r
			then
				Result := r
			end
		ensure
			result_exists: Result /= Void
		end

	current_keys: ARRAY [STRING_8]
			-- 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

	current_version: detachable IMMUTABLE_STRING_8
			-- Version associated to class_name in the current system.

	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: STRING_8): detachable ANY
			-- 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 ANY
			-- Item, if any, yielded by last search operation
			-- (from HASH_TABLE)

	generating_type: TYPE [detachable MISMATCH_INFORMATION]
			-- 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: STRING_8): BOOLEAN
			-- Is there an item in the table with key key?
			-- (from HASH_TABLE)
		require -- from  TABLE
			True
		local
			l_default_key: detachable STRING_8
			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: STRING_8
		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: detachable ANY): 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: STRING_8): 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 ANY
		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

	hash_code_of (a_key: attached STRING_8): INTEGER_32
			-- Hash_code value associated to a_key.
			-- (from HASH_TABLE)
		do
			Result := a_key.hash_code
		ensure -- from HASH_TABLE
			non_negative: Result >= 0
		end

	item alias "[]" (key: STRING_8): detachable ANY 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 STRING_8
			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: STRING_8
		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: detachable ANY
			-- 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): detachable ANY
			-- 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: STRING_8
			-- 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 [detachable ANY, STRING_8]
			-- 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

	stored_version: detachable IMMUTABLE_STRING_8
			-- Version associated to class_name in the stored system.

	Type_name_key: STRING_8 = "_type_name"
			-- Associated key for retrieving the type name of a mismatch.
	
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: detachable ANY): 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 [detachable ANY]): INTEGER_32
			-- Estimated number of elements in other.
			-- (from CONTAINER)
		do
			if attached {FINITE [detachable ANY]} other as f then
				Result := f.count
			elseif attached {READABLE_INDEXABLE [detachable ANY]} 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 [detachable ANY, STRING_8]): 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: MISMATCH_INFORMATION): 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: MISMATCH_INFORMATION): BOOLEAN
			-- Does table contain the same information as other?
			-- (from HASH_TABLE)
		require -- from ANY
			other_not_void: other /= Void
		do
			if count = other.count and then object_comparison = other.object_comparison and then has_default = other.has_default then
				Result := True
				across
					Current as l_c
				until
					not Result
				loop
					other.search (l_c.key)
					if other.found then
						if object_comparison then
							Result := l_c.item ~ other.found_item
						else
							Result := l_c.item = other.found_item
						end
					else
						Result := False
					end
				end
			end
		ensure -- from ANY
			symmetric: Result implies other ~ Current
			consistent: standard_is_equal (other) implies Result
		end

	same_keys (a_search_key, a_key: STRING_8): BOOLEAN
			-- Does a_search_key equal to a_key?
			-- (from HASH_TABLE)
		do
			Result := a_search_key ~ a_key
		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: MISMATCH_INFORMATION): 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_empty: BOOLEAN
			-- Is structure empty?
			-- (from FINITE)
		require -- from  CONTAINER
			True
		do
			Result := count = 0
		end

	is_inserted (v: detachable ANY): 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

	is_version_mismatched: BOOLEAN
			-- Is the stored_version different from the current system version?
		do
			Result := stored_version /~ current_version
		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: STRING_8): 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 ({STRING_8}).is_expanded and then attached k then
					Result := k.generating_type ~ {detachable STRING_8}
				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: STRING_8)
			-- 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 ANY
		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 ANY
		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: detachable ANY; key: STRING_8)
			-- 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 STRING_8
			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 [detachable ANY])
			-- 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 [detachable ANY]
		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: detachable ANY; key: STRING_8)
			-- 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 STRING_8
			l_default_value: detachable ANY
			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 [detachable ANY, STRING_8])
			-- 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: detachable ANY; key: STRING_8)
			-- 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 STRING_8
			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: detachable ANY; key: STRING_8)
			-- 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 ANY
		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: STRING_8; old_key: STRING_8)
			-- 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: detachable ANY
		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: detachable ANY)
			-- 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: detachable ANY)
			-- 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: STRING_8)
			-- 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 STRING_8
			l_default_value: detachable ANY
			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 ANY
		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: MISMATCH_INFORMATION
			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 [detachable ANY]} Mismatch_information.item ("content") as array_content then
					content := array_content.area
				end
				if attached {ARRAY [STRING_8]} 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 [detachable ANY]
			-- 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 -- 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: MISMATCH_INFORMATION)
			-- 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: MISMATCH_INFORMATION)
			-- 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: MISMATCH_INFORMATION
			-- 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: MISMATCH_INFORMATION)
			-- 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: MISMATCH_INFORMATION
			-- 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: MISMATCH_INFORMATION
			-- 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 {NONE} -- Duplication

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

	frozen as_attached: attached MISMATCH_INFORMATION
		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 MISMATCH_INFORMATION
			-- 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: detachable ANY)
			-- 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: detachable ANY)
			-- 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 STRING_8
			-- 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 ANY
			-- 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: detachable ANY
			-- 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 ANY
			-- (from HASH_TABLE)

	ht_deleted_key: detachable STRING_8
			-- 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_put (value: ANY; ckey: POINTER)
			-- Allows run-time to insert items into table
		do
			put (value, create {STRING_8}.make_from_c (ckey))
		end

	internal_search (key: STRING_8)
			-- 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 STRING_8
			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: STRING_8
		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 STRING_8
			-- 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: STRING_8)
			-- 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 STRING_8
			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_callback_pointers
			-- Sets call-back pointers in the run-time
		once
			set_mismatch_information_access (Current, $wipe_out, $internal_put, $set_string_versions)
		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

	set_string_versions (a_stored_version, a_current_version: POINTER)
			-- Set stored_version with a_stored_version.
			-- Set current_version with a_current_version.
		local
			l_imm: IMMUTABLE_STRING_8
		do
			if a_stored_version = default_pointer then
				stored_version := Void
			else
				create l_imm.make_from_c (a_stored_version)
				if l_imm.is_empty then
					stored_version := Void
				else
					stored_version := l_imm
				end
			end
			if a_current_version = default_pointer then
				current_version := Void
			else
				create l_imm.make_from_c (a_current_version)
				if l_imm.is_empty then
					current_version := Void
				else
					current_version := l_imm
				end
			end
		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 {NONE} -- Externals

	set_mismatch_information_access (obj: ANY; init, add, set_vers: POINTER)
		external
			"C signature (EIF_OBJECT, EIF_PROCEDURE, EIF_PROCEDURE, EIF_PROCEDURE) use <eif_retrieve.h>"
		end
	
feature {HASH_TABLE, HASH_TABLE_ITERATION_CURSOR} -- Implementation: content attributes and preservation

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

	keys: SPECIAL [STRING_8]
			-- 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
			-- Printable representation of attributes values
		local
			i: detachable ANY
			k: detachable STRING_8
		do
			from
				create Result.make (20 + class_name.count + 40 * count);
				Result.append ("Attributes of original class ");
				Result.append (class_name);
				Result.append (": ");
				Result.append_integer (count - 1);
				Result.append (" item")
				if count - 1 /= 1 then
					Result.append_character ('s')
				end;
				Result.append_character ('%N')
				start
			until
				after
			loop
				k := key_for_iteration
				if k /~ Type_name_key then
					Result.append ("  ")
					if k = Void then
						Result.append ("Void")
					else
						Result.append (k)
					end;
					Result.append (": ")
					i := item_for_iteration
					if i = Void then
						Result.append ("Void")
					else
						Result.append (i.out)
					end;
					Result.append_character ('%N')
				end
				forth
			end
		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
	
feature -- Settings

	set_versions (a_stored_version: like stored_version; a_current_version: like current_version)
			-- Set stored_version with a_stored_version.
			-- Set current_version with a_current_version.
		do
			stored_version := a_stored_version
			current_version := a_current_version
		ensure
			stored_version_set: stored_version = a_stored_version
			current_version_set: current_version = a_current_version
		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-2020, 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 MISMATCH_INFORMATION