Context Navigation

← Previous Revision
Latest Revision
Next Revision →
Blame
Revision Log

Vcont.h @ 1526

Revision 1526, 17.8 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
16	template <int size>
17	class RawVector {
18	protected:
19	struct Data {
20	byte filler[size];
21	};
22
23	Data *vector;
24	int items;
25	int alloc;
26
27	void RawFree();
28	Data Alloc(int n) { return (Data ) NTL_RAW_ALLOC(n * sizeof(Data)); }
29	void Realloc(int newalloc);
30
31	void Chk() const { ASSERT(items >= 0); }
32	void Pick(pick_ RawVector& v);
33	void SetPicked(pick_ RawVector& v) {
34	RawVector& pick = (RawVector&)(v);
35	pick.items = -1;
36	pick.vector = NULL;
37	}
38
39	void Expand();
40
41	void RawInsert(int q, int count);
42	void RawInsertPick(int i, pick_ RawVector<size>& v);
43
44	void *RawAdd() { Chk(); if(items >= alloc) Expand();
45	return vector + items++; }
46
47	int RawGetIndex(const void *item) const;
48
49	RawVector() { vector = NULL; items = alloc = 0; }
50
51	void RawReserve(int xtra);
52	void RawSwap(RawVector& b);
53	};
54
55	template <class T>
56	class Vector : public RawVector<sizeof(T)>
57	, Moveable< Vector<T> >
58	, DeepCopyOption< Vector<T> > {
59	typedef RawVector<sizeof(T)> B;
60
61	void Free();
62	void __DeepCopy(const Vector& src);
63	T& Get(int i) const { ASSERT(i >= 0 && i < B::items); return (T&)B::vector[i]; }
64	void Chk() const { B::Chk(); }
65	void Expand() { B::Expand(); }
66
67	public:
68	T& Add();
69	void Add(const T& x) { DeepCopyConstruct(B::RawAdd(), x); }
70	void AddPick(pick_ T& x) { ::new(B::RawAdd()) T(x); }
71	void AddN(int n);
72	const T& operator[](int i) const { return Get(i); }
73	T& operator[](int i) { return Get(i); }
74	int GetCount() const { Chk(); return B::items; }
75	bool IsEmpty() const { Chk(); return B::items == 0; }
76	void Trim(int n);
77	void SetCount(int n);
78	void SetCount(int n, const T& init);
79	void SetCountR(int n);
80	void SetCountR(int n, const T& init);
81	void Clear();
82
83	T& At(int i) { if(i >= B::items) SetCountR(i + 1); return (*this)[i]; }
84	T& At(int i, const T& x) { if(i >= B::items) SetCountR(i + 1, x); return (*this)[i]; }
85
86	void Shrink() { B::Realloc(B::items); }
87	void Reserve(int n) { B::RawReserve(n); }
88	int GetAlloc() const { return B::alloc; }
89
90	void Set(int i, const T& x, int count = 1);
91	void Remove(int i, int count = 1);
92	void Remove(const int *sorted_list, int n);
93	void Remove(const Vector<int>& sorted_list);
94	void InsertN(int i, int count = 1);
95	T& Insert(int i) { InsertN(i); return Get(i); }
96	void Insert(int i, const T& x, int count = 1);
97	void Insert(int i, const Vector& x);
98	void Insert(int i, const Vector& x, int offset, int count);
99	void InsertPick(int i, pick_ Vector& x) { B::RawInsertPick(i, x); }
100	void Append(const Vector& x) { Insert(GetCount(), x); }
101	void Append(const Vector& x, int o, int c) { Insert(GetCount(), x, o, c); }
102	void AppendPick(pick_ Vector& x) { B::RawInsertPick(GetCount(), x); }
103	int GetIndex(const T& item) const { return B::RawGetIndex(&item); }
104
105	void Drop(int n = 1) { ASSERT(n <= GetCount()); Trim(B::items - n); }
106	T& Top() { ASSERT(GetCount()); return Get(B::items - 1); }
107	const T& Top() const { ASSERT(GetCount()); return Get(B::items - 1); }
108	T Pop() { T h = Top(); Drop(); return h; }
109
110	operator T() { return (T)B::vector; }
111	operator const T() const { return (T)B::vector; }
112
113	Vector& operator<<(const T& x) { Add(x); return *this; }
114	Vector& operator\|(pick_ T& x) { AddPick(x); return *this; }
115
116	#ifdef UPP
117	void Serialize(Stream& s) { StreamContainer(s, *this); }
118	#endif
119
120	Vector() {}
121	~Vector() { AssertMoveable<T>(); Free(); }
122
123	// Pick assignment & copy. Picked source can only Clear(), ~Vector(), operator=, operator <<=
124	Vector(pick_ Vector& v) { B::Pick(v); }
125	void operator=(pick_ Vector& v) { Free(); B::Pick(v); }
126	bool IsPicked() const { return B::items < 0; }
127
128	// Deep copy
129	Vector(const Vector& v, int) { __DeepCopy(v); }
130
131	// Standard container interface
132	typedef T ValueType;
133	typedef T *Iterator;
134	typedef const T *ConstIterator;
135
136	ConstIterator Begin() const { return (T*)B::vector; }
137	ConstIterator End() const { return (T*)B::vector + B::items; }
138	ConstIterator GetIter(int i) const { ASSERT(i >= 0 && i <= B::items); return Begin() + i; }
139	Iterator Begin() { return (T*)B::vector; }
140	Iterator End() { return (T*)B::vector + B::items; }
141	Iterator GetIter(int i) { ASSERT(i >= 0 && i <= B::items); return Begin() + i; }
142
143	// Optimalizations
144	friend void Swap(Vector& a, Vector& b) { a.B::RawSwap(b); }
145	friend void Append(Vector& dst, const Vector& src) { dst.Append(src); }
146
147	//obsolete names
148	T& DoIndex(int i) { return At(i); }
149	T& DoIndex(int i, const T& x) { return At(i, x); }
150
151	STL_VECTOR_COMPATIBILITY(Vector<T>)
152	};
153
154	template <class T>
155	class Array : Moveable< Array<T> >, DeepCopyOption< Array<T> > {
156	protected:
157	Vector<void *> vector;
158
159	void Free();
160	void __DeepCopy(const Array& v);
161	T& Get(int i) const { return (T )vector[i]; }
162	void Del(void ptr, void lim) { while(ptr < lim) delete (T ) ptr++; }
163	void Init(void ptr, void lim) { while(ptr < lim) *ptr++ = new T; }
164	void Init(void ptr, void lim, const T& x) { while(ptr < lim) *ptr++ = DeepCopyNew(x); }
165
166	public:
167	T& Add() { T q = new T; vector.Add(q); return q; }
168	void Add(const T& x) { vector.Add(DeepCopyNew(x)); }
169	void AddPick(pick_ T& x) { vector.Add(new T(x)); }
170	T& Add(T newt) { vector.Add(newt); return newt; }
171	const T& operator[](int i) const { return Get(i); }
172	T& operator[](int i) { return Get(i); }
173	int GetCount() const { return vector.GetCount(); }
174	bool IsEmpty() const { return vector.IsEmpty(); }
175	void Trim(int n);
176	void SetCount(int n);
177	void SetCount(int n, const T& init);
178	void SetCountR(int n);
179	void SetCountR(int n, const T& init);
180	void Clear() { Free(); vector.Clear(); }
181
182	T& At(int i) { if(i >= GetCount()) SetCountR(i + 1); return Get(i); }
183	T& At(int i, const T& x) { if(i >= GetCount()) SetCountR(i + 1, x); return Get(i); }
184
185	void Shrink() { vector.Shrink(); }
186	void Reserve(int xtra) { vector.Reserve(xtra); }
187	int GetAlloc() const { return vector.GetAlloc(); }
188
189	void Set(int i, const T& x, int count = 1);
190	void Remove(int i, int count = 1);
191	void Remove(const int *sorted_list, int n);
192	void Remove(const Vector<int>& sorted_list);
193	void InsertN(int i, int count = 1);
194	T& Insert(int i) { InsertN(i); return Get(i); }
195	void Insert(int i, const T& x, int count = 1);
196	void Insert(int i, const Array& x);
197	void Insert(int i, const Array& x, int offset, int count);
198	void Append(const Array& x) { Insert(GetCount(), x); }
199	void Append(const Array& x, int o, int c) { Insert(GetCount(), x, o, c); }
200	void InsertPick(int i, pick_ Array& x);
201	void AppendPick(pick_ Array& x) { Insert(GetCount(), x); }
202	int GetIndex(const T& item) const;
203	void Swap(int i1, int i2) { ::Swap(vector[i1], vector[i2]); }
204	void Move(int i1, int i2);
205
206	T Detach(int i) { T t = &Get(i); vector.Remove(i); return t; }
207	T& Set(int i, T newt) { delete (T )vector[i]; vector[i] = newt; return *newt; }
208	void Insert(int i, T *newt);
209
210	void Drop(int n = 1) { Trim(GetCount() - n); }
211	T& Top() { return Get(GetCount() - 1); }
212	const T& Top() const { return Get(GetCount() - 1); }
213	// T Pop() { T h = Top(); Drop(); return h; } // msvc bug
214	T PopDetach() { return (T ) vector.Pop(); }
215
216	void Swap(Array& b) { vector.Swap(b.vector); }
217
218	Array& operator<<(const T& x) { Add(x); return *this; }
219	Array& operator<<(T newt) { Add(newt); return this; }
220	Array& operator\|(pick_ T& x) { AddPick(x); return *this; }
221
222	bool IsPicked() const { return vector.IsPicked(); }
223
224	#ifdef UPP
225	void Serialize(Stream& s) { StreamContainer(s, *this); }
226	#endif
227
228	Array() {}
229	~Array() { Free(); }
230
231	// Pick assignment & copy. Picked source can only Clear(), ~Vector(), operator=, operator<<=
232	Array(pick_ Array& v) : vector(v.vector) {}
233	void operator=(pick_ Array& v) { Free(); vector = v.vector; }
234
235	// Deep copy
236	Array(const Array& v, int) { __DeepCopy(v); }
237
238	class Iterator;
239
240	class ConstIterator {
241	protected:
242	T **ptr;
243	ConstIterator(T **p) { ptr = p; }
244
245	friend class Array<T>;
246	struct NP { int dummy; };
247
248	public:
249	const T& operator() const { return *ptr; }
250	const T operator->() const { return ptr; }
251	const T& operator[](int i) const { return *ptr[i]; }
252
253	ConstIterator& operator++() { ptr++; return *this; }
254	ConstIterator& operator--() { ptr--; return *this; }
255	ConstIterator operator++(int) { ConstIterator t = this; ++this; return t; }
256	ConstIterator operator--(int) { ConstIterator t = this; --this; return t; }
257
258	ConstIterator& operator+=(int i) { ptr += i; return *this; }
259	ConstIterator& operator-=(int i) { ptr -= i; return *this; }
260
261	ConstIterator operator+(int i) const { return ptr + i; }
262	ConstIterator operator-(int i) const { return ptr - i; }
263
264	int operator-(ConstIterator x) const { return ptr - x.ptr; }
265
266	bool operator==(ConstIterator x) const { return ptr == x.ptr; }
267	bool operator!=(ConstIterator x) const { return ptr != x.ptr; }
268	bool operator<(ConstIterator x) const { return ptr < x.ptr; }
269	bool operator>(ConstIterator x) const { return ptr > x.ptr; }
270	bool operator<=(ConstIterator x) const { return ptr <= x.ptr; }
271	bool operator>=(ConstIterator x) const { return ptr >= x.ptr; }
272
273	operator bool() const { return ptr; }
274
275	ConstIterator() {}
276	ConstIterator(NP *null) { ASSERT(null == NULL); ptr = NULL; }
277	};
278
279	class Iterator : public ConstIterator {
280	friend class Array<T>;
281	Iterator(T **p) : ConstIterator(p) {}
282	typedef ConstIterator B;
283	struct NP { int dummy; };
284
285	public:
286	T& operator() { return *B::ptr; }
287	T operator->() { return B::ptr; }
288	T& operator[](int i) { return *B::ptr[i]; }
289
290	const T& operator() const { return *B::ptr; }
291	const T operator->() const { return B::ptr; }
292	const T& operator[](int i) const { return *B::ptr[i]; }
293
294	Iterator& operator++() { B::ptr++; return *this; }
295	Iterator& operator--() { B::ptr--; return *this; }
296	Iterator operator++(int) { Iterator t = this; ++this; return t; }
297	Iterator operator--(int) { Iterator t = this; --this; return t; }
298
299	Iterator& operator+=(int i) { B::ptr += i; return *this; }
300	Iterator& operator-=(int i) { B::ptr -= i; return *this; }
301
302	Iterator operator+(int i) const { return B::ptr + i; }
303	Iterator operator-(int i) const { return B::ptr - i; }
304
305	int operator-(Iterator x) const { return B::operator-(x); }
306
307	Iterator() {}
308	Iterator(NP *null) : ConstIterator(null) {}
309
310	//G++
311	// friend void IterSwap(Iterator a, Iterator b) { ::Swap(a.ptr, b.ptr); }
312	};
313
314	// Standard container interface
315	typedef T ValueType;
316	Iterator Begin() { return (T **)vector.Begin(); }
317	Iterator End() { return (T **)vector.End(); }
318	Iterator GetIter(int pos) { return (T **)vector.GetIter(pos); }
319	ConstIterator Begin() const { return (T **)vector.Begin(); }
320	ConstIterator End() const { return (T **)vector.End(); }
321	ConstIterator GetIter(int pos) const { return (T **)vector.GetIter(pos); }
322
323	// Optimalization
324	friend void Swap(Array& a, Array& b) { ::Swap(a.vector, b.vector); }
325	//GCC forced move from Iterator, ugly workaround
326	private:
327	static void IterSwap0(Iterator a, Iterator b) { ::Swap(a.ptr, b.ptr); }
328	public:
329	friend void IterSwap(Iterator a, Iterator b) { Array<T>::IterSwap0(a, b); }
330
331	//obsolete names
332	T& DoIndex(int i) { return At(i); }
333	T& DoIndex(int i, const T& x) { return At(i, x); }
334
335	STL_VECTOR_COMPATIBILITY(Array<T>)
336	};
337
338	template<class T, int NBLK = 16>
339	class Segtor : Moveable< Segtor<T, NBLK> >, DeepCopyOption< Segtor<T, NBLK> > {
340	protected:
341	struct Block {
342	byte item[NBLK][sizeof(T)];
343	};
344
345	Array<Block> block;
346	int items;
347
348	void DoRange(unsigned beg, unsigned end, void (fn)(T, const T*));
349	void Fill(unsigned beg, unsigned end, const T& x);
350	T& Get(int i) const {
351	ASSERT(i >= 0 && i < items);
352	return (T) block[unsigned(i) / NBLK].item[unsigned(i) % NBLK];
353	}
354	void *Add0() {
355	int blk = unsigned(items) / NBLK, ndx = unsigned(items) % NBLK;
356	if(ndx == 0) block.Add(); items++;
357	return block[blk].item[ndx];
358	}
359	void Del(int n) { if(n < items) DoRange(n, items, DestroyArray); }
360	void Init(int n) { if(n > items) DoRange(items, n, ConstructArray); items = n; }
361	void Init(int n, const T& x) { if(n > items) Fill(items, n, x); items = n; }
362	void Free();
363
364	public:
365	T& Add() { return *::new(Add0()) T; }
366	void Add(const T& x) { DeepCopyConstruct(Add0(), x); }
367	void AddPick(pick_ T& x) { ::new(Add0()) T; }
368	T& operator[](int i) { return Get(i); }
369	const T& operator[](int i) const { return Get(i); }
370	int GetCount() const { return items; }
371	bool IsEmpty() const { return items == 0; }
372	void SetCount(int n);
373	void SetCount(int n, const T& init);
374	void Clear();
375	T& At(int i) { if(i >= items) SetCount(i + 1); return Get(i); }
376	T& At(int i, const T& x) { if(i >= items) SetCount(i + 1, x); return Get(i); }
377	void Shrink() { block.Shrink(); }
378	void Reserve(int xtra) { block.Reserve((xtra + NBLK - 1) / NBLK); }
379	int GetAlloc() const { return block.GetAlloc() * NBLK; }
380
381	void Set(int i, const T& x, int count = 1);
382	int GetIndex(const T& item) const;
383
384	void Drop(int n = 1) { ASSERT(n <= GetCount()); SetCount(GetCount() - n); }
385	T& Top() { ASSERT(GetCount()); return Get(GetCount() - 1); }
386	const T& Top() const { ASSERT(GetCount()); return Get(GetCount() - 1); }
387	T Pop() { T h = Top(); Drop(); return h; }
388
389	void Swap(Segtor& b) { block.Swap(b.block); Swap(items, b.items); }
390
391	Segtor& operator<<(const T& x) { Add(x); return *this; }
392	Segtor& operator\|(pick_ T& x) { AddPick(x); return *this; }
393
394	bool IsPicked() const { return block.IsPicked(); }
395
396	#ifdef UPP
397	void Serialize(Stream& s) { StreamContainer(s, *this); }
398	#endif
399
400	Segtor() { items = 0; }
401	Segtor(pick_ Segtor& s) : block(s.block), items(s.items) {}
402	Segtor(const Segtor& s, int);
403	~Segtor();
404
405	// Standard iterators
406	typedef ConstIIterator<Segtor> ConstIterator;
407	typedef IIterator<Segtor> Iterator;
408
409	// Standard container interface
410	typedef T ValueType;
411	ConstIterator Begin() const { return ConstIterator(*this, 0); }
412	ConstIterator End() const { return ConstIterator(*this, items); }
413	ConstIterator GetIter(int pos) const { return ConstIterator(*this, pos); }
414	Iterator Begin() { return Iterator(*this, 0); }
415	Iterator End() { return Iterator(*this, items); }
416	Iterator GetIter(int pos) { return Iterator(*this, pos); }
417
418	// Optimizations
419	friend void Swap(Segtor& a, Segtor& b) { a.Swap(b); }
420
421	//obsolete names
422	T& DoIndex(int i) { return At(i); }
423	T& DoIndex(int i, const T& x) { return At(i, x); }
424
425	// traits
426	STL_VECTOR_COMPATIBILITY(Segtor<T _cm_ NBLK>)
427	};

Note: See TracBrowser for help on using the repository browser.

Context Navigation

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

Download in other formats: