SHARE
TWEET

Untitled

prasys May 11th, 2011 123 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***************************  SkipList.java  *********************/
  2.  
  3. import java.util.Random;
  4.  
  5.  
  6.  
  7. public class SkipList<T extends Comparable<? super T>> {
  8.     private int maxLevel;
  9.     private SkipListNode<T>[] root;
  10.     private int[] powers;
  11.     private Random rd = new Random();
  12.     SkipList() {
  13.         this(4);
  14.     }
  15.     SkipList(int i) {
  16.         maxLevel = i;
  17.         root = new SkipListNode[maxLevel];
  18.         powers = new int[maxLevel];
  19.         for (int j = 0; j < maxLevel; j++)
  20.             root[j] = null;
  21.         choosePowers();
  22.     }
  23.     public boolean isEmpty() {
  24.         return root[0] == null;
  25.     }
  26.     public void choosePowers() {
  27.         powers[maxLevel-1] = (2 << (maxLevel-1)) - 1;    // 2^maxLevel - 1
  28.         for (int i = maxLevel - 2, j = 0; i >= 0; i--, j++)
  29.            powers[i] = powers[i+1] - (2 << j);           // 2^(j+1)
  30.     }
  31.     public int chooseLevel() {
  32.         int i, r = Math.abs(rd.nextInt()) % powers[maxLevel-1] + 1;
  33.         for (i = 1; i < maxLevel; i++)
  34.             if (r < powers[i])
  35.                 return i-1; // return a level < the highest level;
  36.         return i-1;         // return the highest level;
  37.     }
  38.     // make sure (with isEmpty()) that search() is called for a nonempty list;
  39.     public boolean search(T key) {
  40.         int lvl;
  41.         SkipListNode<T> prev, curr;            // find the highest nonnull
  42.         for (lvl = maxLevel-1; lvl >= 0 && root[lvl] == null; lvl--); // level;
  43.         prev = curr = root[lvl];
  44.         while (true) {
  45.             if (key.equals(curr.key))          // success if equal;
  46.                  return true;
  47.             else if (key.compareTo(curr.key) < 0) { // if smaller, go down,
  48.                  if (lvl == 0)   {              // if possible
  49.                       return false;
  50.                  }
  51.                  else if (curr == root[lvl]) {  // by one level
  52.                       curr = root[--lvl];
  53.                       System.out.println("Checked node with data: " + curr.key); // print the fking search
  54.                  }// starting from the
  55.                  else {
  56.                          curr = prev.next[--lvl]; // predecessor which
  57.                      System.out.println("Checked node with data: " + curr.key); // print the fking search
  58.  
  59.                  }
  60.             }                                  // can be the root;
  61.             else {                             // if greater,
  62.                  prev = curr;                  // go to the next
  63.                  if (curr.next[lvl] != null) {  // non-null node
  64.                       curr = curr.next[lvl];
  65.                       System.out.println("Checked node with data: " + curr.key); // print the fking search
  66.  
  67.                  }// on the same level
  68.                  else {                        // or to a list on a lower level;
  69.                       for (lvl--; lvl >= 0 && curr.next[lvl] == null; lvl--);
  70.                       if (lvl >= 0) {
  71.                            curr = curr.next[lvl];
  72.                   System.out.println("Checked node with data: " + curr.key); // print the fking search
  73.  
  74.                       }
  75.                       else return false;
  76.                  }
  77.             }
  78.         }
  79.     }
  80.    
  81.    
  82.     public void printAll() {
  83.         int lvl;
  84.         SkipListNode<T> prev, curr;            // find the highest nonnull
  85.         for (lvl = maxLevel-1; lvl >= 0 && root[lvl] == null; lvl--); // level;
  86.         prev = curr = root[0];
  87.         System.out.println(lvl);
  88.        
  89.       //  for (int i=0; i < lvl ; i++) {
  90.        //       prev = curr = root[i];
  91.                 while(curr.next[0] != null ) {
  92.                         System.out.print(curr.key + "-");
  93.                         curr = curr.next[lvl];
  94.         //      }
  95.                 //System.out.println(" ");
  96.         }
  97.     }
  98.     public void delete(T key) {
  99.         SkipListNode<T>[] curr = new SkipListNode[maxLevel];
  100.         SkipListNode<T>[] prev = new SkipListNode[maxLevel];
  101.         SkipListNode<T> newNode;
  102.         int lvl, i;
  103.         curr[maxLevel-1] = root[maxLevel-1];
  104.         prev[maxLevel-1] = null;
  105.         for (lvl = maxLevel - 1; lvl >= 0; lvl--) {
  106.             while (curr[lvl] != null && curr[lvl].key.compareTo(key) < 0) {
  107.                 prev[lvl] = curr[lvl];           // go to the next
  108.                 curr[lvl] = curr[lvl].next[lvl]; // if smaller;
  109.             }
  110.             if (curr[lvl] != null && key.equals(curr[lvl].key)) {
  111.                  for (i = 0; i <= lvl; i++) {
  112.                          
  113.                  }
  114.                 return;  
  115.             }
  116.                                  // include duplicates;
  117.             if (lvl > 0)                         // go one level down
  118.                 if (prev[lvl] == null) {         // if not the lowest
  119.                       curr[lvl-1] = root[lvl-1]; // level, using a link
  120.                       prev[lvl-1] = null;        // either from the root
  121.                 }
  122.                 else {                           // or from the predecessor;
  123.                      curr[lvl-1] = prev[lvl].next[lvl-1];
  124.                      prev[lvl-1] = prev[lvl];
  125.                 }
  126.         }
  127.         lvl = chooseLevel();                // generate randomly level
  128.         newNode = new SkipListNode<T>(key,lvl+1); // for newNode;
  129.         for (i = 0; i <= lvl; i++) {        // initialize next fields of
  130.             newNode.next[i] = curr[i];      // newNode and reset to newNode
  131.             if (prev[i] == null)            // either fields of the root
  132.                  root[i] = newNode;         // or next fields of newNode's
  133.             else prev[i].next[i] = newNode; // predecessors;
  134.         }
  135.     }
  136. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top