goldman.collection.ordered
Class BTree<E>

java.lang.Object
  extended by goldman.collection.AbstractCollection<E>
      extended by goldman.collection.ordered.AbstractSearchTree<E>
          extended by goldman.collection.ordered.BTree<E>
All Implemented Interfaces:
Collection<E>, OrderedCollection<E>, Iterable<E>
Direct Known Subclasses:
BPlusTree, TopDownBTree

public class BTree<E>
extends AbstractSearchTree<E>
implements OrderedCollection<E>

A B-tree is a balanced binary search tree in which each node can hold between t-1 and 2t-1 elements, where integer t > 1 is provided as a parameter to the constructor. Our implementation of the B-tree uses bottom-up insertion and deletion. The B-tree is designed for collections that are so large that secondary storage must be used. The larger node size (chosen with knowledge of the page size) helps minimize the number of disk pages that must be read to locate an element.


Nested Class Summary
protected  class BTree.Marker
           
 
Nested classes/interfaces inherited from class goldman.collection.ordered.AbstractSearchTree
AbstractSearchTree.TreeNode
 
Nested classes/interfaces inherited from class goldman.collection.AbstractCollection
AbstractCollection.AbstractLocator<T extends E>, AbstractCollection.VisitingIterator
 
Field Summary
 
Fields inherited from class goldman.collection.ordered.AbstractSearchTree
root
 
Fields inherited from class goldman.collection.AbstractCollection
comp, DEFAULT_CAPACITY, NOT_FOUND, size, version
 
Constructor Summary
BTree()
           
BTree(Comparator<? super E> comp, int t)
           
BTree(int t)
           
 
Method Summary
 void clear()
          Removes all elements from the collection
protected  void createRoot()
          Creates and initializes a new empty root node
protected  goldman.collection.ordered.BTree.BTreeNode find(E target)
          This method sets the global variable curIndex to hold the index for an occurrence of the target (if it is in the collection), or otherwise the insert position for the target in the last non-frontier node on the search path
protected  int getLastNodeSearchIndex()
          
REQUIRES: it is called only after a successful search
 Locator<E> getLocator(E x)
          Returns a locator that has been initialized to an element equivalent to target.
protected  AbstractSearchTree.TreeNode insert(E element)
          Inserts it into the collection
 Locator<E> iterator()
          Creates a new tracker that is at FORE.
 Locator<E> iteratorAtEnd()
          Creates a new tracker that is at AFT.
 E predecessor(E target)
          This method does not require that target be in the collection.
protected  void remove(AbstractSearchTree.TreeNode x)
          Removes the element at curIndex of x
 E successor(E target)
          This method does not require that target be in the collection.
 
Methods inherited from class goldman.collection.ordered.AbstractSearchTree
add, contains, get, getEquivalentElement, max, min, remove, traverseForVisitor, writeElements
 
Methods inherited from class goldman.collection.AbstractCollection
accept, addAll, checkRep, compare, ensureCapacity, equivalent, getCapacity, getComparator, getElementAtRank, getElementAtRank, getSize, isEmpty, retainAll, toArray, toArray, toString, trimToSize
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface goldman.collection.ordered.OrderedCollection
get, getEquivalentElement, max, min
 
Methods inherited from interface goldman.collection.Collection
accept, add, addAll, checkRep, contains, ensureCapacity, getCapacity, getComparator, getSize, isEmpty, remove, retainAll, toArray, toArray, toString, trimToSize
 

Constructor Detail

BTree

public BTree()

BTree

public BTree(int t)
Parameters:
t - the order for the B-tree

BTree

public BTree(Comparator<? super E> comp,
             int t)
Parameters:
comp - the function used to compare two elements
t - the order of the B-tree
Method Detail

createRoot

protected void createRoot()
Creates and initializes a new empty root node


find

protected goldman.collection.ordered.BTree.BTreeNode find(E target)
This method sets the global variable curIndex to hold the index for an occurrence of the target (if it is in the collection), or otherwise the insert position for the target in the last non-frontier node on the search path

Specified by:
find in class AbstractSearchTree<E>
Parameters:
target - the value to search for
Returns:
a reference to a B-tree node that contains an occurrence of the target when there is an equivalent element in the collection. Otherwise it returns the frontier node after setting its parent field set to predecessor of the target on the search path.

getLastNodeSearchIndex

protected int getLastNodeSearchIndex()

REQUIRES: it is called only after a successful search

Overrides:
getLastNodeSearchIndex in class AbstractSearchTree<E>
Returns:
the index, within its tree node, of the element returned in the most recent search.

predecessor

public E predecessor(E target)
This method does not require that target be in the collection.

Specified by:
predecessor in interface OrderedCollection<E>
Parameters:
target - the element for which to find the predecessor
Returns:
the largest element in the ordered collection that is less than target.
Throws:
NoSuchElementException - no element in the collection is less than target

successor

public E successor(E target)
This method does not require that target be in the collection.

Specified by:
successor in interface OrderedCollection<E>
Parameters:
target - the element for which to find the successor
Returns:
the least element in the ordered collection that is greater than target
Throws:
NoSuchElementException - no element in the collection is greater than target

insert

protected AbstractSearchTree.TreeNode insert(E element)
Description copied from class: AbstractSearchTree
Inserts it into the collection

Specified by:
insert in class AbstractSearchTree<E>
Parameters:
element - the new element
Returns:
a reference to the newly added B-tree node

remove

protected void remove(AbstractSearchTree.TreeNode x)
Removes the element at curIndex of x

Specified by:
remove in class AbstractSearchTree<E>
Parameters:
x - a reference to an existing tree node

clear

public void clear()
Removes all elements from the collection

Specified by:
clear in interface Collection<E>
Overrides:
clear in class AbstractCollection<E>

iterator

public Locator<E> iterator()
Creates a new tracker that is at FORE.

Specified by:
iterator in interface Collection<E>
Specified by:
iterator in interface Iterable<E>

iteratorAtEnd

public Locator<E> iteratorAtEnd()
Creates a new tracker that is at AFT.

Specified by:
iteratorAtEnd in interface OrderedCollection<E>

getLocator

public Locator<E> getLocator(E x)
Description copied from interface: Collection
Returns a locator that has been initialized to an element equivalent to target. Like the iterator method, this method enables navigation, but from a specified starting point. This method throws a NoSuchElementException if there is no equivalent element in the collection.

Specified by:
getLocator in interface Collection<E>
Parameters:
x - the element to track
Returns:
a locator initialized at x.
Throws:
NoSuchElementException - there is no element equivalent to x in the collection.