Kstars

SkipList.h
1#ifndef _SkipList_H
2#define _SkipList_H
3
4/*
5 SkipList.h
6
7 See: Pugh, William, "Skip Lists: A Probabilistic Alternative to Balanced Trees"
8
9*/
10#include <limits.h> // INT_MAX
11#include <SkipListElement.h>
12
13#define SKIPLIST_NOT_FOUND -1
14
15class SkipListElement;
16
18{
19 public:
20 SkipList(float probability = 0.5);
21 ~SkipList();
22
23 /// insert new element
24 void insert(const Key searchKey, const Value value);
25 /// search element with key NGT searchKey
26 Key findMAX(const Key searchKey) const;
27 /// search element with key NLT searchKey
28 Key findMIN(const Key searchKey) const;
29 /* ITERATOR SUPPRT */
30 void reset() { iter = myHeader->getElement(0); }
31 int step()
32 {
33 iter = iter->getElement(0);
34 return (iter != NIL);
35 }
36
37 Key getkey()
38 {
39 if (iter != NIL)
40 return iter->getKey();
41 else
42 return (Key)-1;
43 }
44
45 Value getvalue()
46 {
47 if (iter != NIL)
48 return iter->getValue();
49 else
50 return (Value)-1;
51 }
52
53 /// free element with key
54 void free(const Key searchKey);
55 void freeRange(const Key loKey, const Key hiKey);
56
57 /// statistics;
58 void stat();
59
60 private:
61 float myProbability;
62 /// the header (first) list element
63 SkipListElement *myHeader;
64 SkipListElement *iter;
65 long myLength;
66};
67
68#endif // _SkipList_H
Interface for skip list elements See William Pugh's paper: Skip Lists: A Probabilistic Alternative to...
Extends LineList by adding the skip hash to allow the same the data in a LineList to be drawn as a fi...
Definition SkipList.h:18
This file is part of the KDE documentation.
Documentation copyright © 1996-2024 The KDE developers.
Generated on Fri May 24 2024 11:49:22 by doxygen 1.10.0 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.