[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

splaytree.b



This is a multi-part message in MIME format.

--------------620924187DB
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

On the off chance that anyone needs a splay tree in Limbo.
Otherwise, can be stripped down to something more useful, like a
bst with lazy deletion :)

Steve

--------------620924187DB
Content-Type: text/plain; charset=us-ascii; name="splaytree.b"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline; filename="splaytree.b"

#Limbo port of Sleator's top-down.splay.c. 
#"Self-adjusting Binary Search Trees", Sleator & Tarjan, JACM v32 #3,
#July '85.

#Array representation of tree replaces malloc'd nodes.
#Free node slots are kept on a freelist.
#Array of nodes grows by power of 2 when free slots are exhausted. 
#Slot 0 represents the empty tree.
#Slot 0 is also used in splay() as a local node that can be attached to the
#tree temporarily.
#Original returns pointer to new root from tree reshaping functions;  tree.root
#tracks that here, see side effect notes in functions.
#Test driver is fancier and gives approximate timings for tree ops.
#Lack of understanding of reference copying in Limbo made me include
#functions in the adt to enable self ref; some really should be private to
#an implementation module.

implement Tree;

include "sys.m";
	sys: Sys;
include "draw.m";
	Context: import Draw;
include "lib.m";

Nul: con 0;

node: adt {
	key: string;
	left: int;
	right: int;			#if node is inactive, points to next on freelist 
};
	
tree: adt {
	sz: int;			#nodes in tree + nodes on freelist + 1 for dummy
	root: int;			#pointer: 0 iff tree is empty
	n: array of node;	#initial size is 2
	freelist: int;			
	
	init: fn() : ref tree;
	alloc: fn(tr: self ref tree) : int;
	free: fn(tr: self ref tree, item: int);
	splay: fn(tr: self ref tree, key: string);
	insert: fn(tr: self ref tree, key: string);
	delete: fn(tr: self ref tree, key: string);	
	inorder: fn(tr: self ref tree, root: int);   
	find: fn(tr: self ref tree, key: string) : int;
};

tree.init() : ref tree
{
	nodes := array[2] of {node("",Nul,Nul), node("",Nul,Nul)}; 
	return ref tree(2, 0, nodes, 1); #size, root, nodes, freelist start
}

tree.alloc(tr: self ref tree) : int
{
	if(tr.freelist == Nul){		#grow 
		sz := tr.sz * 2;			
		n :=  array[sz] of node;
		for(j := 0; j < tr.sz; j++)
			n[j] = tr.n[j];     #copy 
		for(j = tr.sz; j < sz - 1; j++)
			n[j] = node("", Nul, j + 1);
		n[j] = ("",Nul, Nul);	#end of free list
		tr.freelist = tr.sz;
		tr.sz = sz;
		tr.n = n;
	}
	new := tr.freelist;
	tr.freelist = tr.n[new].right;
	tr.n[new].right = Nul;
	return new;
}

tree.free(tr: self ref tree, item: int)
{
	tr.n[item] = node("", Nul, tr.freelist);
	tr.freelist = item;
}


tree.splay(tr: self ref tree, key: string)
{ 
	l, r, y: int;	
	tr.n[0].left = tr.n[0].right = Nul;	#trick to attach local var to tree
	l = r = 0;
	
	if(tr.root == Nul)
		return;		 
	t := tr.root;

	for(;;) {
		if(key < tr.n[t].key){
			y = tr.n[t].left;
			if(y == Nul)
				break;
			if(key < tr.n[y].key){
				tr.n[t].left = tr.n[y].right;
				tr.n[y].right = t;
				t = y;
				if(tr.n[t].left == Nul)
					break;
			}
			tr.n[r].left = t;				
			r = t;
			t = tr.n[t].left;
		}else if(key > tr.n[t].key){
			y = tr.n[t].right;
			if(y == Nul)
				break;
			if(key > tr.n[y].key){
				tr.n[t].right = tr.n[y].left;
				tr.n[y].left = t;
				t = y;
				if(tr.n[t].right == Nul)
					break;
			}
			tr.n[l].right = t;				    
			l = t;
			t = tr.n[t].right;
		}else
			break;
	}
	tr.n[l].right = tr.n[t].left;			
	tr.n[r].left = tr.n[t].right;
	tr.n[t].left = tr.n[0].right;
	tr.n[t].right = tr.n[0].left;
	tr.root = t;	
}

