Automatic generation produced by ISE Eiffel

Classes
Clusters
Cluster hierarchy
Chart
Relations
Text
Flat
Contracts
Flat contracts
Go to: 
indexing
	description: "Hash tables, used to store items identified by hashable keys"
	instructions: "[
		Several procedures are provided for inserting an item
		with a given key.
		
		Here is how to choose between them:
		
			- Use `put' if you want to do an insertion only if
			  there was no item with the given key, doing nothing
			  otherwise. (You can find out on return if there was one,
			  and what it was.)
		
			- Use `force' if you always want to insert the item;
			  if there was one for the given key it will be removed,
			  (and you can find out on return what it was).
		
			- Use `extend' if you are sure there is no item with
			  the given key, enabling faster insertion (but
			  unpredictable behavior if this assumption is not true).
		
			- Use `replace' if you want to replace an already present
			  item with the given key, and do nothing if there is none.
		
		In addition you can use `replace_key' to change the key of an
		already present item, identified by its previous key, or
		do nothing if there is nothing for that previous key.
		You can find out on return.
	]"
	instructions: "[
		To find out whether a key appears in the table, use `has'.
		To find out the item, if any, associated with a certain key,
		use `item'.
		
		Both of these routines perform a search. If you need
		both pieces of information (does a key appear? And, if so,
		what is the associated item?), you can avoid performing
		two redundant traversals by using instead the combination
		of `search', `found' and `found_item' as follows: 
		
			your_table.search (your_key)
			if your_table.found then
				what_you_where_looking_for := your_table.found_item
				... Do whatever is needed to `what_you_were_looking_for' ... 
			else
				... No item was present for `your_key' ...
			end
	]"
	compatibility: "[
		This version of the class accepts any value of type H as key.
		Previous versions did not accept the default value as a key;
		this restriction no longer applies. Most clients of the old version
		should work correctly with this one; a client that explicitly relied
		on the default value not being hashable should use the old version
		available in the EiffelBase 3.3 compatibility cluster.
		
		Also, `force' now sets either `found' or `not_found'.
		(Previously it would always set `inserted'.)
	]"
	storable_compatibility: "[
		Persistent instances of the old version of this class will not be
		 retrievable with the present version.
	]"
	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, as key argument to
		`put' and `replace_key'.
	]"
	status: "See notice at end of class"
	date: "$Date: 2001/11/16 20:34:23 $"
	revision: "$Revision: 1.1.1.1 $"

class 
	HASH_TABLE [G, H -> HASHABLE]

create 
	make

feature -- Initialization

	accommodate (n: INTEGER) is
			-- Reallocate table with enough space for n items;
			-- keep all current items.
		require
			n >= 0
		local
			i: INTEGER
			new_table: HASH_TABLE [G, H]
			default_key: H
		do
			from
				create new_table.make (count.max (n))
			until
				i = capacity
			loop
				if occupied (i) then
					check
						not new_table.soon_full
					end
					new_table.put (content.item (i), keys.item (i))
				end
				i := i + 1
			end
			if has_default then
				new_table.put (content.item (capacity), default_key)
			end
			set_content (new_table.content)
			set_keys (new_table.keys)
			set_deleted_marks (new_table.deleted_marks)
			capacity := new_table.capacity
			used_slot_count := count
			iteration_position := new_table.iteration_position
		ensure
			count_not_changed: count = old count
			slot_count_same_as_count: used_slot_count = count
			breathing_space: count * 100 < capacity * initial_occupation
		end

	make (n: INTEGER) is
			-- Allocate hash table for at least n items.
			-- The table will be resized automatically
			-- if more than n items are inserted.
		local
			clever: PRIMES
		do
			create clever
			capacity := n.max (minimum_capacity)
			capacity := (capacity * 100) // initial_occupation + 1
			capacity := clever.higher_prime (capacity)
			create content.make (0, capacity)
			create keys.make (0, capacity)
			create deleted_marks.make (0, capacity - 1)
			iteration_position := capacity + 1
		ensure
			breathing_space: n * 100 < capacity * initial_occupation
			minimum_space: minimum_capacity * 100 < capacity * initial_occupation
			more_than_minimum: capacity >= minimum_capacity
			no_status: not special_status
		end
	
