container.hpp 63.2 KB
Newer Older
Kirill Terekhov's avatar
Kirill Terekhov committed
1
2
3
#ifndef _CONTAINER_HPP
#define _CONTAINER_HPP

4
5
6
7
8
#include <cstdlib>
#include <cstddef>
#include <cstring>
#include <cmath>
#include <cassert>
Kirill Terekhov's avatar
Kirill Terekhov committed
9
10
11
12
#include <memory>
#include <new>
#include <iterator>
#include <limits>
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
13
#include "inmost_common.h"
Kirill Terekhov's avatar
Kirill Terekhov committed
14

15
//#define DEBUGMEM
Kirill Terekhov's avatar
Kirill Terekhov committed
16
17

#define NEW_CHUNKS
18
#define __VOLATILE volatile
Kirill Terekhov's avatar
Kirill Terekhov committed
19
20
//#define OUT_OF_RANGE

21
22
23
24
#if defined(_OPENMP)
#include <omp.h>
#endif

Kirill Terekhov's avatar
Kirill Terekhov committed
25
26
//TODO
// 1. change to uniform size_type instead of size_t, make it INMOST_DATA_ENUM_TYPE
Kirill Terekhov's avatar
Kirill Terekhov committed
27
/*
Kirill Terekhov's avatar
Kirill Terekhov committed
28
29
template<class element, class T1> struct isInputRandomIterators
{
Kirill Terekhov's avatar
Kirill Terekhov committed
30
	static void constraints(T1 a, T1 b) { ++a; (void)a++; a==a; a!=a; a-b; }
Kirill Terekhov's avatar
Kirill Terekhov committed
31
32
33
34
35
	isInputRandomIterators() { void(*p)(T1,T1) = constraints; (void)p; }
};

template<class element, class T1> struct isInputForwardIterators
{
Kirill Terekhov's avatar
Kirill Terekhov committed
36
	static void constraints(T1 a) {++a; (void)a++; }
Kirill Terekhov's avatar
Kirill Terekhov committed
37
38
	isInputForwardIterators() { void(*p)(T1) = constraints; (void)p; }
};
Kirill Terekhov's avatar
Kirill Terekhov committed
39
*/
Kirill Terekhov's avatar
Kirill Terekhov committed
40
41
42

