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

Revision 1526, 25.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 <class T>
17inline int sgn(T a) { return a > 0 ? 1 : a < 0 ? -1 : 0; }
18
19template <class T>
20inline T tabs(T a) { return (a >= 0 ? a : -a); }
21
22template <class T>
23inline int cmp(const T& a, const T& b) { return a > b ? 1 : a < b ? -1 : 0; }
24
25template <class I>
26void Reverse(I start, I end)
27{
28        if(start != end && --end != start)
29                do
30                        IterSwap(start, end);
31                while(++start != end && --end != start);
32}
33
34template <class C>
35void Reverse(C& container)
36{
37        Reverse(container.Begin(), container.End());
38}
39
40template <class T, class V>
41void Sum(V& sum, T ptr, T end)
42
43{
44        while(ptr != end)
45                sum += *ptr++;
46}
47
48template <class T>
49typename T::ValueType Sum(const T& c)
50{
51        typename T::ValueType sum;
52        Sum(sum, c.Begin(), c.End());
53        return sum;
54}
55
56template <class T>
57typename T::ValueType Sum(const T& c, const typename T::ValueType& init)
58{
59        typename T::ValueType sum = init;
60        Sum(sum, c.Begin(), c.End());
61        return sum;
62}
63
64template <class T>
65typename T::ValueType Sum0(const T& c)
66{
67        typename T::ValueType sum = 0;
68        Sum(sum, c.Begin(), c.End());
69        return sum;
70}
71
72template <class T>
73T MinElement(T ptr, T end)
74{
75        ASSERT(ptr != end);
76        T min = ptr;
77        while(++ptr != end)
78                if(*ptr < *min) min = ptr;
79        return min;
80}
81
82template <class T>
83const typename T::ValueType& Min(const T& c)
84{
85        return *MinElement(c.Begin(), c.End());
86}
87
88template <class T>
89T MaxElement(T ptr, T end)
90{
91        ASSERT(ptr != end);
92        T max = ptr;
93        while(++ptr != end)
94                if(*max < *ptr) max = ptr;
95        return max;
96}
97
98template <class T>
99const typename T::ValueType& Max(const T& c)
100{
101        return *MaxElement(c.Begin(), c.End());
102}
103
104template<class T>
105struct StdEqual
106{
107        bool operator () (const T& a, const T& b) const { return a == b; }
108};
109
110template<class T>
111struct StdLess {
112        bool operator () (const T& a, const T& b) const { return a < b; }
113};
114
115template<class T>
116struct StdGreater
117{
118        bool operator () (const T& a, const T& b) const { return a > b; }
119};
120
121template <class T, class C>
122bool Compare(T ptr1, T end1, T ptr2, T end2, const C& compare)
123{
124        for(; ptr1 != end1 && ptr2 != end2; ++ptr1, ++ptr2)
125                if(!compare(*ptr1, *ptr2)) return false;
126        return ptr1 == end1 && ptr2 == end2;
127}
128
129template <class T, class C>
130bool Compare(const T& c1, const T& c2, const C& compare)
131{
132        return Compare(c1.Begin(), c1.End(), c2.Begin(), c2.End(), compare);
133}
134
135template <class T>
136bool Compare(const T& c1, const T& c2)
137{
138        typedef typename T::ValueType VT;
139        return Compare(c1, c2, StdEqual<VT>());
140}
141
142template <class T, class V, class C>
143T Find(T ptr, T end, const V& value, const C& equal)
144{
145        while(ptr != end) {
146                if(equal(*ptr, value)) return ptr;
147                ptr++;
148        }
149        return NULL;
150}
151
152template <class T, class V>
153T Find(T ptr, T end, const V& value)
154{
155        return Find(ptr, end, value, StdEqual<T>());
156}
157
158template <class T, class V, class C>
159int FindIndex(const T& cont, const V& value, const C& equal)
160{
161        for(int i = 0; i < cont.GetCount(); i++)
162                if(equal(cont[i], value)) return i;
163        return -1;
164}
165
166template <class T, class V>
167int FindIndex(const T& cont, const V& value)
168{
169        typedef typename T::ValueType VT;
170        return FindIndex(cont, value, StdEqual<VT>());
171}
172
173//////////////////////////////////////////////////////////////////////
174// BinFind
175
176template <class I, class K, class L>
177int BinFindIndex(I begin, I end, const K& key, const L& less)
178{
179        if(begin == end)
180                return 0;
181        int min = 0;
182        int max = end - begin;
183
184        while(min < max)
185        {
186                int mid = (max + min) >> 1;
187                if(less(*(begin + mid), key))
188                        min = mid + 1;
189                else
190                        max = mid;
191        }
192        return min;
193}
194
195template <class C, class K, class L>
196inline int BinFindIndex(const C& container, const K& key, const L& less)
197{
198        return BinFindIndex(container.Begin(), container.End(), key, less);
199}
200
201template <class C, class K>
202inline int BinFindIndex(const C& container, const K& key)
203{
204        typedef typename C::ValueType VT;
205        return BinFindIndex(container, key, StdLess<VT>());
206}
207
208template <class I, class K, class L>
209inline I BinFind(I begin, I end, const K& key, const L& less)
210{
211        return begin + BinFindIndex(begin, end, key, less);
212}
213
214template <class C, class K, class L>
215inline typename C::ConstIterator BinFind(const C& container, const K& key, const L& less)
216{
217        return BinFind(container.Begin(), container.End(), key, less);
218}
219
220template <class C, class K>
221inline typename C::ConstIterator BinFind(const C& container, const K& key)
222{
223        typedef typename C::ValueType VT;
224        return BinFind(container, key, StdLess<VT>());
225}
226
227// -------------------------------------------------------------------
228
229template <class C, class T, class L>
230int FindLowerBound(const C& v, int pos, int count, const T& val, const L& less)
231{
232        while(count > 0) {
233                int half = count >> 1;
234                int m = pos + half;
235                if(less(v[m], val)) {
236                        pos = m + 1;
237                        count = count - half - 1;
238                }
239                else
240                        count = half;
241        }
242        return pos;
243}
244
245template <class I, class T, class L>
246I FindLowerBoundIter(I begin, I end, const T& val, const L& less)
247{
248        return begin + FindLowerBound(begin, 0, end - begin, val, less);
249}
250
251template <class I, class T>
252I FindLowerBoundIter(I begin, I end, const T& val)
253{
254        return begin + FindLowerBound(begin, 0, end - begin, val, StdLess<T>());
255}
256
257template <class C, class T, class L>
258int FindLowerBound(const C& v, const T& val, const L& less)
259{
260        return FindLowerBound(v, 0, v.GetCount(), val, less);
261}
262
263template <class C, class T>
264int FindLowerBound(const C& v, const T& val)
265{
266        return FindLowerBound(v, val, StdLess<TYPENAME C::ValueType>());
267}
268
269template <class C, class T, class L>
270int FindUpperBound(const C& v, int pos, int count, const T& val, const L& less)
271{
272        while(count > 0) {
273                int half = count >> 1;
274                int m = pos + half;
275                if(less(val, v[m]))
276                        count = half;
277                else {
278                        pos = m + 1;
279                        count = count - half - 1;
280                }
281        }
282        return pos;
283}
284
285template <class I, class T, class L>
286I FindUpperBoundIter(I begin, I end, const T& val, const L& less)
287{
288        return begin + FindUpperBound(begin, 0, end - begin, val, less);
289}
290
291template <class I, class T>
292I FindUpperBoundIter(I begin, I end, const T& val)
293{
294        return begin + FindUpperBound(begin, 0, end - begin, val, StdLess<T>());
295}
296
297template <class C, class T, class L>
298int FindUpperBound(const C& v, const T& val, const L& less)
299{
300        return FindUpperBound(v, 0, v.GetCount(), val, less);
301}
302
303template <class C, class T>
304int FindUpperBound(const C& v, const T& val)
305{
306        return FindUpperBound(v, val, StdLess<TYPENAME C::ValueType>());
307}
308
309template <class C, class T, class L>
310int FindBinary(const C& v, const T& val, int pos, int count, const L& less)
311{
312        int i = FindLowerBound(v, pos, count, val, less);
313        return i < count && !less(val, v[i]) ? i : -1;
314}
315
316template <class I, class T, class L>
317I FindBinaryIter(I begin, I end, const T& val, const L& less)
318{
319        int q = FindUpperBound(begin, begin, end, val, less);
320        return q < 0 ? NULL : begin + q;
321}
322
323template <class I, class T>
324I FindBinaryIter(I begin, I end, const T& val)
325{
326        return FindBinaryIter(begin, end, val, StdLess<T>());
327}
328
329template <class C, class T, class L>
330int FindBinary(const C& v, const T& val, const L& less)
331{
332        return FindBinary(v, val, 0, v.GetCount(), less);
333}
334
335template <class C, class T>
336int FindBinary(const C& v, const T& val)
337{
338        return FindBinary(v, val, StdLess<TYPENAME C::ValueType>());
339}
340
341//////////////////////////////////////////////////////////////////////
342// BinFindComp
343
344template <class I, class K, class X>
345int BinFindCompIndex(I begin, I end, const K& key, const X& comp)
346{
347        if(begin == end) // empty array
348                return 0;
349        int min = 0;
350        int max = end - begin;
351        while(min < max)
352        {
353                int mid = (max + min) >> 1;
354                if(comp.Compare(key, *(begin + mid)) > 0)
355                        min = mid + 1;
356                else
357                        max = mid;
358        }
359        return min;
360}
361
362template <class C, class K, class X>
363inline int BinFindCompIndex(const C& container, const K& key, const X& comp)
364{
365        return BinFindCompIndex(container.Begin(), container.End(), key, comp);
366}
367
368template <class I, class K, class X>
369inline I BinFindComp(I begin, I end, const K& key, const X& comp)
370{
371        return begin + BinFindCompIndex(begin, end, key, comp);
372}
373
374template <class C, class K, class X>
375inline typename C::ConstIterator BinFindComp(const C& container, const K& key, const X& comp)
376{
377        return BinFindComp(container.Begin(), container.End(), key, comp);
378}
379
380//////////////////////////////////////////////////////////////////////
381// Append
382
383template <class T, class V>
384void Append(T& dst, V ptr, V end)
385{
386        for(; ptr != end; ++ptr)
387                dst.Add(*ptr);
388}
389
390template <class T, class V>
391void Append(T& dst, V ptr, int n)
392{
393        for(; n--; ++ptr)
394                dst.Add(*ptr);
395}
396
397template <class T, class V>
398void Append(T& dst, const V& src)
399{
400        Append(dst, src.Begin(), src.End());
401}
402
403//////////////////////////////////////////////////////////////////////
404// FindAppend::
405
406template <class C, class I>
407C& FindAppend(C& dest, I begin, I end)
408{
409        for(; begin != end; ++begin)
410                dest.FindAdd(*begin);
411        return dest;
412}
413
414//////////////////////////////////////////////////////////////////////
415
416template <class C, class S>
417inline C& FindAppend(C& dest, const S& source)
418{
419        return FindAppend(dest, source.Begin(), source.End());
420}
421
422//////////////////////////////////////////////////////////////////////
423
424template <class C, class L>
425C& AppendSorted(C& dest, const C& src, const L& less)
426{
427        if(src.IsEmpty())
428                return dest;
429        if(dest.IsEmpty())
430        {
431                dest <<= src;
432                return dest;
433        }
434        if(!less(*src, dest.Top()))
435        {
436                dest.Append(src);
437                return dest;
438        }
439        if(!less(*dest, src.Top()))
440        {
441                dest.Insert(0, src);
442                return dest;
443        }
444        int dc = dest.GetCount();
445        int sc = src.GetCount();
446        dest.SetCount(dc + sc);
447        typename C::Iterator de = dest.End();
448        typename C::ConstIterator se = src.End(), pe = dest.GetIter(dc);
449        --se;
450        --pe;
451        for(;;)
452        {
453                if(less(*se, *pe))
454                {
455                        *--de = *pe;
456                        if(pe == dest.Begin())
457                        { // dest items are finished
458                                *--de = *se;
459                                while(se != src.Begin())
460                                        *--de = *--se;
461                                return dest;
462                        }
463                        --pe;
464                }
465                else
466                {
467                        *--de = *se;
468                        if(se == src.Begin())
469                                return dest; // src items are finished, dest items are in place
470                        --se;
471                }
472        }
473        return dest;
474}
475
476//////////////////////////////////////////////////////////////////////
477
478template <class C>
479C& AppendSorted(C& dest, const C& src)
480{
481        typedef typename C::ValueType VT;
482        return AppendSorted(dest, src, StdLess<VT>());
483}
484
485//////////////////////////////////////////////////////////////////////
486
487template <class C, class L>
488C& UnionSorted(C& dest, const C& src, const L& less)
489{
490        if(src.IsEmpty())
491                return dest;
492        if(dest.IsEmpty())
493        {
494                dest <<= src;
495                return dest;
496        }
497        if(less(dest.Top(), *src))
498        {
499                dest.Append(src);
500                return dest;
501        }
502        if(less(src.Top(), *dest))
503        {
504                dest.Insert(0, src);
505                return dest;
506        }
507        int dc = dest.GetCount();
508        int sc = src.GetCount();
509        dest.SetCount(dc + sc);
510        typename C::Iterator de = dest.End();
511        typename C::ConstIterator se = src.End(), pe = dest.GetIter(dc);
512        --se;
513        --pe;
514        for(;;)
515        {
516                if(less(*se, *pe))
517                {
518                        *--de = *pe;
519                        if(pe == dest.Begin())
520                        { // dest items are finished
521                                *--de = *se;
522                                while(se != src.Begin())
523                                        *--de = *--se;
524                                dest.Remove(0, dest.GetIndex(*de));
525                                return dest;
526                        }
527                        --pe;
528                }
529                else
530                {
531                        *--de = *se;
532                        if(!less(*pe, *se))
533                        {
534                                if(pe == dest.Begin())
535                                {
536                                        while(se != src.Begin())
537                                                *--de = *--se;
538                                        dest.Remove(0, dest.GetIndex(*de));
539                                        return dest;
540                                }
541                                --pe;
542                        }
543                        if(se == src.Begin())
544                        {
545                                int pi = (pe - dest.Begin()) + 1;
546                                dest.Remove(pi, (de - dest.Begin()) - pi);
547                                return dest; // src items are finished, dest items are in place
548                        }
549                        --se;
550                }
551        }
552        return dest;
553}
554
555//////////////////////////////////////////////////////////////////////
556
557template <class C>
558C& UnionSorted(C& dest, const C& src)
559{
560        typedef typename C::ValueType VT;
561        return UnionSorted(dest, src, StdLess<VT>());
562}
563
564//////////////////////////////////////////////////////////////////////
565
566template <class C, class L>
567C& RemoveSorted(C& from, const C& what, const L& less)
568{
569        if(from.IsEmpty() || what.IsEmpty() ||
570           less(from.Top(), *what.Begin()) || less(what.Top(), *from.Begin()))
571                return from;
572        typename C::ConstIterator we = what.End(), wp = BinFind(what, from[0], less);
573        if(wp == we)
574                return from;
575        typename C::Iterator fp = from.Begin() + BinFindIndex(from, *wp), fe = from.End(), fd = fp;
576        if(fp == fe)
577        {
578                from.Clear();
579                return from;
580        }
581        for(;;)
582        {
583                while(less(*fp, *wp))
584                {
585                        *fd = *fp;
586                        ++fd;
587                        if(++fp == fe)
588                        {
589                                from.SetCount(fd - from.Begin());
590                                return from;
591                        }
592                }
593                if(less(*wp, *fp))
594                {
595                        do
596                                if(++wp == we)
597                                {
598                                        Copy(fd, fp, fe);
599                                        fd += (fe - fp);
600                                        from.SetCount(fd - from.Begin());
601                                        return from;
602                                }
603                        while(less(*wp, *fp));
604                }
605                else
606                {
607                        const typename C::ValueType& value = *fp;
608                        while(!less(value, *fp))
609                                if(++fp == fe)
610                                {
611                                        from.SetCount(fd - from.Begin());
612                                        return from;
613                                }
614                        do
615                                if(++wp == we)
616                                {
617                                        Copy(fd, fp, fe);
618                                        fd += (fe - fp);
619                                        from.SetCount(fd - from.Begin());
620                                        return from;
621                                }
622                        while(!less(value, *wp));
623                }
624        }
625}
626
627//////////////////////////////////////////////////////////////////////
628
629template <class C>
630C& RemoveSorted(C& from, const C& what)
631{
632        typedef typename C::ValueType VT;
633        return RemoveSorted(from, what, StdLess<VT>());
634}
635
636//////////////////////////////////////////////////////////////////////
637
638template <class D, class S, class L>
639D& IntersectSorted(D& dest, const S& src, const L& less)
640{
641        if(dest.IsEmpty())
642                return dest;
643        if(src.IsEmpty() || less(dest.Top(), src[0]) || less(src.Top(), dest[0]))
644        { // empty source set or disjunct intervals
645                dest.Clear();
646                return dest;
647        }
648        typename S::ConstIterator ss = BinFind(src, dest[0], less), se = src.End();
649        if(ss == se)
650        {
651                dest.Clear();
652                return dest;
653        }
654        typename D::ConstIterator ds = BinFind(dest, src[0], less), de = dest.End();
655        if(ds == de)
656        {
657                dest.Clear();
658                return dest;
659        }
660        typename D::Iterator d = dest.Begin();
661        int count = 0;
662        for(;;)
663        {
664                if(less(*ss, *ds))
665                {
666                        if(++ss == se)
667                                break;
668                }
669                else
670                {
671                        if(!less(*ds, *ss))
672                        {
673                                *d = *ds;
674                                ++d;
675                                count++;
676                        }
677                        if(++ds == de)
678                                break;
679                }
680        }
681        dest.SetCount(count);
682        return dest;
683}
684
685//////////////////////////////////////////////////////////////////////
686
687template <class D, class S>
688D& IntersectSorted(D& dest, const S& src)
689{
690        typedef typename D::ValueType VT;
691        return IntersectSorted(dest, src, StdLess<VT>());
692}
693
694//////////////////////////////////////////////////////////////////////
695// StreamContainer
696
697#ifdef UPP
698template <class T>
699void StreamContainer(Stream& s, T& cont)
700{
701        int n = cont.GetCount();
702        s / n;
703        if(s.IsLoading())
704        {
705                cont.Clear();
706                while(n--)
707                        s % cont.Add();
708        }
709        else
710        {
711                for(typename T::Iterator ptr = cont.Begin(); n--; ++ptr)
712                        s % *ptr;
713        }
714}
715#endif
716//////////////////////////////////////////////////////////////////////
717// ForwardSort
718
719template <class I, class Less>
720void ForwardSort(I begin, I end, const Less& less)
721{
722        if(begin == end)
723                return;
724        I limit = end;
725        --limit;
726        while(!(begin == limit))
727        {
728                for(I best = limit, next = limit, ptr = limit;; best = ptr)
729                        if(!less(*best, *--ptr))
730                        {
731                                if(ptr == begin)
732                                {
733                                        begin = next;
734                                        break;
735                                }
736                        }
737                        else
738                        {
739                                do
740                                {
741                                        if(ptr == begin)
742                                        {
743                                                IterSwap(begin, best);
744                                                ++begin;
745                                                goto NEXT_ITEM;
746                                        }
747                                }
748                                while(less(*best, *--ptr));
749                                if(ptr == begin)
750                                {
751                                        IterSwap(++begin, best);
752                                        ++begin;
753                                        break;
754                                }
755                                next = ptr;
756                                ++next;
757                        }
758        NEXT_ITEM:
759                ;
760        }
761}
762
763//////////////////////////////////////////////////////////////////////
764
765template <class T, class Less>
766void ForwardSort(T& c, const Less& less)
767{
768        ForwardSort(c.Begin(), c.End(), less);
769}
770
771//////////////////////////////////////////////////////////////////////
772
773template <class T>
774void ForwardSort(T& c)
775{
776        typedef typename T::ValueType VT;
777        ForwardSort(c.Begin(), c.End(), StdLess<VT>());
778}
779
780//////////////////////////////////////////////////////////////////////
781
782enum
783{
784        __SORT_THRESHOLD = 16
785};
786
787//////////////////////////////////////////////////////////////////////
788// Sort
789
790template <class I, class Less>
791inline I IterMedian(I x, I y, I z, const Less& less)
792{
793        return less(*x, *y)
794                ? less(*y, *z) ? y : less(*x, *z) ? z : x
795                : less(*x, *z) ? x : less(*y, *z) ? z : y;
796}
797
798template <class I, class Less>
799void Sort(I begin, I end, const Less& less)
800{
801        int count;
802        while((count = end - begin) > __SORT_THRESHOLD)
803        {
804                I b = begin, e = end, m = IterMedian(b, b + (count >> 1), e - 1, less);
805                for(;; ++b)
806                {
807                        while(less(*m, *--e))
808                                ;
809                        while(less(*b, *m))
810                                ++b;
811                        if(!(b < e))
812                                break;
813                        if(m == b) m = e;
814                        else if(m == e) m = b;
815                        IterSwap(b, e);
816                }
817                if(b - begin < end - e)
818                {
819                        Sort(begin, b, less);
820                        begin = b;
821                }
822                else
823                {
824                        Sort(b, end, less);
825                        end = b;
826                }
827        }
828        if(count >= 1)
829                ForwardSort(begin, end, less);
830}
831
832template <class T, class Less>
833void Sort(T& c, int l, int h, const Less& less)
834{
835        Sort(c.GetIter(l), c.GetIter(h), less);
836}
837
838template <class T, class Less>
839void Sort(T& c, const Less& less)
840{
841        Sort(c.Begin(), c.End(), less);
842}
843
844template <class T>
845void Sort(T& c)
846{
847        typedef typename T::ValueType VT;
848        Sort(c.Begin(), c.End(), StdLess<VT>());
849}
850
851//////////////////////////////////////////////////////////////////////
852// IndexSort
853
854template <class II, class VI, class K>
855struct IndexSortIterator
856{
857        typedef IndexSortIterator<II, VI, K> Iter;
858
859        IndexSortIterator(II ii, VI vi) : ii(ii), vi(vi) {}
860
861        Iter&       operator ++ ()               { ++ii; ++vi; return *this; }
862        Iter&       operator -- ()               { --ii; --vi; return *this; }
863        const K&    operator *  () /*const*/     { return *ii; } //!! Fidler's bug in Array::Iterator
864        Iter        operator +  (int i) const    { return Iter(ii + i, vi + i); }
865        Iter        operator -  (int i) const    { return Iter(ii - i, vi - i); }
866        int         operator -  (Iter b) const   { return (int)(ii - b.ii); }
867        bool        operator == (Iter b) const   { return ii == b.ii; }
868        bool        operator <  (Iter b) const   { return ii <  b.ii; }
869        friend void IterSwap    (Iter a, Iter b) { IterSwap(a.ii, b.ii); IterSwap(a.vi, b.vi); }
870
871        II          ii;
872        VI          vi;
873};
874
875template <class II, class VI, class K, class Less>
876inline void __IndexSort(II begin, II end, VI pair, const Less& less, const K *)
877{
878        Sort(IndexSortIterator<II, VI, K>(begin, pair),
879                IndexSortIterator<II, VI, K>(end, pair + (end - begin)),
880                less);
881}
882
883//////////////////////////////////////////////////////////////////////
884
885template <class II, class VI, class Less>
886inline void IndexSort(II begin, II end, VI pair, const Less& less)
887{
888        if(begin != end)
889                __IndexSort(begin, end, pair, less, &*begin);
890}
891
892//////////////////////////////////////////////////////////////////////
893
894template <class KC, class VC, class Less>
895inline void IndexSort(KC& keys, VC& values, const Less& less)
896{
897        typedef typename KC::ValueType KT;
898        ASSERT(keys.GetCount() == values.GetCount());
899        if(keys.GetCount() >= 2)
900                __IndexSort(keys.Begin(), keys.End(), values.Begin(), less, (KT *)0);
901}
902
903//////////////////////////////////////////////////////////////////////
904
905template <class KC, class VC>
906inline void IndexSort(KC& keys, VC& values)
907{
908        typedef typename KC::ValueType KT;
909        if(keys.GetCount() >= 2)
910                __IndexSort(keys.Begin(), keys.End(), values.Begin(), StdLess<KT>(), (KT *)0);
911}
912
913//////////////////////////////////////////////////////////////////////
914
915template <class I, class V>
916struct SortOrderIterator
917{
918        typedef SortOrderIterator<I, V> Iter;
919
920        SortOrderIterator(int *ii, I vi) : ii(ii), vi(vi) {}
921
922        Iter&       operator ++ ()               { ++ii; return *this; }
923        Iter&       operator -- ()               { --ii; return *this; }
924        const V&    operator *  () const         { return *(vi + *ii); }
925        Iter        operator +  (int i) const    { return Iter(ii + i, vi); }
926        Iter        operator -  (int i) const    { return Iter(ii - i, vi); }
927        int         operator -  (Iter b) const   { return int(ii - b.ii); }
928        bool        operator == (Iter b) const   { return ii == b.ii; }
929        bool        operator <  (Iter b) const   { return ii < b.ii; }
930        friend void IterSwap    (Iter a, Iter b) { IterSwap(a.ii, b.ii); }
931
932        int        *ii;
933        I           vi;
934};
935
936template <class I, class V, class Less>
937inline void __SortOrder(int *begin, int *end, I data, const Less& less, const V *)
938{
939        Sort(SortOrderIterator<I, V>(begin, data), SortOrderIterator<I, V>(end, data), less);
940}
941
942//////////////////////////////////////////////////////////////////////
943
944template <class I, class Less>
945inline Vector<int> GetSortOrder(I begin, I end, const Less& less)
946{
947        Vector<int> index;
948        index.SetCount((int)(end - begin));
949        for(int i = index.GetCount(); --i >= 0; index[i] = i)
950                ;
951        __SortOrder(index.Begin(), index.End(), begin, less, &*begin);
952        return index;
953}
954
955//////////////////////////////////////////////////////////////////////
956
957template <class C, class Less>
958inline Vector<int> GetSortOrder(const C& container, const Less& less)
959{
960        return GetSortOrder(container.Begin(), container.End(), less);
961}
962
963//////////////////////////////////////////////////////////////////////
964
965template <class C>
966inline Vector<int> GetSortOrder(const C& container)
967{
968        typedef typename C::ValueType V;
969        return GetSortOrder(container.Begin(), container.End(), StdLess<V>());
970}
971
972//////////////////////////////////////////////////////////////////////
973
974template <class DC, class I, class F>
975void GetFieldContainer(DC& dest, I begin, I end, F field)
976{
977        for(; begin != end; ++begin)
978                dest.Add((*begin).*field);
979}
980
981//////////////////////////////////////////////////////////////////////
982
983template <class DC, class SC, class F>
984void GetFieldContainer(DC& dest, const SC& src, F field)
985{ GetFieldContainer<DC, TYPENAME SC::ConstIterator, F>(dest, src.Begin(), src.End(), field); }
986
987//////////////////////////////////////////////////////////////////////
988
989template <class I, class F, class O, class E>
990I FindField(I begin, I end, F field, const O& object, const E& equal)
991{
992        for(; begin != end && !equal((*begin).*field, object); ++begin)
993                ;
994        return begin;
995}
996
997//////////////////////////////////////////////////////////////////////
998
999template <class I, class F, class O>
1000I FindField(I begin, I end, F field, const O& object)
1001{ return FindField(begin, end, field, object, StdEqual<O>()); }
1002
1003//////////////////////////////////////////////////////////////////////
1004
1005template <class C, class F, class O, class E>
1006int FindFieldIndex(const C& container, F field, const O& object, const E& equal)
1007{
1008        int i = 0;
1009        for(typename C::ConstIterator b = container.Begin(), e = container.End(); b != e; ++b, ++i)
1010                if(equal((*b).*field, object))
1011                        return i;
1012        return -1;
1013}
1014
1015//////////////////////////////////////////////////////////////////////
1016
1017template <class C, class F, class O>
1018int FindFieldIndex(const C& container, F field, const O& object)
1019{ return FindFieldIndex(container, field, object, StdEqual<O>()); }
1020
1021//////////////////////////////////////////////////////////////////////
1022
1023template <class O, class T, class R>
1024class FieldRelationCls {
1025        O        T::*member;
1026        const R& relation;
1027
1028public:
1029        FieldRelationCls(O (T::*member), const R& relation) : member(member), relation(relation) {}
1030        bool operator () (const T& t1, const T& t2) const { return relation(t1.*member, t2.*member); }
1031};
1032
1033template <class O, class T, class R>
1034inline FieldRelationCls<O, T, R> FieldRelation(O (T::*member), const R& relation)
1035{ return FieldRelationCls<O, T, R>(member, relation); }
1036
1037//////////////////////////////////////////////////////////////////////
1038
1039template <class M, class T, class R>
1040class MethodRelationCls {
1041        M        method;
1042        const R& relation;
1043
1044public:
1045        MethodRelationCls(M method, const R& relation) : method(method), relation(relation) {}
1046        bool operator () (const T& t1, const T& t2) const {
1047                return relation((t1.*method)(), (t2.*method)());
1048        }
1049};
1050
1051template <class O, class T, class R>
1052inline MethodRelationCls<O (T::*)(), T, R>
1053        MethodRelation(O (T::*method)(), const R& relation)
1054{ return MethodRelationCls<O (T::*)(), T, R>(method, relation); }
1055
1056template <class O, class T, class R>
1057inline MethodRelationCls<O (T::*)() const, T, R>
1058        MethodRelation(O (T::*method)() const, const R& relation)
1059{ return MethodRelationCls<O (T::*)() const, T, R>(method, relation); }
1060
1061///////////////////////////////////////////////////////////////////////
1062
1063template <class C, class T>
1064void LruAdd(C& lru, T value, int limit = 10) {
1065        int q = FindIndex(lru, value);
1066        if(q >= 0)
1067                lru.Remove(q);
1068        lru.Insert(0, value);
1069        if(lru.GetCount() > limit)
1070                lru.SetCount(limit);
1071}
Note: See TracBrowser for help on using the repository browser.