4 HashTable Example

ORIGIN '~beta/containers/hashTable';
-- program: Descriptor --
(* This demo program illustrates the usage of the hashTable and
 * extensibleHashTable patterns.  The first part of the demo
 * illustrates inserting and deleting elements from the hashtables,
 * the middle part illustrates the diff and sect operations, and the
 * last part of this program illustrates the possibilities for
 * specifying extend the hashTable dynamically (illustrated by the
 * hashTable4 object).  The use of the statistics operations are also
 * illustrated here.
 * 
 * At the end of this file, a copy of the output of this program is
 * given
 *)
  (#
     intHashTable: hashTable (* a hashTable containing integerObjects *)
       (# element::< integerObject; hashFunction::<  (#  do e->value #); 
       #);
     intEHashTable: extensibleHashTable
     (* a hashTable containing integerObjects *)
       (# element::< integerObject; hashFunction::<  (#  do e->value #); 
       #);
     hashtable1: @intHashTable
       (# rangeInitial::<  (#  do 2->value #) #);
     hashtable2: @intHashTable
       (# rangeInitial::<  (#  do 4->value #) #);
     hashtable3: @intHashTable;
     hashtable4: @intEHashTable
       (# rangeInitial::<  (#  do 2->value #) #);
     i: [10] ^integerObject;
     
  do (* initializing the integerObjects *)
     (for int: 10 repeat
       &integerObject[]->i[int][]; int->i[int]
     for);
     (* initializing hashTable1 and putting some integerObjects into it. *)
     hashtable1.init;
     'hashtable1.capacity: '->puttext;
     hashtable1.capacity->putInt;
     newline;
     'hashtable1.range: '->puttext;
     hashtable1.range->putInt;
     newline;
     (for int: 4 repeat i[int][]->hashtable1.insert for);
     'hashtable1.elements: '->puttext;
     hashtable1.scan
       (#  do current->putint; ','->put #);
     newline;
     'hashtable1.size: '->puttext;
     hashtable1.size->putInt;
     newline;
     newline;
     (* initializing hashTable2 and putting some integerObjects into it. *)
     hashtable2.init;
     'hashtable2.capacity: '->puttext;
     hashtable2.capacity->putInt;
     newline;
     'hashtable2.range: '->puttext;
     hashtable2.range->putInt;
     newline;
     (for int: 4 repeat i[int+3][]->hashtable2.insert for);
     'hashtable2.elements: '->puttext;
     hashtable2.scan
       (#  do current->putint; ','->put #);
     newline;
     'hashtable2.size: '->puttext;
     hashtable2.size->putInt;
     newline;
     newline;
     (* initializing hashTable3 and putting some integerObjects into it. *)
     hashtable3.init;
     (for int: 4 repeat i[int+6][]->hashtable3.insert for);
     'hashtable3.elements: '->puttext;
     hashtable3.scan
       (#  do current->putint; ','->put #);
     newline;
     newline;
     (* deleting integerObject 3 from hashTable3 *)
     '3->hashtable3.delete: '->puttext;
     i[3][]->hashtable3.delete;
     hashtable3.scan
       (#  do current->putint; ','->put #);
     newline;
     newline;
     (* illustrating the diff, and sect operations on hashTables *)
     'hashtable2->hashtable3; hashtable1[]->hashtable3.diff: '->puttext;
     hashtable2->hashtable3;
     hashtable1[]->hashtable3.diff;
     hashtable3.scan
       (#  do current->putint; ','->put #);
     newline;
     'hashtable2->hashtable3; hashtable1[]->hashtable3.sect: '->puttext;
     hashtable2->hashtable3;
     hashtable1[]->hashtable3.sect;
     hashtable3.scan
       (#  do current->putint; ','->put #);
     newline;
     (* Illustrating the use of extensibleHashTable: 
      * Initializing hashTable4 and putting some integerObjects into it.
      *)
     hashtable4.init;
     'hashtable4.capacity: '->puttext;
     hashtable4.capacity->putInt;
     newline;
     'hashtable4.range: '->puttext;
     hashtable4.range->putInt;
     newline;
     (for int: 4 repeat i[int+3][]->hashtable4.insert for);
     'hashtable4.elements: '->puttext;
     hashtable4.scan
       (#  do current->putint; ','->put #);
     newline;
     'hashtable4.size: '->putText;
     hashtable4.size->putInt;
     newline;
     (* illustrating extending an expensibleHashTable *)
     'hashtable4.statistics(# do screen[]->print #): '->putline;
     hashtable4.statistics
       (#  do screen[]->print #);
     (for int: hashTable4.range repeat
       int->putint;
       '->hashtable4.scanIndexed(# ... #): '->puttext;
       i[int][]->hashTable4.hashFunction
         ->hashtable4.scanIndexed (#  do current->putint; ' '->put #);
       'found'->putline;
       
     for);
     '3->hashTable4.extend(# do hashTable4.rehash #)'->putline;
     3->hashTable4.extend (#  do hashTable4.rehash #);
     (for int: 10 repeat
       int->putint;
       '->hashtable4.has: '->puttext;
       (if i[int][]->hashtable4.has
        // true then 'yes'->putline
        else
           'no'->putline
       if);
       
     for);
     (for int: hashTable4.range repeat
       int->putint;
       '->hashtable4.scanIndexed(# ... #): '->puttext;
       i[int][]->hashTable4.hashFunction
         ->hashtable4.scanIndexed
           (# end::<  (#  do 'found'->putline #)
           do current->putint; ' '->put
           #);
       
     for);
     'hashtable4.range: '->puttext;
     hashtable4.range->putInt;
     newline;
     'hashtable4.elements: '->puttext;
     hashtable4.scan
       (#  do current->putint; ','->put #);
     newline;
     'hashtable4.size: '->putText;
     hashtable4.size->putInt;
     newline;
     'hashtable4.statistics(# do screen[]->print #): '->putline;
     hashtable4.statistics
       (#  do screen[]->print #);
     (************ OUTPUT ***************
      * hashtable1.capacity: -1
      * hashtable1.range: 2
      * hashtable1.elements: 3,1,4,2,
      * hashtable1.size: 4
      * 
      * hashtable2.capacity: -1
      * hashtable2.range: 4
      * hashtable2.elements: 5,6,7,4,
      * hashtable2.size: 4
      * 
      * hashtable3.elements: 7,8,9,10,
      * 
      * 3->hashtable3.delete: 7,8,9,10,
      * 
      * hashtable2->hashtable3; hashtable1[]->hashtable3.diff: 5,6,7,
      * hashtable2->hashtable3; hashtable1[]->hashtable3.sect: 4,
      * hashtable4.capacity: -1
      * hashtable4.range: 2
      * hashtable4.elements: 7,5,6,4,
      * hashtable4.size: 4
      * hashtable4.statistics(# do screen[]->print #):
      * Histogram: (2,2)
      * Maximum Collisions: 2
      * Minimum Collisions: 2
      * Average Collisions: 2
      * 1->hashtable4.scanIndexed(# ... #): 7 5 found
      * 2->hashtable4.scanIndexed(# ... #): 6 4 found
      * 3->hashTable4.extend(# do hashTable4.rehash #)
      * 1->hashtable4.has: no
      * 2->hashtable4.has: no
      * 3->hashtable4.has: no
      * 4->hashtable4.has: yes
      * 5->hashtable4.has: yes
      * 6->hashtable4.has: yes
      * 7->hashtable4.has: yes
      * 8->hashtable4.has: no
      * 9->hashtable4.has: no
      * 10->hashtable4.has: no
      * 1->hashtable4.scanIndexed(# ... #): 6 found
      * 2->hashtable4.scanIndexed(# ... #): 7 found
      * 3->hashtable4.scanIndexed(# ... #): found
      * 4->hashtable4.scanIndexed(# ... #): 4 found
      * 5->hashtable4.scanIndexed(# ... #): 5 found
      * hashtable4.range: 5
      * hashtable4.elements: 6,7,4,5,
      * hashtable4.size: 4
      * hashtable4.statistics(# do screen[]->print #):
      * Histogram: (1,1,0,1,1)
      * Maximum Collisions: 1
      * Minimum Collisions: 0
      * Average Collisions: 1
      *********************************)
     
  #)


Container Libraries - Reference Manual
© 1992-2002 Mjølner Informatics
[Modified: Thursday October 19th 2000 at 12:51]