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
|
#ifndef _SkipList_H
#define _SkipList_H
/*
SkipList.h
See: Pugh, William, "Skip Lists: A Probabilistic Alternative to Balanced Trees"
*/
#include <limits.h> // INT_MAX
#include <SkipListElement.h>
#define SKIPLIST_NOT_FOUND -1
class SkipListElement;
class LINKAGE SkipList
{
public:
SkipList(float probability = 0.5);
~SkipList();
/// insert new element
void insert(const Key searchKey, const Value value);
/// search element with key NGT searchKey
Key findMAX(const Key searchKey) const;
/// search element with key NLT searchKey
Key findMIN(const Key searchKey) const;
/* ITERATOR SUPPRT */
void reset() { iter = myHeader->getElement(0); }
int step()
{
iter = iter->getElement(0);
return (iter != NIL);
}
Key getkey()
{
if (iter != NIL)
return iter->getKey();
else
return (Key)-1;
}
Value getvalue()
{
if (iter != NIL)
return iter->getValue();
else
return (Value)-1;
}
/// free element with key
void free(const Key searchKey);
void freeRange(const Key loKey, const Key hiKey);
/// statistics;
void stat();
private:
float myProbability;
/// the header (first) list element
SkipListElement *myHeader;
SkipListElement *iter;
long myLength;
};
#endif // _SkipList_H
|
