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 
15 class SkipListElement;
16 
17 class LINKAGE SkipList
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
int stat(const QString &path, KDE_struct_stat *buf)
This file is part of the KDE documentation.
Documentation copyright © 1996-2022 The KDE developers.
Generated on Fri Aug 19 2022 03:57:55 by doxygen 1.8.17 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.