-
Notifications
You must be signed in to change notification settings - Fork 0
/
skiplist.h
85 lines (67 loc) · 2.16 KB
/
skiplist.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
/**
* SkipList https://en.wikipedia.org/wiki/Skip_list
*
* SkipList with a depth of 1 is similar to a doubly-linked list
* Each item has a p percent chance of being at the next level up
* For our implementation p = 50%
* All elements are inserted at the lowest Depth (1)
* 50% of the elements inserted in Depth = 2
* 50% of 50%, or 25% of the elements inserted in Depth = 3
* and so on
*
* If a Skip List has only 1 level, such as p = 0%
* Insert O(n), Search O(n)
* For Depth > 1
* Insert O(log n), Search O(log n)
* Modifying p allows us to trade off search speed and storage cost
*/
#ifndef ASS4_SKIP_LIST_SKIPLIST_H
#define ASS4_SKIP_LIST_SKIPLIST_H
#include <iostream>
using namespace std;
class SkipList {
// display with level
friend ostream &operator<<(ostream &Out, const SkipList &SkipL);
private:
// private SNode
// defined in .cpp as SkipList::SNode::SNode(int Data) ...
struct SNode {
//SNode constructor initializes Data
explicit SNode(int Data);
int Data;
// link to Next SNode
SNode *Next;
// link to Prev SNode
SNode *Prev;
// link to up one level
SNode *UpLevel;
// link to down one level
SNode *DownLevel;
};
using SNode = struct SNode;
// Depth of SkipList
int Depth;
// array of Depth SNode* objects as FrontGuards linking levels
SNode **FrontGuards;
// array of Depth SNode* objects as RearGuards linking levels
SNode **RearGuards;
// given a SNode, place it before the given NextNode
void addBefore(SNode *NewNode, SNode *NextNode);
// return true 50% of time,
// each node has a 50% chance of being at higher level
bool alsoHigher() const;
public:
// default SkipList has Depth of 1, just one doubly-linked list
explicit SkipList(int Depth = 1);
// destructor
virtual ~SkipList();
// return true if successfully added, no duplicates
bool add(int Data);
// return true if successfully removed
bool remove(int Data);
// return true if found in SkipList
bool contains(int Data);
// find function
SNode* find(int Data, int Level);
};
#endif // ASS4_SKIP_LIST_SKIPLIST_H