Main Page | Namespace List | Class Hierarchy | Class List | File List | Class Members | Related Pages | Search for 

org::gel::mauve::tree::GISTree Class Reference

Records a mapping between gapped sequence coordinates and ungapped sequence coordinates. More...

Collaboration diagram for org::gel::mauve::tree::GISTree:

Collaboration graph
[legend]
List of all members.

Public Member Functions

void _splay (int index)
 splay this node to the root of the tree

long columnToSeqPos (long column)
 Convert a column index to a sequence index, taking the nearest seq index to the left if the column falls in a gap region.

int find (long seq_point)
 find the interval containing a position in the gapped sequence

int find_seqindex (long seq_point)
 find the interval containing a position in the ungapped sequence

Key getKey (int index)
int getLeft (int index)
long getLength (int index)
int getParent (int index)
int getRight (int index)
long getSeqLength (int index)
long getSequenceStart (int index)
long getStart (int index)
 GISTree (TreeStore ts)
 Create a new GISTree using the given TreeStore to store data.

Key increment (int index)
 returns the Key of the node immediately to the right of x, or null if x is already the righ-most tree node

int insert (Key val, long point)
long length ()
 returns the total length of the gapped sequence stored in the tree

int recursiveFind (int index, long[] position)
 find the node below cur_node containing a given position in the gapped sequence, starting at the left-most position below cur_node

int recursiveSeqFind (int index, long[] position)
 Find the node below cur_node containing a given position in the ungapped sequence, starting at the left-most position below cur_node.

long seqPosToColumn (long seq_index)
 Convert a sequence coordinate to a column index.

long sequenceLength ()
 returns the length of ungapped sequence stored in the tree

void setKey (int index, Key k)
void setLeft (int index, int l)
void setLength (int index, long l)
void setParent (int index, int p)
void setRight (int index, int r)
void setSeqLength (int index, long l)

Static Public Attributes

long end = Long.MAX_VALUE

Protected Member Functions

void splay (int index)
 splay a node to the root of the tree


Package Attributes

int rootIndex = TreeStore.NULL_REF
TreeStore ts = null

Static Package Attributes

final long serialVersionUID = 1

Private Member Functions

void recalculateLengths (int index)

Detailed Description

Records a mapping between gapped sequence coordinates and ungapped sequence coordinates.

Implemented using a splay tree for O(n log n) amortized time complexity operations.

Definition at line 11 of file GISTree.java.

Constructor & Destructor Documentation

org::gel::mauve::tree::GISTree::GISTree (  TreeStore  ts  )  [inline]
 

Create a new GISTree using the given TreeStore to store data.

Definition at line 21 of file GISTree.java.

Member Function Documentation

void org::gel::mauve::tree::GISTree::_splay (  int  index  )  [inline]
 

splay this node to the root of the tree

Definition at line 203 of file GISTree.java.

References org::gel::mauve::tree::TreeStore::left, org::gel::mauve::tree::TreeStore::parent, recalculateLengths(), org::gel::mauve::tree::TreeStore::right, and ts.

Referenced by splay().

long org::gel::mauve::tree::GISTree::columnToSeqPos (  long  column  )  [inline]
 

Convert a column index to a sequence index, taking the nearest seq index to the left if the column falls in a gap region.

Definition at line 174 of file GISTree.java.

References find(), getKey(), org::gel::mauve::tree::Key::getSeqLength(), getSequenceStart(), and getStart().

int org::gel::mauve::tree::GISTree::find (  long  seq_point  )  [inline]
 

find the interval containing a position in the gapped sequence

Definition at line 38 of file GISTree.java.

References recursiveFind(), rootIndex, and splay().

Referenced by columnToSeqPos().

int org::gel::mauve::tree::GISTree::find_seqindex (  long  seq_point  )  [inline]
 

find the interval containing a position in the ungapped sequence

Definition at line 47 of file GISTree.java.

References recursiveSeqFind(), rootIndex, and splay().

Referenced by seqPosToColumn().

Key org::gel::mauve::tree::GISTree::getKey (  int  index  )  [inline]
 

Definition at line 366 of file GISTree.java.

References org::gel::mauve::tree::TreeStore::key, and ts.

Referenced by columnToSeqPos(), and insert().

int org::gel::mauve::tree::GISTree::getLeft (  int  index  )  [inline]
 

Definition at line 390 of file GISTree.java.

