[1526] | 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 | };
|
---|