tree.insert(tr: self ref tree, key: string)
{
	new := tr.alloc();
	
	tr.n[new].key = key;

	if(tr.root == Nul){
		tr.root = new;							
		return;
	}
	tr.splay(key);

	t := tr.root;
	if(key < tr.n[t].key){
		tr.n[new].left = tr.n[t].left;
		tr.n[new].right = t;
		tr.n[t].left = Nul;
		tr.root = new;
	}else if (key > tr.n[t].key){
		tr.n[new].right = tr.n[t].right;
		tr.n[new].left = t;
		tr.n[t].right = Nul;
		tr.root = new;
	}else
		tr.free(new);
}

tree.find(tr: self ref tree, key: string) : int
{
	if(tr.root == Nul)
		return 0;
	tr.splay(key);
	if(tr.n[tr.root].key == key)
		return 1;
	return 0;
}

tree.delete(tr: self ref tree, key: string)
{	
	if(tr.root == Nul)
		return; #tree empty
		
	tr.splay(key);
	t := tr.root;
	if(key != tr.n[t].key)
		return; #not found
	
	if(tr.n[t].left == Nul){
		tr.root = tr.n[t].right;
	}else {
		#tricky: set tr.root to splay the left subtree of tr.root.
		tr.root = tr.n[t].left;
		tr.splay(key);
		#tr.root was changed as side effect of splay()
		tr.n[tr.root].right = tr.n[t].right;			
	}
	tr.free(t);
}


tree.inorder(t: self ref tree, root: int)
{
	if(root == Nul)
		return;
	t.inorder(t.n[root].left);
	sys->print("%s\n", t.n[root].key); #e.g.
	t.inorder(t.n[root].right);
}

#-------------------------------------------------------------------------
#test driver w/approximate timings
#read in up to STRCNT (default 500) strings from stdin
#build a tree, shuffle the strings, search the tree, delete all, 4 times
#-------------------------------------------------------------------------

include "bufio.m";
bufmod: Bufio;
Iobuf: import bufmod;
STRCNT: con 500;	

Tree: module
{
	init: fn(ctxt: ref Context, argv: list of string);
};

ms: int;
starttimer()
{
	ms = sys->millisec();
}

etime() : int
{
	nms := sys->millisec();
	dt := nms - ms;
	ms = nms;
	return dt;
}

init(ctxt: ref Context, argv: list of string)
{
	sys = load Sys Sys->PATH;
	bufmod = load Bufio Bufio->PATH;
	rand := load Rand Rand->PATH;
	iob: ref Iobuf;		
	t: ref tree;

	str := array[STRCNT] of string;
	t = tree.init();

	iob = bufmod->fopen(sys->fildes(0), bufmod->OREAD);
	if(iob == nil){
		sys->fprint(sys->fildes(2), "Fatal: open 0\n");
		exit;
	}

	sys->print("Reading ... ");
	j := 0;
	while(j < STRCNT){
		s := iob.gets('\n');
		if(s == nil)
			break;
		str[j++] = s;
	}
	sys->print("%d strings\n", j);
	
	starttimer();  
	rand->init(0);

	for(i := 0; i < 4; i++){
		sys->print("ITERATION: %d\nBuilding tree ...", i + 1);
		for(k := 0; k < j; k++)
			t.insert(str[k]); 
		sys->print("%d ms.\nSearching ...", etime());
		for(k = 0; k < j; k++)
			if(t.find(str[k]) == 0){
				sys->print("Oops\n");
				exit;
			}
		sys->print("%d ms.\nShuffling ...", etime());
		for(k = 0; k < j; k++){
			r := rand->rand(j);
			s := str[k];
			str[k] = str[r];
			str[r] = s;
		}	
		sys->print("%d ms.\nDeleting ...", etime());	
		for(k = 0; k < j; k++)
			t.delete(str[k]);
		sys->print("%d ms.\nTree empty? ...", etime());
		for(k = 0; k < j; k++)
			if(t.find(str[k]) == 1){
				sys->print("Oops\n");
				exit;
		}
		sys->print("%d ms. OK\n", etime());
	}
	
	sys->print("-----\nt.root = %d\n", t.root);
	if(t.root != Nul)
		sys->print("\tBad value\n");
	sys->print("t.sz = %d\n", t.sz);
	freecnt := 0;
	i = t.freelist;
	while(i != Nul){
		freecnt++;
		if(t.n[i].left != Nul){
			sys->print("Bad value on free list at offset %d\n", i);
			exit;
		}
		i = t.n[i].right;
	}
	sys->print("Free list has %d items: ", freecnt);
	if(freecnt != t.sz - 1)
		sys->print("bad value!\n");
	else
		sys->print("OK\n");
}

--------------620924187DB--