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

Revision 1526, 16.6 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
16template <int size>
17void RawVector<size>::Realloc(int newalloc)
18{
19        ASSERT(newalloc >= items);
20        Chk();
21        if(newalloc == alloc) return;
22        Data *newvector = newalloc ? Alloc(newalloc) : NULL;
23        if(vector) {
24                memcpy(newvector, vector, items * sizeof(Data));
25                RawFree();
26        }
27        vector = newvector;
28        alloc = newalloc;
29}
30
31template <int size>
32void RawVector<size>::Expand()
33{
34#ifdef _DEBUG
35        Realloc(ntl_max(2 * alloc, 1));
36#else
37        Realloc(ntl_max(2 * alloc, size == 4 ? 8 : 1));
38#endif
39}
40
41template <int size>
42void RawVector<size>::RawFree()
43{
44        NTL_RAW_FREE(vector, size, sizeof(T));
45}
46
47template <int size>
48void RawVector<size>::Pick(pick_ RawVector& v)
49{
50        vector = v.vector;
51        items = v.items;
52        alloc = v.alloc;
53        SetPicked(v);
54}
55
56template <int size>
57int  RawVector<size>::RawGetIndex(const void *item) const
58{
59        Chk();
60        if(vector == NULL) return -1;
61        int n = (const Data *)item - vector;
62        return n >= 0 && n < items ? n : -1;
63}
64
65template <int size>
66void RawVector<size>::RawSwap(RawVector<size>& b)
67{
68        ::Swap(items, b.items);
69        ::Swap(alloc, b.alloc);
70        ::Swap(vector, b.vector);
71}
72
73template <int size>
74void RawVector<size>::RawReserve(int n)
75{
76        if(n > alloc)
77                Realloc(n);
78}
79
80template <int size>
81void RawVector<size>::RawInsert(int q, int count)
82{
83        Chk();
84        ASSERT(q >= 0 && q <= items);
85        if(!count) return;
86        if(items + count > alloc) {
87                Data *newvector = Alloc(alloc = alloc + ntl_max(alloc, count));
88                if(vector) {
89                        memcpy(newvector, vector, q * sizeof(Data));
90                        memcpy(newvector + q + count, vector + q, (items - q) * sizeof(Data));
91                        RawFree();
92                }
93                vector = newvector;
94        }
95        else
96                memmove(vector + q + count, vector + q, (items - q) * sizeof(Data));
97        items += count;
98}
99
100template <int size>
101void RawVector<size>::RawInsertPick(int i, pick_ RawVector<size>& v) {
102        Chk();
103        v.Chk();
104        if(v.items) {
105                RawInsert(i, v.items);
106                memcpy(vector + i, v.vector, size * v.items);
107        }
108        const_cast< RawVector<size>& >(v).RawFree();
109        SetPicked(v);
110}
111
112// ------------------
113
114template <class T>
115void Vector<T>::Free() {
116        if(B::vector && B::items >= 0)
117                DestroyArray((T *)B::vector, (T *)B::vector + B::items);
118        B::RawFree();
119}
120
121template <class T>
122void Vector<T>::Clear() {
123        if(B::vector && B::items >= 0)
124                SetCount(0);
125        else {
126                B::alloc = B::items = 0;
127                B::vector = NULL;
128        }
129}
130
131template <class T>
132void Vector<T>::__DeepCopy(const Vector& src) {
133        src.Chk();
134        B::items = B::alloc = src.B::items;
135        if(src.vector) {
136                B::vector = B::Alloc(B::alloc);
137                DeepCopyConstructArray((T *)B::vector, (T *)src.B::vector,
138                                       (T *)src.B::vector + B::items);
139        }
140        else
141                B::vector = NULL;
142}
143
144template <class T> inline
145T&  Vector<T>::Add()
146{
147        if(B::items >= B::alloc) Expand();
148        T *p = ::new(B::vector + B::items) T;
149        B::items++;
150        return *p;
151}
152
153template <class T> inline
154void Vector<T>::AddN(int n)
155{
156        ASSERT(n >= 0);
157        if(B::items + n <= B::alloc) {
158                const TYPENAME Vector<T>::Data *w = B::vector + B::items;
159                B::items += n;
160                while(n--)
161                        ::new((void *)w++) T;
162        }
163        else
164                SetCountR(B::items + n);
165}
166
167template <class T>
168void Vector<T>::Trim(int n)
169{
170        ASSERT(n >= 0 && n <= B::items);
171        DestroyArray((T*)B::vector + n, (T*)B::vector + B::items);
172        B::items = n;
173}
174
175template <class T>
176void Vector<T>::SetCount(int n) {
177        Chk();
178        ASSERT(n >= 0);
179        if(n == B::items) return;
180        if(n < B::items)
181                Trim(n);
182        else {
183                if(n > B::alloc) B::Realloc(n);
184                ConstructArray((T*)B::vector + B::items, (T*)B::vector + n);
185                B::items = n;
186        }
187}
188
189template <class T>
190void Vector<T>::SetCount(int n, const T& init) {
191        Chk();
192        ASSERT(n >= 0);
193        if(n == B::items) return;
194        if(n < B::items)
195                DestroyArray((T*)B::vector + n, (T*)B::vector + B::items);
196        else {
197                if(n > B::alloc) B::Realloc(n);
198                DeepCopyConstructFill((T*)B::vector + B::items, (T*)B::vector + n, init);
199        }
200        B::items = n;
201}
202
203template <class T>
204void Vector<T>::SetCountR(int n) {
205        Chk();
206        if(n + B::items > B::alloc)
207                B::Realloc(B::alloc + ntl_max(B::alloc, n));
208        SetCount(n);
209}
210
211template <class T>
212void Vector<T>::SetCountR(int n, const T& init) {
213        Chk();
214        if(n + B::items > B::alloc)
215                B::Realloc(B::alloc + ntl_max(B::alloc, n));
216        SetCount(n, init);
217}
218
219template <class T>
220void Vector<T>::Remove(int q, int count) {
221        Chk();
222        ASSERT(q >= 0 && q <= B::items - count && count >= 0);
223        if(count == 0) return;
224        DestroyArray((T*)B::vector + q, (T*)B::vector + q + count);
225//G++
226        memmove((T*)B::vector + q, (T*)B::vector + q + count, (B::items - q - count) * sizeof(T));
227//      memmove((T*)vector + q, (T*)vector + q + count, (items - q - count) * sizeof(Data));
228        B::items -= count;
229}
230
231template <int size>
232class Data_S_ {
233        byte filler[size];
234};
235
236template <class T>
237void Vector<T>::Remove(const int *sorted_list, int n)
238{
239        Chk();
240        if(!n) return;
241        int pos = *sorted_list;
242        int npos = pos;
243        for(;;) {
244                ASSERT(pos < B::items);
245                if(pos == *sorted_list) {
246                        ((T*)B::vector + pos)->T::~T();
247                        pos++;
248                        sorted_list++;
249                        if(--n == 0) break;
250                        ASSERT(*sorted_list >= pos);
251                }
252                else
253                        *((Data_S_<sizeof(T)>*)B::vector + npos++)
254                                = *((Data_S_<sizeof(T)>*)B::vector + pos++);
255        }
256        while(pos < B::items)
257                *((Data_S_<sizeof(T)>*)B::vector + npos++) = *((Data_S_<sizeof(T)>*)B::vector + pos++);
258        B::items = npos;
259}
260
261template <class T>
262void Vector<T>::Remove(const Vector<int>& v)
263{
264        Remove(v, v.GetCount());
265}
266
267template <class T>
268void Vector<T>::InsertN(int q, int count) {
269        ASSERT(count >= 0);
270        B::RawInsert(q, count);
271        ConstructArray((T*) B::vector + q, (T*)B::vector + q + count);
272}
273
274template <class T>
275void Vector<T>::Insert(int q, const T& x, int count) {
276        if(!count) return;
277        B::RawInsert(q, count);
278        DeepCopyConstructFill((T*)B::vector + q, (T*)B::vector + q + count, x);
279}
280
281template <class T>
282void Vector<T>::Insert(int q, const Vector& x, int offset, int count) {
283        if(!count) return;
284        ASSERT(offset >= 0 && count >= 0 && offset + count <= x.GetCount());
285        B::RawInsert(q, count);
286        DeepCopyConstructArray((T*)B::vector + q, (T*)x.B::vector + offset,
287                               (T*)x.B::vector + offset + count);
288}
289
290template <class T>
291void Vector<T>::Insert(int q, const Vector& x) {
292        if(!x.GetCount()) return;
293        Insert(q, x, 0, x.GetCount());
294}
295
296template <class T>
297void Vector<T>::Set(int i, const T& x, int count) {
298        Chk();
299        ASSERT(i >= 0 && count >= 0);
300        if(count == 0) return;
301        DoIndex(i + count - 1);
302        Fill((T*)B::vector + i, (T*)B::vector + i + count, x);
303}
304
305// ------------------
306
307template <class T>
308void Array<T>::Free() {
309        if(IsPicked()) return;
310        for(int i = 0; i < vector.GetCount(); i++)
311                delete (T *) vector[i];
312}
313
314template <class T>
315void Array<T>::__DeepCopy(const Array<T>& v) {
316        int n = v.GetCount();
317        vector.SetCount(n);
318        for(int i = 0; i < n; i++)
319                vector[i] = DeepCopyNew(v[i]);
320}
321
322template <class T>
323void  Array<T>::Trim(int n)
324{
325        ASSERT(n >= 0 && n <= GetCount());
326        Del(vector.Begin() + n, vector.End());
327        vector.Trim(n);
328}
329
330template <class T>
331void Array<T>::SetCount(int n) {
332        ASSERT(n >= 0);
333        int  lc = vector.GetCount();
334        Del(vector.Begin() + n, vector.End());
335        vector.SetCount(n);
336        Init(vector.Begin() + lc, vector.Begin() + n);
337}
338
339template <class T>
340void Array<T>::SetCount(int n, const T& init) {
341        ASSERT(n >= 0);
342        int  lc = vector.GetCount();
343        Del(vector.Begin() + n, vector.End());
344        vector.SetCount(n);
345        Init(vector.Begin() + lc, vector.Begin() + n, init);
346}
347
348template <class T>
349void Array<T>::SetCountR(int n) {
350        ASSERT(n >= 0);
351        int  lc = vector.GetCount();
352        Del(vector.Begin() + n, vector.End());
353        vector.SetCountR(n);
354        Init(vector.Begin() + lc, vector.Begin() + n);
355}
356
357template <class T>
358void Array<T>::SetCountR(int n, const T& init) {
359        ASSERT(n >= 0);
360        int  lc = vector.GetCount();
361        Del(vector.Begin() + n, vector.End());
362        vector.SetCountR(n);
363        Init(vector.Begin() + lc, vector.Begin() + n, init);
364}
365
366template <class T>
367int  Array<T>::GetIndex(const T& item) const {
368        for(void * const *ptr = vector.Begin(); ptr < vector.End(); ptr++)
369                if(*ptr == (void *)&item) return ptr - vector.Begin();
370        return -1;
371}
372
373template <class T>
374void Array<T>::Move(int i1, int i2) {
375        void *q = vector[i1];
376        vector.Remove(i1);
377        vector.Insert(i2) = q;
378}
379
380template <class T>
381void Array<T>::Remove(int i, int count) {
382        ASSERT(i + count <= GetCount() && count >= 0 && i >= 0);
383        Del(vector.Begin() + i, vector.Begin() + i + count);
384        vector.Remove(i, count);
385}
386
387template <class T>
388void Array<T>::Remove(const int *sorted_list, int n)
389{
390        const int *q = sorted_list;
391        const int *e = sorted_list + n;
392        while(q < e) {
393                ASSERT(*q >= 0 && *q < GetCount());
394                delete (T *)vector[*q++];
395        }
396        vector.Remove(sorted_list, n);
397}
398
399template <class T>
400void Array<T>::Remove(const Vector<int>& sorted_list)
401{
402        Remove(sorted_list, sorted_list.GetCount());
403}
404
405template <class T>
406void Array<T>::Set(int i, const T& x, int count) {
407        ASSERT(i >= 0 && count >= 0);
408        if(i + count >= GetCount())
409                SetCountR(i + count);
410        for(void **ptr = vector.Begin() + i; ptr < vector.Begin() + i + count; ptr++) {
411                delete (T *) *ptr;
412                *ptr = new T(x);
413        }
414}
415
416template <class T>
417void Array<T>::InsertN(int i, int count) {
418        ASSERT(i >= 0 && count >= 0);
419        vector.InsertN(i, count);
420        Init(vector.Begin() + i, vector.Begin() + i + count);
421}
422
423template <class T>
424void Array<T>::Insert(int i, const T& x, int count) {
425        vector.InsertN(i, count);
426        Init(vector.Begin() + i, vector.Begin() + i + count, x);
427}
428
429template <class T>
430void Array<T>::Insert(int i, T *newt) {
431        vector.InsertN(i, 1);
432        vector[i] = newt;
433}
434
435template <class T>
436void Array<T>::Insert(int i, const Array& x) {
437        Insert(i, x, 0, x.GetCount());
438}
439
440template <class T>
441void Array<T>::Insert(int i, const Array& x, int offset, int count) {
442        vector.InsertN(i, count);
443        for(int q = 0; q < count; q++)
444                vector[q + i] = DeepCopyNew(x[q + offset]);
445}
446
447template <class T>
448void Array<T>::InsertPick(int i, pick_ Array& x) {
449        Array xx = x;
450        int cx = xx.GetCount();
451        vector.InsertN(i, cx);
452        for(int q = 0; q < cx; q++)
453                vector[q + i] = x.vector[q];
454}
455
456// ------------------
457
458template <class T, int NBLK>
459Segtor<T, NBLK>::Segtor(const Segtor& s, int) {
460        items = s.items;
461        block.SetCount((items + NBLK - 1) / NBLK);
462        int q = items / NBLK;
463        int r = items % NBLK;
464        int i;
465        for(i = 0; i < q; i++) {
466                T *a = (T *) s.block[i].item;
467                DeepCopyConstructArray((T *) block[i].item, a, a + NBLK);
468        }
469        if(r) {
470                T *a = (T *) s.block[q].item;
471                DeepCopyConstructArray((T *) block[i].item, a, a + r);
472        }
473}
474
475template <class T, int NBLK>
476void Segtor<T, NBLK>::Free() {
477        int q = items / NBLK;
478        int r = items % NBLK;
479        int i;
480        for(i = 0; i < q; i++) {
481                T *a = (T *) block[i].item;
482                DestroyArray(a, a + NBLK);
483        }
484        if(r) {
485                T *a = (T *) block[i].item;
486                DestroyArray(a, a + r);
487        }
488}
489
490template <class T, int NBLK>
491Segtor<T, NBLK>::~Segtor() {
492        if(IsPicked()) return;
493        Free();
494}
495
496template <class T, int NBLK>
497void Segtor<T, NBLK>::DoRange(unsigned beg, unsigned end, void (*fn)(T*, const T*)) {
498        ASSERT(beg <= end);
499        int bblk = beg / NBLK, bidx = beg % NBLK;
500        int eblk = end / NBLK, eidx = end % NBLK;
501        if(eblk == block.GetCount()) {
502                ASSERT(eidx == 0);
503                eblk--;
504                eidx = NBLK;
505        }
506        ASSERT(eblk < block.GetCount());
507        T *tp = (T *)block[bblk].item;
508        if(bblk != eblk) {
509                (*fn)(tp + bidx, tp + NBLK);
510                while(++bblk < eblk) {
511                        tp = (T *)block[bblk].item;
512                        (*fn)(tp, tp + NBLK);
513                }
514                tp = (T *)block[bblk].item;
515                (*fn)(tp, tp + eidx);
516        }
517        else
518                (*fn)(tp + bidx, tp + eidx);
519}
520
521template <class T, int NBLK>
522void Segtor<T, NBLK>::Fill(unsigned beg, unsigned end, const T& x) {
523        ASSERT(beg <= end);
524        int bblk = beg / NBLK, bidx = beg % NBLK;
525        int eblk = end / NBLK, eidx = end % NBLK;
526        if(eblk == block.GetCount()) {
527                ASSERT(eidx == 0);
528                eblk--;
529                eidx = NBLK;
530        }
531        ASSERT(eblk < block.GetCount());
532        T *tp = (T *)block[bblk].item;
533        if(bblk != eblk) {
534                DeepCopyConstructFill(tp + bidx, tp + NBLK, x);
535                while(++bblk < eblk) {
536                        tp = (T *)block[bblk].item;
537                        DeepCopyConstructFill(tp, tp + NBLK, x);
538                }
539                tp = (T *)block[bblk].item;
540                DeepCopyConstructFill(tp, tp + eidx, x);
541        }
542        else
543                DeepCopyConstructFill(tp + bidx, tp + eidx, x);
544}
545
546template <class T, int NBLK>
547void Segtor<T, NBLK>::SetCount(int n) {
548        Del(n);
549        block.SetCount((n + NBLK - 1) / NBLK);
550        Init(n);
551}
552
553template <class T, int NBLK>
554void Segtor<T, NBLK>::SetCount(int n, const T& init) {
555        Del(n);
556        block.SetCount((n + NBLK - 1) / NBLK);
557        Init(n, init);
558}
559
560template <class T, int NBLK>
561void Segtor<T, NBLK>::Clear() {
562        if(!IsPicked())
563                Free();
564        items = 0;
565        block.Clear();
566}
567
568template <class T, int NBLK>
569void Segtor<T, NBLK>::Set(int i, const T& x, int count) {
570        ASSERT(i >= 0 && count >= 0);
571        DoIndex(i + count - 1);
572        Iterator q(*this, i);
573        while(count--)
574                *q++ = x;
575}
576
577template <class T, int NBLK>
578int Segtor<T, NBLK>::GetIndex(const T& item) const {
579        for(int i = 0; i < block.GetCount(); i++) {
580                T *q = (T *) block[i].item;
581                if(&item >= q && &item < q + NBLK)
582                        return &item - q + NBLK * i;
583        }
584        return -1;
585}
586
587// ------------------
588
589template <class T>
590void BiVector<T>::ReAlloc(int newalloc) {
591        ASSERT(items <= newalloc && items >= 0);
592        T *newvector = newalloc ? (T *) NTL_RAW_ALLOC(newalloc * sizeof(T)) : NULL;
593        if(items) {
594                int end = start + items;
595                if(end <= alloc)
596                        memcpy(newvector, vector + start, (end - start) * sizeof(T));
597                else {
598                        memcpy(newvector, vector + start, (alloc - start) * sizeof(T));
599                        memcpy(newvector + alloc - start, vector, (end - alloc) * sizeof(T));
600                }
601                NTL_RAW_FREE(vector, items, sizeof(T));
602        }
603        vector = newvector;
604        alloc = newalloc;
605        start = 0;
606}
607
608template <class T>
609void BiVector<T>::DeepCopy0(const BiVector& src) {
610        alloc = items = src.items;
611        vector = alloc ? (T *) NTL_RAW_ALLOC((alloc * sizeof(T))) : NULL;
612        if(items) {
613                int end = src.start + src.items;
614                if(end <= src.alloc)
615                        DeepCopyConstructArray(vector, src.vector + src.start, src.vector + end);
616                else {
617                        DeepCopyConstructArray(vector, src.vector + src.start, src.vector + src.alloc);
618                        DeepCopyConstructArray(vector + src.alloc - src.start, src.vector,
619                                                   src.vector + end - src.alloc);
620                }
621        }
622        start = 0;
623}
624
625template <class T>
626void BiVector<T>::Clear() {
627        Free();
628        start = items = alloc = 0;
629
630        vector = NULL;
631}
632
633template <class T>
634void BiVector<T>::Add0() {
635        ASSERT(items >= 0);
636        if(items >= alloc)
637                ReAlloc(ntl_max(2 * items, 4));
638        items++;
639}
640
641template <class T>
642void BiVector<T>::Shrink() {
643        ASSERT(items >= 0);
644        if(items < alloc)
645                ReAlloc(items);
646}
647
648template <class T>
649void BiVector<T>::Reserve(int n) {
650        ASSERT(items >= 0);
651        n += items;
652        if(n > alloc)
653                ReAlloc(n);
654}
655
656template <class T>
657void BiVector<T>::Free() {
658        if(vector && items >= 0) {
659                int end = start + items;
660                if(end <= alloc)
661                        DestroyArray(vector + start, vector + end);
662                else {
663                        DestroyArray(vector + start, vector + alloc);
664                        DestroyArray(vector, vector + end - alloc);
665                }
666                NTL_RAW_FREE(vector, items, sizeof(T));
667        }
668}
669
670#ifdef UPP
671template <class T>
672void BiVector<T>::Serialize(Stream& s) {
673        int n = items;
674        s / n;
675        if(s.IsLoading()) {
676                Clear();
677                while(n--)
678                        s % AddTail();
679        }
680        else
681                for(int i = 0; i < items; i++)
682                        s % operator[](i);
683}
684#endif
685
686// ------------------
687
688template <class T>
689void BiArray<T>::Free() {
690        if(!bv.IsPicked())
691                for(int i = 0; i < GetCount(); i++)
692                        delete (T *) bv[i];
693}
694
695template <class T>
696void BiArray<T>::DeepCopy0(const BiArray<T>& v) {
697        int n = v.GetCount();
698        bv.Clear();
699        bv.Reserve(v.GetCount());
700        for(int i = 0; i < n; i++)
701                bv.AddTail() = DeepCopyNew(v[i]);
702}
703
704#ifdef UPP
705template <class T>
706void BiArray<T>::Serialize(Stream& s) {
707        int n = bv.GetCount();
708        s / n;
709        if(s.IsLoading()) {
710                Clear();
711                while(n--)
712                        s % AddTail();
713        }
714        else
715                for(int i = 0; i < bv.GetCount(); i++)
716                        s % operator[](i);
717}
718#endif
Note: See TracBrowser for help on using the repository browser.