container.hpp 75.4 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
388
				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;
				return m_arr+d;
389
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
390
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
391
		void insert(iterator pos, size_type n, const element & x)
Kirill Terekhov's avatar
Kirill Terekhov committed
392
393
394
395
396
397
		{
			if( n > 0 )
			{
				if( static_cast<void *>(pos) == NULL)
				{
					assert(m_arr == NULL);
398
399
400
					m_arr = alloc(n);
					m_size = n;
					std::fill(m_arr,m_arr+m_size,x);
Kirill Terekhov's avatar
Kirill Terekhov committed
401
				}
402
				else
403
				{
404
405
406
407
408
409
					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);
410
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
411
412
413
414
415
			}
		}
		template <class InputIterator>
		void insert(iterator pos, InputIterator first, InputIterator last)
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
416
			size_type n = static_cast<size_type>(std::distance(first,last));
Kirill Terekhov's avatar
Kirill Terekhov committed
417
418
419
420
421
			if( n > 0 )
			{
				if( static_cast<void *>(pos) == NULL)
				{
					assert(m_arr == NULL);
422
423
424
					m_arr = alloc(n);
					m_size = n;
					std::copy(first,last,m_arr);
425
				}
426
				else
Kirill Terekhov's avatar
Kirill Terekhov committed
427
				{
428
429
430
431
432
433
					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
434
435
436
437
438
439
440
				}
			}
		}
		template <class InputIterator>
		void replace(iterator m_first, iterator m_last, InputIterator first, InputIterator last)
		{
			assert( m_size >= 0 );
441
			size_type n = static_cast<size_type>(std::distance(first,last));
Kirill Terekhov's avatar
Kirill Terekhov committed
442
443
444
			if( static_cast<void *>(m_first) == NULL && m_arr == NULL)
			{
				assert(m_arr == NULL);
445
446
447
				m_arr = alloc(n);
				m_size = n;
				std::copy(first,last,m_arr);
Kirill Terekhov's avatar
Kirill Terekhov committed
448
			}
449
			else
Kirill Terekhov's avatar
Kirill Terekhov committed
450
			{
451
452
453
454
				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 )
455
				{
456
457
458
					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);
459
				}
460
				std::copy(first,last,m_arr+d);
Kirill Terekhov's avatar
Kirill Terekhov committed
461
462
			}
		}
463
464
465
466
467
		template <class InputIterator>
		void assign(InputIterator first, InputIterator last)
		{
			replace(begin(),end(),first,last);
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
468
		template<class> friend class shell;
469
	};
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
470
471
472
#if defined(PACK_ARRAY)
#pragma pack(pop,r1)
#endif
Kirill Terekhov's avatar
Kirill Terekhov committed
473
474
475
476
	template<typename element>
	class shell
	{
	public:
Kirill Terekhov's avatar
Kirill Terekhov committed
477
		typedef typename array<element>::size_type size_type;
Kirill Terekhov's avatar
Kirill Terekhov committed
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
		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
493
			_iterator operator -(size_t n) const { return _iterator(e-n); }
Kirill Terekhov's avatar
Kirill Terekhov committed
494
			_iterator & operator -=(size_t n) { e-=n; return *this; }
Kirill Terekhov's avatar
Updates    
Kirill Terekhov committed
495
			_iterator operator +(size_t n) const { return _iterator(e+n); }
Kirill Terekhov's avatar
Kirill Terekhov committed
496
			_iterator & operator +=(size_t n) { e+=n; return *this; }
Kirill Terekhov's avatar
Kirill Terekhov committed
497
			_iterator & operator ++(){ ++e; return *this;}
498
			_iterator operator ++(int) { return _iterator(e++); }
Kirill Terekhov's avatar
Kirill Terekhov committed
499
			_iterator & operator --(){ --e; return *this; }
500
			_iterator operator --(int) { return _iterator(e--); }
Kirill Terekhov's avatar
Kirill Terekhov committed
501
			ptrdiff_t operator -(const _iterator & other) const {return e-other.e;}
502
503
			dtype & operator *() const { return *e; }
			dtype * operator ->() const { return e; }
Kirill Terekhov's avatar
Kirill Terekhov committed
504
			_iterator & operator =(_iterator const & other) { e = other.e; return *this; }
505
506
507
508
509
510
511
			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
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
		};
		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
