Download code

Jump to: navigation, search

Back to Skip_list_(Java)

Download for Windows: single file, zip

Download for UNIX: single file, zip, tar.gz, tar.bz2

SkipSet.java

  1 /* The authors of this work have released all rights to it and placed it
  2 in the public domain under the Creative Commons CC0 1.0 waiver
  3 (http://creativecommons.org/publicdomain/zero/1.0/).
  4 
  5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 12 
 13 Retrieved from: http://en.literateprograms.org/Skip_list_(Java)?oldid=15959
 14 */
 15 
 16 class SkipNode<E extends Comparable<? super E>>
 17 {
 18     public final E value;
 19     public final SkipNode<E>[] forward; // array of pointers
 20 
 21     @SuppressWarnings("unchecked")
 22     public SkipNode(int level, E value) 
 23     {
 24         forward = new SkipNode[level + 1];
 25         this.value = value;
 26     }
 27 }
 28 
 29 public class SkipSet<E extends Comparable<? super E>>
 30 {
 31     public static final double P = 0.5;
 32     public static final int MAX_LEVEL = 6;
 33     public static int randomLevel() {
 34         int lvl = (int)(Math.log(1.-Math.random())/Math.log(1.-P));
 35         return Math.min(lvl, MAX_LEVEL);
 36     } 
 37 
 38     public final SkipNode<E> header = new SkipNode<E>(MAX_LEVEL, null);
 39     public int level = 0;
 40 
 41     public String toString()
 42     {
 43         StringBuilder sb = new StringBuilder();
 44         sb.append("{");
 45         SkipNode<E> x = header.forward[0];
 46         while (x != null) {
 47             sb.append(x.value);
 48             x = x.forward[0];
 49             if (x != null)
 50                 sb.append(",");
 51         }    
 52         sb.append("}");
 53         return sb.toString();
 54     }
 55     public boolean contains(E searchValue)
 56     {
 57         SkipNode<E> x = header;
 58         for (int i = level; i >= 0; i--) {
 59 	    while (x.forward[i] != null && x.forward[i].value.compareTo(searchValue) < 0) {
 60 	        x = x.forward[i];
 61 	    }
 62 	}
 63 	x = x.forward[0];
 64         return x != null && x.value.equals(searchValue);
 65     }
 66     @SuppressWarnings("unchecked")
 67     public void insert(E value)
 68     {
 69         SkipNode<E> x = header;	
 70         SkipNode<E>[] update = new SkipNode[MAX_LEVEL + 1];
 71 
 72         for (int i = level; i >= 0; i--) {
 73 	    while (x.forward[i] != null && x.forward[i].value.compareTo(value) < 0) {
 74 	        x = x.forward[i];
 75 	    }
 76 	    update[i] = x; 
 77 	}
 78 	x = x.forward[0];
 79 
 80         if (x == null || !x.value.equals(value)) {        
 81             int lvl = randomLevel();
 82       
 83             if (lvl > level) {
 84 	        for (int i = level + 1; i <= lvl; i++) {
 85 	            update[i] = header;
 86 	        }
 87 	        level = lvl;
 88 	    }
 89             x = new SkipNode<E>(lvl, value);
 90 	    for (int i = 0; i <= lvl; i++) {
 91 	        x.forward[i] = update[i].forward[i];
 92 	        update[i].forward[i] = x;
 93 	    }
 94         }
 95     }
 96     @SuppressWarnings("unchecked")
 97     public void delete(E value)
 98     {
 99         SkipNode<E> x = header;	
100         SkipNode<E>[] update = new SkipNode[MAX_LEVEL + 1];
101 
102         for (int i = level; i >= 0; i--) {
103 	    while (x.forward[i] != null && x.forward[i].value.compareTo(value) < 0) {
104 	        x = x.forward[i];
105 	    }
106 	    update[i] = x; 
107 	}
108 	x = x.forward[0];
109 
110         if (x.value.equals(value)) {
111             for (int i = 0; i <= level; i++) {
112 	        if (update[i].forward[i] != x)
113 	            break;
114 	        update[i].forward[i] = x.forward[i];
115 	    }
116             while (level > 0 && header.forward[level] == null) {
117 	        level--;
118 	    }
119         }
120     }
121 
122     public static void main(String[] args) {
123 
124         SkipSet<Integer> ss = new SkipSet<Integer>();
125         System.out.println(ss);
126 
127         ss.insert(5);
128         ss.insert(10);
129         ss.insert(7);
130         ss.insert(7);
131         ss.insert(6);
132         
133         if (ss.contains(7)) {
134             System.out.println("7 is in the list");
135         }
136 
137         System.out.println(ss);
138 
139         ss.delete(7);
140         System.out.println(ss);
141         
142         if (!ss.contains(7)) {
143             System.out.println("7 has been deleted");
144         }
145     }
146 }
147 


hijacker
hijacker
hijacker
hijacker