Download code

Jump to: navigation, search

Back to Skip_list_(C_Plus_Plus)

Download for Windows: single file, zip

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

skip_list.cpp

  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_(C_Plus_Plus)?oldid=18741
 14 */
 15 
 16 #include <iostream>
 17 #include <cstdlib>
 18 #include <ctime>
 19 #include <cmath>
 20 #include <cstring>
 21 using namespace std;
 22 const float P = 0.5;
 23 const int MAX_LEVEL = 6;
 24 template <class T>
 25 struct SkipNode {
 26     T value;
 27     SkipNode<T> **forward; // array of pointers
 28 
 29     SkipNode(int level, const T &value) 
 30     {
 31         forward = new SkipNode<T> * [level + 1];
 32         memset(forward, 0, sizeof(SkipNode<T>*)*(level + 1));
 33         this->value = value;
 34     }
 35     ~SkipNode() 
 36     {
 37         delete [] forward;
 38     }
 39 };
 40 template <class T>
 41 struct SkipSet {
 42     SkipNode<T> *header;
 43     int level;
 44 
 45     SkipSet() {
 46         header = new SkipNode<T>(MAX_LEVEL, T());
 47         level = 0;
 48     }
 49     ~SkipSet() {
 50         delete header;
 51     }
 52     void print() const;
 53     bool contains(const T &) const;
 54     void insert(const T &);
 55     void erase(const T &);
 56 };
 57 float frand() {
 58     return (float) rand() / RAND_MAX;
 59 }
 60 int random_level() {
 61     static bool first = true;
 62 
 63     if (first) {
 64         srand( (unsigned)time( NULL ) );
 65         first = false;
 66     }
 67 
 68     int lvl = (int)(log(frand())/log(1.-P));
 69     return lvl < MAX_LEVEL ? lvl : MAX_LEVEL;
 70 } 
 71 template <class T>
 72 void SkipSet<T>::print() const {
 73     const SkipNode<T> *x = header->forward[0];
 74     cout << "{";
 75     while (x != NULL) {
 76         cout << x->value;
 77         x = x->forward[0];
 78         if (x != NULL)
 79             cout << ",";
 80     }    
 81     cout << "}\n";
 82 }
 83 template <class T>
 84 bool SkipSet<T>::contains(const T &search_value) const {
 85     const SkipNode<T> *x = header;
 86     for (int i = level; i >= 0; i--) {
 87         while (x->forward[i] != NULL && x->forward[i]->value < search_value) {
 88             x = x->forward[i];
 89         }
 90     }
 91     x = x->forward[0];
 92     return x != NULL && x->value == search_value;
 93 }
 94 template <class T>
 95 void SkipSet<T>::insert(const T &value) {
 96     SkipNode<T> *x = header;	
 97     SkipNode<T> *update[MAX_LEVEL + 1];
 98     memset(update, 0, sizeof(SkipNode<T>*)*(MAX_LEVEL + 1));
 99 
100     for (int i = level; i >= 0; i--) {
101         while (x->forward[i] != NULL && x->forward[i]->value < value) {
102             x = x->forward[i];
103         }
104         update[i] = x; 
105     }
106     x = x->forward[0];
107 
108     if (x == NULL || x->value != value) {        
109         int lvl = random_level();
110   
111         if (lvl > level) {
112 	    for (int i = level + 1; i <= lvl; i++) {
113 	        update[i] = header;
114 	    }
115 	    level = lvl;
116 	}
117         x = new SkipNode<T>(lvl, value);
118 	for (int i = 0; i <= lvl; i++) {
119 	    x->forward[i] = update[i]->forward[i];
120 	    update[i]->forward[i] = x;
121 	}
122     }
123 }
124 template <class T>
125 void SkipSet<T>::erase(const T &value) {
126     SkipNode<T> *x = header;	
127     SkipNode<T> *update[MAX_LEVEL + 1];
128     memset(update, 0, sizeof(SkipNode<T>*)*(MAX_LEVEL + 1));
129 
130     for (int i = level; i >= 0; i--) {
131         while (x->forward[i] != NULL && x->forward[i]->value < value) {
132             x = x->forward[i];
133         }
134         update[i] = x; 
135     }
136     x = x->forward[0];
137 
138     if (x->value == value) {
139         for (int i = 0; i <= level; i++) {
140 	    if (update[i]->forward[i] != x)
141 	        break;
142 	    update[i]->forward[i] = x->forward[i];
143 	}
144         delete x;
145         while (level > 0 && header->forward[level] == NULL) {
146 	    level--;
147 	}
148     }
149 }
150 int main() {
151 
152     SkipSet<int> ss;
153     ss.print();
154 
155     ss.insert(5);
156     ss.insert(10);
157     ss.insert(7);
158     ss.insert(7);
159     ss.insert(6);
160     
161     if (ss.contains(7)) {
162         cout << "7 is in the list\n";
163     }
164 
165     ss.print();
166 
167     ss.erase(7);
168     ss.print();
169     
170     if (!ss.contains(7)) {
171         cout << "7 has been deleted\n";
172     }
173 
174     return 0;
175 }
176 


hijacker
hijacker
hijacker
hijacker