/[eiffelstudio]/trunk/eweasel/tests/incr071/hash_table.e
ViewVC logotype

Contents of /trunk/eweasel/tests/incr071/hash_table.e

Parent Directory Parent Directory | Revision Log Revision Log


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

Properties

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

  ViewVC Help
Powered by ViewVC 1.1.23