
Cytoscape 2.8.0 API  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object cytoscape.util.intr.IntBTree
public final class IntBTree
An inmemory B^{+}tree that stores integers.
The motivation behind the implementation of this tree is not usefulness. The motivation is to get to know the algorithms associated with this tree structure, so that implementing variants of this structure would become simpler (an example of a variant of this structure is the Rtree). The implementation of this tree uses recursion (as opposed to the iterative approach). While there is a performance penalty paid by using recursion, recursion does make the code much more understandable.
An instance of this class is serializable; however, serialized instances of this class should not be stored in a persistent manner because the serialization implemented in this class makes no attempt at handling class versioning.
Field Summary  

static int 
DEFAULT_MAX_BRANCHES

Constructor Summary  

IntBTree()
Creates a new tree structure with an optimal branching factor. 

IntBTree(int maxBranches)
Creates a new tree structure with the specified maximum branching factor. 
Method Summary  

int 
count(int x)
Returns the number of entries of the integer x in this tree. 
boolean 
delete(int x)
Deletes at most one entry of the integer x. 
void 
empty()
Empties this structure of all elements. 
void 
insert(int x)
Inserts a new entry into this tree structure; duplicate entries may be inserted. 
IntEnumerator 
searchRange(int xMin,
int xMax,
boolean reverseOrder)
Returns an enumeration of all entries in the range [xMin, xMax] currently in this tree, duplicates included. 
int 
size()
Returns the number of elements currently in this structure. 
Methods inherited from class java.lang.Object 

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait 
Field Detail 

public static final int DEFAULT_MAX_BRANCHES
Constructor Detail 

public IntBTree()
public IntBTree(int maxBranches)
maxBranches
 the maximum branching factor of this tree.
IllegalArgumentException
 if maxBranches is less than three.Method Detail 

public final void empty()
public final int size()
NOTE: To retrieve an enumeration of all entries in this tree, use searchRange() with Integer.MIN_VALUE as the lower bound and Integer.MAX_VALUE as the upper bound.
public final void insert(int x)
x
 the new entry to insert.public final boolean delete(int x)
Unfortunately there does not seem to exists an elegant algorithm for efficiently deleting a range of integers while guaranteeing a balanced tree structure.
x
 the integer to try to delete (just one entry).
public final int count(int x)
This method is superfluous because we can use searchRange(x, x, false) to get the same information, paying the same hit in time complexity.
x
 the integer whose count to query.
public final IntEnumerator searchRange(int xMin, int xMax, boolean reverseOrder)
IMPORTANT: The returned enumeration becomes invalid as soon as any structuremodifying operation (insert or delete) is performed on this tree. Accessing an invalid enumeration's methods will result in unpredictable and illdefined behavior in that enumeration, but will have no effect on the integrity of the underlying tree structure.
IMPLEMENTATION NOTE: To find out how many entries are in this tree, one should use the size() method. Doing so using this method will cost O(log(N)) time, where the size() method returns in constant time. The reason why this method takes longer is because we precompute the first element of the enumeration in order to reduce the complexity of the code.
xMin
 the lower [inclusive] bound of the range to search.xMax
 the upper [inclusive] bound of the range to search.reverseOrder
 if false, elements returned are in nondescending
order; if true, elements returned are in nonascending order.
IllegalArgumentException
 if xMin is greater than xMax.

Cytoscape 2.8.0 API  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 