530
			_reverse_iterator operator -(size_t n) const { return _reverse_iterator(e+n); }
Kirill Terekhov's avatar
Kirill Terekhov committed
531
			_reverse_iterator & operator -=(size_t n) { e+=n; return *this; }
Kirill Terekhov's avatar
Updates    
Kirill Terekhov committed
532
			_reverse_iterator operator +(size_t n) const {return _reverse_iterator(e-n); }
Kirill Terekhov's avatar
Kirill Terekhov committed
533
			_reverse_iterator & operator +=(size_t n) { e-=n; return *this; }
Kirill Terekhov's avatar
Kirill Terekhov committed
534
			_reverse_iterator & operator ++(){ --e; return *this;}
535
			_reverse_iterator operator ++(int) { return _reverse_iterator(e--); }
Kirill Terekhov's avatar
Kirill Terekhov committed
536
			_reverse_iterator & operator --(){ ++e; return *this; }
537
			_reverse_iterator operator --(int) { return _reverse_iterator(e++); }
Kirill Terekhov's avatar
Kirill Terekhov committed
538
			ptrdiff_t operator -(const _reverse_iterator & other) const {return other.e-e;}
539
540
			dtype & operator *() const { return *e; }
			dtype * operator ->() const { return e; }
Kirill Terekhov's avatar
Kirill Terekhov committed
541
			_reverse_iterator & operator =(_reverse_iterator const & other) { e = other.e; return *this;}
542
543
544
545
546
547
548
			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
549
550
551
552
553
		};
		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
554
		size_type * m_size;
Kirill Terekhov's avatar
Kirill Terekhov committed
555
		element * local_link;
Kirill Terekhov's avatar
Kirill Terekhov committed
556
		size_type local_size;
Kirill Terekhov's avatar
Kirill Terekhov committed
557
558
		bool fixed;
	public:
Kirill Terekhov's avatar
Kirill Terekhov committed
559
560
		__INLINE element * data() {return *m_arr;}
		__INLINE const element * data() const {return *m_arr;}
561
		shell() :m_arr(NULL), m_size(NULL), local_link(NULL), local_size(0), fixed(false) { }
Kirill Terekhov's avatar
Kirill Terekhov committed
562
		shell(array<element> & arr) //dynamic
563
			: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
564
		shell(element * link, size_type size) //fixed
565
			:m_arr(&local_link), m_size(&local_size), local_link(NULL),local_size(0), fixed(true)
Kirill Terekhov's avatar
Kirill Terekhov committed
566
567
568
569
570
		{
			*m_arr = link;
			*m_size = size;
		}
		shell(const shell & other)
571
			:m_arr(&local_link), m_size(&local_size), local_link(NULL), local_size(0),fixed(other.fixed)
Kirill Terekhov's avatar
Kirill Terekhov committed
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
		{
			if( fixed )
			{
				*m_size = *other.m_size;
				*m_arr = *other.m_arr;
			}
			else
			{
				m_size = other.m_size;
				m_arr = other.m_arr;
			}
		}
		~shell()
		{
		}
587
		__INLINE const element & operator [] (size_type n) const
Kirill Terekhov's avatar
Kirill Terekhov committed
588
589
590
591
		{
			assert(n < *m_size );
			return *((*m_arr)+n);
		}
592
		__INLINE element & operator [] (size_type n)
Kirill Terekhov's avatar
Kirill Terekhov committed
593
594
595
596
		{
			assert(n < *m_size );
			return *((*m_arr)+n);
		}
