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

25
26
#define PACK_ARRAY

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

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

namespace INMOST
{
Kirill Terekhov's avatar
Kirill Terekhov committed
45
46
47
48
49
50
51
52
53
54
55
56
	//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;};
57

58

Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
59
60
61
#if defined(PACK_ARRAY)
#pragma pack(push,r1,4)
#endif
Kirill Terekhov's avatar
Kirill Terekhov committed
62
63
64
	// 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
65
66
67
68
	template<typename element>//, typename enumerator = unsigned int>
	class array
	{
	public:
Kirill Terekhov's avatar
Kirill Terekhov committed
69
70
		typedef unsigned size_type;
		typedef make_unsigned<size_type>::type uenum;
Kirill Terekhov's avatar
Kirill Terekhov committed
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
		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
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
Updates    
Kirill Terekhov committed
88
			_iterator operator +(size_t n) const { return _iterator(e+n); }
Kirill Terekhov's avatar
Kirill Terekhov committed
89
			_iterator & operator +=(size_t n) { e+=n; return *this; }
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
			_iterator & operator --(){ --e; return *this; }
93
			_iterator operator --(int) { return _iterator(e--); }
Kirill Terekhov's avatar
Kirill Terekhov committed
94
			ptrdiff_t operator -(const _iterator & other) const {return e-other.e;}
95
96
			etype & operator *() const { return *e; }
			etype * operator ->() const { return e; }
Kirill Terekhov's avatar
Kirill Terekhov committed
97
			_iterator & operator =(_iterator const & other) { e = other.e; return *this; }
Kirill Terekhov's avatar
Kirill Terekhov committed
98
99
100
101
102
103
			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;}
104
			operator void *() const {return static_cast<void *> (e);}
Kirill Terekhov's avatar
Kirill Terekhov committed
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
		};
		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
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
Updates    
Kirill Terekhov committed
125
			_reverse_iterator operator +(size_t n) const {return _reverse_iterator(e-n); }
Kirill Terekhov's avatar
Kirill Terekhov committed
126
			_reverse_iterator & operator +=(size_t n) { e-=n; return *this; }
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
			_reverse_iterator & operator --(){ ++e; return *this; }
130
			_reverse_iterator operator --(int) { return _reverse_iterator(e++); }
Kirill Terekhov's avatar
Kirill Terekhov committed
131
			ptrdiff_t operator -(const _reverse_iterator & other) const {return other.e-e;}
132
133
			etype & operator *() const { return *e; }
			etype * operator ->() const { return e; }
Kirill Terekhov's avatar
Kirill Terekhov committed
134
			_reverse_iterator & operator =(_reverse_iterator const & other) { e = other.e; return *this;}
Kirill Terekhov's avatar
Kirill Terekhov committed
135
136
137
138
139
140
			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;}
141
			operator void *()const {return static_cast<void *> (e);}
Kirill Terekhov's avatar
Kirill Terekhov committed
142
143
144
145
		};
		typedef _reverse_iterator<element> reverse_iterator;
		typedef _reverse_iterator<const element> const_reverse_iterator;
	private:
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
146

Kirill Terekhov's avatar
Kirill Terekhov committed
147
		element * m_arr;
Kirill Terekhov's avatar
Kirill Terekhov committed
148
		size_type m_size;
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
149

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

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

Kirill Terekhov's avatar
Kirill Terekhov committed
997
998
		void shift_interval(IndType shift)
		{
999
			parray = parray + beg_index;
Kirill Terekhov's avatar
Kirill Terekhov committed
1000
1001
			beg_index += shift;
			end_index += shift;
1002
1003
1004
1005
1006
1007
			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
1008
1009
		IndType get_interval_beg() const { return beg_index; }
		IndType get_interval_end() const { return end_index; }
Kirill Terekhov's avatar
Kirill Terekhov committed
1010
		int size() const {return end_index - beg_index;}
Kirill Terekhov's avatar
Kirill Terekhov committed
1011
1012
		bool empty() const {return beg_index == end_index;}
	};
Kirill Terekhov's avatar
Kirill Terekhov committed
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
	//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)
1030
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
1031
				next->clear();
1032
1033
1034
				delete next;
				next = NULL;
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
			ne = 0;
		}
		element & operator [](size_t n)
		{
			if (n < base)
			{
				assert(n < ne);
				return e[n];
			}
			else
			{
				assert(next);
				return next->operator [](n-base);
			}
		}
		const element & operator [](size_t n) const
		{
			if (n < base)
			{
				assert(n < ne);
				return e[n];
			}
			else
			{
				assert(next);
				return next->operator [](n - base);
			}
		}
1063
		size_t size() const
Kirill Terekhov's avatar
Kirill Terekhov committed
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
		{
			if( ne == base && next )
				return base+next()->size();
			else
				return ne;
		}
		void resize(size_t new_n, const element & c =  element())
		{
			if (new_n <= base)
			{
				for (size_t k = ne; k < new_n; ++k)
1075
					e[k] = c;
Kirill Terekhov's avatar
Kirill Terekhov committed
1076
				ne = new_n;
1077
1078
1079
1080
1081
1082
				if (next)
				{
					next->clear();
					delete next;
					next = NULL;
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
1083
1084
1085
1086
1087
1088
1089
<