References org::gel::mauve::tree::TreeStore::left, and ts.

Referenced by getSequenceStart(), getStart(), and insert().

long org::gel::mauve::tree::GISTree::getLength (  int  index  )  [inline]
 

Definition at line 382 of file GISTree.java.

References org::gel::mauve::tree::TreeStore::length, and ts.

Referenced by getStart().

int org::gel::mauve::tree::GISTree::getParent (  int  index  )  [inline]
 

Definition at line 406 of file GISTree.java.

References org::gel::mauve::tree::TreeStore::parent, and ts.

int org::gel::mauve::tree::GISTree::getRight (  int  index  )  [inline]
 

Definition at line 398 of file GISTree.java.

References org::gel::mauve::tree::TreeStore::right, and ts.

Referenced by insert().

long org::gel::mauve::tree::GISTree::getSeqLength (  int  index  )  [inline]
 

Definition at line 374 of file GISTree.java.

References org::gel::mauve::tree::TreeStore::seqLength, and ts.

Referenced by getSequenceStart(), and sequenceLength().

long org::gel::mauve::tree::GISTree::getSequenceStart (  int  index  )  [inline]
 

Definition at line 55 of file GISTree.java.

References getLeft(), getSeqLength(), rootIndex, and splay().

Referenced by columnToSeqPos(), and seqPosToColumn().

long org::gel::mauve::tree::GISTree::getStart (  int  index  )  [inline]
 

Definition at line 61 of file GISTree.java.

References getLeft(), getLength(), rootIndex, and splay().

Referenced by columnToSeqPos(), and seqPosToColumn().

Key org::gel::mauve::tree::GISTree::increment (  int  index  )  [inline]
 

returns the Key of the node immediately to the right of x, or null if x is already the righ-most tree node

Definition at line 268 of file GISTree.java.

References org::gel::mauve::tree::TreeStore::key, org::gel::mauve::tree::TreeStore::left, org::gel::mauve::tree::TreeStore::parent, org::gel::mauve::tree::TreeStore::right, and ts.

int org::gel::mauve::tree::GISTree::insert (  Key  val,
long  point
)  [inline]
 

Definition at line 67 of file GISTree.java.

References org::gel::mauve::tree::Key::copy(), org::gel::mauve::tree::TreeStore::createGistNode(), org::gel::mauve::tree::Key::cropEnd(), org::gel::mauve::tree::Key::cropStart(), getKey(), getLeft(), org::gel::mauve::tree::Key::getLength(), getRight(), org::gel::mauve::tree::Key::getSeqLength(), recursiveFind(), rootIndex, setKey(), setLeft(), setLength(), setParent(), setRight(), setSeqLength(), splay(), and ts.

Referenced by org::gel::mauve::XMFAAlignment::SuppressWarnings().

long org::gel::mauve::tree::GISTree::length (   )  [inline]
 

returns the total length of the gapped sequence stored in the tree

Definition at line 26 of file GISTree.java.

References org::gel::mauve::tree::TreeStore::length, rootIndex, and ts.

Referenced by org::gel::mauve::XMFAAlignment::SuppressWarnings().

void org::gel::mauve::tree::GISTree::recalculateLengths (  int  index  )  [inline, private]
 

Definition at line 183 of file GISTree.java.

References org::gel::mauve::tree::Key::getLength(), org::gel::mauve::tree::Key::getSeqLength(), org::gel::mauve::tree::TreeStore::key, org::gel::mauve::tree::TreeStore::left, org::gel::mauve::tree::TreeStore::length, org::gel::mauve::tree::TreeStore::parent, org::gel::mauve::tree::TreeStore::right, org::gel::mauve::tree::TreeStore::seqLength, and ts.

Referenced by _splay().

int org::gel::mauve::tree::GISTree::recursiveFind (  int  index,
long[]  position
)  [inline]
 

find the node below cur_node containing a given position in the gapped sequence, starting at the left-most position below cur_node

Parameters:
cur_node The tree node to use as the base for the search. usually the root
position The position to search for. A single element array. The value is modified to reflect the distance into the returned node where the requested position actually occurs. version 2 of recursiveFind -- don't build a potentially huge call stack!

Definition at line 301 of file GISTree.java.

References org::gel::mauve::tree::Key::getLength(), org::gel::mauve::tree::TreeStore::key, org::gel::mauve::tree::TreeStore::left, org::gel::mauve::tree::TreeStore::length, org::gel::mauve::tree::TreeStore::right, and ts.

