Commit | Line | Data |
---|---|---|
e87b4ac1 PR |
1 | // This may look like C code, but it is really -*- C++ -*- |
2 | /* | |
3 | Copyright (C) 1991 Free Software Foundation | |
4 | ||
5 | This file is part of the GNU C++ Library. This library is free | |
6 | software; you can redistribute it and/or modify it under the terms of | |
7 | the GNU Library General Public License as published by the Free | |
8 | Software Foundation; either version 2 of the License, or (at your | |
9 | option) any later version. This library is distributed in the hope | |
10 | that it will be useful, but WITHOUT ANY WARRANTY; without even the | |
11 | implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR | |
12 | PURPOSE. See the GNU Library General Public License for more details. | |
13 | You should have received a copy of the GNU Library General Public | |
14 | License along with this library; if not, write to the Free Software | |
15 | Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. | |
16 | */ | |
17 | ||
18 | /* | |
19 | * Sets implemented via William Pugh SkipList algorithms. | |
20 | * CACM, June 1990, p 668-676. | |
21 | * | |
22 | */ | |
23 | ||
24 | #ifndef _<T>SkipSet_h | |
25 | #ifdef __GNUG__ | |
26 | #pragma interface | |
27 | #endif | |
28 | #define _<T>SkipSet_h 1 | |
29 | ||
30 | #include "<T>.Set.h" | |
31 | ||
32 | #include <values.h> | |
33 | #include <MLCG.h> | |
34 | ||
35 | class <T>SkipSet; | |
36 | class <T>RealSkipSetNode; | |
37 | ||
38 | class <T>SkipSetNode | |
39 | { | |
40 | friend class <T>SkipSet; | |
41 | private: | |
42 | <T>RealSkipSetNode * * forward; | |
43 | <T>SkipSetNode(int size); | |
44 | }; | |
45 | ||
46 | class <T>RealSkipSetNode : public <T>SkipSetNode | |
47 | { | |
48 | friend class <T>SkipSet; | |
49 | private: | |
50 | <T> item; | |
51 | <T>RealSkipSetNode(<T&> h, int size); | |
52 | }; | |
53 | ||
54 | typedef <T>RealSkipSetNode* <T>SkipSetNodePtr; | |
55 | ||
56 | inline <T>SkipSetNode::<T>SkipSetNode(int size) | |
57 | : forward(new <T>SkipSetNodePtr[size+1]) | |
58 | { | |
59 | } | |
60 | ||
61 | inline <T>RealSkipSetNode::<T>RealSkipSetNode(<T&> h, int size) | |
62 | : item(h), | |
63 | <T>SkipSetNode(size) | |
64 | { | |
65 | } | |
66 | ||
67 | class <T>SkipSet : public <T>Set | |
68 | { | |
69 | friend class <T>SkipSetinit; | |
70 | protected: | |
71 | <T>SkipSetNode* header; | |
72 | int level; | |
73 | int max_levels; | |
74 | int randoms_left; | |
75 | long random_bits; | |
76 | ||
77 | static MLCG* gen; | |
78 | int random_level(void); | |
79 | ||
80 | <T>SkipSetNodePtr leftmost(void); | |
81 | <T>SkipSetNodePtr rightmost(void); | |
82 | <T>SkipSetNodePtr pred(<T>SkipSetNodePtr t); | |
83 | <T>SkipSetNodePtr succ(<T>SkipSetNodePtr t); | |
84 | void _kill(void); | |
85 | ||
86 | private: | |
87 | enum { BITS_IN_RANDOM = LONGBITS-1 }; | |
88 | public: | |
89 | <T>SkipSet(long size=DEFAULT_INITIAL_CAPACITY); | |
90 | <T>SkipSet(<T>SkipSet& a); | |
91 | ~<T>SkipSet(); | |
92 | ||
93 | Pix add(<T&> i); | |
94 | void del(<T&> i); | |
95 | int contains(<T&> i); | |
96 | ||
97 | void clear(void); | |
98 | ||
99 | Pix first(void); | |
100 | void next(Pix& i); | |
101 | <T>& operator () (Pix i); | |
102 | Pix seek(<T&> i); | |
103 | ||
104 | Pix last(void); | |
105 | void prev(Pix& i); | |
106 | ||
107 | void operator |= (<T>SkipSet& b); | |
108 | void operator -= (<T>SkipSet& b); | |
109 | void operator &= (<T>SkipSet& b); | |
110 | ||
111 | int operator == (<T>SkipSet& b); | |
112 | int operator != (<T>SkipSet& b); | |
113 | int operator <= (<T>SkipSet& b); | |
114 | ||
115 | int OK(void); | |
116 | }; | |
117 | ||
118 | /* | |
119 | * A little overkill on the inlines. | |
120 | * | |
121 | */ | |
122 | ||
123 | inline <T>SkipSet::~<T>SkipSet(void) | |
124 | { | |
125 | _kill(); | |
126 | delete header; | |
127 | } | |
128 | ||
129 | inline int <T>SkipSet::operator != (<T>SkipSet& b) | |
130 | { | |
131 | return ! (*this == b); | |
132 | } | |
133 | ||
134 | inline <T>SkipSetNodePtr <T>SkipSet::leftmost(void) | |
135 | { | |
136 | return header->forward[0]; | |
137 | } | |
138 | ||
139 | inline <T>SkipSetNodePtr <T>SkipSet::succ(<T>SkipSetNodePtr t) | |
140 | { | |
141 | <T>SkipSetNodePtr result = 0; | |
142 | if (t->forward[0]!=header) result = t->forward[0]; | |
143 | return result; | |
144 | } | |
145 | ||
146 | inline Pix <T>SkipSet::first(void) | |
147 | { | |
148 | return Pix(leftmost()); | |
149 | } | |
150 | ||
151 | inline Pix <T>SkipSet::last(void) | |
152 | { | |
153 | return Pix(rightmost()); | |
154 | } | |
155 | ||
156 | inline void <T>SkipSet::next(Pix& i) | |
157 | { | |
158 | if (i != 0) i = Pix(succ((<T>SkipSetNodePtr)i)); | |
159 | } | |
160 | ||
161 | inline void <T>SkipSet::prev(Pix& i) | |
162 | { | |
163 | if (i != 0) i = Pix(pred((<T>SkipSetNodePtr)i)); | |
164 | } | |
165 | ||
166 | inline <T>& <T>SkipSet::operator () (Pix i) | |
167 | { | |
168 | if (i == 0) error("null Pix"); | |
169 | return ((<T>SkipSetNodePtr)i)->item; | |
170 | } | |
171 | ||
172 | ||
173 | inline int <T>SkipSet::contains(<T&> key) | |
174 | { | |
175 | return seek(key) != 0; | |
176 | } | |
177 | ||
178 | static class <T>SkipSetinit | |
179 | { | |
180 | public: | |
181 | <T>SkipSetinit(); | |
182 | ~<T>SkipSetinit(); | |
183 | private: | |
184 | static int count; | |
185 | } <T>skipSetinit; | |
186 | ||
187 | #endif |