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
*********************************)
#) |