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 | template <class T>
|
---|
17 | inline void Swap(T& a, T& b) { T tmp = a; a = b; b = tmp; }
|
---|
18 |
|
---|
19 | template <class I>
|
---|
20 | inline void IterSwap(I a, I b) { if(a != b) Swap(*a, *b); }
|
---|
21 |
|
---|
22 | template <class T>
|
---|
23 | class RelOps
|
---|
24 | {
|
---|
25 | friend bool operator > (const T& a, const T& b) { return b < a; }
|
---|
26 | friend bool operator != (const T& a, const T& b) { return !(a == b); }
|
---|
27 | friend bool operator <= (const T& a, const T& b) { return !(b < a); }
|
---|
28 | friend bool operator >= (const T& a, const T& b) { return !(a < b); }
|
---|
29 |
|
---|
30 | void operator=(const RelOps&) {} // MSC 6.0 empty base class bug fix
|
---|
31 | };
|
---|
32 |
|
---|
33 | template <class U, class V>
|
---|
34 | class AddOps
|
---|
35 | {
|
---|
36 | friend U& operator -= (U& a, const V& b) { a += -b; return a; }
|
---|
37 | friend U operator + (const U& a, const V& b) { U x(a); x += b; return x; }
|
---|
38 | friend U operator - (const U& a, const V& b) { U x(a); x += -b; return x; }
|
---|
39 |
|
---|
40 | void operator=(const AddOps&) {} // MSC 6.0 empty base class bug fix
|
---|
41 | };
|
---|
42 |
|
---|
43 | template <class T>
|
---|
44 | class PostfixOps
|
---|
45 | {
|
---|
46 | friend T operator ++ (T& i, int) { T x = i; ++i; return x; }
|
---|
47 | friend T operator -- (T& i, int) { T x = i; --i; return x; }
|
---|
48 |
|
---|
49 | void operator=(const PostfixOps&) {} // MSC 6.0 empty base class bug fix
|
---|
50 | };
|
---|
51 |
|
---|
52 | template <class T, int (*compare)(T a, T b)>
|
---|
53 | class CompareRelOps
|
---|
54 | {
|
---|
55 | friend bool operator < (T a, T b) { return (*compare)(a, b) < 0; }
|
---|
56 | friend bool operator > (T a, T b) { return (*compare)(a, b) > 0; }
|
---|
57 | friend bool operator == (T a, T b) { return (*compare)(a, b) == 0; }
|
---|
58 | friend bool operator != (T a, T b) { return (*compare)(a, b) != 0; }
|
---|
59 | friend bool operator <= (T a, T b) { return (*compare)(a, b) <= 0; }
|
---|
60 | friend bool operator >= (T a, T b) { return (*compare)(a, b) >= 0; }
|
---|
61 |
|
---|
62 | void operator=(const CompareRelOps&) {} // MSC 6.0 empty base class bug fix
|
---|
63 | };
|
---|
64 |
|
---|
65 | template <class T>
|
---|
66 | inline void Fill(T *dst, const T *lim, const T& x) {
|
---|
67 | while(dst < lim)
|
---|
68 | *dst++ = x;
|
---|
69 | }
|
---|
70 |
|
---|
71 | template <class T>
|
---|
72 | inline void Copy(T *dst, const T *src, const T *lim) {
|
---|
73 | while(src < lim)
|
---|
74 | *dst++ = *src++;
|
---|
75 | }
|
---|
76 |
|
---|
77 | template <class T>
|
---|
78 | inline void Copy(T *dst, const T *src, int n) {
|
---|
79 | Copy(dst, src, src + n);
|
---|
80 | }
|
---|
81 |
|
---|
82 | inline void Fill(char *t, const char *lim, const char& x)
|
---|
83 | { memset(t, x, size_t(lim - t)); }
|
---|
84 | inline void Copy(char *dst, const char *src, const char *lim)
|
---|
85 | { memcpy(dst, src, size_t((byte *)lim - (byte *)src)); }
|
---|
86 |
|
---|
87 | inline void Fill(signed char *t, const signed char *lim, const signed char& x)
|
---|
88 | { memset(t, x, size_t(lim - t)); }
|
---|
89 | inline void Copy(signed char *dst, const signed char *src, const signed char *lim)
|
---|
90 | { memcpy(dst, src, size_t((byte *)lim - (byte *)src)); }
|
---|
91 |
|
---|
92 | inline void Fill(unsigned char *t, const unsigned char *lim, const unsigned char& x)
|
---|
93 | { memset(t, x, size_t(lim - t)); }
|
---|
94 | inline void Copy(unsigned char *dst, const unsigned char *src, const unsigned char *lim)
|
---|
95 | { memcpy(dst, src, size_t((byte *)lim - (byte *)src)); }
|
---|
96 |
|
---|
97 | template <class T>
|
---|
98 | inline void DeepCopyConstruct(void *p, const T& x) {
|
---|
99 | ::new(p) T(x);
|
---|
100 | }
|
---|
101 |
|
---|
102 | template <class T>
|
---|
103 | inline T *DeepCopyNew(const T& x) {
|
---|
104 | return new T(x);
|
---|
105 | }
|
---|
106 |
|
---|
107 | template <class T>
|
---|
108 | inline void ConstructArray(T *t, const T *lim) {
|
---|
109 | while(t < lim)
|
---|
110 | ::new(t++) T;
|
---|
111 | }
|
---|
112 |
|
---|
113 | template <class T>
|
---|
114 | inline void DestroyArray(T *t, const T *lim) {
|
---|
115 | while(t < lim) {
|
---|
116 | t->T::~T();
|
---|
117 | t++;
|
---|
118 | }
|
---|
119 | }
|
---|
120 |
|
---|
121 | template <class T>
|
---|
122 | inline void DeepCopyConstructArray(T *t, const T *s, const T *lim) {
|
---|
123 | while(s < lim)
|
---|
124 | DeepCopyConstruct(t++, *s++);
|
---|
125 | }
|
---|
126 |
|
---|
127 | template <class T>
|
---|
128 | inline void DeepCopyConstructFill(T *t, const T *lim, const T& x) {
|
---|
129 | while(t < lim)
|
---|
130 | DeepCopyConstruct(t++, x);
|
---|
131 | }
|
---|
132 |
|
---|
133 | #ifdef NO_MOVEABLE_CHECK
|
---|
134 |
|
---|
135 | template <class T>
|
---|
136 | inline void AssertMoveable() {}
|
---|
137 |
|
---|
138 | #define MoveableTemplate(T)
|
---|
139 |
|
---|
140 | template <class T>
|
---|
141 | class Moveable
|
---|
142 | {
|
---|
143 | void operator=(const Moveable&) {} // MSC 6.0 empty base class bug fix
|
---|
144 | };
|
---|
145 |
|
---|
146 | #define NTL_MOVEABLE(T)
|
---|
147 |
|
---|
148 | #else
|
---|
149 |
|
---|
150 | template <class T>
|
---|
151 | inline void AssertMoveablePtr(T, T) {}
|
---|
152 |
|
---|
153 | template <class T>
|
---|
154 | inline void AssertMoveable0(T *t) { AssertMoveablePtr(&**t, *t); }
|
---|
155 |
|
---|
156 | template <class T>
|
---|
157 | inline void AssertMoveable(T *t = 0) { if(t) AssertMoveable0(t); }
|
---|
158 |
|
---|
159 | template <class T>
|
---|
160 | struct Moveable {
|
---|
161 | friend void AssertMoveable0(T *) {}
|
---|
162 | void operator=(const Moveable&) {} // MSC 6.0 empty base class bug fix
|
---|
163 | };
|
---|
164 |
|
---|
165 | #if defined(COMPILER_MSC) || defined(COMPILER_GNU)
|
---|
166 | #define NTL_MOVEABLE(T) inline void AssertMoveable0(T *) {}
|
---|
167 | #else
|
---|
168 | #define NTL_MOVEABLE(T) template<> inline void AssertMoveable<T>(T *) {}
|
---|
169 | #endif
|
---|
170 |
|
---|
171 | #endif
|
---|
172 |
|
---|
173 | NTL_MOVEABLE(bool);
|
---|
174 | NTL_MOVEABLE(char);
|
---|
175 | NTL_MOVEABLE(signed char);
|
---|
176 | NTL_MOVEABLE(unsigned char);
|
---|
177 | NTL_MOVEABLE(short);
|
---|
178 | NTL_MOVEABLE(unsigned short);
|
---|
179 | NTL_MOVEABLE(int);
|
---|
180 | NTL_MOVEABLE(unsigned int);
|
---|
181 | NTL_MOVEABLE(long);
|
---|
182 | NTL_MOVEABLE(unsigned long);
|
---|
183 | NTL_MOVEABLE(float);
|
---|
184 | NTL_MOVEABLE(double);
|
---|
185 | NTL_MOVEABLE(void *);
|
---|
186 | NTL_MOVEABLE(const void *);
|
---|
187 |
|
---|
188 | template <class T>
|
---|
189 | class DeepCopyOption {
|
---|
190 | public:
|
---|
191 | friend T& operator<<=(T& dest, const T& src)
|
---|
192 | { (&dest)->T::~T(); ::new(&dest) T(src, 1); return dest; }
|
---|
193 | friend void DeepCopyConstruct(void *dest, const T& src)
|
---|
194 | { ::new (dest) T(src, 0); }
|
---|
195 | friend T *DeepCopyNew(const T& src)
|
---|
196 | { return ::new T(src, 0); }
|
---|
197 | void operator=(const DeepCopyOption&) {} // MSC 6.0 empty base class bug fix
|
---|
198 | };
|
---|
199 |
|
---|
200 | template <class T>
|
---|
201 | class PolyDeepCopyNew
|
---|
202 | {
|
---|
203 | public:
|
---|
204 | friend T *DeepCopyNew(const T& t) { return t.Copy(); }
|
---|
205 | void operator=(const PolyDeepCopyNew&) {} // MSC 6.0 empty base class bug fix
|
---|
206 | };
|
---|
207 |
|
---|
208 | template <class T>
|
---|
209 | class WithDeepCopy : public T {
|
---|
210 | public:
|
---|
211 | WithDeepCopy(const T& a) : T(a, 1) {}
|
---|
212 | WithDeepCopy(const WithDeepCopy& a) : T(a, 1) {}
|
---|
213 | WithDeepCopy& operator=(const WithDeepCopy& a) { (T&)*this <<= a; return *this; }
|
---|
214 | WithDeepCopy(int, pick_ T& a) : T(a) {}
|
---|
215 | WithDeepCopy& operator^=(pick_ T& a) { (T&)*this = a; return *this; }
|
---|
216 | WithDeepCopy() {}
|
---|
217 | };
|
---|
218 |
|
---|
219 | template <class V>
|
---|
220 | class ConstIIterator {
|
---|
221 | protected:
|
---|
222 | const V *cont;
|
---|
223 | int ii;
|
---|
224 | typedef TYPENAME V::ValueType T;
|
---|
225 | struct NP { int dummy; };
|
---|
226 |
|
---|
227 | public:
|
---|
228 | const T& operator*() const { return (*cont)[ii]; }
|
---|
229 | const T *operator->() const { return &(*cont)[ii]; }
|
---|
230 | const T& operator[](int i) const { return (*cont)[ii + i]; }
|
---|
231 |
|
---|
232 | ConstIIterator& operator++() { ++ii; return *this; }
|
---|
233 | ConstIIterator& operator--() { --ii; return *this; }
|
---|
234 | ConstIIterator operator++(int) { ConstIIterator t = *this; ++ii; return t; }
|
---|
235 | ConstIIterator operator--(int) { ConstIIterator t = *this; --ii; return t; }
|
---|
236 |
|
---|
237 | ConstIIterator& operator+=(int d) { ii += d; return *this; }
|
---|
238 | ConstIIterator& operator-=(int d) { ii -= d; return *this; }
|
---|
239 |
|
---|
240 | ConstIIterator operator+(int d) const { return ConstIIterator(cont, ii + d); }
|
---|
241 | ConstIIterator operator-(int d) const { return ConstIIterator(cont, ii - d); }
|
---|
242 |
|
---|
243 | int operator-(const ConstIIterator& b) const { return ii - b.ii; }
|
---|
244 |
|
---|
245 | bool operator==(const ConstIIterator& b) const { return ii == b.ii; }
|
---|
246 | bool operator!=(const ConstIIterator& b) const { return ii != b.ii; }
|
---|
247 | bool operator<(const ConstIIterator& b) const { return ii < b.ii; }
|
---|
248 | bool operator>(const ConstIIterator& b) const { return ii > b.ii; }
|
---|
249 | bool operator<=(const ConstIIterator& b) const { return ii <= b.ii; }
|
---|
250 | bool operator>=(const ConstIIterator& b) const { return ii >= b.ii; }
|
---|
251 |
|
---|
252 | operator bool() const { return ii < 0; }
|
---|
253 |
|
---|
254 | ConstIIterator() {}
|
---|
255 | ConstIIterator(NP *null) { ASSERT(null == NULL); ii = -1; }
|
---|
256 | ConstIIterator(const V& _cont, int ii) : cont(&_cont), ii(ii) {}
|
---|
257 | };
|
---|
258 |
|
---|
259 | template <class V>
|
---|
260 | class IIterator {
|
---|
261 | protected:
|
---|
262 | V *cont;
|
---|
263 | int ii;
|
---|
264 | typedef TYPENAME V::ValueType T;
|
---|
265 | struct NP { int dummy; };
|
---|
266 |
|
---|
267 | public:
|
---|
268 | T& operator*() { return (*cont)[ii]; }
|
---|
269 | T *operator->() { return &(*cont)[ii]; }
|
---|
270 | T& operator[](int i) { return (*cont)[ii + i]; }
|
---|
271 |
|
---|
272 | const T& operator*() const { return (*cont)[ii]; }
|
---|
273 | const T *operator->() const { return &(*cont)[ii]; }
|
---|
274 | const T& operator[](int i) const { return (*cont)[ii + i]; }
|
---|
275 |
|
---|
276 | IIterator& operator++() { ++ii; return *this; }
|
---|
277 | IIterator& operator--() { --ii; return *this; }
|
---|
278 | IIterator operator++(int) { IIterator t = *this; ++ii; return t; }
|
---|
279 | IIterator operator--(int) { IIterator t = *this; --ii; return t; }
|
---|
280 |
|
---|
281 | IIterator& operator+=(int d) { ii += d; return *this; }
|
---|
282 | IIterator& operator-=(int d) { ii -= d; return *this; }
|
---|
283 |
|
---|
284 | IIterator operator+(int d) const { return IIterator(*cont, ii + d); }
|
---|
285 | IIterator operator-(int d) const { return IIterator(*cont, ii - d); }
|
---|
286 |
|
---|
287 | int operator-(const IIterator& b) const { return ii - b.ii; }
|
---|
288 |
|
---|
289 | bool operator==(const IIterator& b) const { return ii == b.ii; }
|
---|
290 | bool operator!=(const IIterator& b) const { return ii != b.ii; }
|
---|
291 | bool operator<(const IIterator& b) const { return ii < b.ii; }
|
---|
292 | bool operator>(const IIterator& b) const { return ii > b.ii; }
|
---|
293 | bool operator<=(const IIterator& b) const { return ii <= b.ii; }
|
---|
294 | bool operator>=(const IIterator& b) const { return ii >= b.ii; }
|
---|
295 |
|
---|
296 | operator bool() const { return ii < 0; }
|
---|
297 |
|
---|
298 | IIterator() {}
|
---|
299 | IIterator(NP *null) { ASSERT(null == NULL); ii = -1; }
|
---|
300 | IIterator(V& _cont, int ii) : cont(&_cont), ii(ii) {}
|
---|
301 | };
|
---|
302 |
|
---|
303 | int Pow2Bound(int i);
|
---|
304 |
|
---|
305 | unsigned memhash(const void *ptr, size_t size);
|
---|
306 |
|
---|
307 | inline unsigned GetHashValue0(const void *ptr) { return (unsigned)(size_t) ptr; }
|
---|
308 | inline unsigned GetHashValue0(char a) { return (unsigned)a; }
|
---|
309 | inline unsigned GetHashValue0(signed char a) { return (unsigned)a; }
|
---|
310 | inline unsigned GetHashValue0(unsigned char a) { return (unsigned)a; }
|
---|
311 | inline unsigned GetHashValue0(short a) { return (unsigned)a; }
|
---|
312 | inline unsigned GetHashValue0(unsigned short a) { return (unsigned)a; }
|
---|
313 | inline unsigned GetHashValue0(int a) { return (unsigned)a; }
|
---|
314 | inline unsigned GetHashValue0(unsigned int a) { return (unsigned)a; }
|
---|
315 | inline unsigned GetHashValue0(long a) { return (unsigned)a; }
|
---|
316 | inline unsigned GetHashValue0(unsigned long a) { return (unsigned)a; }
|
---|
317 | inline unsigned GetHashValue0(bool a) { return (unsigned)a; }
|
---|
318 |
|
---|
319 | unsigned GetHashValue0(const double& a);
|
---|
320 |
|
---|
321 | template <class T>
|
---|
322 | inline unsigned GetHashValue(const T& ptr) { return GetHashValue0(ptr); }
|
---|
323 |
|
---|
324 | struct CombineHash {
|
---|
325 | unsigned hash;
|
---|
326 |
|
---|
327 | public:
|
---|
328 | CombineHash& Put(unsigned h) { hash = ((hash << 4) + hash) ^ h; return *this; }
|
---|
329 |
|
---|
330 | operator unsigned() const { return hash; }
|
---|
331 |
|
---|
332 | CombineHash() { hash = 1234567890U; }
|
---|
333 | CombineHash(unsigned h1) { hash = 1234567890U; Put(h1); }
|
---|
334 | CombineHash(unsigned h1, unsigned h2) { hash = 1234567890U; Put(h1); Put(h2); }
|
---|
335 | CombineHash(unsigned h1, unsigned h2, unsigned h3)
|
---|
336 | { hash = 1234567890U; Put(h1); Put(h2); Put(h3); }
|
---|
337 | CombineHash(unsigned h1, unsigned h2, unsigned h3, unsigned h4)
|
---|
338 | { hash = 1234567890U; Put(h1); Put(h2); Put(h3); Put(h4); }
|
---|
339 | };
|
---|
340 |
|
---|
341 | // Allocation hack. In UPP, there is no need for this, but using NTL outside might benefit
|
---|
342 | // warning - currently there is a bug that results in invalid count/size parameters
|
---|
343 | // dont use them before fixed
|
---|
344 |
|
---|
345 | #ifndef NTL_RAW_ALLOC
|
---|
346 |
|
---|
347 | #define NTL_RAW_ALLOC(size) new byte[(size)]
|
---|
348 | #define NTL_RAW_FREE(ptr, count, size) delete[] (byte *)(ptr)
|
---|
349 |
|
---|
350 | #endif
|
---|
351 |
|
---|
352 | // workaround for broken standard libraries...
|
---|
353 |
|
---|
354 | template <class T> inline const T& ntl_max(const T& a, const T& b) { return a > b ? a : b; }
|
---|
355 |
|
---|
356 | // STL compatibility hacks
|
---|
357 |
|
---|
358 | #define STL_INDEX_COMPATIBILITY(C) \
|
---|
359 | typedef T value_type; \
|
---|
360 | typedef ConstIterator const_iterator; \
|
---|
361 | typedef const T& const_reference; \
|
---|
362 | typedef const T& const_reference; \
|
---|
363 | typedef int size_type; \
|
---|
364 | typedef int difference_type; \
|
---|
365 | const_iterator begin() const { return B::Begin(); } \
|
---|
366 | const_iterator end() const { return B::End(); } \
|
---|
367 | void clear() { B::Clear(); } \
|
---|
368 | size_type size() { return B::GetCount(); } \
|
---|
369 |
|
---|
370 | #define STL_BI_COMPATIBILITY(C) \
|
---|
371 | typedef T value_type; \
|
---|
372 | typedef ConstIterator const_iterator; \
|
---|
373 | typedef const T& const_reference; \
|
---|
374 | typedef const T& const_reference; \
|
---|
375 | typedef int size_type; \
|
---|
376 | typedef int difference_type; \
|
---|
377 | const_iterator begin() const { return Begin(); } \
|
---|
378 | const_iterator end() const { return End(); } \
|
---|
379 | void clear() { Clear(); } \
|
---|
380 | size_type size() { return GetCount(); } \
|
---|
381 | typedef Iterator iterator; \
|
---|
382 | typedef T& reference; \
|
---|
383 | iterator begin() { return Begin(); } \
|
---|
384 | iterator end() { return End(); } \
|
---|
385 |
|
---|
386 | #define STL_MAP_COMPATIBILITY(C) \
|
---|
387 | typedef T value_type; \
|
---|
388 | typedef ConstIterator const_iterator; \
|
---|
389 | typedef const T& const_reference; \
|
---|
390 | typedef const T& const_reference; \
|
---|
391 | typedef int size_type; \
|
---|
392 | typedef int difference_type; \
|
---|
393 | const_iterator begin() const { return B::Begin(); } \
|
---|
394 | const_iterator end() const { return B::End(); } \
|
---|
395 | void clear() { B::Clear(); } \
|
---|
396 | size_type size() { return B::GetCount(); } \
|
---|
397 | typedef Iterator iterator; \
|
---|
398 | typedef T& reference; \
|
---|
399 | iterator begin() { return B::Begin(); } \
|
---|
400 | iterator end() { return B::End(); } \
|
---|
401 |
|
---|
402 | #define STL_VECTOR_COMPATIBILITY(C) \
|
---|
403 | typedef T value_type; \
|
---|
404 | typedef ConstIterator const_iterator; \
|
---|
405 | typedef const T& const_reference; \
|
---|
406 | typedef const T& const_reference; \
|
---|
407 | typedef int size_type; \
|
---|
408 | typedef int difference_type; \
|
---|
409 | const_iterator begin() const { return Begin(); } \
|
---|
410 | const_iterator end() const { return End(); } \
|
---|
411 | void clear() { Clear(); } \
|
---|
412 | size_type size() { return GetCount(); } \
|
---|
413 | typedef Iterator iterator; \
|
---|
414 | typedef T& reference; \
|
---|
415 | iterator begin() { return Begin(); } \
|
---|
416 | iterator end() { return End(); } \
|
---|
417 | reference front() { return (*this)[0]; } \
|
---|
418 | const_reference front() const { return (*this)[0]; } \
|
---|
419 | reference back() { return Top(); } \
|
---|
420 | const_reference back() const { return Top(); } \
|
---|
421 | void push_back(const T& x) { Add(x); } \
|
---|
422 | void pop_back() { Drop(); }
|
---|