/[eiffelstudio]/FreeELKS/trunk/library/structures/table/hash_table.e
ViewVC logotype

Contents of /FreeELKS/trunk/library/structures/table/hash_table.e

Parent Directory Parent Directory | Revision Log Revision Log


Revision 91473 - (show annotations)
Sun Feb 26 10:41:00 2006 UTC (13 years, 10 months ago) by ericb
File size: 36899 byte(s)
Removed unique features

1 indexing
2
3 description:
4 "Hash tables, used to store items identified by hashable keys"
5
6 instructions: "[
7 Several procedures are provided for inserting an item
8 with a given key.
9
10 Here is how to choose between them:
11
12 - Use `put' if you want to do an insertion only if
13 there was no item with the given key, doing nothing
14 otherwise. (You can find out on return if there was one,
15 and what it was.)
16
17 - Use `force' if you always want to insert the item;
18 if there was one for the given key it will be removed,
19 (and you can find out on return what it was).
20
21 - Use `extend' if you are sure there is no item with
22 the given key, enabling faster insertion (but
23 unpredictable behavior if this assumption is not true).
24
25 - Use `replace' if you want to replace an already present
26 item with the given key, and do nothing if there is none.
27
28 In addition you can use `replace_key' to change the key of an
29 already present item, identified by its previous key, or
30 do nothing if there is nothing for that previous key.
31 You can find out on return.
32 ]"
33
34 instructions: "[
35 To find out whether a key appears in the table, use `has'.
36 To find out the item, if any, associated with a certain key,
37 use `item'.
38
39 Both of these routines perform a search. If you need
40 both pieces of information (does a key appear? And, if so,
41 what is the associated item?), you can avoid performing
42 two redundant traversals by using instead the combination
43 of `search', `found' and `found_item' as follows:
44
45 your_table.search (your_key)
46 if your_table.found then
47 what_you_where_looking_for := your_table.found_item
48 ... Do whatever is needed to `what_you_were_looking_for' ...
49 else
50 ... No item was present for `your_key' ...
51 end
52 ]"
53
54 compatibility: "[
55 This version of the class accepts any value of type H as key.
56 Previous versions did not accept the default value as a key;
57 this restriction no longer applies. Most clients of the old version
58 should work correctly with this one; a client that explicitly relied
59 on the default value not being hashable should use the old version
60 available in the EiffelBase 3.3 compatibility cluster.
61
62 Also, `force' now sets either `found' or `not_found'.
63 (Previously it would always set `inserted'.)
64 ]"
65
66 storable_compatibility: "[
67 Persistent instances of the old version of this class will not be
68 retrievable with the present version.
69 ]"
70
71 warning: "[
72 Modifying an object used as a key by an item present in a table will
73 cause incorrect behavior. If you will be modifying key objects,
74 pass a clone, not the object itself, as key argument to
75 `put' and `replace_key'.
76 ]"
77
78 status: "See notice at end of class"
79 date: "$Date$"
80 revision: "$Revision$"
81
82 class HASH_TABLE [G, H -> HASHABLE] inherit
83
84 UNBOUNDED [G]
85 rename
86 has as has_item
87 redefine
88 has_item, copy, is_equal
89 end
90
91 TABLE [G, H]
92 rename
93 has as has_item,
94 wipe_out as clear_all,
95 extend as collection_extend
96 export
97 {NONE} prune_all
98 redefine
99 copy, is_equal, clear_all, has_item
100 end
101
102 MISMATCH_CORRECTOR
103 export
104 {NONE} all
105 undefine
106 copy, is_equal
107 redefine
108 correct_mismatch
109 end
110
111 create
112 make
113
114 feature -- Initialization
115
116 make (n: INTEGER) is
117 -- Allocate hash table for at least `n' items.
118 -- The table will be resized automatically
119 -- if more than `n' items are inserted.
120 local
121 clever: PRIMES
122 l_content: ARRAY [G]
123 l_keys: ARRAY [H]
124 l_deleted_marks: ARRAY [BOOLEAN]
125 do
126 create clever
127 capacity := n.Max (Minimum_capacity)
128 capacity := capacity + capacity // 2 + 1
129 capacity := clever.higher_prime (capacity)
130 create l_content.make (0, capacity)
131 content := l_content.area
132 create l_keys.make (0, capacity)
133 keys := l_keys.area
134 -- Position `capacity' ignored by hash sequences,
135 -- used to store value for default key.
136
137 create l_deleted_marks.make (0, capacity)
138 deleted_marks := l_deleted_marks.area
139 iteration_position := capacity + 1
140 ensure
141 breathing_space: n < capacity * Initial_occupation
142 minimum_space: Minimum_capacity < capacity * Initial_occupation
143 more_than_minimum: capacity >= Minimum_capacity
144 no_status: not special_status
145 end
146
147 accommodate (n: INTEGER) is
148 -- Reallocate table with enough space for `n' items;
149 -- keep all current items.
150 require
151 n >= 0
152 local
153 i: INTEGER
154 new_table: HASH_TABLE [G, H]
155 default_key: H
156 l_content: like content
157 l_keys: like keys
158 do
159 -- (Could also use iteration facilities.)
160 from
161 create new_table.make (count.max (n))
162 l_content := content
163 l_keys := keys
164 until
165 i = capacity
166 loop
167 if occupied (i) then
168 check
169 not new_table.soon_full
170 -- See invariant clause `sized_generously_enough'
171 end
172 new_table.put (l_content.item (i), l_keys.item (i))
173 end
174 i := i + 1
175 end
176
177 if has_default then
178 new_table.put (l_content.item (capacity), default_key)
179 end
180
181 set_content (new_table.content)
182 set_keys (new_table.keys)
183 set_deleted_marks (new_table.deleted_marks)
184
185 capacity := new_table.capacity
186 used_slot_count := count
187 iteration_position := new_table.iteration_position
188 ensure
189 count_not_changed: count = old count
190 slot_count_same_as_count: used_slot_count = count
191 breathing_space: count < capacity * Initial_occupation
192 end
193
194
195 feature -- Access
196
197 found_item: G
198 -- Item, if any, yielded by last search operation
199
200 item alias "[]", infix "@" (key: H): G assign put is
201 -- Item associated with `key', if present
202 -- otherwise default value of type `G'
203 local
204 old_control, old_position: INTEGER
205 do
206 old_control := control; old_position := position
207 internal_search (key)
208 if found then
209 Result := content.item (position)
210 end
211 control := old_control; position := old_position
212 ensure then
213 default_value_if_not_present:
214 (not (has (key))) implies (Result = computed_default_value)
215 end
216
217 has (key: H): BOOLEAN is
218 -- Is there an item in the table with key `key'?
219 local
220 old_control, old_position: INTEGER
221 do
222 old_control := control; old_position := position
223 internal_search (key)
224 Result := found
225 control := old_control; position := old_position
226 ensure then
227 default_case:
228 (key = computed_default_key) implies (Result = has_default)
229 end
230
231 has_item (v: G): BOOLEAN is
232 -- Does structure include `v'?
233 -- (Reference or object equality,
234 -- based on `object_comparison'.)
235 local
236 i: INTEGER
237 l_content: like content
238 do
239 if has_default then
240 Result := (v = default_key_value)
241 end
242 if not Result then
243 l_content := content
244 if object_comparison then
245 from
246 until
247 i = capacity or else Result
248 loop
249 Result := occupied (i) and then equal (v, l_content.item (i))
250 i := i + 1
251 end
252 else
253 from
254 until
255 i = capacity or else Result
256 loop
257 Result := occupied (i) and then (v = l_content.item (i))
258 i := i + 1
259 end
260 end
261 end
262 end
263
264 current_keys: ARRAY [H] is
265 -- New array containing actually used keys, from 1 to `count'
266 local
267 j: INTEGER
268 old_iteration_position: INTEGER
269 do
270 old_iteration_position := iteration_position
271 from
272 create Result.make (1, count)
273 start
274 until
275 off
276 loop
277 j := j + 1
278 Result.put (key_for_iteration, j)
279 forth
280 end
281 iteration_position := old_iteration_position
282 ensure
283 good_count: Result.count = count
284 end
285
286 item_for_iteration: G is
287 -- Element at current iteration position
288 require
289 not_off: not off
290 do
291 Result := content.item (iteration_position)
292 end
293
294 key_for_iteration: H is
295 -- Key at current iteration position
296 require
297 not_off: not off
298 do
299 Result := keys.item (iteration_position)
300 ensure
301 at_iteration_position: Result = key_at (iteration_position)
302 end
303
304 cursor: CURSOR is
305 -- Current cursor position
306 do
307 create {HASH_TABLE_CURSOR} Result.make (iteration_position)
308 ensure
309 cursor_not_void: Result /= Void
310 end
311
312 feature -- Measurement
313
314 count: INTEGER
315 -- Number of items in table
316
317 capacity: INTEGER
318 -- Number of items that may be stored.
319
320 occurrences (v: G): INTEGER is
321 -- Number of table items equal to `v'.
322 local
323 old_iteration_position: INTEGER
324 do
325 old_iteration_position := iteration_position
326 if object_comparison then
327 from
328 start
329 until
330 off
331 loop
332 if equal (item_for_iteration, v) then
333 Result := Result + 1
334 end
335 forth
336 end
337 else
338 from
339 start
340 until
341 off
342 loop
343 if item_for_iteration = v then
344 Result := Result + 1
345 end
346 forth
347 end
348 end
349 iteration_position := old_iteration_position
350 end
351
352 feature -- Comparison
353
354 is_equal (other: like Current): BOOLEAN is
355 -- Does table contain the same information as `other'?
356 do
357 Result :=
358 equal (keys, other.keys) and
359 equal (content, other.content) and
360 equal (deleted_marks, other.deleted_marks) and
361 (has_default = other.has_default)
362 end
363
364 feature -- Status report
365
366 full: BOOLEAN is False
367 -- Is structure filled to capacity? (Answer: no.)
368
369 extendible: BOOLEAN is True
370 -- May new items be added? (Answer: yes.)
371
372 prunable: BOOLEAN is
373 -- May items be removed? (Answer: yes.)
374 do
375 Result := True
376 end
377
378 conflict: BOOLEAN is
379 -- Did last operation cause a conflict?
380 do
381 Result := (control = Conflict_constant)
382 end
383
384 inserted: BOOLEAN is
385 -- Did last operation insert an item?
386 do
387 Result := (control = Inserted_constant)
388 end
389
390 replaced: BOOLEAN is
391 -- Did last operation replace an item?
392 do
393 Result := (control = Replaced_constant)
394 end
395
396 removed: BOOLEAN is
397 -- Did last operation remove an item?
398 do
399 Result := (control = Removed_constant)
400 end
401
402 found: BOOLEAN is
403 -- Did last operation find the item sought?
404 do
405 Result := (control = Found_constant)
406 end
407
408 not_found: BOOLEAN is
409 -- Did last operation fail to find the item sought?
410 do
411 Result := (control = Not_found_constant)
412 end
413
414 after, off: BOOLEAN is
415 -- Is cursor past last item?
416 do
417 Result := is_off_position (iteration_position)
418 ensure
419 definition:
420 Result = ((not has_default and (iteration_position >= capacity)) or
421 (has_default and (iteration_position = (capacity + 1))))
422 end
423
424 valid_cursor (c: CURSOR): BOOLEAN is
425 -- Can cursor be moved to position `c'?
426 require
427 c_not_void: c /= Void
428 local
429 ht_cursor: HASH_TABLE_CURSOR
430 cursor_position: INTEGER
431 do
432 ht_cursor ?= c
433 if ht_cursor /= Void then
434 cursor_position := ht_cursor.position
435 Result :=
436 (is_off_position (cursor_position)) or else
437 ((cursor_position >= 0) and
438 (cursor_position <= capacity) and then
439 truly_occupied (cursor_position))
440 end
441 end
442
443 valid_key (k: H): BOOLEAN is
444 -- Is `k' a valid key?
445 -- (Answer: always yes for hash tables in this version)
446 do
447 Result := True
448 ensure then
449 Result
450 end
451
452 feature -- Cursor movement
453
454 start is
455 -- Bring cursor to first position.
456 do
457 iteration_position := -1
458 forth
459 end
460
461 forth is
462 -- Advance cursor to next occupied position,
463 -- or `off' if no such position remains.
464 require
465 not_off: not off
466 do
467 from
468 iteration_position := iteration_position + 1
469 until
470 off or else truly_occupied (iteration_position)
471 loop
472 iteration_position := iteration_position + 1
473 end
474 end
475
476 go_to (c: CURSOR) is
477 -- Move to position `c'.
478 require
479 c_not_void: c /= Void
480 valid_cursor: valid_cursor (c)
481 local
482 ht_cursor: HASH_TABLE_CURSOR
483 do
484 ht_cursor ?= c
485 if ht_cursor /= Void then
486 iteration_position := ht_cursor.position
487 end
488 end
489
490 search (key: H) is
491 -- Search for item of key `key'.
492 -- If found, set `found' to true, and set
493 -- `found_item' to item associated with `key'.
494 local
495 default_value: G
496 do
497 internal_search (key)
498 if found then
499 found_item := content.item (position)
500 else
501 found_item := default_value
502 end
503 ensure
504 found_or_not_found: found or not_found
505 item_if_found: found implies (found_item = content.item (position))
506 end
507
508 search_item: G is
509 obsolete
510 "Use found_item instead."
511 do
512 Result := found_item
513 end
514
515 feature -- Element change
516
517 put (new: G; key: H) is
518 -- Insert `new' with `key' if there is no other item
519 -- associated with the same key.
520 -- Set `inserted' if and only if an insertion has
521 -- been made (i.e. `key' was not present).
522 -- If so, set `position' to the insertion position.
523 -- If not, set `conflict'.
524 -- In either case, set `found_item' to the item
525 -- now associated with `key' (previous item if
526 -- there was one, `new' otherwise).
527 --
528 -- To choose between various insert/replace procedures,
529 -- see `instructions' in the Indexing clause.
530 do
531 internal_search (key)
532 if found then
533 set_conflict
534 found_item := content.item (position)
535 else
536 if soon_full then
537 add_space
538 internal_search (key)
539 check
540 not found
541 -- The key didn't magically insert itself.
542 end
543 end
544 if deleted_position /= Impossible_position then
545 position := deleted_position
546 set_not_deleted (position)
547 end
548 count := count + 1
549 used_slot_count := used_slot_count + 1
550 put_at_position (new, key)
551 found_item := new
552 set_inserted
553 end
554 ensure then
555 conflict_or_inserted: conflict or inserted
556 insertion_done: inserted implies item (key) = new
557 now_present: inserted implies has (key)
558 one_more_if_inserted: inserted implies (count = old count + 1)
559 one_more_slot_if_inserted_unless_reallocated:
560 inserted implies
561 ((used_slot_count = old used_slot_count + 1) or
562 (used_slot_count = count))
563 unchanged_if_conflict: conflict implies (count = old count)
564 same_item_if_conflict: conflict implies (item (key) = old (item (key)))
565 slot_count_unchanged_if_conflict:
566 conflict implies (used_slot_count = old used_slot_count)
567 found_item_associated_with_key: found_item = item (key)
568 new_item_if_inserted: inserted implies (found_item = new)
569 old_item_if_conflict: conflict implies (found_item = old (item (key)))
570 default_property:
571 has_default =
572 ((inserted and (key = computed_default_key)) or
573 ((conflict or (key /= computed_default_key))
574 and (old has_default)))
575 end
576
577 force (new: G; key: H) is
578 -- Update table so that `new' will be the item associated
579 -- with `key'.
580 -- If there was an item for that key, set `found'
581 -- and set `found_item' to that item.
582 -- If there was none, set `not_found' and set
583 -- `found_item' to the default value.
584 --
585 -- To choose between various insert/replace procedures,
586 -- see `instructions' in the Indexing clause.
587 require else
588 True
589 local
590 default_key: H
591 do
592 search (key)
593 if not_found then
594 if soon_full then
595 add_space
596 internal_search (key)
597 end
598 if deleted_position /= Impossible_position then
599 position := deleted_position
600 set_not_deleted (position)
601 end
602 keys.put (key, position)
603 if key = default_key then
604 set_default
605 end
606 count := count + 1
607 used_slot_count := used_slot_count + 1
608 end
609 content.put (new, position)
610 ensure then
611 insertion_done: item (key) = new
612 now_present: has (key)
613 found_or_not_found: found or not_found
614 not_found_if_was_not_present: not_found = not (old has (key))
615 same_count_or_one_more: (count = old count) or (count = old count + 1)
616 same_slot_count_or_one_more_unless_reallocated:
617 (used_slot_count = old used_slot_count) or
618 (used_slot_count = old used_slot_count + 1) or
619 (used_slot_count = count)
620 found_item_is_old_item: found implies (found_item = old (item (key)))
621 default_value_if_not_found:
622 not_found implies (found_item = computed_default_value)
623 -- The reverse is not true, as we can always insert
624 -- an item with the default value, for any key.
625
626 default_property:
627 has_default =
628 ((key = computed_default_key) or
629 ((key /= computed_default_key) and (old has_default)))
630 end
631
632 extend (new: G; key: H) is
633 -- Assuming there is no item of key `key',
634 -- insert `new' with `key'.
635 -- Set `inserted'.
636 --
637 -- To choose between various insert/replace procedures,
638 -- see `instructions' in the Indexing clause.
639 require
640 not_present: not has (key)
641 do
642 search_for_insertion (key)
643 if soon_full then
644 add_space
645 search_for_insertion (key)
646 end
647 if position < capacity and then deleted_marks.item (position) then
648 set_not_deleted (position)
649 else
650 used_slot_count := used_slot_count + 1
651 end
652 count := count + 1
653 put_at_position (new, key)
654 set_inserted
655 ensure
656 inserted: inserted
657 insertion_done: item (key) = new
658 one_more: count = old count + 1
659 same_slot_count_or_one_more_unless_reallocated:
660 (used_slot_count = old used_slot_count) or
661 (used_slot_count = old used_slot_count + 1) or
662 (used_slot_count = count)
663 default_property:
664 has_default =
665 ((key = computed_default_key) or (old has_default))
666 end
667
668 replace (new: G; key: H) is
669 -- Replace item at `key', if present,
670 -- with `new'; do not change associated key.
671 -- Set `replaced' if and only if a replacement has been made
672 -- (i.e. `key' was present); otherwise set `not_found'.
673 -- Set `found_item' to the item previously associated
674 -- with `key' (default value if there was none).
675 --
676 -- To choose between various insert/replace procedures,
677 -- see `instructions' in the Indexing clause.
678 do
679 search (key)
680 if found then
681 content.put (new, position)
682 set_replaced
683 end
684 ensure
685 replaced_or_not_found: replaced or not_found
686 insertion_done: replaced implies item (key) = new
687 no_change_if_not_found: not_found implies
688 item (key) = old (item (key))
689 found_item_is_old_item: found_item = old (item (key))
690 end
691
692 replace_key (new_key: H; old_key: H) is
693 -- If there is an item of key `old_key' and no item of key
694 -- `new_key', replace the former's key by `new_key',
695 -- set `replaced', and set `found_item' to the item
696 -- previously associated with `old_key'.
697 -- Otherwise set `not_found' or `conflict' respectively.
698 -- If `conflict', set `found_item' to the item previously
699 -- associated with `new_key'.
700 --
701 -- To choose between various insert/replace procedures,
702 -- see `instructions' in the Indexing clause.
703 local
704 insert_position: INTEGER
705 default_value: G
706 default_key: H
707 do
708 put (default_value, new_key)
709 if inserted then
710 count := count - 1
711 used_slot_count := used_slot_count - 1
712 insert_position := position
713 search (old_key)
714 if found then
715 content.put (found_item, insert_position)
716 if old_key = default_key then
717 set_no_default
718 else
719 remove_at_position
720 end
721 if new_key = default_key then
722 set_default
723 end
724 set_replaced
725 -- The call to `search' has set `found_item'
726 -- to the item previously associated with `old_key'.
727 else
728 position := insert_position
729 remove_at_position
730 check
731 not_found: not_found
732 end
733 end
734 -- else the call to `put' has set `found_item'
735 -- to the item previously associated with `new_key'.
736 end
737 ensure
738 same_count: count = old count
739 same_slot_count: used_slot_count = old used_slot_count
740 replaced_or_conflict_or_not_found: replaced or conflict or not_found
741 old_absent: (replaced and not equal (new_key, old_key))
742 implies (not has (old_key))
743 new_present: (replaced or conflict) = has (new_key)
744 new_item: replaced implies (item (new_key) = old (item (old_key)))
745 not_found_iff_no_old_key: not_found = old (not has (old_key))
746 conflict_iff_already_present: conflict = old (has (new_key))
747 not_inserted_if_conflict: conflict implies
748 (item (new_key) = old (item (new_key)))
749 default_property:
750 has_default =
751 ((new_key = computed_default_key) or
752 ((new_key /= computed_default_key) and (old has_default)))
753 end
754
755 merge (other: HASH_TABLE [G, H]) is
756 -- Merge `other' into Current. If `other' has some elements
757 -- with same key as in `Current', replace them by one from
758 -- `other'.
759 require
760 other_not_void: other /= Void
761 do
762 from
763 other.start
764 until
765 other.after
766 loop
767 force (other.item_for_iteration, other.key_for_iteration)
768 other.forth
769 end
770 ensure
771 inserted: other.current_keys.linear_representation.for_all (agent has)
772 end
773
774 feature -- Removal
775
776 remove (key: H) is
777 -- Remove item associated with `key', if present.
778 -- Set `removed' if and only if an item has been
779 -- removed (i.e. `key' was present);
780 -- if so, set `position' to index of removed element.
781 -- If not, set `not_found'.
782 -- Reset `found_item' to its default value if `removed'.
783 local
784 default_key: H
785 default_value: G
786 do
787 internal_search (key)
788 if found then
789 if key = default_key then
790 set_no_default
791 else
792 remove_at_position
793 end
794 count := count - 1
795 set_removed
796 found_item := default_value
797 end
798 ensure
799 removed_or_not_found: removed or not_found
800 not_present: not has (key)
801 one_less: found implies (count = old count - 1)
802 same_slot_count: used_slot_count = old used_slot_count
803 default_case:
804 (key = computed_default_key) implies (not has_default)
805 non_default_case:
806 (key /= computed_default_key) implies
807 (has_default = old has_default)
808 end
809
810 clear_all is
811 -- Reset all items to default values; reset status.
812 local
813 default_value: G
814 do
815 content.clear_all
816 keys.clear_all
817 deleted_marks.clear_all
818 found_item := default_value
819 count := 0
820 used_slot_count := 0
821 position := 0
822 iteration_position := capacity + 1
823 set_no_status
824 set_no_default
825 ensure then
826 position_equal_to_zero: position = 0
827 count_equal_to_zero: count = 0
828 used_slot_count_equal_to_zero: used_slot_count = 0
829 has_default_set: not has_default
830 no_status: not special_status
831 end
832
833 feature -- Conversion
834
835 linear_representation: ARRAYED_LIST [G] is
836 -- Representation as a linear structure
837 local
838 old_iteration_position: INTEGER
839 do
840 old_iteration_position := iteration_position
841 from
842 create Result.make (count)
843 start
844 until
845 off
846 loop
847 Result.extend (item_for_iteration)
848 forth
849 end
850 iteration_position := old_iteration_position
851 ensure then
852 Result_exists: Result /= Void
853 good_count: Result.count = count
854 end
855
856 feature -- Duplication
857
858 copy (other: like Current) is
859 -- Re-initialize from `other'.
860 do
861 standard_copy (other)
862 set_keys (other.keys.twin)
863 set_content (other.content.twin)
864 set_deleted_marks (other.deleted_marks.twin)
865 end
866
867 feature {NONE} -- Transformation
868
869 correct_mismatch is
870 -- Attempt to correct object mismatch during retrieve using `mismatch_information'.
871 local
872 array_content: ARRAY [G]
873 array_keys: ARRAY [H]
874 array_marks: ARRAY [BOOLEAN]
875 do
876 -- In version 5.1 and earlier, `content', `keys' and `deleted_marks'
877 -- where of base class ARRAY. In 5.2 we changed it to be a SPECIAL for
878 -- efficiency reasons. In order to retrieve an old HASH_TABLE we
879 -- need to convert those ARRAY instances into SPECIAL instances.
880
881 -- Convert `content' from ARRAY to SPECIAL
882 array_content ?= mismatch_information.item ("content")
883 if array_content /= Void then
884 content := array_content.area
885 end
886
887 -- Convert `keys' from ARRAY to SPECIAL
888 array_keys ?= mismatch_information.item ("keys")
889 if array_keys /= Void then
890 keys := array_keys.area
891 end
892
893 -- Convert `deleted_marks' from ARRAY to SPECIAL
894 array_marks ?= mismatch_information.item ("deleted_marks")
895 if array_marks /= Void then
896 deleted_marks := array_marks.area
897 end
898
899 if content = Void or keys = Void or deleted_marks = Void then
900 -- Could not retrieve old version of HASH_TABLE. We throw an exception.
901 Precursor {MISMATCH_CORRECTOR}
902 end
903 end
904
905 feature {HASH_TABLE} -- Implementation: content attributes and preservation
906
907 content: SPECIAL [G]
908 -- Array of contents
909
910 keys: SPECIAL [H]
911 -- Array of keys
912
913 deleted_marks: SPECIAL [BOOLEAN]
914 -- Is position that of a deleted element?
915
916 has_default: BOOLEAN
917 -- Is the default key present?
918
919 set_default is
920 -- Record information that there is a value for default key.
921 do
922 has_default := True
923 end
924
925 set_no_default is
926 -- Record information that there is no value for default key.
927 local
928 default_value: G
929 do
930 has_default := False
931 content.put (default_value, capacity)
932 end
933
934 feature {HASH_TABLE} -- Implementation: search attributes
935
936 iteration_position: INTEGER
937 -- Cursor for iteration primitives
938
939 position: INTEGER
940 -- Hash table cursor, updated after each operation:
941 -- put, remove, has, replace, force, change_key...
942
943 soon_full: BOOLEAN is
944 -- Is table close to being filled to current capacity?
945 -- (If so, resizing is needed to avoid performance degradation.)
946 do
947 Result := ((used_slot_count + 1) >= capacity * Max_occupation)
948 ensure
949 Result = ((used_slot_count + 1) >= capacity * Max_occupation)
950 end
951
952 control: INTEGER
953 -- Control code set by operations that may produce
954 -- several possible conditions.
955
956 deleted_position: INTEGER
957 -- Place where a deleted element was found during a search
958
959 feature {NONE} -- Implementation
960
961 Max_occupation: REAL is 0.9
962 -- Filling percentage over which table will be resized
963
964 Initial_occupation: REAL is 0.67
965 -- Filling percentage for initial requested occupation (2/3)
966
967 Impossible_position: INTEGER is - 1
968 -- Position outside the array indices
969
970 used_slot_count: INTEGER
971 -- Number of slots occuped by an element either present
972 -- or marked as deleted
973
974 occupied (i: INTEGER): BOOLEAN is
975 -- Is position `i' occupied by a non-default key and a value?
976 require
977 in_bounds: i >= 0 and i < capacity
978 local
979 default_key: H
980 do
981 Result := (keys.item (i) /= default_key)
982 end
983
984 truly_occupied (i: INTEGER): BOOLEAN is
985 -- Is position `i' occupied by a key and a value?
986 require
987 in_bounds: i >= 0 and i <= capacity
988 do
989 Result := (has_default and i = capacity) or else (i < capacity and then occupied (i))
990 ensure
991 normal_key: (i < capacity) implies (occupied (i) implies Result)
992 default_key: (i = capacity) implies (Result = has_default)
993 end
994
995 is_off_position (pos: INTEGER): BOOLEAN is
996 -- Is `pos' a cursor position past last item?
997 do
998 Result := (not has_default and (pos >= capacity)) or
999 (has_default and (pos = (capacity + 1)))
1000 ensure
1001 definition:
1002 Result = ((not has_default and (pos >= capacity)) or
1003 (has_default and (pos = (capacity + 1))))
1004 end
1005
1006 set_content (c: like content) is
1007 -- Assign `c' to `content'.
1008 do
1009 content := c
1010 end
1011
1012 deleted (i: INTEGER): BOOLEAN is
1013 -- Is position `i' that of a deleted item?
1014 require
1015 in_bounds: i >= 0 and i <= capacity
1016 do
1017 Result := deleted_marks.item (i)
1018 end
1019
1020 set_not_deleted (i: INTEGER) is
1021 -- Mark position `i' as not deleted.
1022 require
1023 in_bounds: i >= 0 and i <= capacity
1024 do
1025 deleted_marks.put (False, i)
1026 end
1027
1028 set_deleted (i: INTEGER) is
1029 -- Mark position `i' as deleted.
1030 require
1031 in_bounds: i >= 0 and i <= capacity
1032 do
1033 deleted_marks.put (True, i)
1034 ensure
1035 deleted: deleted (i)
1036 end
1037
1038 set_keys (c: like keys) is
1039 -- Assign `c' to `keys'.
1040 do
1041 keys := c
1042 end
1043
1044 set_deleted_marks (d: like deleted_marks) is
1045 -- Assign `d' to `deleted_marks'.
1046 do
1047 deleted_marks := d
1048 end
1049
1050 default_key_value: G is
1051 -- Value associated with the default key, if any
1052 require
1053 has_default: has_default
1054 do
1055 Result := content.item (capacity)
1056 end
1057
1058 computed_default_key: H is
1059 -- Default key
1060 -- (For performance reasons, used only in assertions;
1061 -- elsewhere, see use of local entity `default_key'.)
1062 do
1063 -- No instructions necessary (returns default value of type H)
1064 end
1065
1066 computed_default_value: G is
1067 -- Default value of type G
1068 -- (For performance reasons, used only in assertions;
1069 -- elsewhere, see use of local entity `default_value'.)
1070 do
1071 -- No instructions necessary (returns default value of type G)
1072 end
1073
1074 internal_search (key: H) is
1075 -- Search for item of key `key'.
1076 -- If successful, set `position' to index
1077 -- of item with this key (the same index as the key's index).
1078 -- If not, set `position' to possible position for insertion,
1079 -- and set status to `found' or `not_found'.
1080 local
1081 default_key: H
1082 hash_value, increment, l_pos, l_capacity: INTEGER
1083 first_deleted_position: INTEGER
1084 stop: BOOLEAN
1085 l_keys: like keys
1086 l_deleted_marks: like deleted_marks
1087 do
1088 first_deleted_position := Impossible_position
1089 if key = default_key then
1090 position := capacity
1091 if has_default then
1092 control := Found_constant
1093 else
1094 control := Not_found_constant
1095 end
1096 else
1097 from
1098 l_keys := keys
1099 l_deleted_marks := deleted_marks
1100 l_capacity := capacity
1101 hash_value := key.hash_code
1102 increment := 1 + hash_value \\ (l_capacity - 1)
1103 l_pos := (hash_value \\ l_capacity)
1104 until
1105 stop
1106 loop
1107 if l_deleted_marks.item (l_pos) then
1108 if first_deleted_position = Impossible_position then
1109 first_deleted_position := l_pos
1110 end
1111 -- Go to next increment.
1112 l_pos := (l_pos + increment) \\ l_capacity
1113 elseif l_keys.item (l_pos) = default_key then
1114 stop := True
1115 control := Not_found_constant
1116 elseif l_keys.item (l_pos).is_equal (key) then
1117 stop := True
1118 control := Found_constant
1119 else
1120 -- Go to next increment.
1121 l_pos := (l_pos + increment) \\ l_capacity
1122 end
1123 end
1124 position := l_pos
1125 end
1126 deleted_position := first_deleted_position
1127 ensure
1128 found_or_not_found: found or not_found
1129 deleted_item_at_deleted_position:
1130 (deleted_position /= Impossible_position) implies
1131 (deleted (deleted_position))
1132 default_value_if_not_found:
1133 not_found implies
1134 (content.item (position) = computed_default_value)
1135 default_iff_at_capacity:
1136 (position = capacity) = (key = computed_default_key)
1137 end
1138
1139 search_for_insertion (key: H) is
1140 -- Assuming there is no item of key `key', compute
1141 -- `position' at which to insert such an item.
1142 require
1143 not_present: not has (key)
1144 local
1145 default_key: H
1146 hash_value, increment, l_pos, l_capacity: INTEGER
1147 l_deleted_marks: like deleted_marks
1148 l_keys: like keys
1149 do
1150 if key = default_key then
1151 check
1152 not has_default
1153 -- Because of the precondition
1154 end
1155 position := capacity
1156 else
1157 from
1158 hash_value := key.hash_code
1159 l_capacity := capacity
1160 increment := 1 + hash_value \\ (l_capacity - 1)
1161 l_pos := (hash_value \\ l_capacity)
1162 l_deleted_marks := deleted_marks
1163 l_keys := keys
1164 until
1165 l_deleted_marks.item (l_pos) or l_keys.item (l_pos) = default_key
1166 loop
1167 l_pos := (l_pos + increment) \\ l_capacity
1168 end
1169 position := l_pos
1170 end
1171 ensure
1172 deleted_or_default:
1173 deleted (position) or (key_at (position) = computed_default_key)
1174 default_iff_at_capacity:
1175 (position = capacity) = (key = computed_default_key)
1176 end
1177
1178 put_at_position (new: G; key: H) is
1179 -- Put `new' with `key' at `position'.
1180 require
1181 in_bounds: position >= 0 and position <= capacity
1182 default_if_at_capacity:
1183 (position = capacity) implies (key = computed_default_key)
1184 local
1185 default_key: H
1186 l_pos: INTEGER
1187 do
1188 l_pos := position
1189 content.put (new, l_pos)
1190 keys.put (key, l_pos)
1191 if key = default_key then
1192 set_default
1193 end
1194 ensure
1195 item_at_position: content.item (position) = new
1196 key_at_position: key_at (position) = key
1197 default_if_at_capacity:
1198 (position = capacity) implies has_default
1199 end
1200
1201 remove_at_position is
1202 -- Remove item at `position'
1203 require
1204 in_bounds: position >= 0 and position <= capacity
1205 local
1206 default_value: G
1207 default_key: H
1208 l_pos: INTEGER
1209 do
1210 l_pos := position
1211 content.put (default_value, l_pos)
1212 keys.put (default_key, l_pos)
1213 set_deleted (l_pos)
1214 if iteration_position = l_pos then
1215 forth
1216 end
1217 ensure
1218 deleted: deleted (position)
1219 status_not_changed: control = old control
1220 count_not_changed: count = old count
1221 slot_count_not_changed: used_slot_count = old used_slot_count
1222 key_at (position) = computed_default_key
1223 end
1224
1225 key_at (n: INTEGER): H is
1226 -- Key at position `n'
1227 require
1228 in_bounds: n >= 0 and n < capacity
1229 do
1230 Result := keys.item (n)
1231 end
1232
1233 initial_position (hash_value: INTEGER): INTEGER is
1234 -- Initial position for an item of hash code `hash_value'
1235 do
1236 Result := (hash_value \\ capacity)
1237 end
1238
1239 position_increment (hash_value: INTEGER): INTEGER is
1240 -- Distance between successive positions for hash code
1241 -- `hash_value' (computed for no cycle: `capacity' is prime)
1242 do
1243 Result := 1 + hash_value \\ (capacity - 1)
1244 end
1245
1246 to_next_candidate (increment: INTEGER) is
1247 -- Move from current `position' to next for same key
1248 do
1249 position := (position + increment) \\ capacity
1250 end
1251
1252 Conflict_constant: INTEGER is 1
1253 -- Could not insert an already existing key
1254
1255 set_conflict is
1256 -- Set status to conflict.
1257 do
1258 control := Conflict_constant
1259 ensure
1260 conflict: conflict
1261 end
1262
1263 Found_constant: INTEGER is 2
1264 -- Key found
1265
1266 set_found is
1267 -- Set status to found.
1268 do
1269 control := Found_constant
1270 ensure
1271 found: found
1272 end
1273
1274 Inserted_constant: INTEGER is 3
1275 -- Insertion successful
1276
1277 set_inserted is
1278 -- Set status to inserted.
1279 do
1280 control := Inserted_constant
1281 ensure
1282 inserted: inserted
1283 end
1284
1285 Not_found_constant: INTEGER is 4
1286 -- Key not found
1287
1288 set_not_found is
1289 -- Set status to not found.
1290 do
1291 control := Not_found_constant
1292 ensure
1293 not_found: not_found
1294 end
1295
1296 set_no_status is
1297 -- Set status to normal.
1298 do
1299 control := 0
1300 ensure
1301 default_status: not special_status
1302 end
1303
1304 Removed_constant: INTEGER is 5
1305 -- Remove successful
1306
1307 set_removed is
1308 -- Set status to removed.
1309 do
1310 control := Removed_constant
1311 ensure
1312 removed: removed
1313 end
1314
1315 Replaced_constant: INTEGER is 6
1316 -- Replaced value
1317
1318 set_replaced is
1319 -- Set status to replaced.
1320 do
1321 control := Replaced_constant
1322 ensure
1323 replaced: replaced
1324 end
1325
1326 special_status: BOOLEAN is
1327 -- Has status been set to some non-default value?
1328 do
1329 Result := (control > 0)
1330 ensure
1331 Result = (control > 0)
1332 end
1333
1334 add_space is
1335 -- Increase capacity.
1336 do
1337 -- Be pessimistic: plan for more growth by allocating 1.5 more than before
1338 accommodate (count + count // 2)
1339 ensure
1340 count_not_changed: count = old count
1341 slot_count_same_as_count: used_slot_count = count
1342 breathing_space: count < capacity * Initial_occupation
1343 end
1344
1345 Minimum_capacity: INTEGER is 5
1346
1347 feature {NONE} -- Inapplicable
1348
1349 prune (v: G) is
1350 -- Remove one occurrence of `v' if any.
1351 do
1352 end
1353
1354 collection_extend (v: G) is
1355 -- Insert a new occurrence of `v'.
1356 do
1357 end
1358
1359 invariant
1360
1361 keys_not_void: keys /= Void
1362 content_not_void: content /= Void
1363 deleted_marks_not_void: deleted_marks /= Void
1364 keys_same_capacity_plus_one: keys.count = capacity + 1
1365 content_same_capacity_plus_one: content.count = capacity + 1
1366 deleted_same_capacity: deleted_marks.count = capacity + 1
1367 valid_iteration_position: off or truly_occupied (iteration_position)
1368 control_non_negative: control >= 0
1369 special_status: special_status =
1370 (conflict or inserted or replaced or removed or found or not_found)
1371
1372 max_occupation_meaningful: (Max_occupation > 0) and (Max_occupation < 1)
1373 initial_occupation_meaningful: (Initial_occupation > 0) and (Initial_occupation < 1)
1374 sized_generously_enough: Initial_occupation < Max_occupation
1375 count_big_enough: 0 <= count
1376 count_small_enough: count <= capacity
1377 breathing_space: count <= capacity * Max_occupation
1378 count_no_more_than_slot_count: count <= used_slot_count
1379 slot_count_big_enough: 0 <= count
1380 slot_count_small_enough: used_slot_count <= capacity
1381
1382 indexing
1383
1384 library: "[
1385 EiffelBase: Library of reusable components for Eiffel.
1386 ]"
1387
1388 status: "[
1389 Copyright 1986-2001 Interactive Software Engineering (ISE).
1390 For ISE customers the original versions are an ISE product
1391 covered by the ISE Eiffel license and support agreements.
1392 ]"
1393
1394 license: "[
1395 EiffelBase may now be used by anyone as FREE SOFTWARE to
1396 develop any product, public-domain or commercial, without
1397 payment to ISE, under the terms of the ISE Free Eiffel Library
1398 License (IFELL) at http://eiffel.com/products/base/license.html.
1399 ]"
1400
1401 source: "[
1402 Interactive Software Engineering Inc.
1403 ISE Building
1404 360 Storke Road, Goleta, CA 93117 USA
1405 Telephone 805-685-1006, Fax 805-685-6869
1406 Electronic mail <info@eiffel.com>
1407 Customer support http://support.eiffel.com
1408 ]"
1409
1410 info: "[
1411 For latest info see award-winning pages: http://eiffel.com
1412 ]"
1413
1414 end -- class HASH_TABLE
1415
1416

Properties

Name Value
svn:eol-style native
svn:keywords Author Date Id Revision

  ViewVC Help
Powered by ViewVC 1.1.23