btree.sa


Generated by gen_html_sa_files from ICSI. Contact gomes@icsi.berkeley.edu for details
 
---------------------------> Sather 1.1 source file <--------------------------
-- BTREES, also called (a,b)-trees are gerneralized avl-trees
-- 22.3.1995 Holger Klawitter <holger@math.uni-muenster.de>
-- Defined classes:
--   B_TREE{KEY,ELT}
-- Helper classes:
--   B_TREE{KEY,ELT,NODE}
--   BT_NODE{KEY,ELT}
--   BT_NELEM{KEY,ELT,NODE}


class B_TREE{ KEY < $IS_LT{KEY}, ELT }

class B_TREE{ KEY < $IS_LT{KEY}, ELT } is include B_TREE{KEY,ELT,BT_NODE{KEY,ELT}}; end; -- class B_TREE

class B_TREE{ KEY < $IS_LT{KEY}, ELT, NODE < $BT_NODE{KEY,ELT,NODE} }

class B_TREE{ KEY < $IS_LT{KEY}, ELT, NODE < $BT_NODE{KEY,ELT,NODE} } < $MAP{ KEY, ELT } is -- B_TREES can be used as an alternative of *MAPs. They are optimized -- for usage in environment with slow access to elt. private include COMPARE{ELT}; private attr root: NODE; readonly attr size: INT; create: SAME is return new end; aset( k: KEY, d: ELT ) -- Associate d with k and store it in the btree. -- If this key already exists in the btree the data will -- be overwritten. Association void to the key is -- equivalent to delete the key with its data. pre ~void(self) is node,e: NODE; pos: INT; found: BOOL; stack ::= #A_STACK{TUP{INT,NODE}}; item ::= #TUP{KEY,ELT}( k, d ); if void(root) then root := #NODE(item); size := 1; return end; found := root.find( k, stack ); node := stack.top.t2; pos := stack.pop.t1; if found then node.setItem( pos, item ) else size := size + 1; e := #NODE( item ); loop if node.size < node.maxSize then node.nodeInsert( e, pos ); break! elsif node = root then root := node.split( e, pos ); break! elsif node.rightFree( stack ) then node.pushRight( e, pos, stack ); break! elsif node.leftFree( stack ) then node.pushLeft( e, pos, stack ); break! end; e := node.split( e, pos ); node := stack.top.t2; pos := stack.pop.t1 end end end; -- aset aget( k: KEY ): ELT pre ~void(self) is stack ::= #A_STACK{TUP{INT,NODE}}; if root.find(k,stack) then return stack.top.t2[stack.top.t1].item.t2; else return void end; end; -- aget delete( k: KEY ) -- Remove the key and its associated elt from the btree. pre ~void(self) is dummy ::= delete(k) end; delete( k: KEY ): ELT -- Removes the key and its associated elt from the btree. -- Returns the element being deleted or void if none found. pre ~void(self) is node,delNode: NODE; pos, delPos: INT; found: BOOL; if void(root) then return void end; stack ::= #A_STACK{TUP{INT,NODE}}; found := root.find( k, stack ); if ~found then return void end; size := size - 1; delNode := stack.top.t2; delPos := stack.top.t1; res ::= delNode[delPos].item.t2; if ~void(delNode[delPos].node) then -- not a true leaf delNode.findPred( stack ); node := stack.top.t2; pos := stack.pop.t1 - 1; delNode.setItem( delPos, node[pos].item ) else node := delNode; pos := stack.pop.t1 -- same as delPos, but I want to pop the stack end; loop if node = root then node.nodeDelete(pos); if node.size = 0 then root := node[0].node end; break! elsif node.size > node.minSize then node.nodeDelete( pos ); break! elsif node.leftSpare( stack ) then node.pullLeft( pos, stack ); break! elsif node.rightSpare( stack ) then node.pullRight( pos, stack ); break! end; if stack.top.t1 < stack.top.t2.size then node.joinRight( pos, stack ) else node.joinLeft( pos, stack ) end; node := stack.top.t2; pos := stack.pop.t1 end; return res end; -- delete has_ind( k: KEY ): BOOL -- Answer 'true' if such a key exists within the btree. pre ~void(self) is if void(root) then return false end; stack ::= #A_STACK{TUP{INT,NODE}}; res ::= root.find( k, stack ); return res end; -- has_ind has( e: ELT ): BOOL is return has_elt(e) end; has_elt( e: ELT ): BOOL pre ~void(self) is loop other ::= root.elt!; if elt_eq(e,other) then return true end; end; return false end; -- has_elt str: STR is return SYS::id(self).str end; copy: SAME is res ::= #SAME; loop pair ::= pair!; res[pair.t1] := pair.t2 end; return res end; -- copy ind!: KEY -- Yield all keys in-order. pre ~void(self) is loop yield root.ind! end end; elt!: ELT -- Yield all elt in order of the keys. pre ~void(self) is loop yield root.elt! end end; pair!: TUP{KEY,ELT} -- Yield all pairs of key and elt in the order of the keys. pre ~void(self) is loop yield root.pair! end end; end; -- class B_TREE