597
		__INLINE const element & at (size_type n) const
Kirill Terekhov's avatar
Kirill Terekhov committed
598
599
600
601
		{
			assert(n < *m_size );
			return *((*m_arr)+n);
		}
602
		__INLINE element & at (size_type n)
Kirill Terekhov's avatar
Kirill Terekhov committed
603
604
605
606
607
608
609
610
611
612
		{
			assert(n < *m_size );
			return *((*m_arr)+n);
		}
		shell & operator =(shell const & other)
		{
			fixed = other.fixed;
			if( fixed )
			{
				m_size = &local_size;
613
				m_arr = &local_link;
Kirill Terekhov's avatar
Kirill Terekhov committed
614
615
616
617
618
619
620
621
622
623
624
625
				*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
626
			assert( !fixed ); // array size is fixed
627
628
			*m_arr = array<element>::realloc(*m_arr,*m_size,(*m_size)+1);
			(*m_arr)[(*m_size)++] = e;
Kirill Terekhov's avatar
Kirill Terekhov committed
629
630
631
		}
		void pop_back()
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
632
			assert( !fixed ); // array size is fixed
Kirill Terekhov's avatar
Kirill Terekhov committed
633
			assert((*m_arr) != NULL);
634
			if( *m_size > 0)
Kirill Terekhov's avatar
Kirill Terekhov committed
635
			{
636
637
				*m_arr = array<element>::realloc(*m_arr,*m_size,(*m_size)-1);
				(*m_size)--;
Kirill Terekhov's avatar
Kirill Terekhov committed
638
			}
639
			else clear();
Kirill Terekhov's avatar
Kirill Terekhov committed
640
		}
641
		__INLINE element & back()
Kirill Terekhov's avatar
Kirill Terekhov committed
642
643
644
645
646
		{
			assert(*m_arr != NULL);
			assert(*m_size > 0 );
			return (*m_arr)[(*m_size)-1];
		}
647
		__INLINE const element & back() const
Kirill Terekhov's avatar
Kirill Terekhov committed
648
649
650
651
652
		{
			assert(*m_arr != NULL);
			assert(*m_size > 0 );
			return (*m_arr)[(*m_size)-1];
		}
653
		__INLINE element & front()
Kirill Terekhov's avatar
Kirill Terekhov committed
654
655
656
657
658
		{
			assert(*m_arr != NULL);
			assert(*m_size > 0 );
			return (*m_arr)[0];
		}
659
		__INLINE const element & front() const
Kirill Terekhov's avatar
Kirill Terekhov committed
660
661
662
663
664
		{
			assert(*m_arr != NULL);
			assert(*m_size > 0 );
			return (*m_arr)[0];
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
665
		__INLINE size_type capacity() { return array<element>::growth_formula(*m_size); }
Kirill Terekhov's avatar
Kirill Terekhov committed
666
		__INLINE bool empty() const { if( *m_size ) return false; return true; }
Kirill Terekhov's avatar
Kirill Terekhov committed
667
		void resize(size_type n, element c = element() )
Kirill Terekhov's avatar
Kirill Terekhov committed
668
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
669
			assert( !fixed ); // array size is fixed
Kirill Terekhov's avatar
Kirill Terekhov committed
670
			size_type oldsize = *m_size;
Kirill Terekhov's avatar
Kirill Terekhov committed
671
672
673
			*m_size = n;
			if( *m_size > 0 )
			{
674
675
				*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
676
			}
677
			else clear();
Kirill Terekhov's avatar
Kirill Terekhov committed
678
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
679
		__INLINE size_type size() const {return *m_size;}
680
681
		void clear()
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
682
			assert( !fixed ); // array size is fixed
683
			if( *m_arr ) delete [] *m_arr;
684
			*m_arr = NULL;
685
			*m_size = 0;
Kirill Terekhov's avatar
Kirill Terekhov committed
686
687
688
689
		}
		void swap(shell<element> & other)
		{
			element * t_m_arr = *m_arr;
Kirill Terekhov's avatar
Kirill Terekhov committed
690
			size_type t_m_size = *m_size;
Kirill Terekhov's avatar
Kirill Terekhov committed
691
692
693
694
695
			*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
696
		__INLINE iterator begin() { return *m_arr; }
697
698
699
700
701
702
703
		__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); }
