src/org/gel/mauve/tree/GISTree.java

Go to the documentation of this file.
00001 package org.gel.mauve.tree;
00002 
00003 import java.io.Serializable;
00004 import java.util.Arrays;
00005 
00011 public class GISTree implements Serializable {
00012         static final long serialVersionUID = 1;
00013 
00014         public static long end = Long.MAX_VALUE;
00015 
00016         int rootIndex = TreeStore.NULL_REF;
00017 
00018         TreeStore ts = null;
00019 
00021         public GISTree (TreeStore ts) {
00022                 this.ts = ts;
00023         }
00024 
00026         public long length () {
00027                 return (rootIndex == TreeStore.NULL_REF) ? 0 : ts.length[rootIndex];
00028         }
00029 
00030         // interval sequence specific:
00031 
00033         public long sequenceLength () {
00034                 return rootIndex == TreeStore.NULL_REF ? 0 : getSeqLength (rootIndex);
00035         }
00036 
00038         public int find (long seq_point) {
00039                 long [] position = new long [1];
00040                 position[0] = seq_point;
00041                 int index = recursiveFind (rootIndex, position);
00042                 splay (index);
00043                 return rootIndex;
00044         }
00045 
00047         public int find_seqindex (long seq_point) {
00048                 long [] position = new long [1];
00049                 position[0] = seq_point;
00050                 int index = recursiveSeqFind (rootIndex, position);
00051                 splay (index);
00052                 return rootIndex;
00053         }
00054 
00055         public long getSequenceStart (int index) {
00056                 splay (index);
00057                 return getLeft (rootIndex) != TreeStore.NULL_REF ? getSeqLength (getLeft (rootIndex))
00058                                 : 0;
00059         }
00060 
00061         public long getStart (int index) {
00062                 splay (index);
00063                 return getLeft (rootIndex) != TreeStore.NULL_REF ? getLength (getLeft (rootIndex))
00064                                 : 0;
00065         }
00066 
00067         public int insert (Key val, long point) {
00068                 long [] position = new long [1];
00069                 position[0] = point;
00070                 int newIndex = ts.createGistNode ();
00071 
00072                 setKey (newIndex, (Key) val.copy ()); // newNode.setKey((Key)val.copy());
00073                 setLength (newIndex, val.getLength ()); // newNode.setLength(val.getLength());
00074                 setSeqLength (newIndex, val.getSeqLength ()); // newNode.setSeqLength(val.getSeqLength());
00075 
00076                 // just insert new_node as root if the tree is empty
00077                 if (rootIndex == TreeStore.NULL_REF) {
00078                         rootIndex = newIndex;
00079                         return rootIndex;
00080                 }
00081 
00082                 int insertionIndex = recursiveFind (rootIndex, position);
00083 
00084                 // insert the new node below ins_node
00085                 if (position[0] > 0
00086                                 && position[0] < getKey (insertionIndex).getLength ()) {
00087                         // trunc ins_node, do a right insert of new_node and the right part
00088                         // of ins_node
00089                         int rightIndex = ts.createGistNode ();
00090                         // Question: does inserting two nodes at once violate the splay
00091                         // rules?
00092                         // probably, but i'm not sure it really matters
00093                         setRight (newIndex, rightIndex);
00094                         setParent (rightIndex, newIndex);
00095                         setKey (rightIndex, (Key) getKey (insertionIndex).copy ());
00096 
00097                         // crop the key
00098                         getKey (rightIndex).cropStart (position[0]);
00099                         setLength (rightIndex, val.getLength ());
00100                         setSeqLength (rightIndex, val.getSeqLength ());
00101                         // question: do I need to update new_node.length or will the splay
00102                         // operations
00103                         // take care of it?
00104 
00105                         getKey (insertionIndex).cropEnd (
00106                                         getKey (insertionIndex).getLength () - position[0]);
00107                         setSeqLength (insertionIndex, getKey (insertionIndex)
00108                                         .getSeqLength ());
00109                         setLength (insertionIndex, getKey (insertionIndex).getLength ());
00110                         // now position[0] ought to be equal to ins_node.length,
00111                         // so new_node should get inserted right below it
00112                 }
00113 
00114                 if (position[0] == 0) {
00115                         // find the right-most child of the left subtree and insert there
00116                         int currentIndex = getLeft (insertionIndex);
00117                         if (currentIndex != TreeStore.NULL_REF) {
00118                                 while (getRight (currentIndex) != TreeStore.NULL_REF) {
00119                                         currentIndex = getRight (currentIndex);
00120                                 }
00121                                 // insert to the right of cur_node
00122                                 setRight (currentIndex, newIndex);
00123                                 setParent (newIndex, currentIndex);
00124                         } else {
00125                                 // insert to the left of ins_node
00126                                 setLeft (insertionIndex, newIndex);
00127                                 setParent (newIndex, insertionIndex);
00128                         }
00129                 }
00130 
00131                 if (position[0] >= getKey (insertionIndex).getLength ()) {
00132                         // find the left-most child of the right subtree and insert there
00133                         int currentIndex = getRight (insertionIndex);
00134                         if (currentIndex != TreeStore.NULL_REF) {
00135                                 while (getLeft (currentIndex) != TreeStore.NULL_REF) {
00136                                         currentIndex = getLeft (currentIndex);
00137                                 }
00138                                 // insert to the left of cur_node
00139                                 setLeft (currentIndex, newIndex);
00140                                 setParent (newIndex, currentIndex);
00141                         } else {
00142                                 // insert to the right of ins_node
00143                                 setRight (insertionIndex, newIndex);
00144                                 setParent (newIndex, insertionIndex);
00145                         }
00146                 }
00147                 splay (newIndex);
00148                 return newIndex;
00149         }
00150 
00154         protected void splay (int index) {
00155                 _splay (index);
00156                 rootIndex = index;
00157         }
00158 
00162         public long seqPosToColumn (long seq_index) {
00163                 int l_iter = find_seqindex (seq_index);
00164                 long fk_left_seq_off = getSequenceStart (l_iter);
00165                 long fk_left_col = getStart (l_iter);
00166                 fk_left_col += seq_index - fk_left_seq_off;
00167                 return fk_left_col;
00168         }
00169 
00174         public long columnToSeqPos (long column) {
00175                 int l_iter = find (column);
00176                 long seq_off = getSequenceStart (l_iter);
00177                 long left_col = getStart (l_iter);
00178                 if (column != left_col && getKey (l_iter).getSeqLength () != 0)
00179                         seq_off += column - left_col;
00180                 return seq_off;
00181         }
00182 
00183         private void recalculateLengths (int index) {
00184                 ts.length[index] = ts.key[index].getLength ();
00185                 ts.seqLength[index] = ts.key[index].getSeqLength ();
00186 
00187                 if (ts.right[index] != TreeStore.NULL_REF) {
00188                         ts.length[index] += ts.length[ts.right[index]];
00189                         ts.seqLength[index] += ts.seqLength[ts.right[index]];
00190                         ts.parent[ts.right[index]] = index;
00191                 }
00192 
00193                 if (ts.left[index] != TreeStore.NULL_REF) {
00194                         ts.length[index] += ts.length[ts.left[index]];
00195                         ts.seqLength[index] += ts.seqLength[ts.left[index]];
00196                         ts.parent[ts.left[index]] = index;
00197                 }
00198         }
00199 
00203         public void _splay (int index) {
00204                 // splay operations and node naming convention taken from
00205                 // http://www.cs.nyu.edu/algvis/java/SplayTree.html
00206                 while (ts.parent[index] != TreeStore.NULL_REF) {
00207                         int yIndex = ts.parent[index];
00208                         int zIndex = (ts.parent[yIndex] != TreeStore.NULL_REF) ? ts.parent[yIndex]
00209                                         : yIndex;
00210                         if (ts.left[ts.parent[index]] == index) {
00211                                 if (ts.parent[ts.parent[index]] == TreeStore.NULL_REF) {
00212                                         ts.left[yIndex] = ts.right[index];
00213                                         ts.right[index] = yIndex;
00214                                 } else if (ts.left[ts.parent[ts.parent[index]]] == ts.parent[index]) {
00215                                         // zig-zig
00216                                         ts.left[zIndex] = ts.right[yIndex];
00217                                         ts.left[yIndex] = ts.right[index];
00218                                         ts.right[yIndex] = zIndex;
00219                                         ts.right[index] = yIndex;
00220                                 } else {
00221                                         // zag-zig
00222                                         ts.right[zIndex] = ts.left[index];
00223                                         ts.left[yIndex] = ts.right[index];
00224                                         ts.right[index] = yIndex;
00225                                         ts.left[index] = zIndex;
00226                                 }
00227                         } else {
00228                                 if (ts.right[ts.parent[index]] != index)
00229                                         throw new Error ("Inconsistency error");
00230 
00231                                 // zagging
00232                                 if (ts.parent[ts.parent[index]] == TreeStore.NULL_REF) {
00233                                         // zag
00234                                         ts.right[yIndex] = ts.left[index];
00235                                         ts.left[index] = yIndex;
00236                                 } else if (ts.left[ts.parent[ts.parent[index]]] == ts.parent[index]) {
00237                                         // zig-zag
00238                                         ts.left[zIndex] = ts.right[index];
00239                                         ts.right[yIndex] = ts.left[index];
00240                                         ts.left[index] = yIndex;
00241                                         ts.right[index] = zIndex;
00242                                 } else {
00243                                         // zag-zag
00244                                         ts.right[zIndex] = ts.left[yIndex];
00245                                         ts.right[yIndex] = ts.left[index];
00246                                         ts.left[yIndex] = zIndex;
00247                                         ts.left[index] = yIndex;
00248                                 }
00249                         }
00250                         // update parents and lengths
00251                         ts.parent[index] = ts.parent[zIndex];
00252                         if (ts.parent[index] != TreeStore.NULL_REF) {
00253                                 if (ts.left[ts.parent[index]] == zIndex)
00254                                         ts.left[ts.parent[index]] = index;
00255                                 else
00256                                         ts.right[ts.parent[index]] = index;
00257                         }
00258                         recalculateLengths (zIndex);
00259                         recalculateLengths (yIndex);
00260                         recalculateLengths (index);
00261                 }
00262         }
00263 
00268         public Key increment (int index) {
00269                 // if x has a right child, find its leftmost descendant
00270                 if (ts.right[index] != TreeStore.NULL_REF) {
00271                         int leftie = ts.right[index];
00272                         while (ts.left[leftie] != TreeStore.NULL_REF)
00273                                 leftie = ts.left[leftie];
00274                         return ts.key[leftie];
00275                 }
00276 
00277                 // look for the least ancestor where x was the left descendant
00278                 while (ts.parent[index] != TreeStore.NULL_REF) {
00279                         if (ts.left[ts.parent[index]] == index)
00280                                 return ts.key[ts.parent[index]];
00281                         index = ts.parent[index];
00282                 }
00283 
00284                 // x is already the right-most tree value
00285                 return null;
00286         }
00287 
00301         public int recursiveFind (int index, long [] position) {
00302                 while (index != TreeStore.NULL_REF) {
00303                         long left_len = ts.left[index] != TreeStore.NULL_REF ? ts.length[ts.left[index]]
00304                                         : 0;
00305                         if (ts.left[index] != TreeStore.NULL_REF
00306                                         && position[0] < ts.length[ts.left[index]]) {
00307                                 index = ts.left[index];
00308                                 continue;
00309                         }
00310 
00311                         // it's not part of the left subtree, subtract off the left subtree
00312                         // length
00313                         position[0] -= left_len;
00314                         if (ts.right[index] != TreeStore.NULL_REF
00315                                         && position[0] >= ts.key[index].getLength ()) {
00316                                 position[0] -= ts.key[index].getLength ();
00317                                 index = ts.right[index];
00318                                 continue;
00319                         }
00320 
00321                         // return this node if nothing else can be done
00322                         return index;
00323                 }
00324                 return TreeStore.NULL_REF;
00325         }
00326 
00340         public int recursiveSeqFind (int index, long [] position) {
00341                 while (index != TreeStore.NULL_REF) {
00342                         long left_len = ts.left[index] != TreeStore.NULL_REF ? ts.seqLength[ts.left[index]]
00343                                         : 0;
00344                         if (ts.left[index] != TreeStore.NULL_REF
00345                                         && position[0] < ts.seqLength[ts.left[index]]) {
00346                                 index = ts.left[index];
00347                                 continue;
00348                         }
00349 
00350                         // it's not part of the left subtree, subtract off the left subtree
00351                         // length
00352                         position[0] -= left_len;
00353                         if (ts.right[index] != TreeStore.NULL_REF
00354                                         && position[0] >= ts.key[index].getSeqLength ()) {
00355                                 position[0] -= ts.key[index].getSeqLength ();
00356                                 index = ts.right[index];
00357                                 continue;
00358                         }
00359 
00360                         // return this node if nothing else can be done
00361                         return index;
00362                 }
00363                 return TreeStore.NULL_REF;
00364         }
00365 
00366         public Key getKey (int index) {
00367                 return ts.key[index];
00368         }
00369 
00370         public void setKey (int index, Key k) {
00371                 ts.key[index] = k;
00372         }
00373 
00374         public long getSeqLength (int index) {
00375                 return ts.seqLength[index];
00376         }
00377 
00378         public void setSeqLength (int index, long l) {
00379                 ts.seqLength[index] = l;
00380         }
00381 
00382         public long getLength (int index) {
00383                 return ts.length[index];
00384         }
00385 
00386         public void setLength (int index, long l) {
00387                 ts.length[index] = l;
00388         }
00389 
00390         public int getLeft (int index) {
00391                 return ts.left[index];
00392         }
00393 
00394         public void setLeft (int index, int l) {
00395                 ts.left[index] = l;
00396         }
00397 
00398         public int getRight (int index) {
00399                 return ts.right[index];
00400         }
00401 
00402         public void setRight (int index, int r) {
00403                 ts.right[index] = r;
00404         }
00405 
00406         public int getParent (int index) {
00407                 return ts.parent[index];
00408         }
00409 
00410         public void setParent (int index, int p) {
00411                 ts.parent[index] = p;
00412         }
00413 
00414 }

Generated on Mon Aug 19 06:03:43 2013 for Mauve by doxygen 1.3.6