% ==================================================== % HashTable: a kind of SET for Settools/Containers % % J.Vaucher (may 1995) % % - On creation, the parameter Hsize gives an % initial size of the hashtable (0 defaults % to 7). % - This is increased automatically by 40% % whenever utilisation rises to 100% % - If automatic resizing is unwanted give a % negative value to Hsize % - The hash function was adapted from the one we % in the SIMDBM DataBase package. It does a % reasonable job even with KEY with blanks like % " 0" to " 1000". % =================================================== EXTERNAL CLASS structures; % external class containers; Set CLASS HashTable(HSIZE); Integer HSIZE; Virtual: procedure hashKey is text procedure hashKey(E); ref(element) E; ; procedure hash is integer procedure hash(T); text T; ; BEGIN % ----------------------------------------------- % ++++ internal classes +++ % ----------------------------------------------- CLASS CellArray(Limit); integer Limit; begin ref(ListCell) array List(1:Limit); end; CLASS ListCell( EL, Next); ref(element) EL; ref(ListCell) Next;; % ----------------------------------------------- % Default virtuals % ----------------------------------------------- text procedure hashKey (el); ref(element) el; hashKey :- el.key; integer procedure hash(t); text t; begin integer N, K; K := abs( minint // 16); t.Setpos(1); while t.More do begin N := 11*N + Rank(t.Getchar); IF N > K THEN N := rem( N, K); end; hash := randint(1, Hsize, N); end of HASH; % ----------------------------------------------- % Local variables % ----------------------------------------------- ref (CellArray) Htable; boolean Flexible; ! if we must adjust size of table automatically ; integer Nentries; ref(Set) procedure ADD_ELEMENT(el); ref(element) el; begin integer index; ref(ListCell) p; text Key; Key :- hashKey(EL); index := hash(Key); P :- HTable.List(index); while P =/= none and then hashKey(P.el) <> Key do P :- P.next; if P == none then begin HTable.List(index) :- new ListCell(EL,HTable.List(index)); Nentries := Nentries + 1; if Nentries > Hsize and Flexible then Resize; end else P.EL :- el; add_element :- this set; end; ref(element) procedure FIND_ELEMENT(key); text key; begin ref(ListCell) p; p :- HTable.List(hash(key)); while P =/= none and then hashKey(P.el) <> Key do P :- P.next; if p =/= none then find_element :- p.EL; end; ref(element) procedure FIND_OR_ADD(key,newElement); text key; #ifdef CIM procedure newElement is ref (element) procedure newElement;; #else ref (element) procedure newElement; #endif begin ref(ListCell) p; integer index; ref(element) EL; index := hash(key); p :- HTable.List(index); while P =/= none and then hashKey(P.el) <> Key do P :- P.next; if P == none then begin find_or_add :- EL :- newElement; HTable.List(index) :- new ListCell(EL,HTable.List(index)); Nentries := Nentries + 1; if Nentries > Hsize and Flexible then Resize; end else find_or_add :- p.EL; end; ref(element) procedure REMOVE_ELEMENT(key); text key; begin ref(ListCell) p,p2; integer i; i := hash(key); p :- HTable.List(i); while P =/= none and then hashKey(P.el) <> Key do begin P2 :- P; P :- P.next; end; if p =/= none then begin remove_element :- p.El; if P2 == none then HTable.List(i) :- P.next else P2.next :- P.next; Nentries := Nentries - 1; end; end; ref(Container) procedure FOR_EACH_ELEMENT(proc); #ifdef CIM procedure proc is procedure proc(el); ref(element) el;; #else procedure proc; #endif begin ref(ListCell) p,pp; integer i; for i := 1 step 1 until Hsize do begin p :- HTable.List(i); while P =/= none do begin pp :- P.next; proc(P.el); P :- pp; end; end; for_each_element :- this Container; end; Boolean procedure IS_EMPTY; is_empty := Nentries = 0 ; integer procedure SIZE; size := Nentries ; ref(Container) procedure MAKE_EMPTY; begin Hsize := 5; Htable :- new CellArray(Hsize); Nentries := 0; make_empty :- this Container; end; ref(element) procedure ELEMENT_NUMBER(elnr); integer elnr; if elnr > 0 then begin end; % ------------------------------------------------- % Resizing flexible tables % % - a table is resized if the occupation > 100 % % ------------------------------------------------- procedure Resize; begin ref(CellArray) HT; integer Size, OldSize; OldSize := Hsize; Hsize := 1.4 * Hsize; HT :- new CellArray(Hsize); begin ref(ListCell) p,pp; integer i, i2; for i := 1 step 1 until OldSize do begin p :- HTable.List(i); while P =/= none do begin pp :- P.next; i2 := hash(hashKey(P.el)); P.next :- HT.List(i2); HT.List(i2) :- P; P :- pp; end; end; end; HTable :- HT; end; procedure dist; begin integer i,j; ref(ListCell) p; outimage; for i := 1 step 1 until HSIZE do begin outint(i,5); outtext(": "); p :- HTable.List(i); while P =/= none do begin outchar('*'); P :- P.next end; outimage; end; end; % ------------------------------------------------- % Initialisation % ------------------------------------------------- Flexible := Hsize >= 0; if Hsize = 0 then Hsize := 5; Htable :- new CellArray(abs(Hsize)); END ------------- TableDeHachage ------------ ;