704
705
		iterator erase(iterator pos)
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
706
			assert( !fixed ); // array size is fixed
Kirill Terekhov's avatar
Kirill Terekhov committed
707
			ptrdiff_t d = pos-begin();
708
			ptrdiff_t s = iterator((*m_arr)+(*m_size)-1)-pos;
Kirill Terekhov's avatar
Kirill Terekhov committed
709
			(*m_size)--;
710
			if( *m_size > 0 )
Kirill Terekhov's avatar
Kirill Terekhov committed
711
			{
712
713
				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
714
			}
715
			else clear();
Kirill Terekhov's avatar
Kirill Terekhov committed
716
717
718
719
			return (*m_arr)+d;
		}
		iterator erase(iterator b, iterator e)
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
720
			assert( !fixed ); // array size is fixed
Kirill Terekhov's avatar
Kirill Terekhov committed
721
722
723
724
			ptrdiff_t d = b-begin();
			ptrdiff_t s = end()-e;
			ptrdiff_t n = e-b;
			(*m_size) -= n;
725
			if( *m_size > 0 )
Kirill Terekhov's avatar
Kirill Terekhov committed
726
			{
727
728
729
				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
730
			}
731
			else clear();
Kirill Terekhov's avatar
Kirill Terekhov committed
732
733
734
735
			return (*m_arr)+d;
		}
		iterator insert(iterator pos, const element & x)
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
736
			assert( !fixed ); // array size is fixed
Kirill Terekhov's avatar
Kirill Terekhov committed
737
738
739
			if( static_cast<void *>(pos) == NULL )
			{
				assert((*m_arr) == NULL);
740
741
742
743
				*m_size = 1;
				*m_arr = array<element>::alloc(*m_size);
				(*m_arr)[0] = x;
				return *m_arr;
Kirill Terekhov's avatar
Kirill Terekhov committed
744
			}
745
			else
746
			{
747
748
749
750
751
752
753
				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;
754
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
755
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
756
		void insert(iterator pos, size_type n, const element & x)
Kirill Terekhov's avatar
Kirill Terekhov committed
757
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
758
			assert( !fixed ); // array size is fixed
759
			if( n )
Kirill Terekhov's avatar
Kirill Terekhov committed
760
761
762
763
			{
				if( static_cast<void *>(pos) == NULL)
				{
					assert((*m_arr) == NULL);
764
765
766
					*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
767
				}
768
				else
769
				{
770
771
772
773
774
775
					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);
776
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
777
778
779
780
781
			}
		}
		template <class InputIterator>
		void insert(iterator pos, InputIterator first, InputIterator last)
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
782
			assert( !fixed ); // array size is fixed
783
784
			size_type n = static_cast<size_type>(std::distance(first,last));
			if( n )
Kirill Terekhov's avatar
Kirill Terekhov committed
785
786
787
788
			{
				if( static_cast<void *>(pos) == NULL)
				{
					assert((*m_arr) == NULL);
789
790
791
					*m_arr = array<element>::alloc(n);
					*m_size = n;
					std::copy(first,last,*m_arr);
792
				}
793
				else
Kirill Terekhov's avatar
Kirill Terekhov committed
794
				{
795
796
797
798
799
800
					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
801
802
803
804
805
806
				}
			}
		}
		template <class InputIterator>
		void replace(iterator m_first, iterator m_last, InputIterator first, InputIterator last)
		{
807
			size_type n = static_cast<size_type>(std::distance(first,last));
Kirill Terekhov's avatar
Kirill Terekhov committed
808
809
810
			if( static_cast<void *>(m_first) == NULL)
			{
				assert((*m_arr)==NULL);
811
812
813
				*m_arr = array<element>::alloc(n);
				*m_size = n;
				std::copy(first,last,*m_arr);
Kirill Terekhov's avatar
Kirill Terekhov committed
814
			}
815
			else
Kirill Terekhov's avatar
Kirill Terekhov committed
816
			{
817
818
819
820
				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 )
821
				{
822
823
824
					*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);
825
				}
