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
|
#ifndef _SkipListElement_H
#define _SkipListElement_H
/** \file SkipListElement.h
Interface for skip list elements
See William Pugh's paper:
Skip Lists: A Probabilistic Alternative to Balanced Trees
\author: Bruno Grossniklaus, 13.11.97
\version: 1.0
History:
13.11.97; Gro; Version 1.0
*/
#include <SpatialGeneral.h>
#define SKIPLIST_MAXLEVEL 6 // maximum node level
#define NIL 0 // invalid pointer
#ifdef _WIN32
#define KEY_MAX _I64_MAX
#else
#define KEY_MAX LLONG_MAX
#endif
typedef int64 Key; // key type
typedef int Value; // value type
class SkipListElement;
class LINKAGE SkipListElement
{
public:
SkipListElement(long level = 0, Key key = 0, Value value = 0);
/** get key of element */
Key getKey() const { return myKey; };
/** set key of element */
void setKey(Key key) { myKey = key; };
/** get value of element */
Value getValue() const { return myValue; }
/** set value of element */
void setValue(Value value) { myValue = value; }
/** get level of element */
long getLevel() const { return (myLevel); };
/** Set level of element */
void setLevel(long level) { myLevel = level; }
/** get next element in level */
SkipListElement *getElement(long level);
/** set next element in level */
void setElement(long level, SkipListElement *element);
private:
long myLevel; // level of element
Key myKey; // key of element
Value myValue; // value of element
SkipListElement *myNext[SKIPLIST_MAXLEVEL]; // pointers to next elements
};
#endif // _SkipListElement_H
|
