source: GTP/trunk/Lib/Geom/shared/GTGeometry/src/libs/ntl/detail/Index.hpp @ 1526

Revision 1526, 12.0 KB checked in by gumbau, 18 years ago (diff)

Updated modules to the new interface and the new simplification algorithm improvements.
Line 
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
16inline void HashBase::LinkTo(int i, Link& l, int& m) const
17{
18        if(m >= 0) {
19                Link& bl = link[m];
20                l.next = m;
21                l.prev = bl.prev;
22                bl.prev = i;
23                link[l.prev].next = i;
24        }
25        else
26                m = l.prev = l.next = i;
27}
28
29inline void HashBase::Unlink(int i, Link& l, int& m)
30{
31        if(i == m) {
32                if(l.next == i) {
33                        m = -1;
34                        return;
35                }
36                m = l.next;
37        }
38        link[l.next].prev = l.prev;
39        link[l.prev].next = l.next;
40}
41
42inline void HashBase::Unlink(int i, Link& l)
43{
44        Unlink(i, l, hash[i] & UNSIGNED_HIBIT ? unlinked : Mapi(i));
45}
46
47inline int& HashBase::Mapi(int i) const
48{
49        return Maph(hash[i]);
50}
51
52inline int& HashBase::Maph(unsigned _hash) const
53{
54        unsigned h = _hash & ~UNSIGNED_HIBIT;
55        return map[int(((h >> 7) ^ (h >> 22) ^ (h >> 15) ^ h) & mask)];
56}
57
58inline void HashBase::DoIndex() const
59{
60        if(hash.GetCount() <= mask)
61                FinishIndex();
62        else
63                Reindex();
64}
65
66inline int HashBase::Find(unsigned _hash) const
67{
68        if(hash.GetCount() == 0) return -1;
69        if(link.GetCount() < hash.GetCount())
70                DoIndex();
71        return Maph(_hash & ~UNSIGNED_HIBIT);
72}
73
74inline int HashBase::FindNext(int i) const
75{
76        if(link.GetCount() < hash.GetCount())
77                DoIndex();
78        int q = link[i].next;
79        return q == Mapi(i) ? -1 : q;
80}
81
82inline int HashBase::FindLast(unsigned _hash) const
83{
84        if(hash.GetCount() == 0) return - 1;
85        if(link.GetCount() < hash.GetCount())
86                DoIndex();
87        int i = Find(_hash & ~UNSIGNED_HIBIT);
88        return i >= 0 ? link[i].prev : -1;
89}
90
91inline int HashBase::FindPrev(int i) const
92{
93        if(link.GetCount() < hash.GetCount())
94                DoIndex();
95        int q = link[i].prev;
96        return q == link[Mapi(i)].prev ? -1 : q;
97}
98
99inline void HashBase::Unlink(int i)
100{
101        ASSERT(!IsUnlinked(i));
102        hash[i] |= UNSIGNED_HIBIT;
103        if(i < link.GetCount()) {
104                Link& lnk = link[i];
105                Unlink(i, lnk, Mapi(i));
106                LinkTo(i, lnk, unlinked);
107        }
108}
109
110template <class T, class V, class HashFn>
111AIndex<T, V, HashFn>::AIndex(const AIndex& s, int)
112:       key(s.key, 0),
113        hash(s.hash, 0) {}
114
115template <class T, class V, class HashFn>
116void AIndex<T, V, HashFn>::Hash() {
117        for(int i = 0; i < key.GetCount(); i++)
118                hash.Add(hashfn(key[i]));
119}
120
121template <class T, class V, class HashFn>
122AIndex<T, V, HashFn>& AIndex<T, V, HashFn>::operator=(pick_ V& s) {
123        key = s;
124        hash.Clear();
125        Hash();
126        return *this;
127}
128
129template <class T, class V, class HashFn>
130AIndex<T, V, HashFn>& AIndex<T, V, HashFn>::operator<<=(const V& s) {
131        key <<= s;
132        hash.Clear();
133        Hash();
134        return *this;
135}
136
137template <class T, class V, class HashFn>
138AIndex<T, V, HashFn>::AIndex(pick_ V& s) : key(s) {
139        Hash();
140}
141
142template <class T, class V, class HashFn>
143AIndex<T, V, HashFn>::AIndex(const V& s, int) : key(s, 1) {
144        Hash();
145}
146
147template <class T, class V, class HashFn>
148void AIndex<T, V, HashFn>::Add(const T& x, unsigned _hash) {
149        key.Add(x);
150        hash.Add(_hash);
151}
152
153template <class T, class V, class HashFn>
154void AIndex<T, V, HashFn>::Add(const T& x) {
155        Add(x, hashfn(x));
156}
157
158template <class T, class V, class HashFn>
159int  AIndex<T, V, HashFn>::FindAdd(const T& _key, unsigned _hash) {
160        int i = Find(_key, _hash);
161        if(i >= 0) return i;
162        i = key.GetCount();
163        Add(_key, _hash);
164        return i;
165}
166
167template <class T, class V, class HashFn>
168int AIndex<T, V, HashFn>::Put(const T& x, unsigned _hash)
169{
170        int q = hash.Put(_hash);
171        if(q < 0) {
172                q = key.GetCount();
173                Add(x, _hash);
174        }
175        else
176                key[q] = x;
177        return q;
178}
179
180template <class T, class V, class HashFn>
181int AIndex<T, V, HashFn>::Put(const T& x)
182{
183        return Put(x, hashfn(x));
184}
185
186template <class T, class V, class HashFn>
187int  AIndex<T, V, HashFn>::FindPut(const T& _key, unsigned _hash)
188{
189        int i = Find(_key, _hash);
190        if(i >= 0) return i;
191        return Put(_key, _hash);
192}
193
194template <class T, class V, class HashFn>
195int  AIndex<T, V, HashFn>::FindPut(const T& key)
196{
197        return FindPut(key, hashfn(key));
198}
199
200template <class T, class V, class HashFn>
201inline int AIndex<T, V, HashFn>::Find(const T& x, unsigned _hash) const {
202        return Find0(x, hash.Find(_hash));
203}
204
205template <class T, class V, class HashFn>
206int AIndex<T, V, HashFn>::Find(const T& x) const {
207        return Find(x, hashfn(x));
208}
209
210template <class T, class V, class HashFn>
211int AIndex<T, V, HashFn>::FindNext(int i) const {
212        return Find0(key[i], hash.FindNext(i));
213}
214
215template <class T, class V, class HashFn>
216inline int AIndex<T, V, HashFn>::FindLast(const T& x, unsigned _hash) const {
217        return FindB(x, hash.FindLast(_hash));
218}
219
220template <class T, class V, class HashFn>
221int AIndex<T, V, HashFn>::FindLast(const T& x) const {
222        return FindLast(x, hashfn(x));
223}
224
225template <class T, class V, class HashFn>
226int AIndex<T, V, HashFn>::FindPrev(int i) const {
227        return FindB(key[i], hash.FindPrev(i));
228}
229
230template <class T, class V, class HashFn>
231int  AIndex<T, V, HashFn>::FindAdd(const T& key) {
232        return FindAdd(key, hashfn(key));
233}
234
235template <class T, class V, class HashFn>
236void  AIndex<T, V, HashFn>::Set(int i, const T& x, unsigned _hash) {
237        key[i] = x;
238        hash.Set(i, _hash);
239}
240
241template <class T, class V, class HashFn>
242void  AIndex<T, V, HashFn>::Set(int i, const T& x) {
243        Set(i, x, hashfn(x));
244}
245
246#ifdef UPP
247template <class T, class V, class HashFn>
248void AIndex<T, V, HashFn>::Serialize(Stream& s) {
249        if(s.IsLoading()) ClearIndex();
250        key.Serialize(s);
251        hash.Serialize(s);
252}
253#endif
254
255template <class T, class V, class HashFn>
256int AIndex<T, V, HashFn>::UnlinkKey(const T& k, unsigned h)
257{
258        int n = 0;
259        int q = hash.Find(h);
260        while(q >= 0) {
261                int w = q;
262                q = hash.FindNext(q);
263                if(k == key[w]) {
264                        hash.Unlink(w);
265                        n++;
266                }
267        }
268        return n;
269}
270
271template <class T, class V, class HashFn>
272int AIndex<T, V, HashFn>::UnlinkKey(const T& k)
273{
274        return UnlinkKey(k, hashfn(k));
275}
276
277template <class T, class V, class HashFn>
278void AIndex<T, V, HashFn>::Sweep()
279{
280        Vector<int> b = hash.GetUnlinked();
281        Sort(b);
282        Remove(b);
283}
284
285template <class T, class V, class HashFn>
286void AIndex<T, V, HashFn>::Insert(int i, const T& k, unsigned h) {
287        key.Insert(i, k);
288        hash.Insert(i, h);
289}
290
291template <class T, class V, class HashFn>
292void AIndex<T, V, HashFn>::Insert(int i, const T& k) {
293        key.Insert(i, k);
294        hash.Insert(i, hashfn(k));
295}
296
297template <class T, class V, class HashFn>
298void AIndex<T, V, HashFn>::Remove(int i)
299{
300        key.Remove(i);
301        hash.Remove(i);
302}
303
304template <class T, class V, class HashFn>
305void AIndex<T, V, HashFn>::Remove(const int *sorted_list, int count)
306{
307        key.Remove(sorted_list, count);
308        hash.Remove(sorted_list, count);
309}
310
311template <class T, class V, class HashFn>
312void AIndex<T, V, HashFn>::Remove(const Vector<int>& sl)
313{
314        Remove(sl, sl.GetCount());
315}
316
317template <class T, class V, class HashFn>
318int AIndex<T, V, HashFn>::RemoveKey(const T& k, unsigned h)
319{
320        Vector<int> rk;
321        int q = Find(k, h);
322        while(q >= 0) {
323                rk.Add(q);
324                q = FindNext(q);
325        }
326        Remove(rk);
327        return rk.GetCount();
328}
329
330template <class T, class V, class HashFn>
331int AIndex<T, V, HashFn>::RemoveKey(const T& k)
332{
333        return RemoveKey(k, hashfn(k));
334}
335
336// ------------------
337
338template <class T, class HashFn>
339void ArrayIndex<T, HashFn>::Add(T *newt, unsigned _hash) {
340        B::key.Add(newt);
341        B::hash.Add(_hash);
342}
343
344template <class T, class HashFn>
345void ArrayIndex<T, HashFn>::Add(T *newt) {
346        Add(newt, B::hashfn(*newt));
347}
348
349template <class T, class HashFn>
350void ArrayIndex<T, HashFn>::Set(int i, T *newt, unsigned _hash) {
351        B::key.Set(i, newt);
352        B::hash.Set(i, _hash);
353}
354
355template <class T, class HashFn>
356void ArrayIndex<T, HashFn>::Set(int i, T *newt) {
357        Set(i, newt, B::hashfn(*newt));
358}
359
360// --------------------
361
362template <class K, class T, class V, class HashFn>
363int AMap<K, T, V, HashFn>::FindAdd(const K& k) {
364        int i = Find(k);
365        if(i < 0) {
366                i = GetCount();
367                Add(k);
368        }
369        return i;
370}
371
372template <class K, class T, class V, class HashFn>
373int AMap<K, T, V, HashFn>::FindAdd(const K& k, const T& x) {
374        int i = Find(k);
375        if(i < 0) {
376                i = GetCount();
377                Add(k, x);
378        }
379        return i;
380}
381
382template <class K, class T, class V, class HashFn>
383int AMap<K, T, V, HashFn>::FindAddPick(const K& k, pick_ T& x) {
384        int i = Find(k);
385        if(i < 0) {
386                i = GetCount();
387                AddPick(k, x);
388        }
389        return i;
390}
391
392template <class K, class T, class V, class HashFn>
393void AMap<K, T, V, HashFn>::Put(const K& k, const T& x)
394{
395        int i = key.Put(k);
396        if(i < value.GetCount())
397                value[i] = x;
398        else {
399                ASSERT(i == value.GetCount());
400                value.Add(x);
401        }
402}
403
404template <class K, class T, class V, class HashFn>
405void AMap<K, T, V, HashFn>::PutPick(const K& k, pick_ T& x)
406{
407        int i = key.Put(k);
408        if(i < value.GetCount())
409                value[i] = x;
410        else {
411                ASSERT(i == value.GetCount());
412                value.AddPick(x);
413        }
414}
415
416template <class K, class T, class V, class HashFn>
417T&  AMap<K, T, V, HashFn>::Put(const K& k)
418{
419        int i = key.Put(k);
420        if(i < value.GetCount())
421                return value[i];
422        else {
423                ASSERT(i == value.GetCount());
424                return value.Add();
425        }
426}
427
428template <class K, class T, class V, class HashFn>
429int AMap<K, T, V, HashFn>::FindPut(const K& k)
430{
431        int i = Find(k);
432        if(i < 0) {
433                i = key.Put(k);
434                if(i >= value.GetCount()) {
435                        ASSERT(i == value.GetCount());
436                        i = value.GetCount();
437                        value.Add();
438                }
439        }
440        return i;
441}
442
443template <class K, class T, class V, class HashFn>
444int AMap<K, T, V, HashFn>::FindPut(const K& k, const T& init)
445{
446        int i = Find(k);
447        if(i < 0) {
448                i = key.Put(k);
449                if(i >= value.GetCount()) {
450                        ASSERT(i == value.GetCount());
451                        i = value.GetCount();
452                        value.Add(init);
453                }
454                else
455                        value[i] = init;
456        }
457        return i;
458}
459
460template <class K, class T, class V, class HashFn>
461int AMap<K, T, V, HashFn>::FindPutPick(const K& k, pick_ T& init)
462{
463        int i = Find(k);
464        if(i < 0) {
465                i = key.Put(k);
466                if(i >= value.GetCount()) {
467                        ASSERT(i == value.GetCount());
468                        i = value.GetCount();
469                        value.Add(init);
470                }
471                else
472                        value[i] = init;
473        }
474        return i;
475}
476
477template <class K, class T, class V, class HashFn>
478T&  AMap<K, T, V, HashFn>::GetAdd(const K& k) {
479        int i = Find(k);
480        if(i >= 0) return value[i];
481        return Add(k);
482}
483
484template <class K, class T, class V, class HashFn>
485T&  AMap<K, T, V, HashFn>::GetAdd(const K& k, const T& x) {
486        int i = Find(k);
487        if(i >= 0) return value[i];
488        Add(k, x);
489        return value.Top();
490}
491
492template <class K, class T, class V, class HashFn>
493T&  AMap<K, T, V, HashFn>::GetAddPick(const K& k, pick_ T& x) {
494        int i = Find(k);
495        if(i >= 0) return value[i];
496        AddPick(k, x);
497        return value.Top();
498}
499
500template <class K, class T, class V, class HashFn>
501T&  AMap<K, T, V, HashFn>::GetPut(const K& k) {
502        return value[FindAdd(k)];
503}
504
505template <class K, class T, class V, class HashFn>
506T&  AMap<K, T, V, HashFn>::GetPut(const K& k, const T& x) {
507        return value[FindAdd(k, x)];
508}
509
510template <class K, class T, class V, class HashFn>
511T&  AMap<K, T, V, HashFn>::GetPutPick(const K& k, pick_ T& x) {
512        return value[FindAddPick(k, x)];
513}
514
515#ifdef UPP
516template <class K, class T, class V, class HashFn>
517void AMap<K, T, V, HashFn>::Serialize(Stream& s) {
518        int version = 0;
519        s / version % key % value;
520}
521#endif
522
523template <class K, class T, class V, class HashFn>
524int AMap<K, T, V, HashFn>::RemoveKey(const K& k)
525{
526        Vector<int> rk;
527        int q = Find(k);
528        while(q >= 0) {
529                rk.Add(q);
530                q = FindNext(q);
531        }
532        Remove(rk);
533        return rk.GetCount();
534}
Note: See TracBrowser for help on using the repository browser.