hash - hash support

include "hash.m";
hash := load Hash Hash->PATH;

Hash: module{
	PATH: con "/dis/lib/hash.dis";
	fun1, fun2: fn(s:string,n:int):int;

	HashVal: adt{
		i: int;
		r: real;
		s: string;
	};

	HashNode: adt{
		key:string;
		val:ref HashVal;  # insert() can update contents
	};

	HashTable: adt{
		a:	array of list of HashNode;
		find:	fn(h:self ref HashTable, key:string):ref 
HashVal;
		insert:	fn(h:self ref HashTable, key:string, 
val:HashVal);
		delete:	fn(h:self ref HashTable, key:string);
		all:	fn(h:self ref HashTable): list of HashNode;
	};
	new: fn(size:int):ref HashTable;
};

Description

The hash module provides support for arrays that are indexed by keys of type string. The values may be any combination of int, real, or string.

new

new: fn(size:int):ref HashTable;

## returns HashTable adt.

The new function creates and returns a new HashTable with size nodes.

HashVal adt

The HashVal adt contains the data values of the hash.

HashNode adt

The HashNode adt contains the key/value pairs for each element (node) of the hash.

HashTable adt

The HashTable adt contains a single data member (an array of list of the hash nodes) and functions to manipulate the hash table. The HashTable functions are described below.

h.insert

insert: fn(h:self ref HashTable, key:string, val:HashVal);

The insert function inserts a node into the hash table h with a key of key and a value of val. This function can also be used to update the contents of an existing node.

h.find

find: fn(h:self ref HashTable, key:string):ref HashVal;

## returns HashVal adt or nil if not found.

The find function searches the hash table h for the node with a key of key. If such a node is found, the return is a reference to the appropriate HashVal adt. If the node is not found, the return is nil.

h.delete

delete: fn(h:self ref HashTable, key:string);

The delete function deletes the node from h with a key of key.

h.all

all: fn(h:self ref HashTable): list of HashNode;

## returns list of all nodes.

The all function returns a list of all the nodes in the hash table h.

fun1, fun2

fun1, fun2: fn(s:string,n:int):int;

The functions fun1 and fun2 are used internally by the member functions of the HashTable adt to compute the hash numbers.

Example

The following example demonstrates creating and accessing a hash table:

implement Hashtest;
include "sys.m";
    sys: Sys;
include "draw.m";
include "hash.m";
    hash: Hash;
    HashVal,
    HashNode,
    HashTable : import hash;
Hashtest: module
{
    init: fn(ctxt: ref Draw->Context, argv: list of 
string);
};

init(ctxt: ref Draw->Context, argv: list of string)
{
    sys = load Sys Sys->PATH;
    hash = load Hash Hash->PATH;
    myval : HashVal;
# create a new hash table
    myhash := hash->new(5);
# insert nodes
    myval.i = 2;
    myval.r = 3.45;
    myval.s = "test";
    myhash.insert("another", myval);
    
    myhash.insert("foo", (1, 2.0, "bar"));
    
# note that myval.i, myval.r maintain previous assignments
    myval.s = "did it";
    myhash.insert("The tractor", myval);
    
# print value for a key
    stringvalprint("foo", myhash);
    stringvalprint("The tractor", myhash);
# change a node
    myval.s = "didn't do it";
    myhash.insert("The tractor", myval);
# get all the nodes
    allnodes := myhash.all();
# print all the key/value pairs
    node : HashNode;
    while( allnodes != nil ) {
        node = hd allnodes;
        nodeprint(node.key, node.val);
        allnodes = tl allnodes;
    }
}
stringvalprint(key: string, myhash: ref hash->HashTable)
{
    sys->print("%s %s\n", key, myhash.find(key).s);
    return;
}

nodeprint(key: string, val: ref HashVal)
{
    spacer := "";
    nspaces := 15 - len key;
    for( i := 1 ; i < nspaces ; i++ ) {
        spacer = spacer + " ";
    }
    sys->print("%s%s=>  ( %d, %.2f, %s)\n", key, spacer, 
val.i, val.r, val.s);
}

[Top] [Prev] [Next] [Bottom]

infernosupport@lucent.com