• API
• FAQ
• Tools
• Archive
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.

Top