namespace INMOST
{
Kirill Terekhov's avatar
Kirill Terekhov committed
43
44
45
46
47
48
49
50
51
52
53
54
	//add more templates as needed
	template<class T> struct make_unsigned;
	template<> struct make_unsigned<char> {typedef unsigned char type;};
	template<> struct make_unsigned<short> {typedef unsigned short type;};
	template<> struct make_unsigned<int> {typedef unsigned int type;};
	template<> struct make_unsigned<long> {typedef unsigned long type;};
	template<> struct make_unsigned<long long> {typedef unsigned long long type;};
	template<> struct make_unsigned<unsigned char> {typedef unsigned char type;};
	template<> struct make_unsigned<unsigned short> {typedef unsigned short type;};
	template<> struct make_unsigned<unsigned int> {typedef unsigned int type;};
	template<> struct make_unsigned<unsigned long> {typedef unsigned long type;};
	template<> struct make_unsigned<unsigned long long> {typedef unsigned long long type;};
55

56

Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
57
58
59
#if defined(PACK_ARRAY)
#pragma pack(push,r1,4)
#endif
Kirill Terekhov's avatar
Kirill Terekhov committed
60
61
62
	// notice: array class would not properly support classes that contain self-references
	//         like std::map
	// notice: next class shell have to implement same algorithms as array
Kirill Terekhov's avatar
Kirill Terekhov committed
63
64
65
66
	template<typename element>//, typename enumerator = unsigned int>
	class array
	{
	public:
Kirill Terekhov's avatar
Kirill Terekhov committed
67
68
		typedef unsigned size_type;
		typedef make_unsigned<size_type>::type uenum;
Kirill Terekhov's avatar
Kirill Terekhov committed
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
		template<typename etype>
		class _iterator
		{
		private:
			etype * e;
		public:
			typedef etype * pointer;
			typedef etype & reference;
			typedef etype value_type;
			typedef ptrdiff_t difference_type;
			typedef std::random_access_iterator_tag iterator_category;
			_iterator():e(NULL){}
			_iterator(etype * i):e(i){}
			_iterator(const _iterator & other){e = other.e;}
			~_iterator() {};
Kirill Terekhov's avatar
Updates    
Kirill Terekhov committed
84
			_iterator operator -(size_t n) const { return _iterator(e-n); }
Kirill Terekhov's avatar
Kirill Terekhov committed
85
			_iterator & operator -=(size_t n) { e-=n; return *this; }
Kirill Terekhov's avatar
Updates    
Kirill Terekhov committed
86
			_iterator operator +(size_t n) const { return _iterator(e+n); }
Kirill Terekhov's avatar
Kirill Terekhov committed
87
			_iterator & operator +=(size_t n) { e+=n; return *this; }
Kirill Terekhov's avatar
Kirill Terekhov committed
88
			_iterator & operator ++(){ ++e; return *this;}
89
			_iterator operator ++(int) { return _iterator(e++); }
Kirill Terekhov's avatar
Kirill Terekhov committed
90
			_iterator & operator --(){ --e; return *this; }
91
			_iterator operator --(int) { return _iterator(e--); }
Kirill Terekhov's avatar
Kirill Terekhov committed
92
			ptrdiff_t operator -(const _iterator & other) const {return e-other.e;}
93
94
			etype & operator *() const { return *e; }
			etype * operator ->() const { return e; }
Kirill Terekhov's avatar
Kirill Terekhov committed
95
			_iterator & operator =(_iterator const & other) { e = other.e; return *this; }
Kirill Terekhov's avatar
Kirill Terekhov committed
96
97
98
99
100
101
			bool operator ==(const _iterator & other) const { return e == other.e;}
			bool operator !=(const _iterator & other) const { return e != other.e;}
			bool operator <(const _iterator & other) const { return e < other.e;}
			bool operator >(const _iterator & other) const { return e > other.e;}
			bool operator <=(const _iterator & other) const { return e <= other.e;}
			bool operator >=(const _iterator & other) const { return e >= other.e;}
102
			operator void *() const {return static_cast<void *> (e);}
Kirill Terekhov's avatar
Kirill Terekhov committed
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
		};
		typedef _iterator<element> iterator;
		typedef _iterator<const element> const_iterator;
		template<typename etype>
		class _reverse_iterator
		{
		private:
			etype * e;
		public:
			typedef etype * pointer;
			typedef etype & reference;
			typedef etype value_type;
			typedef ptrdiff_t difference_type;
			typedef std::random_access_iterator_tag iterator_category;
			_reverse_iterator():e(NULL){}
			_reverse_iterator(etype * i):e(i){}
			_reverse_iterator(const _reverse_iterator & other){e = other.e;}
			~_reverse_iterator() {};
Kirill Terekhov's avatar
Updates    
Kirill Terekhov committed
121
			_reverse_iterator operator -(size_t n) const { return _reverse_iterator(e+n); }
Kirill Terekhov's avatar
Kirill Terekhov committed
122
			_reverse_iterator & operator -=(size_t n) { e+=n; return *this; }
Kirill Terekhov's avatar
Updates    
Kirill Terekhov committed
123
			_reverse_iterator operator +(size_t n) const {return _reverse_iterator(e-n); }
Kirill Terekhov's avatar
Kirill Terekhov committed
124
			_reverse_iterator & operator +=(size_t n) { e-=n; return *this; }
Kirill Terekhov's avatar
Kirill Terekhov committed
125
			_reverse_iterator & operator ++(){ --e; return *this;}
126
			_reverse_iterator operator ++(int) { return _reverse_iterator(e--); }
Kirill Terekhov's avatar
Kirill Terekhov committed
127
			_reverse_iterator & operator --(){ ++e; return *this; }
128
			_reverse_iterator operator --(int) { return _reverse_iterator(e++); }
Kirill Terekhov's avatar
Kirill Terekhov committed
129
			ptrdiff_t operator -(const _reverse_iterator & other) const {return other.e-e;}
130
131
			etype & operator *() const { return *e; }
			etype * operator ->() const { return e; }
Kirill Terekhov's avatar
Kirill Terekhov committed
132
			_reverse_iterator & operator =(_reverse_iterator const & other) { e = other.e; return *this;}
Kirill Terekhov's avatar
Kirill Terekhov committed
133
134
135
136
137
138
			bool operator ==(const _reverse_iterator & other) const { return e == other.e;}
			bool operator !=(const _reverse_iterator & other) const { return e != other.e;}
			bool operator <(const _reverse_iterator & other) const { return e < other.e;}
			bool operator >(const _reverse_iterator & other) const { return e > other.e;}
			bool operator <=(const _reverse_iterator & other) const { return e <= other.e;}
			bool operator >=(const _reverse_iterator & other) const { return e >= other.e;}
139
			operator void *()const {return static_cast<void *> (e);}
Kirill Terekhov's avatar
Kirill Terekhov committed
140
141
142
143
		};
		typedef _reverse_iterator<element> reverse_iterator;
		typedef _reverse_iterator<const element> const_reverse_iterator;
	private:
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
144

Kirill Terekhov's avatar
Kirill Terekhov committed
145
		element * m_arr;
Kirill Terekhov's avatar
Kirill Terekhov committed
146
		size_type m_size;
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
147

Kirill Terekhov's avatar
Kirill Terekhov committed
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
		//notice: push_back, pop_back, insert, erase are optimized for current growth_formula
		__INLINE static size_type growth_formula(size_type future_size)
		{
			uenum v = static_cast<uenum>(future_size);
			v--;
			v|= (v>>1);
			v|= (v>>2);
			v|= (v>>4);
			v|= (v>>8);
			v|= (v>>16);
			//TODO produces compiler warning
			//if( sizeof(size_type) > 4 ) v|= (v>>32); //must be compile time brench
			v++;
			return static_cast<size_type>(v);
		}
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
	protected:
		static element * realloc(element * ptr, size_type old_size, size_type new_size)
		{
			size_type gf = growth_formula(new_size);
			if( gf != growth_formula(old_size) )
			{
				element * tmp = new element[gf];
#if defined(DEBUGMEM)
				if( tmp == NULL ) {std::cout << __FILE__ << ":" << __LINE__ << "allocation returns NULL\n";}
#endif
				std::copy(ptr,ptr+std::min(old_size,new_size),tmp);
				delete [] ptr;
				ptr = tmp;
				assert(ptr != NULL);
			}
			return ptr;
		}
		static element * alloc(size_type init_size)
		{
			element * tmp = new element[growth_formula(init_size)];
#if defined(DEBUGMEM)
			if( tmp == NULL ) {std::cout << __FILE__ << ":" << __LINE__ << "allocation returns NULL\n";}
#endif
			assert(tmp != NULL);
			return tmp;
		}
		static element * copy(const element * ibeg, const element * iend, element * obeg) 
		{
			if (std::less<const element *>()(ibeg, obeg)) 
			{
				obeg += (iend - ibeg);
				std::copy_backward(ibeg, iend, obeg);
				return obeg;
			} else return std::copy(ibeg, iend, obeg);
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
198
	public:
Kirill Terekhov's avatar
Kirill Terekhov committed
199
200
		__INLINE element * data() {return m_arr;}
		__INLINE const element * data() const {return m_arr;}
Kirill Terekhov's avatar
Kirill Terekhov committed
201
		array() {m_arr = NULL; m_size = 0;}
Kirill Terekhov's avatar
Kirill Terekhov committed
202
		array(size_type n,element c = element())
Kirill Terekhov's avatar
Kirill Terekhov committed
203
204
		{
			m_size = n;
205
206
			m_arr = alloc(n);
			std::fill(m_arr,m_arr+m_size,c);
Kirill Terekhov's avatar
Kirill Terekhov committed
207
208
209
210
		}
		template<class InputIterator>
		array(InputIterator first, InputIterator last)
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
211
			m_size = static_cast<size_type>(std::distance(first,last));
212
213
			m_arr = alloc(m_size);
			std::copy(first,last,m_arr);
Kirill Terekhov's avatar
Kirill Terekhov committed
214
215
216
217
		}
		array(const array & other)
		{
			m_size = other.m_size;
218
			if( m_size )
Kirill Terekhov's avatar
Kirill Terekhov committed
219
			{
220
221
				m_arr = alloc(m_size);
				std::copy(other.m_arr,other.m_arr+other.m_size,m_arr);
Kirill Terekhov's avatar
Kirill Terekhov committed
222
223
224
			}
			else m_arr = NULL;
		}
225
		~array() {clear();}
226
		__INLINE const element & operator [] (size_type n) const
Kirill Terekhov's avatar
Kirill Terekhov committed
227
228
229
230
		{
			assert(n < m_size);
			return m_arr[n];
		}
231
		__INLINE element & operator [] (size_type n)
Kirill Terekhov's avatar
Kirill Terekhov committed
232
233
234
235
		{
			assert(n < m_size);
			return m_arr[n];
		}
236
		__INLINE const element & at (size_type n) const
Kirill Terekhov's avatar
Kirill Terekhov committed
237
238
239
240
		{
			assert(n < m_size);
			return m_arr[n];
		}
241
		__INLINE element & at (size_type n)
Kirill Terekhov's avatar
Kirill Terekhov committed
242
243
244
245
		{
			assert(n < m_size);
			return m_arr[n];
		}
246
		__INLINE element & at_safe (size_type n)
Kirill Terekhov's avatar
Kirill Terekhov committed
247
248
249
250
251
252
253
254
		{
			if( n >= m_size ) resize(n+1);
			return m_arr[n];
		}
		array & operator =(array const & other)
		{
			if( this != &other )
			{
255
				if(m_arr != NULL )
256
					clear();
Kirill Terekhov's avatar
Kirill Terekhov committed
257
258
259
				if( other.m_arr != NULL )
				{
					m_size = other.m_size;
260
261
					m_arr = alloc(m_size);
					std::copy(other.m_arr,other.m_arr+other.m_size,m_arr);
Kirill Terekhov's avatar
Kirill Terekhov committed
262
263
264
265
266
267
				}
			}
			return *this;
		}
		void push_back(const element & e)
		{
268
269
			m_arr = realloc(m_arr,m_size,m_size+1);
			m_arr[m_size++] = e;
Kirill Terekhov's avatar
Kirill Terekhov committed
270
271
272
273
		}
		void pop_back()
		{
			assert(m_arr != NULL);
Kirill Terekhov's avatar
Kirill Terekhov committed
274
275
			if( m_size > 0)
			{
276
277
				m_arr = realloc(m_arr,m_size,m_size-1);
				m_size--;
Kirill Terekhov's avatar
Kirill Terekhov committed
278
			}
279
			else clear();
Kirill Terekhov's avatar
Kirill Terekhov committed
280
		}
281
		__INLINE element & back()
Kirill Terekhov's avatar
Kirill Terekhov committed
282
283
284
285
286
		{
			assert(m_arr != NULL);
			assert(m_size > 0);
			return m_arr[m_size-1];
		}
287
		__INLINE const element & back() const
Kirill Terekhov's avatar
Kirill Terekhov committed
288
289
290
291
292
		{
			assert(m_arr != NULL);
			assert(m_size > 0);
			return m_arr[m_size-1];
		}
293
		__INLINE element & front()
Kirill Terekhov's avatar
Kirill Terekhov committed
294
295
296
297
298
		{
			assert(m_arr != NULL);
			assert(m_size > 0);
			return m_arr[0];
		}
299
		__INLINE const element & front() const
Kirill Terekhov's avatar
Kirill Terekhov committed
300
301
302
303
304
		{
			assert(m_arr != NULL);
			assert(m_size > 0);
			return m_arr[0];
		}
305
		__INLINE size_type capacity() { return growth_formula(m_size); }
Kirill Terekhov's avatar
Kirill Terekhov committed
306
		__INLINE bool empty() const { if( m_size ) return false; return true; }
Kirill Terekhov's avatar
Kirill Terekhov committed
307
		void resize(size_type n, element c = element() )
Kirill Terekhov's avatar
Kirill Terekhov committed
308
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
309
			size_type oldsize = m_size;
Kirill Terekhov's avatar
Kirill Terekhov committed
310
311
312
			m_size = n;
			if( m_size > 0 )
			{
313
314
				m_arr = realloc(m_arr,oldsize,m_size);
				if( oldsize < m_size ) std::fill(m_arr+oldsize,m_arr+m_size,c);
Kirill Terekhov's avatar
Kirill Terekhov committed
315
			}
316
			else clear();
Kirill Terekhov's avatar
Kirill Terekhov committed
317
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
318
319
		__INLINE size_type size() const {return m_size;}
		__INLINE size_type capacity() const {return growth_formula(m_size);}
320
321
		void clear()
		{
322
			if( m_arr ) delete [] m_arr;
323
			m_arr = NULL;
324
			m_size = 0;
Kirill Terekhov's avatar
Kirill Terekhov committed
325
326
327
328
		}
		void swap(array<element> & other)
		{
			element * t_m_arr = m_arr;
Kirill Terekhov's avatar
Kirill Terekhov committed
329
			size_type t_m_size = m_size;
Kirill Terekhov's avatar
Kirill Terekhov committed
330
331
332
333
334
			m_arr = other.m_arr;
			m_size = other.m_size;
			other.m_arr = t_m_arr;
			other.m_size = t_m_size;
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
335
336
337
338
339
340
341
342
		__INLINE iterator begin() { return m_arr; }
		__INLINE iterator end() { return m_arr+m_size; }
		__INLINE const_iterator begin() const { return m_arr; }
		__INLINE const_iterator end() const { return m_arr+m_size; }
		__INLINE reverse_iterator rbegin() { return reverse_iterator(m_arr+m_size-1); }
		__INLINE reverse_iterator rend() { return reverse_iterator(m_arr-1); }
		__INLINE const_reverse_iterator rbegin() const { return const_reverse_iterator(m_arr+m_size-1); }
		__INLINE const_reverse_iterator rend() const { return const_reverse_iterator(m_arr-1); }
343
344
		iterator erase(iterator pos)
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
345
			ptrdiff_t d = pos-begin();
346
			ptrdiff_t s = iterator(m_arr+(m_size-1))-pos;
Kirill Terekhov's avatar
Kirill Terekhov committed
347
348
349
			m_size--;
			if( m_size > 0 )
			{
350
351
				if( s ) copy(m_arr+d+1, m_arr+d+1+s, m_arr+d);
				m_arr = realloc(m_arr, m_size+1, m_size);
Kirill Terekhov's avatar
Kirill Terekhov committed
352
			}
353
			else clear();
Kirill Terekhov's avatar
Kirill Terekhov committed
354
355
356
357
358
359
360
361
362
363
			return m_arr+d;
		}
		iterator erase(iterator b, iterator e)
		{
			ptrdiff_t d = b-begin();
			ptrdiff_t s = end()-e;
			ptrdiff_t n = e-b;
			m_size -= n;
			if( m_size > 0 )
			{
364
365
366
				if( s ) copy(m_arr+d+1,m_arr+d+1+s,m_arr+d);
				m_arr = realloc(m_arr,m_size+n,m_size);
				
Kirill Terekhov's avatar
Kirill Terekhov committed
367
			}
368
			else clear();
Kirill Terekhov's avatar
Kirill Terekhov committed
369
370
371
372
373
374
375
			return m_arr+d;
		}
		iterator insert(iterator pos, const element & x)
		{
			if( static_cast<void *>(pos) == NULL)
			{
				assert(m_arr == NULL);
376
377
378
379
				m_size = 1;
				m_arr = alloc(m_size);
				m_arr[0] = x;
				return m_arr;
380
			}
381
			else
382
			{
383
384
385
386
387
				ptrdiff_t d = pos-begin();
				ptrdiff_t s = end()-pos;
				m_arr = realloc(m_arr,m_size,m_size+1);
				if( s ) copy(m_arr+d,m_arr+d+s,m_arr+d+1);
				m_arr[d] = x;
Kirill Terekhov's avatar
fix    
Kirill Terekhov committed
388
				m_size++;
389
				return m_arr+d;
390
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
391
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
392
		void insert(iterator pos, size_type n, const element & x)
Kirill Terekhov's avatar
Kirill Terekhov committed
393
394
395
396
397
398
		{
			if( n > 0 )
			{
				if( static_cast<void *>(pos) == NULL)
				{
					assert(m_arr == NULL);
399
400
401
					m_arr = alloc(n);
					m_size = n;
					std::fill(m_arr,m_arr+m_size,x);
Kirill Terekhov's avatar
Kirill Terekhov committed
402
				}
403
				else
404
				{
405
406
407
408
409
410
					ptrdiff_t d = pos-begin();
					ptrdiff_t s = end()-pos;
					m_arr = realloc(m_arr,m_size,m_size+n);
					m_size += n;
					if( s ) copy(m_arr+d,m_arr+d+s,m_arr+d+n);
					std::fill(m_arr+d,m_arr+d+n,x);
411
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
412
413
414
415
416
			}
		}
		template <class InputIterator>
		void insert(iterator pos, InputIterator first, InputIterator last)
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
417
			size_type n = static_cast<size_type>(std::distance(first,last));
Kirill Terekhov's avatar
Kirill Terekhov committed
418
419
420
421
422
			if( n > 0 )
			{
				if( static_cast<void *>(pos) == NULL)
				{
					assert(m_arr == NULL);
423
424
425
					m_arr = alloc(n);
					m_size = n;
					std::copy(first,last,m_arr);
426
				}
427
				else
Kirill Terekhov's avatar
Kirill Terekhov committed
428
				{
429
430
431
432
433
434
					ptrdiff_t d = pos-begin();
					ptrdiff_t s = end()-pos;
					m_arr = realloc(m_arr,m_size,m_size+n);
					m_size += n;
					if( s ) copy(m_arr+d,m_arr+d+s,m_arr+d+n);
					std::copy(first,last,m_arr+d);
Kirill Terekhov's avatar
Kirill Terekhov committed
435
436
437
438
439
440
441
				}
			}
		}
		template <class InputIterator>
		void replace(iterator m_first, iterator m_last, InputIterator first, InputIterator last)
		{
			assert( m_size >= 0 );
442
			size_type n = static_cast<size_type>(std::distance(first,last));
Kirill Terekhov's avatar
Kirill Terekhov committed
443
444
445
			if( static_cast<void *>(m_first) == NULL && m_arr == NULL)
			{
				assert(m_arr == NULL);
446
447
448
				m_arr = alloc(n);
				m_size = n;
				std::copy(first,last,m_arr);
Kirill Terekhov's avatar
Kirill Terekhov committed
449
			}
450
			else
Kirill Terekhov's avatar
Kirill Terekhov committed
451
			{
452
453
454
455
				ptrdiff_t q = m_last-m_first;
				ptrdiff_t d = m_first-iterator(m_arr);
				ptrdiff_t s = iterator(m_arr+m_size)-m_last;
				if( n-q != 0 )
456
				{
457
458
459
					m_arr = realloc(m_arr,m_size,m_size+static_cast<size_type>(n-q));	
					m_size+=static_cast<size_type>(n-q);
					if( s ) copy(m_arr+d+q,m_arr+d+q+s,m_arr+d+n);
460
				}
461
				std::copy(first,last,m_arr+d);
Kirill Terekhov's avatar
Kirill Terekhov committed
462
463
			}
		}
464
465
466
467
468
		template <class InputIterator>
		void assign(InputIterator first, InputIterator last)
		{
			replace(begin(),end(),first,last);
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
469
		template<class> friend class shell;
470
	};
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
471
472
473
#if defined(PACK_ARRAY)
#pragma pack(pop,r1)
#endif
Kirill Terekhov's avatar
Kirill Terekhov committed
474
475
476
477
	template<typename element>
	class shell
	{
	public:
Kirill Terekhov's avatar
Kirill Terekhov committed
478
		typedef typename array<element>::size_type size_type;
Kirill Terekhov's avatar
Kirill Terekhov committed
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
		template<typename dtype>
		class _iterator
		{
		private:
			dtype * e;
		public:
			typedef dtype * pointer;
			typedef dtype & reference;
			typedef dtype value_type;
			typedef ptrdiff_t difference_type;
			typedef std::random_access_iterator_tag iterator_category;
			_iterator():e(NULL){}
			_iterator(dtype * i):e(i){}
			_iterator(const _iterator & other){e = other.e;}
			~_iterator() {};
Kirill Terekhov's avatar
Updates    
Kirill Terekhov committed
494
			_iterator operator -(size_t n) const { return _iterator(e-n); }
Kirill Terekhov's avatar
Kirill Terekhov committed
495
			_iterator & operator -=(size_t n) { e-=n; return *this; }
Kirill Terekhov's avatar
Updates    
Kirill Terekhov committed
496
			_iterator operator +(size_t n) const { return _iterator(e+n); }
Kirill Terekhov's avatar
Kirill Terekhov committed
497
			_iterator & operator +=(size_t n) { e+=n; return *this; }
Kirill Terekhov's avatar
Kirill Terekhov committed
498
			_iterator & operator ++(){ ++e; return *this;}
499
			_iterator operator ++(int) { return _iterator(e++); }
Kirill Terekhov's avatar
Kirill Terekhov committed
500
			_iterator & operator --(){ --e; return *this; }
501
			_iterator operator --(int) { return _iterator(e--); }
Kirill Terekhov's avatar
Kirill Terekhov committed
502
			ptrdiff_t operator -(const _iterator & other) const {return e-other.e;}
503
504
			dtype & operator *() const { return *e; }
			dtype * operator ->() const { return e; }
Kirill Terekhov's avatar
Kirill Terekhov committed
505
			_iterator & operator =(_iterator const & other) { e = other.e; return *this; }
506
507
508
509
510
511
512
			bool operator ==(const _iterator & other) const { return e == other.e;}
			bool operator !=(const _iterator & other) const { return e != other.e;}
			bool operator <(const _iterator & other) const { return e < other.e;}
			bool operator >(const _iterator & other) const { return e > other.e;}
			bool operator <=(const _iterator & other) const { return e <= other.e;}
			bool operator >=(const _iterator & other) const { return e >= other.e;}
			operator void *() const {return static_cast<void *> (e);}
Kirill Terekhov's avatar
Kirill Terekhov committed
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
		};
		typedef _iterator<element> iterator;
		typedef _iterator<const element> const_iterator;
		template<typename dtype>
		class _reverse_iterator
		{
		private:
			dtype * e;
		public:
			typedef dtype * pointer;
			typedef dtype & reference;
			typedef dtype value_type;
			typedef ptrdiff_t difference_type;
			typedef std::random_access_iterator_tag iterator_category;
			_reverse_iterator():e(NULL){}
			_reverse_iterator(dtype * i):e(i){}
			_reverse_iterator(const _reverse_iterator & other){e = other.e;}
			~_reverse_iterator() {};
Kirill Terekhov's avatar
Updates    
Kirill Terekhov committed
531
			_reverse_iterator operator -(size_t n) const { return _reverse_iterator(e+n); }
Kirill Terekhov's avatar
Kirill Terekhov committed
532
			_reverse_iterator & operator -=(size_t n) { e+=n; return *this; }
Kirill Terekhov's avatar
Updates    
Kirill Terekhov committed
533
			_reverse_iterator operator +(size_t n) const {return _reverse_iterator(e-n); }
Kirill Terekhov's avatar
Kirill Terekhov committed
534
			_reverse_iterator & operator +=(size_t n) { e-=n; return *this; }
Kirill Terekhov's avatar
Kirill Terekhov committed
535
			_reverse_iterator & operator ++(){ --e; return *this;}
536
			_reverse_iterator operator ++(int) { return _reverse_iterator(e--); }
Kirill Terekhov's avatar
Kirill Terekhov committed
537
			_reverse_iterator & operator --(){ ++e; return *this; }
538
			_reverse_iterator operator --(int) { return _reverse_iterator(e++); }
Kirill Terekhov's avatar
Kirill Terekhov committed
539
			ptrdiff_t operator -(const _reverse_iterator & other) const {return other.e-e;}
540
541
			dtype & operator *() const { return *e; }
			dtype * operator ->() const { return e; }
Kirill Terekhov's avatar
Kirill Terekhov committed
542
			_reverse_iterator & operator =(_reverse_iterator const & other) { e = other.e; return *this;}
543
544
545
546
547
548
549
			bool operator ==(const _reverse_iterator & other) const { return e == other.e;}
			bool operator !=(const _reverse_iterator & other) const { return e != other.e;}
			bool operator <(const _reverse_iterator & other) const { return e < other.e;}
			bool operator >(const _reverse_iterator & other) const { return e > other.e;}
			bool operator <=(const _reverse_iterator & other) const { return e <= other.e;}
			bool operator >=(const _reverse_iterator & other)const { return e >= other.e;}
			operator void *() const {return static_cast<void *> (e);}
Kirill Terekhov's avatar
Kirill Terekhov committed
550
551
552
553
554
		};
		typedef _reverse_iterator<element> reverse_iterator;
		typedef _reverse_iterator<const element> const_reverse_iterator;
	private:
		element ** m_arr;
Kirill Terekhov's avatar
Kirill Terekhov committed
555
		size_type * m_size;
Kirill Terekhov's avatar
Kirill Terekhov committed
556
		element * local_link;
Kirill Terekhov's avatar
Kirill Terekhov committed
557
		size_type local_size;
Kirill Terekhov's avatar
Kirill Terekhov committed
558
559
		bool fixed;
	public:
Kirill Terekhov's avatar
Kirill Terekhov committed
560
561
		__INLINE element * data() {return *m_arr;}
		__INLINE const element * data() const {return *m_arr;}
562
		shell() :m_arr(NULL), m_size(NULL), local_link(NULL), local_size(0), fixed(false) { }
Kirill Terekhov's avatar
Kirill Terekhov committed
563
		shell(array<element> & arr) //dynamic
564
			:m_arr(&arr.m_arr), m_size(&arr.m_size), local_link(NULL), local_size(0), fixed(false) {}
Kirill Terekhov's avatar
Kirill Terekhov committed
565
		shell(element * link, size_type size) //fixed
566
			:m_arr(&local_link), m_size(&local_size), local_link(NULL),local_size(0), fixed(true)
Kirill Terekhov's avatar
Kirill Terekhov committed
567
568
569
570
571
		{
			*m_arr = link;
			*m_size = size;
		}
		shell(const shell & other)
572
			:m_arr(&local_link), m_size(&local_size), local_link(NULL), local_size(0),fixed(other.fixed)
Kirill Terekhov's avatar
Kirill Terekhov committed
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
		{
			if( fixed )
			{
				*m_size = *other.m_size;
				*m_arr = *other.m_arr;
			}
			else
			{
				m_size = other.m_size;
				m_arr = other.m_arr;
			}
		}
		~shell()
		{
		}
588
		__INLINE const element & operator [] (size_type n) const
Kirill Terekhov's avatar
Kirill Terekhov committed
589
590
591
592
		{
			assert(n < *m_size );
			return *((*m_arr)+n);
		}
593
		__INLINE element & operator [] (size_type n)
Kirill Terekhov's avatar
Kirill Terekhov committed
594
595
596
597
		{
			assert(n < *m_size );
			return *((*m_arr)+n);
		}
598
		__INLINE const element & at (size_type n) const
Kirill Terekhov's avatar
Kirill Terekhov committed
599
600
601
602
		{
			assert(n < *m_size );
			return *((*m_arr)+n);
		}
603
		__INLINE element & at (size_type n)
Kirill Terekhov's avatar
Kirill Terekhov committed
604
605
606
607
608
609
610
611
612
613
		{
			assert(n < *m_size );
			return *((*m_arr)+n);
		}
		shell & operator =(shell const & other)
		{
			fixed = other.fixed;
			if( fixed )
			{
				m_size = &local_size;
614
				m_arr = &local_link;
Kirill Terekhov's avatar
Kirill Terekhov committed
615
616
617
618
619
620
621
622
623
624
625
626
				*m_size = *other.m_size;
				*m_arr = *other.m_arr;
			}
			else
			{
				m_size = other.m_size;
				m_arr = other.m_arr;
			}
			return *this;
		}
		void push_back(const element & e)
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
627
			assert( !fixed ); // array size is fixed
628
629
			*m_arr = array<element>::realloc(*m_arr,*m_size,(*m_size)+1);
			(*m_arr)[(*m_size)++] = e;
Kirill Terekhov's avatar
Kirill Terekhov committed
630
631
632
		}
		void pop_back()
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
633
			assert( !fixed ); // array size is fixed
Kirill Terekhov's avatar
Kirill Terekhov committed
634
			assert((*m_arr) != NULL);
635
			if( *m_size > 0)
Kirill Terekhov's avatar
Kirill Terekhov committed
636
			{
637
638
				*m_arr = array<element>::realloc(*m_arr,*m_size,(*m_size)-1);
				(*m_size)--;
Kirill Terekhov's avatar
Kirill Terekhov committed
639
			}
640
			else clear();
Kirill Terekhov's avatar
Kirill Terekhov committed
641
		}
642
		__INLINE element & back()
Kirill Terekhov's avatar
Kirill Terekhov committed
643
644
645
646
647
		{
			assert(*m_arr != NULL);
			assert(*m_size > 0 );
			return (*m_arr)[(*m_size)-1];
		}
648
		__INLINE const element & back() const
Kirill Terekhov's avatar
Kirill Terekhov committed
649
650
651
652
653
		{
			assert(*m_arr != NULL);
			assert(*m_size > 0 );
			return (*m_arr)[(*m_size)-1];
		}
654
		__INLINE element & front()
Kirill Terekhov's avatar
Kirill Terekhov committed
655
656
657
658
659
		{
			assert(*m_arr != NULL);
			assert(*m_size > 0 );
			return (*m_arr)[0];
		}
660
		__INLINE const element & front() const
Kirill Terekhov's avatar
Kirill Terekhov committed
661
662
663
664
665
		{
			assert(*m_arr != NULL);
			assert(*m_size > 0 );
			return (*m_arr)[0];
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
666
		__INLINE size_type capacity() { return array<element>::growth_formula(*m_size); }
Kirill Terekhov's avatar
Kirill Terekhov committed
667
		__INLINE bool empty() const { if( *m_size ) return false; return true; }
Kirill Terekhov's avatar
Kirill Terekhov committed
668
		void resize(size_type n, element c = element() )
Kirill Terekhov's avatar
Kirill Terekhov committed
669
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
670
			assert( !fixed ); // array size is fixed
Kirill Terekhov's avatar
Kirill Terekhov committed
671
			size_type oldsize = *m_size;
Kirill Terekhov's avatar
Kirill Terekhov committed
672
673
674
			*m_size = n;
			if( *m_size > 0 )
			{
675
676
				*m_arr = array<element>::realloc(*m_arr,oldsize,*m_size);
				if( oldsize < *m_size ) std::fill((*m_arr)+oldsize,(*m_arr)+(*m_size),c);
Kirill Terekhov's avatar
Kirill Terekhov committed
677
			}
678
			else clear();
Kirill Terekhov's avatar
Kirill Terekhov committed
679
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
680
		__INLINE size_type size() const {return *m_size;}
681
682
		void clear()
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
683
			assert( !fixed ); // array size is fixed
684
			if( *m_arr ) delete [] *m_arr;
685
			*m_arr = NULL;
686
			*m_size = 0;
Kirill Terekhov's avatar
Kirill Terekhov committed
687
688
689
690
		}
		void swap(shell<element> & other)
		{
			element * t_m_arr = *m_arr;
Kirill Terekhov's avatar
Kirill Terekhov committed
691
			size_type t_m_size = *m_size;
Kirill Terekhov's avatar
Kirill Terekhov committed
692
693
694
695
696
			*m_arr = *other.m_arr;
			*m_size = *other.m_size;
			*other.m_arr = t_m_arr;
			*other.m_size = t_m_size;
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
697
		__INLINE iterator begin() { return *m_arr; }
698
699
700
701
702
703
704
		__INLINE iterator end() { return (*m_arr)+(*m_size); }
		__INLINE const_iterator begin() const { return (*m_arr); }
		__INLINE const_iterator end() const { return (*m_arr)+(*m_size); }
		__INLINE reverse_iterator rbegin() { return reverse_iterator((*m_arr)+(*m_size)-1); }
		__INLINE reverse_iterator rend() { return reverse_iterator((*m_arr)-1); }
		__INLINE const_reverse_iterator rbegin() const { return const_reverse_iterator((*m_arr)+(*m_size)-1); }
		__INLINE const_reverse_iterator rend() const { return const_reverse_iterator((*m_arr)-1); }
705
706
		iterator erase(iterator pos)
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
707
			assert( !fixed ); // array size is fixed
Kirill Terekhov's avatar
Kirill Terekhov committed
708
			ptrdiff_t d = pos-begin();
709
			ptrdiff_t s = iterator((*m_arr)+(*m_size)-1)-pos;
Kirill Terekhov's avatar
Kirill Terekhov committed
710
			(*m_size)--;
711
			if( *m_size > 0 )
Kirill Terekhov's avatar
Kirill Terekhov committed
712
			{
713
714
				if( s ) array<element>::copy((*m_arr)+d+1, (*m_arr)+d+1+s, (*m_arr)+d);
				*m_arr = array<element>::realloc(*m_arr, (*m_size)+1, *m_size);
Kirill Terekhov's avatar
Kirill Terekhov committed
715
			}
716
			else clear();
Kirill Terekhov's avatar
Kirill Terekhov committed
717
718
719
720
			return (*m_arr)+d;
		}
		iterator erase(iterator b, iterator e)
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
721
			assert( !fixed ); // array size is fixed
Kirill Terekhov's avatar
Kirill Terekhov committed
722
723
724
725
			ptrdiff_t d = b-begin();
			ptrdiff_t s = end()-e;
			ptrdiff_t n = e-b;
			(*m_size) -= n;
726
			if( *m_size > 0 )
Kirill Terekhov's avatar
Kirill Terekhov committed
727
			{
728
729
730
				if( s ) array<element>::copy((*m_arr)+d+1,(*m_arr)+d+1+s,(*m_arr)+d);
				*m_arr = array<element>::realloc(*m_arr,(*m_size)+n,*m_size);
				
Kirill Terekhov's avatar
Kirill Terekhov committed
731
			}
732
			else clear();
Kirill Terekhov's avatar
Kirill Terekhov committed
733
734
735
736
			return (*m_arr)+d;
		}
		iterator insert(iterator pos, const element & x)
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
737
			assert( !fixed ); // array size is fixed
Kirill Terekhov's avatar
Kirill Terekhov committed
738
739
740
			if( static_cast<void *>(pos) == NULL )
			{
				assert((*m_arr) == NULL);
741
742
743
744
				*m_size = 1;
				*m_arr = array<element>::alloc(*m_size);
				(*m_arr)[0] = x;
				return *m_arr;
Kirill Terekhov's avatar
Kirill Terekhov committed
745
			}
746
			else
747
			{
748
749
750
751
752
753
754
				ptrdiff_t d = pos-begin();
				ptrdiff_t s = end()-pos;
				*m_arr = array<element>::realloc(*m_arr,*m_size,(*m_size)+1);
				(*m_size)++;
				if( s ) array<element>::copy((*m_arr)+d,(*m_arr)+d+s,(*m_arr)+d+1);
				(*m_arr)[d] = x;
				return (*m_arr)+d;
755
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
756
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
757
		void insert(iterator pos, size_type n, const element & x)
Kirill Terekhov's avatar
Kirill Terekhov committed
758
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
759
			assert( !fixed ); // array size is fixed
760
			if( n )
Kirill Terekhov's avatar
Kirill Terekhov committed
761
762
763
764
			{
				if( static_cast<void *>(pos) == NULL)
				{
					assert((*m_arr) == NULL);
765
766
767
					*m_arr = array<element>::alloc(n);
					*m_size = n;
					std::fill(*m_arr,(*m_arr)+(*m_size),x);
Kirill Terekhov's avatar
Kirill Terekhov committed
768
				}
769
				else
770
				{
771
772
773
774
775
776
					ptrdiff_t d = pos-iterator(*m_arr);
					ptrdiff_t s = iterator((*m_arr)+(*m_size))-pos;
					*m_arr = array<element>::realloc(*m_arr,*m_size,(*m_size)+n);
					*m_size += n;
					if( s ) array<element>::copy((*m_arr)+d,(*m_arr)+d+s,(*m_arr)+d+n);
					std::fill((*m_arr)+d,(*m_arr)+d+n,x);
777
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
778
779
780
781
782
			}
		}
		template <class InputIterator>
		void insert(iterator pos, InputIterator first, InputIterator last)
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
783
			assert( !fixed ); // array size is fixed
784
785
			size_type n = static_cast<size_type>(std::distance(first,last));
			if( n )
Kirill Terekhov's avatar
Kirill Terekhov committed
786
787
788
789
			{
				if( static_cast<void *>(pos) == NULL)
				{
					assert((*m_arr) == NULL);
790
791
792
					*m_arr = array<element>::alloc(n);
					*m_size = n;
					std::copy(first,last,*m_arr);
793
				}
794
				else
Kirill Terekhov's avatar
Kirill Terekhov committed
795
				{
796
797
798
799
800
801
					ptrdiff_t d = pos-iterator(*m_arr);
					ptrdiff_t s = iterator((*m_arr)+(*m_size))-pos;
					*m_arr = array<element>::realloc(*m_arr,*m_size,(*m_size)+n);
					*m_size += n;
					if( s ) array<element>::copy((*m_arr)+d,(*m_arr)+d+s,(*m_arr)+d+n);
					std::copy(first,last,(*m_arr)+d);
Kirill Terekhov's avatar
Kirill Terekhov committed
802
803
804
805
806
807
				}
			}
		}
		template <class InputIterator>
		void replace(iterator m_first, iterator m_last, InputIterator first, InputIterator last)
		{
808
			size_type n = static_cast<size_type>(std::distance(first,last));
Kirill Terekhov's avatar
Kirill Terekhov committed
809
810
811
			if( static_cast<void *>(m_first) == NULL)
			{
				assert((*m_arr)==NULL);
812
813
814
				*m_arr = array<element>::alloc(n);
				*m_size = n;
				std::copy(first,last,*m_arr);
Kirill Terekhov's avatar
Kirill Terekhov committed
815
			}
816
			else
Kirill Terekhov's avatar
Kirill Terekhov committed
817
			{
818
819
820
821
				ptrdiff_t q = m_last-m_first;
				ptrdiff_t d = m_first-iterator(*m_arr);
				ptrdiff_t s = iterator((*m_arr)+(*m_size))-m_last;
				if( n-q != 0 )
822
				{
823
824
825
					*m_arr = array<element>::realloc(*m_arr,*m_size,(*m_size)+static_cast<size_type>(n-q));	
					(*m_size)+=static_cast<size_type>(n-q);
					if( s ) array<element>::copy((*m_arr)+d+q,(*m_arr)+d+q+s,(*m_arr)+d+n);
826
				}
827
				std::copy(first,last,(*m_arr)+d);
Kirill Terekhov's avatar
Kirill Terekhov committed
828
829
			}
		}
830
831
832
		template <class InputIterator>
		void assign(InputIterator first, InputIterator last)
		{
833
			replace(begin(),end(),first,last);
Kirill Terekhov's avatar
Kirill Terekhov committed
834
835
		}
	};
836

Kirill Terekhov's avatar
Kirill Terekhov committed
837
838
839
840
841
842
843
	template<typename IndType,typename ValType>
	class interval
	{
	public:
		typedef ValType * iterator;
		typedef ValType const * const_iterator;
	private:
844
		ValType * parray;
Kirill Terekhov's avatar
Kirill Terekhov committed
845
846
847
848
		IndType beg_index, end_index;
	public:
		void clear()
		{
849
			if (!empty()) delete [] (parray + beg_index);
850
			parray = NULL;
851
			end_index = beg_index;
Kirill Terekhov's avatar
Kirill Terekhov committed
852
853
854
855
856
857
858
859
860
861
862
863
		}
		void swap(interval<IndType, ValType> & other)
		{
			{
				IndType tmp = beg_index;
				beg_index = other.beg_index;
				other.beg_index = tmp;
				tmp = end_index;
				end_index = other.end_index;
				other.end_index = tmp;
			}
			{
864
865
866
				ValType * tmp = parray;
				parray = other.parray;
				other.parray = tmp;
Kirill Terekhov's avatar
Kirill Terekhov committed
867
868
869
870
871
872
			}
		}
		interval()
		{
			beg_index = 0;
			end_index = 0;
873
			parray = NULL;
Kirill Terekhov's avatar
Kirill Terekhov committed
874
875
876
877
		}
		interval(IndType beg)
		{
			beg_index = beg;
878
879
			end_index = beg_index;
			parray = NULL;
Kirill Terekhov's avatar
Kirill Terekhov committed
880
881
882
883
884
885
886
		}
		interval(IndType beg, IndType end, ValType c = ValType())
		{
			beg_index = beg;
			end_index = end;
			if (beg != end)
			{
887
				ValType * tmp = new ValType[end_index-beg_index];
888
#if defined(DEBUGMEM)
889
				if( tmp == NULL ) {std::cout << __FILE__ << ":" << __LINE__ << "allocation returns NULL\n";}
890
#endif
891
892
893
894
				parray = tmp;
				assert(parray != NULL);
				parray = parray - beg_index;
				std::fill(parray+beg_index,parray+end_index,c);
Kirill Terekhov's avatar
Kirill Terekhov committed
895
			}
896
			else parray = NULL;
Kirill Terekhov's avatar
Kirill Terekhov committed
897
898
899
900
901
902
903
		}
		interval(const interval & other)
		{
			beg_index = other.beg_index;
			end_index = other.end_index;
			if( beg_index != end_index )
			{
904
				ValType * tmp = new ValType[end_index-beg_index];
905
#if defined(DEBUGMEM)
906
				if( tmp == NULL ) {std::cout << __FILE__ << ":" << __LINE__ << "allocation returns NULL\n";}
907
#endif
908
909
910
911
				parray = static_cast<ValType *>(tmp);
				assert(parray != NULL);
				parray = parray - beg_index;
				std::copy(other.parray+beg_index,other.parray+end_index,parray+beg_index);
Kirill Terekhov's avatar
Kirill Terekhov committed
912
			}
913
			else parray = NULL;
Kirill Terekhov's avatar
Kirill Terekhov committed
914
915
916
		}
		~interval()
		{
917
			clear();
Kirill Terekhov's avatar
Kirill Terekhov committed
918
919
920
921
922
		}
		interval & operator =(interval const & other)
		{
			if( &other != this )
			{
923
				clear();
Kirill Terekhov's avatar
Kirill Terekhov committed
924
925
926
927
				beg_index = other.beg_index;
				end_index = other.end_index;
				if( beg_index != end_index )
				{
928
					ValType * tmp = new ValType[end_index-beg_index];
929
#if defined(DEBUGMEM)
930
931
932
933
934
935
					if( tmp == NULL ) {std::cout << __FILE__ << ":" << __LINE__ << "allocation returns NULL\n";}
#endif
					parray = static_cast<ValType *>(tmp);
					assert(parray != NULL);
					parray = parray - beg_index;
					std::copy(other.parray+beg_index,other.parray+end_index,parray+beg_index);
Kirill Terekhov's avatar
Kirill Terekhov committed
936
937
938
939
940
941
942
943
				}
			}
			return *this;
		}
		ValType & at(IndType row)
		{
			assert(row >= beg_index);
			assert(row < end_index);
944
			return parray[row];
Kirill Terekhov's avatar
Kirill Terekhov committed
945
946
947
948
949
		}
		const ValType & at(IndType row) const
		{
			assert(row >= beg_index);
			assert(row < end_index);
950
			return parray[row];
Kirill Terekhov's avatar
Kirill Terekhov committed
951
952
953
954
955
		}
		ValType & operator [](IndType row)
		{
			assert(row >= beg_index );
			assert(row < end_index );
956
			return parray[row];
Kirill Terekhov's avatar
Kirill Terekhov committed
957
958
959
960
961
		}
		const ValType & operator [](IndType row) const
		{
			assert(row >= beg_index );
			assert(row < end_index );
962
			return parray[row];
Kirill Terekhov's avatar
Kirill Terekhov committed
963
964
965
966
967
968
		}
		void set_interval_beg(IndType beg)
		{
			IndType shift = beg-beg_index;
			shift_interval(shift);
		}
969
		void set_interval_end(IndType end, const ValType & c = ValType())
Kirill Terekhov's avatar
Kirill Terekhov committed
970
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
971
			if( end == end_index ) return;
Kirill Terekhov's avatar
Kirill Terekhov committed
972
973
			if( beg_index != end )
			{
974
				ValType * parray_new = new ValType[end-beg_index];
975
#if defined(DEBUGMEM)
976
				if( parray_new == NULL ) {std::cout << __FILE__ << ":" << __LINE__ << "allocation returns NULL\n";}
977
#endif
978
979
				assert(parray_new != NULL);
				parray_new = parray_new - beg_index;
980
				//IndType mbeg = beg_index;
Kirill Terekhov's avatar
Kirill Terekhov committed
981
				IndType mend = std::min(end,end_index);
982
				if( !empty() ) 
983
				{
984
					//~ std::cout << beg_index << ":" << end_index << " new end " << end << " old ptr " << (void*)parray << " new ptr " << (void *)parray_new << std::endl;
Kirill Terekhov's avatar
Kirill Terekhov committed
985
					std::copy(parray+beg_index,parray+mend,parray_new+beg_index);
986
					clear();
987
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
988
				if( mend < end ) std::fill(parray_new+mend,parray_new+end,c);
989
				parray = parray_new;
Kirill Terekhov's avatar
Kirill Terekhov committed
990
			}
991
			else clear();
Kirill Terekhov's avatar
Kirill Terekhov committed
992
993
			end_index = end;
		}
994

Kirill Terekhov's avatar
Kirill Terekhov committed
995
996
		void shift_interval(IndType shift)
		{
997
			parray = parray + beg_index;
Kirill Terekhov's avatar
Kirill Terekhov committed
998
999
			beg_index += shift;
			end_index += shift;
1000
1001
1002
1003
1004
1005
			parray = parray - beg_index;
		}
		iterator begin() {return parray+beg_index;}
		const_iterator begin() const {return parray+beg_index;}
		iterator end() {return parray + end_index;}
		const_iterator end() const {return parray + end_index;}
Kirill Terekhov's avatar
Kirill Terekhov committed
1006
1007
		IndType get_interval_beg() const { return beg_index; }
		IndType get_interval_end() const { return end_index; }
Kirill Terekhov's avatar
Kirill Terekhov committed
1008
		int size() const {return end_index - beg_index;}
Kirill Terekhov's avatar
Kirill Terekhov committed
1009
1010
		bool empty() const {return beg_index == end_index;}
	};
Kirill Terekhov's avatar
Kirill Terekhov committed
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
	//this is supposed to provide thread-safe storage type for chunks in chunk_array
	//the idea is that pointer to block is never moved
	//so that access to any entry before size() is correct on resize
	//critical section is required on resize()
	template<typename element, size_t base = 512>
	class linked_array
	{
		element e[base]; //storage of current node
		size_t ne; //number of elements in array
		linked_array * next; //link to next node
		linked_array(const linked_array & b) {} //don't copy me
		linked_array & operator = (linked_array const & b) { return *this; } //don't copy me
	public:
		linked_array() : ne(0), next(NULL) {}
		void clear()
		{
			if (next)
1028
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
1029
				next->clear();
1030
1031
1032
				delete next;
				next = NULL;
			}