feature -- Access

	current_keys: ARRAY [H] is
			-- New array containing actually used keys, from 1 to count
		local
			j: INTEGER
			old_iteration_position: INTEGER
		do
			old_iteration_position := iteration_position
			from
				create Result.make (1, count)
				start
			until
				off
			loop
				j := j + 1
				Result.put (key_for_iteration, j)
				forth
			end
			iteration_position := old_iteration_position
		ensure
			good_count: Result.count = count
		end

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

	found_item: G
			-- Item, if any, yielded by last search operation

	has (key: H): BOOLEAN is
			-- Is there an item in the table with key key?
		local
			old_control, old_position: INTEGER
		do
			old_control := control
			old_position := position
			internal_search (key)
			Result := found
			control := old_control
			position := old_position
		ensure then
			default_case: (key = computed_default_key) implies (Result = has_default)
		end

	has_item (v: G): BOOLEAN is
			-- Does structure include v?
			-- (Reference or object equality,
			-- based on object_comparison.)
		local
			i: INTEGER
		do
			if has_default then
				Result := (v = default_key_value)
			end
			if not Result then
				if object_comparison then
					from
					until
						i = capacity or else Result
					loop
						Result := occupied (i) and then equal (v, content.item (i))
						i := i + 1
					end
				else
					from
					until
						i = capacity or else Result
					loop
						Result := occupied (i) and then (v = content.item (i))
						i := i + 1
					end
				end
			end
		ensure -- from CONTAINER
			not_found_in_empty: Result implies not is_empty
		end

	item (key: H): G is
			-- Item associated with key, if present
			-- otherwise default value of type G
			-- Was declared in HASH_TABLE as synonym of @.
		require -- from TABLE
			valid_key: valid_key (k)
		local
			old_control, old_position: INTEGER
		do
			old_control := control
			old_position := position
			internal_search (key)
			if found then
				Result := content.item (position)
			end
			control := old_control
			position := old_position
		ensure then
			default_value_if_not_present: (not (has (key))) implies (Result = computed_default_value)
		end

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

	key_for_iteration: H is
			-- Key at current iteration position
		require
			not_off: not off
		do
			Result := keys.item (iteration_position)
		ensure
			at_iteration_position: Result = key_at (iteration_position)
		end

	infix "@" (key: H): G is
			-- Item associated with key, if present
			-- otherwise default value of type G
			-- Was declared in HASH_TABLE as synonym of item.
		require -- from TABLE
			valid_key: valid_key (k)
		local
			old_control, old_position: INTEGER
		do
			old_control := control
			old_position := position
			internal_search (key)
			if found then
				Result := content.item (position)
			end
			control := old_control
			position := old_position
		ensure then
			default_value_if_not_present: (not (has (key))) implies (Result = computed_default_value)
		end
	
feature -- Measurement

	capacity: INTEGER
			-- Number of items that may be stored.

	count: INTEGER
			-- Number of items in table

	occurrences (v: G): INTEGER is
			-- Number of table items equal to v.
		local
			old_iteration_position: INTEGER
		do
			old_iteration_position := iteration_position
			if object_comparison then
				from
					start
				until
					off
				loop
					if equal (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 -- Comparison

	is_equal (other: like Current): BOOLEAN is
			-- Does table contain the same information as other?
		require -- from ANY
			other_not_void: other /= void
		do
			Result := equal (keys, other.keys) and equal (content, other.content) and equal (deleted_marks, other.deleted_marks) and (has_default = other.has_default)
		ensure -- from ANY
			symmetric: Result implies other.is_equal (Current)
			consistent: standard_is_equal (other) implies Result
		end
	
feature -- Status report

	after: BOOLEAN is
			-- Is cursor past last item?
			-- Was declared in HASH_TABLE as synonym of off.
		do
			Result := is_off_position (iteration_position)
		ensure
			definition: Result = ((not has_default and (iteration_position >= capacity)) or (has_default and (iteration_position = (capacity + 1))))
		end

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

	conflict: BOOLEAN is
			-- Did last operation cause a conflict?
		do
			Result := (control = conflict_constant)
		end

	empty: BOOLEAN is
		obsolete "ELKS 2000: Use `is_empty' instead"
			-- Is there no element?
			-- (from CONTAINER)
		do
			Result := is_empty
		end

	Extendible: BOOLEAN is True
			-- May new items be added? (Answer: yes.)

	found: BOOLEAN is
			-- Did last operation find the item sought?
		do
			Result := (control = found_constant)
		end

	Full: BOOLEAN is False
			-- Is structure filled to capacity? (Answer: no.)

	inserted: BOOLEAN is
			-- Did last operation insert an item?
		do
			Result := (control = inserted_constant)
		end

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

	is_inserted (v: G): BOOLEAN is
			-- 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 is
			-- Did last operation fail to find the item sought?
		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
			-- Is cursor past last item?
			-- Was declared in HASH_TABLE as synonym of after.
		do
			Result := is_off_position (iteration_position)
		ensure
			definition: Result = ((not has_default and (iteration_position >= capacity)) or (has_default and (iteration_position = (capacity + 1))))
		end

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

	removed: BOOLEAN is
			-- Did last operation remove an item?
		do
			Result := (control = removed_constant)
		end

	replaced: BOOLEAN is
			-- Did last operation replace an item?
		do
			Result := (control = replaced_constant)
		end

	valid_cursor (c: CURSOR): BOOLEAN is
			-- Can cursor be moved to position c?
		require
			c_not_void: c /= void
		local
			ht_cursor: HASH_TABLE_CURSOR
			cursor_position: INTEGER
		do
			ht_cursor ?= c
			if ht_cursor /= void then
				cursor_position := ht_cursor.position
				Result := (is_off_position (cursor_position)) or else ((cursor_position >= 0) and (cursor_position <= capacity) and then truly_occupied (cursor_position))
			end
		end

	valid_key (k: H): BOOLEAN is
			-- Is k a valid key?
			-- (Answer: always yes for hash tables in this version)
		do
			Result := True
		ensure then
			Result
		end
	
feature -- Status setting

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

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

	forth is
			-- Advance cursor to next occupied position,
			-- or off if no such position remains.
		require
			not_off: not off
		do
			from
				iteration_position := iteration_position + 1
			until
				off or else truly_occupied (iteration_position)
			loop
				iteration_position := iteration_position + 1
			end
		end

	go_to (c: CURSOR) is
			-- Move to position c.
		require
			c_not_void: c /= void
			valid_cursor: valid_cursor (c)
		local
			ht_cursor: HASH_TABLE_CURSOR
		do
			ht_cursor ?= c
			if ht_cursor /= void then
				iteration_position := ht_cursor.position
			end
		end

	search (key: H) is
			-- Search for item of key key.
			-- If found, set found to true, and set
			-- found_item to item associated with key.
		local
			default_value: G
		do
			internal_search (key)
			if found then
				found_item := content.item (position)
			else
				found_item := default_value
			end
		ensure
			found_or_not_found: found or not_found
			item_if_found: found implies (found_item = content.item (position))
		end

	search_item: G is
		obsolete "Use found_item instead."
		do
			Result := found_item
		end

	start is
			-- Bring cursor to first position.
		do
			iteration_position := - 1
			forth
		end
	
feature -- Element change

	extend (new: G; key: H) is
			-- 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.
		require
			not_present: not has (key)
		do
			search_for_insertion (key)
			if soon_full then
				add_space
				search_for_insertion (key)
			end
			if position < capacity and then deleted (position) then
				set_not_deleted (position)
			else
				used_slot_count := used_slot_count + 1
			end
			count := count + 1
			put_at_position (new, key)
			set_inserted
		ensure
			inserted: inserted
			insertion_done: item (key) = new
			one_more: count = old count + 1
			same_slot_count_or_one_more_unless_reallocated: (used_slot_count = old used_slot_count) or (used_slot_count = old used_slot_count + 1) or (used_slot_count = count)
			default_property: has_default = ((key = computed_default_key) or (old has_default))
		end

	fill (other: CONTAINER [G]) is
			-- 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
		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: H) is
			-- 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.
		require else
			True
		local
			default_key: H
		do
			search (key)
			if not_found then
				if soon_full then
					add_space
					internal_search (key)
				end
				if deleted_position /= impossible_position then
					position := deleted_position
					set_not_deleted (position)
				end
				keys.put (key, position)
				if key = default_key then
					set_default
				end
				count := count + 1
				used_slot_count := used_slot_count + 1
			end
			content.put (new, position)
		ensure then
			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)
			same_slot_count_or_one_more_unless_reallocated: (used_slot_count = old used_slot_count) or (used_slot_count = old used_slot_count + 1) or (used_slot_count = count)
			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

	put (new: G; key: H) is
			-- 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.
		require -- from TABLE
			valid_key: valid_key (k)
		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 found
					end
				end
				if deleted_position /= impossible_position then
					position := deleted_position
					set_not_deleted (position)
				end
				count := count + 1
				used_slot_count := used_slot_count + 1
				put_at_position (new, key)
				found_item := new
				set_inserted
			end
		ensure then
			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)
			one_more_slot_if_inserted_unless_reallocated: inserted implies ((