cytoscape.util.intr
Class IntBTree

java.lang.Object
  cytoscape.util.intr.IntBTree

All Implemented Interfaces:

Serializable

public final class IntBTree
extends Object
implements Serializable

An in-memory 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 R-tree). 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.

See Also:

Serialized Form

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

DEFAULT_MAX_BRANCHES

public static final int DEFAULT_MAX_BRANCHES

See Also:

Constant Field Values

Constructor Detail

IntBTree

public IntBTree()

Creates a new tree structure with an optimal branching factor.

IntBTree

public IntBTree(int maxBranches)

Creates a new tree structure with the specified maximum branching factor. Overriding the default maximum branching factor is only useful for testing purposes; there are no performance gains to be had.

Parameters:

maxBranches - the maximum branching factor of this tree.

Throws:

IllegalArgumentException - if maxBranches is less than three.

Method Detail

empty

public final void empty()

Empties this structure of all elements. This method returns in constant time (note however that garbage collection will take place in the background).

size

public final int size()

Returns the number of elements currently in this structure. Duplicate entries are counted however many times they are present. This method returns in constant time.

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.

insert

public final void insert(int x)

Inserts a new entry into this tree structure; duplicate entries may be inserted. This method has a time complexity of O(log(N)) where N is the number of entries currently stored in this tree structure.

Parameters:

x - the new entry to insert.

delete

public final boolean delete(int x)

Deletes at most one entry of the integer x. This method has a time complexity of O(log(N)) where N is the number of entries currently stored in this tree structure.

Unfortunately there does not seem to exists an elegant algorithm for efficiently deleting a range of integers while guaranteeing a balanced tree structure.

Parameters:

x - the integer to try to delete (just one entry).

Returns:

true if and only if an entry was deleted (at most one entry is deleted by this method).

count

public final int count(int x)

Returns the number of entries of the integer x in this tree. This method has a time complexity of O(log(N)) where N is the total number of entries currently in this tree structure.

This method is superfluous because we can use searchRange(x, x, false) to get the same information, paying the same hit in time complexity.

Parameters:

x - the integer whose count to query.

Returns:

the number of entries x currently in this structure.

searchRange

public final 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. The elements of the enumeration are returned in non-descending order if the reverseOrder input parameter is false; otherwise, elements of the enumeration are returned in non-ascending order. This method takes O(log(N)) time to compute a return value, where N is the total number of entries currently in this tree structure. The returned enumeration reports the number of elements remaining in constant time. The returned enumeration can be completely traversed in O(K) time, where K is the number of elements in the returned enumeration. Note, however, that there is no guarantee that each successive element of the enumeration is returned in constant time; instead, the time complexity of accessing each successive element is only constant on average, and is in fact O(log(K)).

IMPORTANT: The returned enumeration becomes invalid as soon as any structure-modifying operation (insert or delete) is performed on this tree. Accessing an invalid enumeration's methods will result in unpredictable and ill-defined 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 pre-compute the first element of the enumeration in order to reduce the complexity of the code.

Parameters:

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 non-descending order; if true, elements returned are in non-ascending order.

Returns:

an enumeration of all entries matching this search query, duplicates included; elements returned are in non-descending order if reverseOrder is false; elements returned are in non-ascending order if reverseOrder is true.

Throws:

IllegalArgumentException - if xMin is greater than xMax.