1 | ////////////////////////////////////////////////////////////////////////////////
|
---|
2 | // NTL Nonstandard Template Library for C++
|
---|
3 | // Copyright (c) 2003 by Miroslav Fidler, Tomas Rylek
|
---|
4 | //
|
---|
5 | // Created by Miroslav Fidler, Tomas Rylek, cxl@volny.cz
|
---|
6 | //
|
---|
7 | // Permission to use, copy, modify, distribute and sell this software for any
|
---|
8 | // purpose is hereby granted without fee, provided that the above copyright
|
---|
9 | // notice appear in all copies and that both that copyright notice and this
|
---|
10 | // permission notice appear in supporting documentation.
|
---|
11 | // The author makes no representations about the suitability of this software
|
---|
12 | // for any purpose. It is provided "as is"
|
---|
13 | // without express or implied warranty.
|
---|
14 | ////////////////////////////////////////////////////////////////////////////////
|
---|
15 |
|
---|
16 | enum { UNSIGNED_HIBIT = 0x80000000 };
|
---|
17 |
|
---|
18 | class HashBase : Moveable<HashBase> {
|
---|
19 | struct Link : Moveable<Link> {
|
---|
20 | int next;
|
---|
21 | int prev;
|
---|
22 | };
|
---|
23 | Vector<unsigned> hash;
|
---|
24 | mutable Vector<Link> link;
|
---|
25 | mutable int *map;
|
---|
26 | mutable int mask;
|
---|
27 | mutable int unlinked;
|
---|
28 |
|
---|
29 | void LinkBefore(int i, Link& l, int bi) const;
|
---|
30 | void LinkTo(int i, Link& l, int& m) const;
|
---|
31 | void Unlink(int i, Link& l, int& mi);
|
---|
32 | void Unlink(int i, Link& l);
|
---|
33 | int& Maph(unsigned _hash) const;
|
---|
34 | int& Mapi(int i) const;
|
---|
35 | void FinishIndex() const;
|
---|
36 | void DoIndex() const;
|
---|
37 | void Free() const;
|
---|
38 |
|
---|
39 | public:
|
---|
40 | void ClearIndex() const;
|
---|
41 | void Reindex(int n) const;
|
---|
42 | void Reindex() const;
|
---|
43 |
|
---|
44 | void Add(unsigned hash);
|
---|
45 | void Set(int i, unsigned hash);
|
---|
46 | void SetUn(int i, unsigned hash);
|
---|
47 | unsigned operator [] (int i) const { return hash[i]; }
|
---|
48 | int Find(unsigned hash) const;
|
---|
49 | int FindNext(int i) const;
|
---|
50 | int FindLast(unsigned hash) const;
|
---|
51 | int FindPrev(int i) const;
|
---|
52 | int Put(unsigned hash);
|
---|
53 |
|
---|
54 | bool IsUnlinked(int i) const { return hash[i] & UNSIGNED_HIBIT; }
|
---|
55 | void Unlink(int i);
|
---|
56 | Vector<int> GetUnlinked() const;
|
---|
57 |
|
---|
58 | void Remove(int i);
|
---|
59 | void Remove(const int *sorted_list, int count);
|
---|
60 | void Insert(int i, unsigned hash);
|
---|
61 |
|
---|
62 | int GetCount() const { return hash.GetCount(); }
|
---|
63 | void Trim(int count);
|
---|
64 | void Drop(int n);
|
---|
65 | void Clear() { hash.Clear(); ClearIndex(); }
|
---|
66 |
|
---|
67 | void Reserve(int n);
|
---|
68 | void Shrink();
|
---|
69 |
|
---|
70 | #ifdef UPP
|
---|
71 | void Serialize(Stream& s);
|
---|
72 | #endif
|
---|
73 |
|
---|
74 | HashBase();
|
---|
75 | ~HashBase();
|
---|
76 |
|
---|
77 | HashBase(pick_ HashBase& b);
|
---|
78 | void operator=(pick_ HashBase& b);
|
---|
79 | HashBase(const HashBase& b, int);
|
---|
80 | void operator<<=(const HashBase& b);
|
---|
81 |
|
---|
82 | bool IsPicked() const { return hash.IsPicked(); }
|
---|
83 |
|
---|
84 | const unsigned *Begin() const { return hash.Begin(); }
|
---|
85 | const unsigned *End() const { return hash.End(); }
|
---|
86 |
|
---|
87 | void Swap(HashBase& b);
|
---|
88 | };
|
---|
89 |
|
---|
90 | template <class T>
|
---|
91 | struct StdHash {
|
---|
92 | unsigned operator()(const T& x) const { return GetHashValue(x); }
|
---|
93 | };
|
---|
94 |
|
---|
95 | template <class T, class V, class HashFn>
|
---|
96 | class AIndex {
|
---|
97 | public: // GCC bug ?
|
---|
98 | HashFn hashfn;
|
---|
99 |
|
---|
100 | protected:
|
---|
101 | V key;
|
---|
102 | HashBase hash;
|
---|
103 |
|
---|
104 | int Find0(const T& x, int i) const {
|
---|
105 | while(i >= 0 && !(x == key[i])) i = hash.FindNext(i);
|
---|
106 | return i;
|
---|
107 | }
|
---|
108 | int FindB(const T& x, int i) const {
|
---|
109 | while(i >= 0 && !(x == key[i])) i = hash.FindPrev(i);
|
---|
110 | return i;
|
---|
111 | }
|
---|
112 | void Hash();
|
---|
113 |
|
---|
114 | public:
|
---|
115 | void Add(const T& x, unsigned _hash);
|
---|
116 | void Add(const T& x);
|
---|
117 | int FindAdd(const T& key, unsigned _hash);
|
---|
118 | int FindAdd(const T& key);
|
---|
119 | AIndex& operator<<(const T& x) { Add(x); return *this; }
|
---|
120 |
|
---|
121 | int Put(const T& x, unsigned _hash);
|
---|
122 | int Put(const T& x);
|
---|
123 | int FindPut(const T& key, unsigned _hash);
|
---|
124 | int FindPut(const T& key);
|
---|
125 |
|
---|
126 | int Find(const T& x, unsigned _hash) const;
|
---|
127 | int Find(const T& x) const;
|
---|
128 | int FindNext(int i) const;
|
---|
129 | int FindLast(const T& x, unsigned _hash) const;
|
---|
130 | int FindLast(const T& x) const;
|
---|
131 | int FindPrev(int i) const;
|
---|
132 |
|
---|
133 | void Set(int i, const T& x, unsigned _hash);
|
---|
134 | void Set(int i, const T& x);
|
---|
135 |
|
---|
136 | const T& operator[](int i) const { return key[i]; }
|
---|
137 | int GetCount() const { return key.GetCount(); }
|
---|
138 | bool IsEmpty() const { return key.IsEmpty(); }
|
---|
139 |
|
---|
140 | void Clear() { hash.Clear(); key.Clear(); }
|
---|
141 |
|
---|
142 | void ClearIndex() const { hash.ClearIndex(); }
|
---|
143 | void Reindex(int n) const { hash.Reindex(n); }
|
---|
144 | void Reindex() const { hash.Reindex(); }
|
---|
145 |
|
---|
146 | void Unlink(int i) { hash.Unlink(i); }
|
---|
147 | int UnlinkKey(const T& k, unsigned h);
|
---|
148 | int UnlinkKey(const T& k);
|
---|
149 | bool IsUnlinked(int i) const { return hash.IsUnlinked(i); }
|
---|
150 | void Sweep();
|
---|
151 |
|
---|
152 | void Insert(int i, const T& k, unsigned h);
|
---|
153 | void Insert(int i, const T& k);
|
---|
154 | void Remove(int i);
|
---|
155 | void Remove(const int *sorted_list, int count);
|
---|
156 | void Remove(const Vector<int>& sorted_list);
|
---|
157 | int RemoveKey(const T& k, unsigned h);
|
---|
158 | int RemoveKey(const T& k);
|
---|
159 |
|
---|
160 | void Trim(int n) { key.SetCount(n); hash.Trim(n); }
|
---|
161 | void Drop(int n = 1) { key.Drop(n); hash.Drop(n); }
|
---|
162 | const T& Top() const { return key.Top(); }
|
---|
163 |
|
---|
164 | void Reserve(int n) { key.Reserve(n); hash.Reserve(n); }
|
---|
165 | void Shrink() { key.Shrink(); hash.Shrink(); }
|
---|
166 | int GetAlloc() const { return key.GetAlloc(); }
|
---|
167 |
|
---|
168 | #ifdef UPP
|
---|
169 | void Serialize(Stream& s);
|
---|
170 | #endif
|
---|
171 |
|
---|
172 | V PickKeys() { return key; }
|
---|
173 | const V& GetKeys() const { return key; }
|
---|
174 |
|
---|
175 | // Pick assignment & copy. Picked source can only Clear(), ~AIndex(), operator=, operator<<=
|
---|
176 |
|
---|
177 | AIndex& operator=(pick_ V& s);
|
---|
178 | AIndex& operator<<=(const V& s);
|
---|
179 |
|
---|
180 | // Standard container interface
|
---|
181 | typedef T ValueType;
|
---|
182 | typedef typename V::ConstIterator ConstIterator;
|
---|
183 | ConstIterator Begin() const { return key.Begin(); }
|
---|
184 | ConstIterator End() const { return key.End(); }
|
---|
185 | ConstIterator GetIter(int pos) const { return key.GetIter(pos); }
|
---|
186 |
|
---|
187 | void Swap(AIndex& b) { ::Swap(hash, b.hash);
|
---|
188 | ::Swap(key, b.key); }
|
---|
189 | // Optimalizations
|
---|
190 | friend int GetCount(const AIndex& v) { return v.GetCount(); }
|
---|
191 |
|
---|
192 | protected:
|
---|
193 | AIndex(pick_ V& s);
|
---|
194 | AIndex(const V& s, int);
|
---|
195 | AIndex() {}
|
---|
196 | AIndex(const AIndex& s, int);
|
---|
197 | };
|
---|
198 |
|
---|
199 | template <class T, class HashFn = StdHash<T> >
|
---|
200 | class Index : public AIndex<T, Vector<T>, HashFn>,
|
---|
201 | Moveable< Index<T, HashFn> >,
|
---|
202 | DeepCopyOption< Index<T, HashFn > > {
|
---|
203 | typedef AIndex< T, Vector<T>, HashFn > B;
|
---|
204 | public:
|
---|
205 | T Pop() { T x = B::Top(); B::Drop(); return x; }
|
---|
206 |
|
---|
207 | Index() {}
|
---|
208 | Index(pick_ Index& s) : B(s) {}
|
---|
209 | Index(const Index& s, int) : B(s, 1) {}
|
---|
210 | Index(pick_ Vector<T>& s) : B(s) {}
|
---|
211 | Index(const Vector<T>& s, int) : B(s, 1) {}
|
---|
212 |
|
---|
213 | Index& operator=(pick_ Vector<T>& x) { B::operator=(x); return *this; }
|
---|
214 |
|
---|
215 | friend void Swap(Index& a, Index& b) { a.B::Swap(b); }
|
---|
216 |
|
---|
217 | typedef typename B::ConstIterator ConstIterator; // GCC bug (?)
|
---|
218 | STL_INDEX_COMPATIBILITY(Index<T _cm_ HashFn>)
|
---|
219 | };
|
---|
220 |
|
---|
221 | template <class T, class HashFn = StdHash<T> >
|
---|
222 | class ArrayIndex : public AIndex<T, Array<T>, HashFn>,
|
---|
223 | Moveable< ArrayIndex<T, HashFn> >,
|
---|
224 | DeepCopyOption< ArrayIndex<T, HashFn > > {
|
---|
225 | typedef AIndex< T, Array<T>, HashFn > B;
|
---|
226 | public:
|
---|
227 | void Add(const T& x, unsigned _hash) { B::Add(x, _hash); }
|
---|
228 | void Add(const T& x) { B::Add(x); }
|
---|
229 | void Set(int i, const T& x, unsigned _hash) { B::Set(i, x, _hash); }
|
---|
230 | void Set(int i, const T& x) { B::Set(i, x); }
|
---|
231 |
|
---|
232 | void Add(T *newt, unsigned _hash);
|
---|
233 | void Add(T *newt);
|
---|
234 | void Set(int i, T *newt, unsigned _hash);
|
---|
235 | void Set(int i, T *newt);
|
---|
236 |
|
---|
237 | ArrayIndex() {}
|
---|
238 | ArrayIndex(pick_ ArrayIndex& s) : B(s) {}
|
---|
239 | ArrayIndex(const ArrayIndex& s, int) : B(s, 1) {}
|
---|
240 | ArrayIndex(pick_ Array<T>& s) : B(s) {}
|
---|
241 | ArrayIndex(const Array<T>& s, int) : B(s, 1) {}
|
---|
242 |
|
---|
243 | ArrayIndex& operator=(pick_ Array<T>& x) { B::operator=(x); return *this; }
|
---|
244 |
|
---|
245 | friend void Swap(ArrayIndex& a, ArrayIndex& b) { a.B::Swap(b); }
|
---|
246 |
|
---|
247 | typedef typename B::ConstIterator ConstIterator; // GCC bug (?)
|
---|
248 | STL_INDEX_COMPATIBILITY(ArrayIndex<T _cm_ HashFn>)
|
---|
249 | };
|
---|