abstract class $BT_NODE{ KEY < $IS_LT{KEY}, ELT,

abstract class $BT_NODE{ KEY < $IS_LT{KEY}, ELT, NODE < $BT_NODE{KEY,ELT,NODE} } is create: SAME; create(t:TUP{KEY,ELT}): SAME; is_eq(n:NODE): BOOL; aget(i:INT): BT_NELEM{KEY,ELT,NODE}; size: INT; minSize: INT; maxSize: INT; setItem(pos:INT,t:TUP{KEY,ELT}); setNode(pos:INT,node:NODE); leftFree(stack:A_STACK{TUP{INT,NODE}}): BOOL; rightFree(stack:A_STACK{TUP{INT,NODE}}): BOOL; leftSpare(stack:A_STACK{TUP{INT,NODE}}): BOOL; rightSpare(stack:A_STACK{TUP{INT,NODE}}): BOOL; pushLeft(e:NODE,pos:INT,stack:A_STACK{TUP{INT,NODE}}); pushRight(e:NODE,pos:INT,stack:A_STACK{TUP{INT,NODE}}); split(e:NODE,pos:INT): NODE; nodeInsert(n:NODE,pos:INT); pullLeft(pos:INT,stack:A_STACK{TUP{INT,NODE}}); pullRight(pos:INT,stack:A_STACK{TUP{INT,NODE}}); joinLeft(pos:INT,stack:A_STACK{TUP{INT,NODE}}); joinRight(pos:INT,stack:A_STACK{TUP{INT,NODE}}); nodeDelete(pos:INT); findPred(stack:A_STACK{TUP{INT,NODE}}); find(k:KEY,stack:A_STACK{TUP{INT,NODE}}): BOOL; ind!: KEY; elt!: ELT; pair!: TUP{KEY,ELT}; end;

class BT_NODE{ KEY < $IS_LT{KEY}, ELT } < $BT_NODE{KEY,ELT,BT_NODE{KEY,ELT}}

class BT_NODE{ KEY < $IS_LT{KEY}, ELT } < $BT_NODE{KEY,ELT,BT_NODE{KEY,ELT}} is -- This class is inernally used by B_TREE. -- It represents the root and all nodes in a B_BTEE. -- The general structure of a BT_NODE is as follows: -- [0].node [0].item [1].node [1].item ... [k].node [k].item [k+1].node -- ([k+1].item is always unused) --include COMPARABLE; include AREF{BT_NELEM{KEY,ELT,SAME}} aset->private aset; -- Array of items and nodes. attr size: INT; -- Current fill ratio of the node. const maxSize: INT := 4; -- maximal number of elt tuples. -- MUST BE EVEN AND GREATER THAN 2. const minSize: INT := maxSize / 2; create: SAME is return new(maxSize+1); end; create( t: TUP{KEY,ELT} ): SAME is res ::= new(maxSize+1); res.setItem( 0, t ); res.size := 1; return res end; -- create is_eq( n: SAME ): BOOL is return SYS::ob_eq(self,n) end; setItem( pos: INT, t: TUP{KEY,ELT} ) pre pos>=0 and pos<=maxSize is [pos] := [pos].item(t) end; -- setItem setNode( pos: INT, node: SAME ) pre pos>=0 and pos<=maxSize is [pos] := [pos].node(node) end; -- setNode -- Predicates for sibling nodes leftFree( stack: A_STACK{TUP{INT,SAME}} ): BOOL pre ~void(stack.top) and stack.top.t2 /= self is parent ::= stack.top; return parent.t1 > 0 and parent.t2[parent.t1-1].node.size < maxSize end; -- leftFree rightFree( stack: A_STACK{TUP{INT,SAME}} ): BOOL pre ~void(stack.top) and stack.top.t2 /= self is parent ::= stack.top; return parent.t1 < parent.t2.size and parent.t2[parent.t1+1].node.size < maxSize end; -- rightFree leftSpare( stack: A_STACK{TUP{INT,SAME}} ): BOOL pre ~void(stack.top) and stack.top.t2 /= self is parent ::= stack.top; return parent.t1 > 0 and parent.t2[parent.t1-1].node.size > minSize end; -- leftSpare rightSpare( stack: A_STACK{TUP{INT,SAME}} ): BOOL pre ~void(stack.top) and stack.top.t2 /= self is parent ::= stack.top; return parent.t1 < parent.t2.size and parent.t2[parent.t1+1].node.size > minSize end; -- rightSpare ------------ Insertion pushLeft( e: SAME, pos: INT, stack: A_STACK{TUP{INT,SAME}} ) pre size=maxSize is parent, left: SAME; i, ppos: INT; parent := stack.top.t2; ppos := stack.top.t1; left := parent[ppos-1].node; left.setItem( left.size, parent[ppos-1].item ); if pos = 0 then -- item goes up left.setNode( left.size+1, e[0].node ); parent.setItem( ppos-1, e[0].item ); setNode( 0, e[1].node ) else -- item[0] goes up, insert item parent.setItem( ppos-1, [0].item ); left.setNode( left.size+1, [0].node ); loop i:= 0.upto!(pos-2); [i] := [i+1] end; [pos-1] := e[0]; setNode( pos, e[1].node ) end; left.size := left.size + 1 end; pushRight( e: SAME, pos: INT, stack: A_STACK{TUP{INT,SAME}} ) pre size = maxSize is parent, right: SAME; i, ppos: INT; parent := stack.top.t2; ppos := stack.top.t1; right := parent[ppos+1].node; loop i:= right.size.downto!( 0 ); -- create some space right[i+1] := right[i] end; right.setItem( 0, parent[ppos].item ); if pos = size then -- item goes up parent.setItem( ppos, e[0].item ); setNode( size, e[0].node ); right.setNode( 0, e[1].node ) else -- last item goes up, item will be inserted. parent.setItem( ppos, [size-1].item ); right.setNode( 0, [size].node ); setNode( size, [size-1].node ); loop i := (size-2).downto!(pos); [i+1] := [i] end; [pos] := e[0]; setNode( pos+1, e[1].node ) end; right.size := right.size + 1 end; split( e: SAME, pos: INT ): SAME pre size = maxSize is i: INT; newNode: SAME := #; if pos <= minSize then -- item does not go right loop i := minSize.upto!(size); newNode[i-minSize] := [i]; [i] := void end; if pos = minSize then -- item goes up newNode.setNode( 0, e[1].node ); setNode( minSize, e[0].node ) else -- item stays left loop i := minSize.downto!(pos+1); [i] := [i-1] end; [pos] := e[0]; setNode( pos+1, e[1].node ); e.setItem( 0, [minSize].item ); setItem( minSize, void ) end; else -- item goes right loop i := size.downto!(pos); newNode[i-minSize] := [i]; [i] := void end; newNode.setNode( pos-minSize, e[1].node ); newNode[pos-minSize-1] := e[0]; loop i := (pos-1).downto!(minSize+1); newNode[i-minSize-1] := [i]; [i] := void end; e.setItem( 0, [minSize].item ); setItem( minSize, void ) end; size := minSize; newNode.size := minSize; e.setNode( 0, self ); -- generate the new node to insert. e.setNode( 1, newNode ); assert e.size = 1; return e end; nodeInsert( n: SAME, pos: INT ) pre pos>=0 and pos<=maxSize and size<maxSize is i: INT; loop i := size.downto!(pos); [i+1] := [i] end; [pos] := n[0]; setNode( pos+1, n[1].node ); size := size + 1 end; ------------ Deletion pullLeft( pos: INT, stack: A_STACK{TUP{INT,SAME}} ) is parent, left: SAME; i, ppos: INT; parent := stack.top.t2; ppos := stack.top.t1; left := parent[ppos-1].node; loop i := pos.downto!(1); -- Move hole to the left end. [i] := [i-1] end; setItem( 0, parent[ppos-1].item ); -- get from parent setNode( 0, left[size].node ); parent.setItem( ppos-1, left[left.size-1].item ); -- refill parent left[left.size] := void; left.setItem( left.size-1, void ); left.size := left.size - 1 end; pullRight( pos: INT, stack: A_STACK{TUP{INT,SAME}} ) is parent, right: SAME; i, ppos: INT; parent := stack.top.t2; ppos := stack.top.t1; right := parent[ppos+1].node; loop i := pos.upto!(size-1); -- Close hole. [i] := [i+1] end; setItem( size-1, parent[ppos].item ); -- Get right end from parent. setNode( size, right[0].node ); parent.setItem( ppos, right[0].item ); loop i := 1.upto!( right.size ); right[i-1] := right[i] end; right[right.size] := void; -- more efficient than 'just' setNode. right.size := right.size - 1 end; joinLeft( pos: INT, stack: A_STACK{TUP{INT,SAME}} ) pre size = minSize is parent, left: SAME; i, ppos: INT; parent := stack.top.t2; ppos := stack.top.t1; left := parent[ppos-1].node; assert left.size = minSize; loop i := pos.downto!( 1 ); -- Move hole to the left. [i] := [i-1] end; setNode( 0, left[left.size].node ); -- Get from parent. setItem( 0, parent[ppos-1].item ); loop i := size.downto!( 0 ); -- Make BIG hole for left sibling. [i+minSize] := [i] -- means [i+left.size] := [i] end; loop i := 0.upto!(minSize-1); [i] := left[i] end; parent.setNode( ppos-1, self ); parent.setItem( ppos-1, parent[ppos].item ); size := maxSize end; joinRight( pos: INT, stack: A_STACK{TUP{INT,SAME}} ) pre size = minSize is parent, right: SAME; i, ppos: INT; parent := stack.top.t2; ppos := stack.top.t1; right := parent[ppos+1].node; assert right.size = minSize; loop i := (pos+1).upto!( size ); -- Close hole. [i-1] := [i] end; setItem( size-1, parent[ppos].item ); -- Get from parent. loop i := 0.upto!( right.size ); -- Do joining. [size+i] := right[i] end; parent.setNode( ppos+1, self ); size := maxSize end; nodeDelete( pos: INT ) pre pos>=0 and pos<=maxSize is i: INT; loop i := pos.upto!(size-1); [i] := [i+1] end; [size] := void; size := size - 1 end; findPred( stack: A_STACK{TUP{INT,SAME}} ) is node ::= stack.top.t2[stack.top.t1].node; loop until!( void(node) ); stack.push( #TUP{INT,SAME}(node.size, node) ); node := node[node.size].node end end; ------------ Retrieval find( k: KEY, stack: A_STACK{TUP{INT,SAME}} ): BOOL is if void(self) then return false end; loop i ::= 0.upto!(size-1); if [i].item.t1 = k then stack.push( #TUP{INT,SAME}(i,self) ); return true elsif k < [i].item.t1 then stack.push( #TUP{INT,SAME}(i,self) ); return ~void([i].node) and [i].node.find( k, stack ) end end; stack.push( #TUP{INT,SAME}(size,self) ); return ~void([size].node) and [size].node.find( k, stack ) end; ------------ Iterators ind!: KEY is if ~void(self) then loop i ::= 0.upto!(size); loop yield [i].node.ind! end; if ~void([i].item) -- and i<size but this is redunant then yield [i].item.t1 end end end end; elt!: ELT is if ~void(self) then loop i ::= 0.upto!(size); loop yield [i].node.elt! end; if ~void([i].item) -- and i<size but this is redunant then yield [i].item.t2 end end end end; pair!: TUP{KEY,ELT} is if ~void(self) then loop i ::= 0.upto!(size); loop yield [i].node.pair! end; if ~void([i].item) -- and i<size but this is redunant then yield [i].item end end end end; end; -- class BT_NODE

immutable class BT_NELEM{KEY<$IS_LT{KEY},

immutable class BT_NELEM{KEY<$IS_LT{KEY}, ELT, NODE < $BT_NODE{ KEY, ELT, NODE } } -- BT_NELEM is being internally used by BT_NODE to store the -- nodes and the items efficiently. is attr node: NODE; attr item: TUP{ KEY, ELT }; create( n: NODE, i: TUP{KEY,ELT} ): SAME is return node(n).item(i) end; end; -- class BT_NELEM