826
				std::copy(first,last,(*m_arr)+d);
Kirill Terekhov's avatar
Kirill Terekhov committed
827
828
			}
		}
829
830
831
		template <class InputIterator>
		void assign(InputIterator first, InputIterator last)
		{
832
			replace(begin(),end(),first,last);
Kirill Terekhov's avatar
Kirill Terekhov committed
833
834
		}
	};
835

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

Kirill Terekhov's avatar
Kirill Terekhov committed
994
995
		void shift_interval(IndType shift)
		{
996
			parray = parray + beg_index;
Kirill Terekhov's avatar
Kirill Terekhov committed
997
998
			beg_index += shift;
			end_index += shift;
999
1000
1001
1002
1003
1004
			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
1005
1006
		IndType get_interval_beg() const { return beg_index; }
		IndType get_interval_end() const { return end_index; }
Kirill Terekhov's avatar
Kirill Terekhov committed
1007
		int size() const {return end_index - beg_index;}
Kirill Terekhov's avatar
Kirill Terekhov committed
1008
1009
		bool empty() const {return beg_index == end_index;}
	};
1010

Kirill Terekhov's avatar
Kirill Terekhov committed
1011
1012
1013
1014
	template<typename element, unsigned int stacked>
	class dynarray
	{
	public:
Kirill Terekhov's avatar
Kirill Terekhov committed
1015
		typedef size_t size_type;
Kirill Terekhov's avatar
Kirill Terekhov committed
1016
1017
1018
1019
1020
1021
1022
1023
1024
		template<typename dtype>
		class _iterator
		{
		private:
			dtype * e;
		public:
			typedef dtype * pointer;
			typedef dtype & reference;
			typedef dtype value_type;
Kirill Terekhov's avatar
Kirill Terekhov committed
1025
			typedef size_type difference_type;
Kirill Terekhov's avatar
Kirill Terekhov committed
1026
1027
1028
1029
1030
			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
1031
			_iterator operator -(size_type n) const { return _iterator(e-n); }
Kirill Terekhov's avatar
Kirill Terekhov committed
1032
			_iterator & operator -=(size_type n) { e-=n; return *this; }
Kirill Terekhov's avatar
Updates    
Kirill Terekhov committed
1033
			_iterator operator +(size_type n) const { return _iterator(e+n); }
Kirill Terekhov's avatar
Kirill Terekhov committed
1034
			_iterator & operator +=(size_type n) { e+=n; return *this; }
Kirill Terekhov's avatar
Kirill Terekhov committed
1035
			_iterator & operator ++(){ ++e; return *this;}
1036
			_iterator operator ++(int) { return _iterator(e++); }
Kirill Terekhov's avatar
Kirill Terekhov committed
1037
			_iterator & operator --(){ --e; return *this; }
1038
			_iterator operator --(int) { return _iterator(e--); }
Kirill Terekhov's avatar
Kirill Terekhov committed
1039
			size_type operator -(const _iterator & other) const {return static_cast<size_type>(e-other.e);}
1040
1041
			dtype & operator *() const { return *e; }
			dtype * operator ->() const { return e; }
Kirill Terekhov's avatar
Kirill Terekhov committed
1042
			_iterator & operator =(_iterator const & other) { e = other.e; return *this; }
Kirill Terekhov's avatar
Updates    
Kirill Terekhov committed
1043
1044
1045
1046
1047
1048
			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;}
1049
			operator void *()const {return static_cast<void *> (e);}