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 | class BiVector : Moveable< BiVector<T> >, DeepCopyOption< BiVector<T> > {
|
---|
18 | protected:
|
---|
19 | T *vector;
|
---|
20 | int start;
|
---|
21 | mutable int items;
|
---|
22 | int alloc;
|
---|
23 |
|
---|
24 | int EI() const { return (start + items - 1) % alloc; }
|
---|
25 | void ReAlloc(int newalloc);
|
---|
26 | void Add0();
|
---|
27 | void DeepCopy0(const BiVector& src);
|
---|
28 | T *AddHead0() { Add0(); return &vector[start = (start + alloc - 1) % alloc]; }
|
---|
29 | T *AddTail0() { Add0(); return &vector[EI()]; }
|
---|
30 | void Free();
|
---|
31 | void Pick(pick_ BiVector& x) { vector = x.vector; start = x.start; items = x.items;
|
---|
32 | alloc = x.alloc; x.items = -1; }
|
---|
33 | void Copy(T *dst, int start, int count) const;
|
---|
34 |
|
---|
35 | public:
|
---|
36 | int GetCount() const { return items; }
|
---|
37 | bool IsEmpty() const { return items == 0; }
|
---|
38 | void Clear();
|
---|
39 |
|
---|
40 | T& AddHead() { return *new(AddHead0()) T; }
|
---|
41 | T& AddTail() { return *new(AddTail0()) T; }
|
---|
42 | void AddHead(const T& x) { new(AddHead0()) T(x); }
|
---|
43 | void AddTail(const T& x) { new(AddTail0()) T(x); }
|
---|
44 | void AddHeadPick(pick_ T& x) { new(AddHead0()) T(x); }
|
---|
45 | void AddTailPick(pick_ T& x) { new(AddTail0()) T(x); }
|
---|
46 | T& Head() { ASSERT(items > 0); return vector[start]; }
|
---|
47 | T& Tail() { ASSERT(items > 0); return vector[EI()]; }
|
---|
48 | const T& Head() const { ASSERT(items > 0); return vector[start]; }
|
---|
49 | const T& Tail() const { ASSERT(items > 0); return vector[EI()]; }
|
---|
50 | void DropHead() { (&Head())->T::~T(); items--; start = (start + 1) % alloc; }
|
---|
51 | void DropTail() { (&Tail())->T::~T(); items--; }
|
---|
52 |
|
---|
53 | T& operator[](int i) { ASSERT(i >= 0 && i < items);
|
---|
54 | return vector[(start + i) % alloc]; }
|
---|
55 | const T& operator[](int i) const { ASSERT(i >= 0 && i < items);
|
---|
56 | return vector[(start + i) % alloc]; }
|
---|
57 | void Shrink();
|
---|
58 | void Reserve(int n);
|
---|
59 | int GetAlloc() const { return alloc; }
|
---|
60 |
|
---|
61 | #ifdef UPP
|
---|
62 | void Serialize(Stream& s);
|
---|
63 | #endif
|
---|
64 |
|
---|
65 | bool IsPicked() { return items < 0; }
|
---|
66 |
|
---|
67 | BiVector(const BiVector& src, int) { DeepCopy0(src); }
|
---|
68 | BiVector(pick_ BiVector& src) { Pick(src); }
|
---|
69 | void operator=(pick_ BiVector& src) { Free(); Pick(src); }
|
---|
70 | BiVector() { start = items = alloc = 0; vector = NULL; }
|
---|
71 | ~BiVector() { AssertMoveable<T>(); Free(); }
|
---|
72 |
|
---|
73 | typedef ConstIIterator<BiVector> ConstIterator;
|
---|
74 | typedef IIterator<BiVector> Iterator;
|
---|
75 |
|
---|
76 | typedef T ValueType;
|
---|
77 |
|
---|
78 | ConstIterator Begin() const { return ConstIterator(*this, 0); }
|
---|
79 | ConstIterator End() const { return ConstIterator(*this, GetCount()); }
|
---|
80 | ConstIterator GetIter(int pos) const { return ConstIterator(*this, pos); }
|
---|
81 | Iterator Begin() { return Iterator(*this, 0); }
|
---|
82 | Iterator End() { return Iterator(*this, GetCount()); }
|
---|
83 | Iterator GetIter(int pos) { return Iterator(*this, pos); }
|
---|
84 |
|
---|
85 | friend void Swap(BiVector& a, BiVector& b) { ::Swap(a.vector, b.vector);
|
---|
86 | ::Swap(a.start, b.start);
|
---|
87 | ::Swap(a.items, b.items);
|
---|
88 | ::Swap(a.alloc, b.alloc); }
|
---|
89 |
|
---|
90 | STL_BI_COMPATIBILITY(BiVector<T>)
|
---|
91 | };
|
---|
92 |
|
---|
93 | template <class T>
|
---|
94 | class BiArray : Moveable< BiArray<T> >, DeepCopyOption< BiArray<T> > {
|
---|
95 | protected:
|
---|
96 | BiVector<void *> bv;
|
---|
97 |
|
---|
98 | void Free();
|
---|
99 | void DeepCopy0(const BiArray<T>& v);
|
---|
100 |
|
---|
101 | public:
|
---|
102 | int GetCount() const { return bv.GetCount(); }
|
---|
103 | bool IsEmpty() const { return GetCount() == 0; }
|
---|
104 | void Clear() { Free(); bv.Clear(); }
|
---|
105 |
|
---|
106 | T& AddHead() { T *q = new T; bv.AddHead(q); return *q; }
|
---|
107 | T& AddTail() { T *q = new T; bv.AddTail(q); return *q; }
|
---|
108 | void AddHead(const T& x) { bv.AddHead(new T(x)); }
|
---|
109 | void AddTail(const T& x) { bv.AddTail(new T(x)); }
|
---|
110 | void AddHeadPick(pick_ T& x) { bv.AddHead(new T(x)); }
|
---|
111 | void AddTailPick(pick_ T& x) { bv.AddTail(new T(x)); }
|
---|
112 | void AddHead(T *newt) { bv.AddHead(newt); }
|
---|
113 | void AddTail(T *newt) { bv.AddTail(newt); }
|
---|
114 | T& Head() { return *(T *) bv.Head(); }
|
---|
115 | T& Tail() { return *(T *) bv.Tail(); }
|
---|
116 | const T& Head() const { return *(const T *) bv.Head(); }
|
---|
117 | const T& Tail() const { return *(const T *) bv.Tail(); }
|
---|
118 | void DropHead() { delete (T*) bv.Head(); bv.DropHead(); }
|
---|
119 | void DropTail() { delete (T*) bv.Tail(); bv.DropTail(); }
|
---|
120 | T *DetachHead() { T *q = (T*) bv.Head(); bv.DropHead(); return q; }
|
---|
121 | T *DetachTail() { T *q = (T*) bv.Tail(); bv.DropTail(); return q; }
|
---|
122 |
|
---|
123 | T& operator[](int i) { return *(T *) bv[i]; }
|
---|
124 | const T& operator[](int i) const { return *(const T *) bv[i]; }
|
---|
125 |
|
---|
126 | void Shrink() { bv.Shrink(); }
|
---|
127 | void Reserve(int n) { bv.Reserve(n); }
|
---|
128 | int GetAlloc() const { return bv.GetAlloc(); }
|
---|
129 |
|
---|
130 | #ifdef UPP
|
---|
131 | void Serialize(Stream& s);
|
---|
132 | #endif
|
---|
133 |
|
---|
134 | bool IsPicked() const { return bv.IsPicked(); }
|
---|
135 |
|
---|
136 | BiArray(const BiArray& v, int) { DeepCopy0(v); }
|
---|
137 |
|
---|
138 | BiArray(pick_ BiArray& src) : bv(src.bv) {}
|
---|
139 | void operator=(pick_ BiArray& src) { Free(); bv = src.bv; }
|
---|
140 | BiArray() {}
|
---|
141 | ~BiArray() { Free(); }
|
---|
142 |
|
---|
143 | typedef ConstIIterator<BiArray> ConstIterator;
|
---|
144 | typedef IIterator<BiArray> Iterator;
|
---|
145 |
|
---|
146 | typedef T ValueType;
|
---|
147 |
|
---|
148 | ConstIterator Begin() const { return ConstIterator(*this, 0); }
|
---|
149 | ConstIterator End() const { return ConstIterator(*this, GetCount()); }
|
---|
150 | ConstIterator GetIter(int pos) const { return ConstIterator(*this, pos); }
|
---|
151 | Iterator Begin() { return Iterator(*this, 0); }
|
---|
152 | Iterator End() { return Iterator(*this, GetCount()); }
|
---|
153 | Iterator GetIter(int pos) { return Iterator(*this, pos); }
|
---|
154 |
|
---|
155 | friend void Swap(BiArray& a, BiArray& b) { ::Swap(a.bv, b.bv); }
|
---|
156 |
|
---|
157 | STL_BI_COMPATIBILITY(BiArray<T>)
|
---|
158 | };
|
---|