Referenced by find(), and insert().

int org::gel::mauve::tree::GISTree::recursiveSeqFind (  int  index,
long[]  position
)  [inline]
 

Find the node below cur_node containing a given position in the ungapped sequence, starting at the left-most position below cur_node.

Parameters:
cur_node The tree node to use as the base for the search. usually the root
position The position to search for. A single element array. The value is modified to reflect the distance into the returned node where the requested position actually occurs. version 2 of recursiveSeqFind -- don't build a potentially huge call stack!

Definition at line 340 of file GISTree.java.

References org::gel::mauve::tree::Key::getSeqLength(), org::gel::mauve::tree::TreeStore::key, org::gel::mauve::tree::TreeStore::left, org::gel::mauve::tree::TreeStore::right, org::gel::mauve::tree::TreeStore::seqLength, and ts.

Referenced by find_seqindex().

long org::gel::mauve::tree::GISTree::seqPosToColumn (  long  seq_index  )  [inline]
 

Convert a sequence coordinate to a column index.

Definition at line 162 of file GISTree.java.

References find_seqindex(), getSequenceStart(), and getStart().

Referenced by org::gel::mauve::XMFAAlignment::getRange().

long org::gel::mauve::tree::GISTree::sequenceLength (   )  [inline]
 

returns the length of ungapped sequence stored in the tree

Definition at line 33 of file GISTree.java.

References getSeqLength(), and rootIndex.

void org::gel::mauve::tree::GISTree::setKey (  int  index,
Key  k
)  [inline]
 

Definition at line 370 of file GISTree.java.

References org::gel::mauve::tree::TreeStore::key, and ts.

Referenced by insert().

void org::gel::mauve::tree::GISTree::setLeft (  int  index,
int  l
)  [inline]
 

Definition at line 394 of file GISTree.java.

References org::gel::mauve::tree::TreeStore::left, and ts.

Referenced by insert().

void org::gel::mauve::tree::GISTree::setLength (  int  index,
long  l
)  [inline]
 

Definition at line 386 of file GISTree.java.

References org::gel::mauve::tree::TreeStore::length, and ts.

Referenced by insert().

void org::gel::mauve::tree::GISTree::setParent (  int  index,
int  p
)  [inline]
 

Definition at line 410 of file GISTree.java.

References org::gel::mauve::tree::TreeStore::parent, and ts.

Referenced by insert().

void org::gel::mauve::tree::GISTree::setRight (  int  index,
int  r
)  [inline]
 

Definition at line 402 of file GISTree.java.

References org::gel::mauve::tree::TreeStore::right, and ts.

Referenced by insert().

void org::gel::mauve::tree::GISTree::setSeqLength (  int  index,
long  l
)  [inline]
 

Definition at line 378 of file GISTree.java.

References org::gel::mauve::tree::TreeStore::seqLength, and ts.

Referenced by insert().

void org::gel::mauve::tree::GISTree::splay (  int  index  )  [inline, protected]
 

splay a node to the root of the tree

Definition at line 154 of file GISTree.java.

References _splay(), and rootIndex.

Referenced by find(), find_seqindex(), getSequenceStart(), getStart(), and insert().

Member Data Documentation

long org::gel::mauve::tree::GISTree::end = Long.MAX_VALUE [static]
 

Definition at line 14 of file GISTree.java.

int org::gel::mauve::tree::GISTree::rootIndex = TreeStore.NULL_REF [package]
 

Definition at line 16 of file GISTree.java.

Referenced by find(), find_seqindex(), getSequenceStart(), getStart(), insert(), length(), sequenceLength(), and splay().

final long org::gel::mauve::tree::GISTree::serialVersionUID = 1 [static, package]
 

Definition at line 12 of file GISTree.java.

TreeStore org::gel::mauve::tree::GISTree::ts = null [package]
 

Definition at line 18 of file GISTree.java.

Referenced by _splay(), getKey(), getLeft(), getLength(), getParent(), getRight(), getSeqLength(), increment(), insert(), length(), recalculateLengths(), recursiveFind(), recursiveSeqFind(), setKey(), setLeft(), setLength(), setParent(), setRight(), and setSeqLength().

The documentation for this class was generated from the following file:
Generated on Wed May 22 06:05:40 2013 for Mauve by doxygen 1.3.6