container.hpp 105 KB
Newer Older
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
1

Kirill Terekhov's avatar
Kirill Terekhov committed
2
3
4
5
6
7
8
9
10
11
12
13
14
#ifndef _CONTAINER_HPP
#define _CONTAINER_HPP


#include <stdlib.h>
#include <stddef.h>
#include <string.h>
#include <memory>
#include <new>
#include <iterator>
#include <cmath>
#include <assert.h>
#include <limits>
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
15
#include "inmost_common.h"
Kirill Terekhov's avatar
Kirill Terekhov committed
16

Kirill Terekhov's avatar
Kirill Terekhov committed
17
18

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

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

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

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

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

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

Kirill Terekhov's avatar
Kirill Terekhov committed
150
		element * m_arr;
Kirill Terekhov's avatar
Kirill Terekhov committed
151
		size_type m_size;
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
152

Kirill Terekhov's avatar
Kirill Terekhov committed
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
		//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);
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
168
	public:
Kirill Terekhov's avatar
Kirill Terekhov committed
169
170
		__INLINE element * data() {return m_arr;}
		__INLINE const element * data() const {return m_arr;}
Kirill Terekhov's avatar
Kirill Terekhov committed
171
		array() {m_arr = NULL; m_size = 0;}
Kirill Terekhov's avatar
Kirill Terekhov committed
172
		array(size_type n,element c = element())
Kirill Terekhov's avatar
Kirill Terekhov committed
173
174
		{
			m_size = n;
Kirill Terekhov's avatar
Kirill Terekhov committed
175
			m_arr = static_cast<element *>(malloc(sizeof(element)*growth_formula(m_size)));
Kirill Terekhov's avatar
Kirill Terekhov committed
176
			assert(m_arr != NULL);
Kirill Terekhov's avatar
Kirill Terekhov committed
177
			for(size_type i = 0; i < m_size; i++) new (m_arr+i) element(c);
Kirill Terekhov's avatar
Kirill Terekhov committed
178
179
180
181
		}
		template<class InputIterator>
		array(InputIterator first, InputIterator last)
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
182
183
184
			//isInputForwardIterators<element,InputIterator>();
			m_size = static_cast<size_type>(std::distance(first,last));
			m_arr = static_cast<element *>(malloc(sizeof(element)*growth_formula(m_size)));
Kirill Terekhov's avatar
Kirill Terekhov committed
185
186
			assert(m_arr != NULL);
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
187
				size_type i = 0;
Kirill Terekhov's avatar
Kirill Terekhov committed
188
189
190
191
192
193
194
				InputIterator it = first;
				while(it != last) new (m_arr+i++) element(*it++);
			}
		}
		array(const array & other)
		{
			m_size = other.m_size;
195
			if( m_size )
Kirill Terekhov's avatar
Kirill Terekhov committed
196
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
197
				m_arr = static_cast<element *>(malloc(sizeof(element)*growth_formula(m_size)));
Kirill Terekhov's avatar
Kirill Terekhov committed
198
199
200
				assert(m_arr != NULL);
			}
			else m_arr = NULL;
Kirill Terekhov's avatar
Kirill Terekhov committed
201
			for(size_type i = 0; i < m_size; i++) new (m_arr+i) element(other.m_arr[i]);
Kirill Terekhov's avatar
Kirill Terekhov committed
202
203
204
		}
		~array()
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
205
			for(size_type i = 0; i < m_size; i++) m_arr[i].~element();
Kirill Terekhov's avatar
Kirill Terekhov committed
206
207
208
209
			if( m_arr != NULL ) free(m_arr);
			m_arr = NULL;
			m_size = 0;
		}
210
		__INLINE const element & operator [] (size_type n) const
Kirill Terekhov's avatar
Kirill Terekhov committed
211
212
213
214
		{
			assert(n < m_size);
			return m_arr[n];
		}
215
		__INLINE element & operator [] (size_type n)
Kirill Terekhov's avatar
Kirill Terekhov committed
216
217
218
219
		{
			assert(n < m_size);
			return m_arr[n];
		}
220
		__INLINE const element & at (size_type n) const
Kirill Terekhov's avatar
Kirill Terekhov committed
221
222
223
224
		{
			assert(n < m_size);
			return m_arr[n];
		}
225
		__INLINE element & at (size_type n)
Kirill Terekhov's avatar
Kirill Terekhov committed
226
227
228
229
		{
			assert(n < m_size);
			return m_arr[n];
		}
230
		__INLINE element & at_safe (size_type n)
Kirill Terekhov's avatar
Kirill Terekhov committed
231
232
233
234
235
236
237
238
		{
			if( n >= m_size ) resize(n+1);
			return m_arr[n];
		}
		array & operator =(array const & other)
		{
			if( this != &other )
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
239
				for(size_type i = 0; i < m_size; i++) m_arr[i].~element();
240
				if(m_arr != NULL )
Kirill Terekhov's avatar
Kirill Terekhov committed
241
242
243
				{
					free(m_arr);
					m_arr = NULL;
244
					m_size = 0;
Kirill Terekhov's avatar
Kirill Terekhov committed
245
246
247
248
				}
				if( other.m_arr != NULL )
				{
					m_size = other.m_size;
Kirill Terekhov's avatar
Kirill Terekhov committed
249
					m_arr = static_cast<element *>(malloc(sizeof(element)*growth_formula(m_size)));
Kirill Terekhov's avatar
Kirill Terekhov committed
250
251
252
253
254
255
256
257
					assert(m_arr != NULL);
					memcpy(m_arr,other.m_arr,sizeof(element)*m_size);
				}
			}
			return *this;
		}
		void push_back(const element & e)
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
258
259
260
261
262
263
264
265
266
267
268
269
270
#if !defined(USE_OPTIMIZED_ARRAY_ALLOCATION)
			//unoptimized variant
			if( m_size+1 > growth_formula(m_size) )
				m_arr = static_cast<element *>(realloc(m_arr,sizeof(element)*growth_formula(++m_size)));
			else ++m_size;
#else
			//optimized for current growth_formula
			if( m_size < 2 )
				m_arr = static_cast<element *>(realloc(m_arr,sizeof(element)*(++m_size)));
			else if( ((m_size+1) & (m_size-1)) == 1 )
				m_arr = static_cast<element *>(realloc(m_arr,sizeof(element)*(m_size++ << 1)));
			else m_size++;
#endif
Kirill Terekhov's avatar
Kirill Terekhov committed
271
272
273
274
275
276
277
			assert(m_arr != NULL);
			new (m_arr+m_size-1) element(e);
		}
		void pop_back()
		{
			assert(m_arr != NULL);
			m_arr[m_size--].~element();
Kirill Terekhov's avatar
Kirill Terekhov committed
278
279
280
281
282
283
284
285
286
287
288
			if( m_size > 0)
			{
#if !defined(USE_OPTIMIZED_ARRAY_ALLOCATION)
				//unoptimized variant
				size_type gf = growth_formula(m_size);
				if( m_size+1 > gf )
					m_arr = static_cast<element *>(realloc(m_arr,sizeof(element)*gf));
#else
				if( ((m_size+1) & (m_size-1)) == 1 || m_size == 1)
					m_arr = static_cast<element *>(realloc(m_arr,sizeof(element)*m_size));
#endif
Kirill Terekhov's avatar
Kirill Terekhov committed
289
				assert(m_arr != NULL);
290
291
			}
			else
Kirill Terekhov's avatar
Kirill Terekhov committed
292
293
294
295
296
			{
				free(m_arr);
				m_arr = NULL;
			}
		}
297
		__INLINE element & back()
Kirill Terekhov's avatar
Kirill Terekhov committed
298
299
300
301
302
		{
			assert(m_arr != NULL);
			assert(m_size > 0);
			return m_arr[m_size-1];
		}
303
		__INLINE const element & back() const
Kirill Terekhov's avatar
Kirill Terekhov committed
304
305
306
307
308
		{
			assert(m_arr != NULL);
			assert(m_size > 0);
			return m_arr[m_size-1];
		}
309
		__INLINE element & front()
Kirill Terekhov's avatar
Kirill Terekhov committed
310
311
312
313
314
		{
			assert(m_arr != NULL);
			assert(m_size > 0);
			return m_arr[0];
		}
315
		__INLINE const element & front() const
Kirill Terekhov's avatar
Kirill Terekhov committed
316
317
318
319
320
		{
			assert(m_arr != NULL);
			assert(m_size > 0);
			return m_arr[0];
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
321
		__INLINE size_type capacity() { return m_size; }
Kirill Terekhov's avatar
Kirill Terekhov committed
322
		__INLINE bool empty() const { if( m_size ) return false; return true; }
Kirill Terekhov's avatar
Kirill Terekhov committed
323
		void resize(size_type n, element c = element() )
Kirill Terekhov's avatar
Kirill Terekhov committed
324
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
325
			size_type oldsize = m_size;
Kirill Terekhov's avatar
Kirill Terekhov committed
326
			m_size = n;
Kirill Terekhov's avatar
Kirill Terekhov committed
327
			for(size_type i = m_size; i < oldsize; i++) m_arr[i].~element(); //delete elements, located over the size
Kirill Terekhov's avatar
Kirill Terekhov committed
328
329
			if( m_size > 0 )
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
330
331
				if( growth_formula(oldsize) != growth_formula(m_size) )
					m_arr = static_cast<element *>(realloc(m_arr,sizeof(element)*growth_formula(m_size)));
Kirill Terekhov's avatar
Kirill Terekhov committed
332
				assert(m_arr != NULL);
Kirill Terekhov's avatar
Kirill Terekhov committed
333
				for(size_type i = oldsize; i < m_size; i++) new (m_arr+i) element(c); //initialize extra entities
Kirill Terekhov's avatar
Kirill Terekhov committed
334
335
336
337
338
339
340
			}
			else
			{
				free(m_arr);
				m_arr = NULL;
			}
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
341
342
		__INLINE size_type size() const {return m_size;}
		__INLINE size_type capacity() const {return growth_formula(m_size);}
343
344
		void clear()
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
345
			for(size_type i = 0; i < m_size; i++) m_arr[i].~element();
346
347
348
			m_size = 0;
			if( m_arr ) free(m_arr);
			m_arr = NULL;
Kirill Terekhov's avatar
Kirill Terekhov committed
349
350
351
352
		}
		void swap(array<element> & other)
		{
			element * t_m_arr = m_arr;
Kirill Terekhov's avatar
Kirill Terekhov committed
353
			size_type t_m_size = m_size;
Kirill Terekhov's avatar
Kirill Terekhov committed
354
355
356
357
358
			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
359
360
361
362
363
364
365
366
		__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); }
367
368
		iterator erase(iterator pos)
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
369
370
371
372
373
374
375
			ptrdiff_t d = pos-begin();
			ptrdiff_t s = iterator(m_arr+m_size-1)-pos;
			(*pos).~element();
			m_size--;
			if( m_size > 0 )
			{
				if( s > 0 ) memmove(m_arr+d,m_arr+d+1,sizeof(element)*s);
Kirill Terekhov's avatar
Kirill Terekhov committed
376
377
378
379
380
381
382
383
384
				//unoptimized variant
#if !defined(USE_OPTIMIZED_ARRAY_ALLOCATION)
				size_type gf = growth_formula(m_size);
				if( m_size+1 > gf )
					m_arr = static_cast<element *>(realloc(m_arr,sizeof(element)*gf));
#else
				if( ((m_size+1) & (m_size-1)) == 1 || m_size == 1)
					m_arr = static_cast<element *>(realloc(m_arr,sizeof(element)*m_size));
#endif
Kirill Terekhov's avatar
Kirill Terekhov committed
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
				assert(m_arr != NULL);
			}
			else
			{
				free(m_arr);
				m_arr = NULL;
			}
			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;
			for(iterator i = b; i != e; i++) (*i).~element();
			m_size -= n;
			if( m_size > 0 )
			{
				if( s > 0 ) memmove(m_arr+d,m_arr+d+1,sizeof(element)*s);
Kirill Terekhov's avatar
Kirill Terekhov committed
404
405
406
				size_type gf = growth_formula(m_size);
				if( m_size+n > gf )
					m_arr = static_cast<element *>(realloc(m_arr,sizeof(element)*gf));
Kirill Terekhov's avatar
Kirill Terekhov committed
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
				assert(m_arr != NULL);
			}
			else
			{
				free(m_arr);
				m_arr = NULL;
			}
			return m_arr+d;
		}
		iterator insert(iterator pos, const element & x)
		{
			if( static_cast<void *>(pos) == NULL)
			{
				assert(m_arr == NULL);
				pos = iterator(m_arr = static_cast<element *>(malloc(sizeof(element))));
				assert(m_arr != NULL);
			}
			ptrdiff_t d = pos-begin();
			ptrdiff_t s = end()-pos;
Kirill Terekhov's avatar
Kirill Terekhov committed
426
427
428
429
430
431
432
433
434
435
436
437
438
439

			//unoptimized variant
#if !defined(USE_OPTIMIZED_ARRAY_ALLOCATION)
			if( m_size+1 > growth_formula(m_size) )
				m_arr = static_cast<element *>(realloc(m_arr,sizeof(element)*growth_formula(++m_size)));
			else ++m_size;
#else
			//optimized for current growth_formula
			if( m_size < 2 )
				m_arr = static_cast<element *>(realloc(m_arr,sizeof(element)*(++m_size)));
			else if( ((m_size+1) & (m_size-1)) == 1 )
				m_arr = static_cast<element *>(realloc(m_arr,sizeof(element)*(m_size++ << 1)));
			else ++m_size;
#endif
Kirill Terekhov's avatar
Kirill Terekhov committed
440
441
442
443
444
			assert(m_arr != NULL);
			if( s > 0 ) memmove(m_arr+d+1,m_arr+d,sizeof(element)*s);
			new (m_arr+d) element(x);
			return m_arr+d;
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
445
		void insert(iterator pos, size_type n, const element & x)
Kirill Terekhov's avatar
Kirill Terekhov committed
446
447
448
449
450
451
452
453
454
455
456
		{
			if( n > 0 )
			{
				if( static_cast<void *>(pos) == NULL)
				{
					assert(m_arr == NULL);
					pos = iterator(m_arr = static_cast<element *>(malloc(sizeof(element))));
					assert(m_arr != NULL);
				}
				ptrdiff_t d = pos-begin();
				ptrdiff_t s = end()-pos;
Kirill Terekhov's avatar
Kirill Terekhov committed
457
458
459

				if( m_size+n > growth_formula(m_size) )
					m_arr = static_cast<element *>(realloc(m_arr,sizeof(element)*growth_formula(m_size+n)));
Kirill Terekhov's avatar
Kirill Terekhov committed
460
				m_size+=n;
Kirill Terekhov's avatar
Kirill Terekhov committed
461

Kirill Terekhov's avatar
Kirill Terekhov committed
462
463
				assert(m_arr != NULL);
				if( s > 0 ) memmove(m_arr+d+n,m_arr+d,sizeof(element)*s);
Kirill Terekhov's avatar
Kirill Terekhov committed
464
				for(size_type i = 0; i < n; i++) new (m_arr+d+i) element(x);
Kirill Terekhov's avatar
Kirill Terekhov committed
465
466
467
468
469
			}
		}
		template <class InputIterator>
		void insert(iterator pos, InputIterator first, InputIterator last)
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
470
			size_type n = static_cast<size_type>(std::distance(first,last));
Kirill Terekhov's avatar
Kirill Terekhov committed
471
472
473
474
475
476
477
478
479
480
			if( n > 0 )
			{
				if( static_cast<void *>(pos) == NULL)
				{
					assert(m_arr == NULL);
					pos = iterator(m_arr = static_cast<element *>(malloc(sizeof(element))));
					assert(m_arr != NULL);
				}
				ptrdiff_t d = pos-begin();
				ptrdiff_t s = end()-pos;
Kirill Terekhov's avatar
Kirill Terekhov committed
481
482
483

				if( m_size+n > growth_formula(m_size) )
					m_arr = static_cast<element *>(realloc(m_arr,sizeof(element)*growth_formula(m_size+n)));
Kirill Terekhov's avatar
Kirill Terekhov committed
484
				m_size+=n;
485

Kirill Terekhov's avatar
Kirill Terekhov committed
486
487
488
489
				assert(m_arr != NULL);
				if( s > 0 ) memmove(m_arr+d+n,m_arr+d,sizeof(element)*s);
				{
					InputIterator it = first;
Kirill Terekhov's avatar
Kirill Terekhov committed
490
					size_type i = 0;
Kirill Terekhov's avatar
Kirill Terekhov committed
491
492
493
494
495
496
497
498
					while(it != last) new (m_arr+d+i++) element(*it++);
				}
			}
		}
		template <class InputIterator>
		void replace(iterator m_first, iterator m_last, InputIterator first, InputIterator last)
		{
			assert( m_size >= 0 );
Kirill Terekhov's avatar
Kirill Terekhov committed
499
			ptrdiff_t n = static_cast<ptrdiff_t>(std::distance(first,last));
Kirill Terekhov's avatar
Kirill Terekhov committed
500
501
502
503
504
505
			if( static_cast<void *>(m_first) == NULL && m_arr == NULL)
			{
				assert(m_arr == NULL);
				m_first = m_last = iterator(m_arr = static_cast<element *>(malloc(sizeof(element))));
				assert(m_arr != NULL);
			}
506
			ptrdiff_t q = m_last-m_first;
Kirill Terekhov's avatar
Kirill Terekhov committed
507
508
509
510
511
			ptrdiff_t d = m_first-iterator(m_arr);
			ptrdiff_t s = iterator(m_arr+m_size)-m_last;
			for(iterator it = m_first; it != m_last; it++) (*it).~element();
			if( n-q != 0 )
			{
512
				size_type gf = growth_formula(m_size+static_cast<size_type>(n-q));
Kirill Terekhov's avatar
Kirill Terekhov committed
513
514
				if( gf != growth_formula(m_size) )
					m_arr = static_cast<element *>(realloc(m_arr,sizeof(element)*gf));
515
				m_size+=static_cast<size_type>(n-q);
Kirill Terekhov's avatar
Kirill Terekhov committed
516
517
518
519
				if( s > 0 ) memmove(m_arr+d+n,m_arr+d+q,sizeof(element)*s);
			}
			{
				InputIterator it = first;
Kirill Terekhov's avatar
Kirill Terekhov committed
520
				size_type i = 0;
Kirill Terekhov's avatar
Kirill Terekhov committed
521
522
523
				while(it != last) new (m_arr+d+i++) element(*it++);
			}
		}
524
525
526
527
528
		template <class InputIterator>
		void assign(InputIterator first, InputIterator last)
		{
			replace(begin(),end(),first,last);
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
529
		template<class> friend class shell;
530
	};
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
531
532
533
#if defined(PACK_ARRAY)
#pragma pack(pop,r1)
#endif
Kirill Terekhov's avatar
Kirill Terekhov committed
534
535
536
537
	template<typename element>
	class shell
	{
	public:
Kirill Terekhov's avatar
Kirill Terekhov committed
538
		typedef typename array<element>::size_type size_type;
Kirill Terekhov's avatar
Kirill Terekhov committed
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
		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
554
			_iterator operator -(size_t n) const { return _iterator(e-n); }
Kirill Terekhov's avatar
Kirill Terekhov committed
555
			_iterator & operator -=(size_t n) { e-=n; return *this; }
Kirill Terekhov's avatar
Updates    
Kirill Terekhov committed
556
			_iterator operator +(size_t n) const { return _iterator(e+n); }
Kirill Terekhov's avatar
Kirill Terekhov committed
557
			_iterator & operator +=(size_t n) { e+=n; return *this; }
Kirill Terekhov's avatar
Kirill Terekhov committed
558
559
560
561
562
563
			_iterator & operator ++(){ ++e; return *this;}
			_iterator operator ++(int){ return _iterator(e++); }
			_iterator & operator --(){ --e; return *this; }
			_iterator operator --(int){ return _iterator(e--); }
			ptrdiff_t operator -(const _iterator & other) const {return e-other.e;}
			dtype & operator *() { return *e; }
564
			const dtype & operator *() const { return *e; }
Kirill Terekhov's avatar
Kirill Terekhov committed
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
			dtype * operator ->() { return e; }
			_iterator & operator =(_iterator const & other) { e = other.e; return *this; }
			bool operator ==(const _iterator & other) { return e == other.e;}
			bool operator !=(const _iterator & other) { return e != other.e;}
			bool operator <(const _iterator & other) { return e < other.e;}
			bool operator >(const _iterator & other) { return e > other.e;}
			bool operator <=(const _iterator & other) { return e <= other.e;}
			bool operator >=(const _iterator & other) { return e >= other.e;}
			operator void *() {return static_cast<void *> (e);}
		};
		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
592
			_reverse_iterator operator -(size_t n) const { return _reverse_iterator(e+n); }
Kirill Terekhov's avatar
Kirill Terekhov committed
593
			_reverse_iterator & operator -=(size_t n) { e+=n; return *this; }
Kirill Terekhov's avatar
Updates    
Kirill Terekhov committed
594
			_reverse_iterator operator +(size_t n) const {return _reverse_iterator(e-n); }
Kirill Terekhov's avatar
Kirill Terekhov committed
595
			_reverse_iterator & operator +=(size_t n) { e-=n; return *this; }
Kirill Terekhov's avatar
Kirill Terekhov committed
596
597
598
599
600
601
			_reverse_iterator & operator ++(){ --e; return *this;}
			_reverse_iterator operator ++(int){ return _reverse_iterator(e--); }
			_reverse_iterator & operator --(){ ++e; return *this; }
			_reverse_iterator operator --(int){ return _reverse_iterator(e++); }
			ptrdiff_t operator -(const _reverse_iterator & other) const {return other.e-e;}
			dtype & operator *() { return *e; }
602
			const dtype & operator *() const { return *e; }
Kirill Terekhov's avatar
Kirill Terekhov committed
603
604
605
606
607
608
609
610
611
612
613
614
615
616
			dtype * operator ->() { return e; }
			_reverse_iterator & operator =(_reverse_iterator const & other) { e = other.e; return *this;}
			bool operator ==(const _reverse_iterator & other) { return e == other.e;}
			bool operator !=(const _reverse_iterator & other) { return e != other.e;}
			bool operator <(const _reverse_iterator & other) { return e < other.e;}
			bool operator >(const _reverse_iterator & other) { return e > other.e;}
			bool operator <=(const _reverse_iterator & other) { return e <= other.e;}
			bool operator >=(const _reverse_iterator & other) { return e >= other.e;}
			operator void *() {return static_cast<void *> (e);}
		};
		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
617
		size_type * m_size;
Kirill Terekhov's avatar
Kirill Terekhov committed
618
		element * local_link;
Kirill Terekhov's avatar
Kirill Terekhov committed
619
		size_type local_size;
Kirill Terekhov's avatar
Kirill Terekhov committed
620
621
		bool fixed;
	public:
Kirill Terekhov's avatar
Kirill Terekhov committed
622
623
		__INLINE element * data() {return *m_arr;}
		__INLINE const element * data() const {return *m_arr;}
Kirill Terekhov's avatar
Kirill Terekhov committed
624
625
626
627
628
629
630
		shell() {m_arr = NULL; m_size = NULL; fixed = false;}
		shell(array<element> & arr) //dynamic
		{
			m_arr = &arr.m_arr;
			m_size = &arr.m_size;
			fixed = false;
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
631
		shell(element * link, size_type size) //fixed
Kirill Terekhov's avatar
Kirill Terekhov committed
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
		{
			m_arr = &local_link;
			*m_arr = link;
			m_size = &local_size;
			*m_size = size;
			fixed = true;
		}
		shell(const shell & other)
		{
			fixed = other.fixed;
			if( fixed )
			{
				m_size = &local_size;
				m_arr = &local_link;
				*m_size = *other.m_size;
				*m_arr = *other.m_arr;
			}
			else
			{
				m_size = other.m_size;
				m_arr = other.m_arr;
			}
		}
		~shell()
		{
		}
658
		__INLINE const element & operator [] (size_type n) const
Kirill Terekhov's avatar
Kirill Terekhov committed
659
660
661
662
		{
			assert(n < *m_size );
			return *((*m_arr)+n);
		}
663
		__INLINE element & operator [] (size_type n)
Kirill Terekhov's avatar
Kirill Terekhov committed
664
665
666
667
		{
			assert(n < *m_size );
			return *((*m_arr)+n);
		}
668
		__INLINE const element & at (size_type n) const
Kirill Terekhov's avatar
Kirill Terekhov committed
669
670
671
672
		{
			assert(n < *m_size );
			return *((*m_arr)+n);
		}
673
		__INLINE element & at (size_type n)
Kirill Terekhov's avatar
Kirill Terekhov committed
674
675
676
677
678
679
680
681
682
683
		{
			assert(n < *m_size );
			return *((*m_arr)+n);
		}
		shell & operator =(shell const & other)
		{
			fixed = other.fixed;
			if( fixed )
			{
				m_size = &local_size;
684
				m_arr = &local_link;
Kirill Terekhov's avatar
Kirill Terekhov committed
685
686
687
688
689
690
691
692
693
694
695
696
				*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
697
			assert( !fixed ); // array size is fixed
Kirill Terekhov's avatar
Kirill Terekhov committed
698
699
700
701
702
703
704
705
706
707
708
#if !defined(USE_OPTIMIZED_ARRAY_ALLOCATION)
			//unoptimized variant
			if( (*m_size)+1 > array<element>::growth_formula(*m_size) )
				*m_arr = static_cast<element *>(realloc(*m_arr,sizeof(element)*array<element>::growth_formula(++(*m_size))));
			else ++(*m_size);
#else
			//optimized for current growth_formula
			if( *m_size < 2 )
				*m_arr = static_cast<element *>(realloc(*m_arr,sizeof(element)*(++(*m_size))));
			else if( (((*m_size)+1) & ((*m_size)-1)) == 1 )
				*m_arr = static_cast<element *>(realloc(*m_arr,sizeof(element)*((*m_size)++ << 1)));
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
709
			else ++(*m_size);
Kirill Terekhov's avatar
Kirill Terekhov committed
710
#endif
Kirill Terekhov's avatar
Kirill Terekhov committed
711
712
713
714
715
			assert((*m_arr) != NULL);
			new ((*m_arr)+(*m_size)-1) element(e);
		}
		void pop_back()
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
716
			assert( !fixed ); // array size is fixed
Kirill Terekhov's avatar
Kirill Terekhov committed
717
718
719
720
			assert((*m_arr) != NULL);
			(*m_arr)[(*m_size)--].~element();
			if( (*m_size) > 0 )
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
721
722
723
724
725
726
727
728
729
#if !defined(USE_OPTIMIZED_ARRAY_ALLOCATION)
				//unoptimized variant
				size_type gf = array<element>::growth_formula(*m_size);
				if( (*m_size)+1 > gf )
					*m_arr = static_cast<element *>(realloc(m_arr,sizeof(element)*gf));
#else
				if( (((*m_size)+1) & ((*m_size)-1)) == 1 || (*m_size) == 1)
					*m_arr = static_cast<element *>(realloc(*m_arr,sizeof(element)*(*m_size)));
#endif
Kirill Terekhov's avatar
Kirill Terekhov committed
730
731
732
733
734
735
736
737
				assert( (*m_arr) != NULL );
			}
			else
			{
				free(*m_arr);
				(*m_arr) = NULL;
			}
		}
738
		__INLINE element & back()
Kirill Terekhov's avatar
Kirill Terekhov committed
739
740
741
742
743
		{
			assert(*m_arr != NULL);
			assert(*m_size > 0 );
			return (*m_arr)[(*m_size)-1];
		}
744
		__INLINE const element & back() const
Kirill Terekhov's avatar
Kirill Terekhov committed
745
746
747
748
749
		{
			assert(*m_arr != NULL);
			assert(*m_size > 0 );
			return (*m_arr)[(*m_size)-1];
		}
750
		__INLINE element & front()
Kirill Terekhov's avatar
Kirill Terekhov committed
751
752
753
754
755
		{
			assert(*m_arr != NULL);
			assert(*m_size > 0 );
			return (*m_arr)[0];
		}
756
		__INLINE const element & front() const
Kirill Terekhov's avatar
Kirill Terekhov committed
757
758
759
760
761
		{
			assert(*m_arr != NULL);
			assert(*m_size > 0 );
			return (*m_arr)[0];
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
762
		__INLINE size_type capacity() { return array<element>::growth_formula(*m_size); }
Kirill Terekhov's avatar
Kirill Terekhov committed
763
		__INLINE bool empty() const { if( *m_size ) return false; return true; }
Kirill Terekhov's avatar
Kirill Terekhov committed
764
		void resize(size_type n, element c = element() )
Kirill Terekhov's avatar
Kirill Terekhov committed
765
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
766
			assert( !fixed ); // array size is fixed
Kirill Terekhov's avatar
Kirill Terekhov committed
767
			size_type oldsize = *m_size;
Kirill Terekhov's avatar
Kirill Terekhov committed
768
			*m_size = n;
Kirill Terekhov's avatar
Kirill Terekhov committed
769
			for(size_type i = *m_size; i < oldsize; i++) (*m_arr)[i].~element(); //delete elements, located over the size
Kirill Terekhov's avatar
Kirill Terekhov committed
770
771
			if( *m_size > 0 )
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
772
773
				if( array<element>::growth_formula(oldsize) != array<element>::growth_formula(*m_size) )
					*m_arr = static_cast<element *>(realloc(*m_arr,sizeof(element)*array<element>::growth_formula(*m_size)));
Kirill Terekhov's avatar
Kirill Terekhov committed
774
				assert( (*m_arr) != NULL );
Kirill Terekhov's avatar
Kirill Terekhov committed
775
				for(size_type i = oldsize; i < *m_size; i++) new ((*m_arr)+i) element(c); //initialize extra entities
Kirill Terekhov's avatar
Kirill Terekhov committed
776
777
778
779
780
781
782
			}
			else
			{
				free(*m_arr);
				*m_arr = NULL;
			}
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
783
		__INLINE size_type size() const {return *m_size;}
784
785
		void clear()
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
786
			assert( !fixed ); // array size is fixed
Kirill Terekhov's avatar
Kirill Terekhov committed
787
			for(size_type i = 0; i < *m_size; i++) (*m_arr)[i].~element();
788
789
790
			*m_size = 0;
			if( *m_arr ) free(*m_arr);
			*m_arr = NULL;
Kirill Terekhov's avatar
Kirill Terekhov committed
791
792
793
794
		}
		void swap(shell<element> & other)
		{
			element * t_m_arr = *m_arr;
Kirill Terekhov's avatar
Kirill Terekhov committed
795
			size_type t_m_size = *m_size;
Kirill Terekhov's avatar
Kirill Terekhov committed
796
797
798
799
800
			*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
801
802
803
804
805
806
807
808
		__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); }
809
810
		iterator erase(iterator pos)
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
811
			assert( !fixed ); // array size is fixed
Kirill Terekhov's avatar
Kirill Terekhov committed
812
813
814
815
816
817
818
			ptrdiff_t d = pos-begin();
			ptrdiff_t s = iterator(*m_arr+(*m_size)-1)-pos;
			(*pos).~element();
			(*m_size)--;
			if( (*m_size) > 0 )
			{
				if( s > 0 )memmove(*m_arr+d,*m_arr+d+1,sizeof(element)*s);
Kirill Terekhov's avatar
Kirill Terekhov committed
819
820
821
822
823
824
825
826
#if !defined(USE_OPTIMIZED_ARRAY_ALLOCATION)
				size_type gf = array<element>::growth_formula(*m_size);
				if( (*m_size)+1 > gf )
					*m_arr = static_cast<element *>(realloc(*m_arr,sizeof(element)*gf));
#else
				if( (((*m_size)+1) & ((*m_size)-1)) == 1 || (*m_size) == 1)
					*m_arr = static_cast<element *>(realloc(*m_arr,sizeof(element)*(*m_size)));
#endif
Kirill Terekhov's avatar
Kirill Terekhov committed
827
828
829
830
831
832
833
834
835
836
837
				assert((*m_arr) != NULL);
			}
			else
			{
				free(*m_arr);
				*m_arr = NULL;
			}
			return (*m_arr)+d;
		}
		iterator erase(iterator b, iterator e)
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
838
			assert( !fixed ); // array size is fixed
Kirill Terekhov's avatar
Kirill Terekhov committed
839
840
841
842
843
844
845
			ptrdiff_t d = b-begin();
			ptrdiff_t s = end()-e;
			ptrdiff_t n = e-b;
			for(iterator i = b; i != e; i++) (*i).~element();
			(*m_size) -= n;
			if( (*m_size) > 0 )
			{
846
				if( s > 0 ) memmove(*m_arr+d,*m_arr+d+n,sizeof(element)*s);
Kirill Terekhov's avatar
Kirill Terekhov committed
847
848
849
				size_type gf = array<element>::growth_formula(*m_size);
				if( (*m_size)+n > gf )
					*m_arr = static_cast<element *>(realloc(*m_arr,sizeof(element)*gf));
Kirill Terekhov's avatar
Kirill Terekhov committed
850
851
852
853
854
855
856
857
858
859
860
				assert((*m_arr) != NULL);
			}
			else
			{
				free(*m_arr);
				*m_arr = NULL;
			}
			return (*m_arr)+d;
		}
		iterator insert(iterator pos, const element & x)
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
861
			assert( !fixed ); // array size is fixed
Kirill Terekhov's avatar
Kirill Terekhov committed
862
863
864
865
866
867
868
869
			if( static_cast<void *>(pos) == NULL )
			{
				assert((*m_arr) == NULL);
				pos = iterator((*m_arr) = static_cast<element *>(malloc(sizeof(element))));
				assert((*m_arr) != NULL);
			}
			ptrdiff_t d = pos-begin();
			ptrdiff_t s = end()-pos;
Kirill Terekhov's avatar
Kirill Terekhov committed
870
871
872
873
874
875
876
877
878
879
880
881
882
883

#if !defined(USE_OPTIMIZED_ARRAY_ALLOCATION)
			//unoptimized variant
			if( (*m_size)+1 > array<element>::growth_formula(*m_size) )
				*m_arr = static_cast<element *>(realloc(*m_arr,sizeof(element)*array<element>::growth_formula(++(*m_size))));
			else ++(*m_size);
#else
			//optimized for current growth_formula
			if( *m_size < 2 )
				*m_arr = static_cast<element *>(realloc(*m_arr,sizeof(element)*(++(*m_size))));
			else if( (((*m_size)+1) & ((*m_size)-1)) == 1 )
				*m_arr = static_cast<element *>(realloc(*m_arr,sizeof(element)*((*m_size)++ << 1)));
			else ++(*m_size);
#endif
Kirill Terekhov's avatar
Kirill Terekhov committed
884
885
886
887
888
			assert((*m_arr) != NULL);
			if( s > 0 ) memmove((*m_arr)+d+1,(*m_arr)+d,sizeof(element)*s);
			new ((*m_arr)+d) element(x);
			return (*m_arr)+d;
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
889
		void insert(iterator pos, size_type n, const element & x)
Kirill Terekhov's avatar
Kirill Terekhov committed
890
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
891
			assert( !fixed ); // array size is fixed
Kirill Terekhov's avatar
Kirill Terekhov committed
892
893
894
895
896
897
898
899
900
901
			if( n > 0 )
			{
				if( static_cast<void *>(pos) == NULL)
				{
					assert((*m_arr) == NULL);
					pos = iterator((*m_arr) = static_cast<element *>(malloc(sizeof(element))));
					assert((*m_arr) != NULL);
				}
				ptrdiff_t d = pos-iterator(*m_arr);
				ptrdiff_t s = iterator((*m_arr)+(*m_size))-pos;
Kirill Terekhov's avatar
Kirill Terekhov committed
902
903
904

				if( (*m_size)+n > array<element>::growth_formula(*m_size) )
					*m_arr = static_cast<element *>(realloc(*m_arr,sizeof(element)*array<element>::growth_formula((*m_size)+n)));
Kirill Terekhov's avatar
Kirill Terekhov committed
905
				(*m_size)+=n;
906

Kirill Terekhov's avatar
Kirill Terekhov committed
907
908
				assert((*m_arr) != NULL);
				if( s > 0 ) memmove((*m_arr)+d+n,(*m_arr)+d,sizeof(element)*s);
Kirill Terekhov's avatar
Kirill Terekhov committed
909
				for(size_type i = 0; i < n; i++) new ((*m_arr)+d+i) element(x);
Kirill Terekhov's avatar
Kirill Terekhov committed
910
911
912
913
914
			}
		}
		template <class InputIterator>
		void insert(iterator pos, InputIterator first, InputIterator last)
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
915
			assert( !fixed ); // array size is fixed
Kirill Terekhov's avatar
Kirill Terekhov committed
916
			ptrdiff_t n = static_cast<ptrdiff_t>(std::distance(first,last));
Kirill Terekhov's avatar
Kirill Terekhov committed
917
918
919
920
921
922
923
924
925
926
			if( n > 0 )
			{
				if( static_cast<void *>(pos) == NULL)
				{
					assert((*m_arr) == NULL);
					pos = iterator((*m_arr) = static_cast<element *>(malloc(sizeof(element))));
					assert((*m_arr) != NULL);
				}
				ptrdiff_t d = pos-iterator(*m_arr);
				ptrdiff_t s = iterator((*m_arr)+(*m_size))-pos;
Kirill Terekhov's avatar
Kirill Terekhov committed
927
928
929
930
931
932


				if( (*m_size)+n > array<element>::growth_formula(*m_size) )
					*m_arr = static_cast<element *>(realloc(*m_arr,sizeof(element)*array<element>::growth_formula((*m_size)+static_cast<size_type>(n))));
				(*m_size)+=static_cast<size_type>(n);

Kirill Terekhov's avatar
Kirill Terekhov committed
933
934
935
936
				assert((*m_arr) != NULL);
				if( s > 0 ) memmove((*m_arr)+d+n,(*m_arr)+d,sizeof(element)*s);
				{
					InputIterator it = first;
Kirill Terekhov's avatar
Kirill Terekhov committed
937
					size_type i = 0;
Kirill Terekhov's avatar
Kirill Terekhov committed
938
939
940
941
942
943
944
					while(it != last) new ((*m_arr)+d+i++) element(*it++);
				}
			}
		}
		template <class InputIterator>
		void replace(iterator m_first, iterator m_last, InputIterator first, InputIterator last)
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
945
			ptrdiff_t n = static_cast<ptrdiff_t>(std::distance(first,last));
Kirill Terekhov's avatar
Kirill Terekhov committed
946
947
948
949
950
951
			if( static_cast<void *>(m_first) == NULL)
			{
				assert((*m_arr)==NULL);
				m_first = m_last = iterator((*m_arr) = static_cast<element *>(malloc(sizeof(element))));
				assert((*m_arr)!=NULL);
			}
952
			ptrdiff_t q = m_last-m_first;
Kirill Terekhov's avatar
Kirill Terekhov committed
953
954
955
956
957
			ptrdiff_t d = m_first-iterator(*m_arr);
			ptrdiff_t s = iterator((*m_arr)+(*m_size))-m_last;
			for(iterator it = m_first; it != m_last; it++) (*it).~element();
			if( n-q != 0 )
			{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
958
				assert( !fixed ); // array size is fixed
Kirill Terekhov's avatar
Kirill Terekhov committed
959
960
961
962
				size_type gf = array<element>::growth_formula((*m_size)+static_cast<size_type>(n-q));
				if( gf != array<element>::growth_formula(*m_size) )
					*m_arr = static_cast<element *>(realloc(*m_arr,sizeof(element)*gf));
				(*m_size)+=static_cast<size_type>(n-q);
Kirill Terekhov's avatar
Kirill Terekhov committed
963
			}
964
			if( s > 0 )
Kirill Terekhov's avatar
Kirill Terekhov committed
965
				memmove((*m_arr)+d+n,(*m_arr)+d+q,sizeof(element)*s);
Kirill Terekhov's avatar
Kirill Terekhov committed
966
967
			{
				InputIterator it = first;
Kirill Terekhov's avatar
Kirill Terekhov committed
968
				size_type i = 0;
Kirill Terekhov's avatar
Kirill Terekhov committed
969
970
971
				while(it != last) new ((*m_arr)+d+i++) element(*it++);
			}
		}
972
973
974
975
976
		template <class InputIterator>
		void assign(InputIterator first, InputIterator last)
		{
			replace(begin(),end(),first,last);
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
977
978
979
	};


980
981

	template <typename IndType,typename ValType>
Kirill Terekhov's avatar
Kirill Terekhov committed
982
983
984
985
986
987
988
989
	class sparse_data
	{
	public:
		typedef unsigned enumerate;
		static const enumerate prealloc = 4;
		typedef struct pair_t
		{
			IndType first;
990
			ValType second;
Kirill Terekhov's avatar
Kirill Terekhov committed
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
			pair_t() :first(0),second(0.0) {}
			pair_t(IndType first, ValType second) :first(0), second(0.0) {}
		} pair;
		typedef pair * iterator;
		typedef const iterator const_iterator;
	private:
		static int comparator(const void * pa, const void * pb)
		{
			pair * a = (pair *)pa;
			pair * b = (pair *)pb;
			return a->first - b->first;
		}
		pair * array;
		enumerate arr_size;
		enumerate arr_alloc;
		void test_allocate()
		{
			if( arr_size > arr_alloc )
			{
				enumerate old_arr_alloc = arr_alloc;
				while(arr_size > arr_alloc) arr_alloc = arr_alloc << 1;
				array = static_cast<pair *>(realloc(array,arr_alloc*sizeof(pair)));
				assert(array != NULL);
				for (enumerate i = old_arr_alloc; i < arr_alloc; i++) array[i].first = std::numeric_limits<IndType>::max();
				//memset(array+old_arr_alloc,0xff,sizeof(pair)*(arr_alloc-old_arr_alloc));
			}
		}
	public:
		void swap(sparse_data<IndType, ValType> & other)
		{
			pair * tmp = array;
			array = other.array;
			other.array = tmp;
			enumerate itmp = arr_size;
			arr_size = other.arr_size;
			other.arr_size = itmp;
			itmp = arr_alloc;
			arr_alloc = other.arr_alloc;
			other.arr_alloc = itmp;
		}
		void reserve(enumerate size)
		{
			enumerate new_alloc = 1;
			while( new_alloc < size ) new_alloc = new_alloc << 1;
			array = static_cast<pair *>(realloc(array,new_alloc*sizeof(pair)));
			assert(array != NULL);
			for (enumerate i = arr_alloc; i < new_alloc; i++) array[i].first = std::numeric_limits<IndType>::max();
			//memset(array+arr_alloc,0xff,sizeof(pair)*(new_alloc-arr_alloc));
			arr_alloc = new_alloc;
		}
		iterator lower_bound(IndType ind)
		{
			/*
			if( arr_size < 16 )
1045
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
1046
1047
1048
1049
				for(enumerate i = 0; i < arr_size; i++)
					if( array[i].first >= ind ) return array+i;
				return array+arr_size;
			}
1050
			*/
Kirill Terekhov's avatar
Kirill Terekhov committed
1051
1052
1053
1054
1055
1056
			unsigned k = 0;
			for(unsigned b = arr_alloc >> 1; b ; b = b >> 1)
			{
				unsigned j = k | b;
				if( array[j].first <= ind ) k = j;
			}
1057
1058
			if( array[k].first < ind ) k++;

Kirill Terekhov's avatar
Kirill Terekhov committed
1059
1060
1061
1062
1063
			return array+k;
		}
		iterator find(IndType ind)
		{
			iterator k = lower_bound(ind);
Kirill Terekhov's avatar
Kirill Terekhov committed
1064
			if( k == end() ) return end();
Kirill Terekhov's avatar
Kirill Terekhov committed
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
			if( k->first == ind ) return k;
			return end();
		}
		iterator insert(iterator pos, const IndType & x)
		{
			assert(pos == end() || x < pos->first);//check here that we don't break the order
			ptrdiff_t d = pos-array;
			ptrdiff_t s = arr_size-d;
			arr_size++;
			test_allocate();
			if( s ) memmove(array+d+1,array+d,sizeof(pair)*s);
			(array+d)->first = x;
			new (&(array[d].second)) ValType();
			return array+d;
		}
		void push_back(const pair & in)
		{
			assert(arr_size == 0 || in.first < (array+arr_size-1)->first);//check here that we don't break the order
			arr_size++;
			test_allocate();
			(array+arr_size-1)->first = in.first;
			(array+arr_size-1)->second = in.second;
		}
		iterator erase(iterator pos)
1089
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
			ptrdiff_t d = pos-array;
			ptrdiff_t s = (array+arr_size-1)-pos;
			(pos->second).~ValType();
			memmove(array+d,array+d+1,sizeof(pair)*s);
			arr_size--;
			return array+d;
		}
		sparse_data(pair * first, pair * last)
		{
			arr_size = last-first;
			arr_alloc = static_cast<enumerate>(prealloc);
			if( arr_size <= arr_alloc )
				array = static_cast<pair *>(malloc(arr_alloc*sizeof(pair)));
			else
			{
				array = NULL;
				test_allocate();
			}
			assert(array != NULL);
			memcpy(array,first,sizeof(pair)*arr_size);
			for (enumerate i = arr_alloc; i < arr_size; i++) array[i].first = std::numeric_limits<IndType>::max();
			//memset(array+arr_size,0xff,sizeof(pair)*(arr_alloc-arr_size));
			bool need_sort = false;
			for(enumerate k = 1; k < arr_size; k++)
				if( array[k].first < array[k-1].first )
				{
					need_sort = true;
					break;
				}
			if( need_sort ) qsort(array,sizeof(pair),arr_size,comparator);
		}
		sparse_data()
		{
			arr_size = 0;
			arr_alloc = static_cast<enumerate>(prealloc);
			array = static_cast<pair *>(malloc(sizeof(pair)*arr_alloc));
			assert(array != NULL);
			for (enumerate i = 0; i < arr_alloc; i++) array[i].first = std::numeric_limits<IndType>::max();
			//memset(array,0xff,sizeof(pair)*arr_alloc);
		}
		sparse_data(const sparse_data & other)
		{
			arr_size = other.arr_size;
			arr_alloc = other.arr_alloc;
			array = static_cast<pair *>(malloc(arr_alloc*sizeof(pair)));
			assert(array != NULL);
			memcpy(array,other.array,other.arr_alloc*sizeof(pair));
		}
		~sparse_data()
		{
			for(iterator i = begin(); i != end(); i++) (i->second).~ValType();
			free(array);
			arr_size = arr_alloc = 0;
		}
		sparse_data & operator =(sparse_data const & other)
		{
			if( &other != this )
			{
				for(iterator i = begin(); i != end(); i++) (i->second).~ValType();
				arr_size = other.arr_size;
				arr_alloc = other.arr_alloc;
				array = static_cast<pair *>(realloc(array,arr_alloc*sizeof(pair)));
				assert(array != NULL);
				memcpy(array,other.array,arr_alloc*sizeof(pair));
			}
			return *this;
		}
		ValType & operator [](IndType row)
		{
			iterator q = lower_bound(row);
			if( q != end() && q->first == row ) return q->second;
			return insert(q,row)->second;
		}
		ValType operator [](IndType row) const
		{
			iterator q = lower_bound(row);
			assert(q != end() && q->first == row);
			return q->second;
		}
		enumerate size() const { return arr_size; }
		bool empty() const {return size() == 0; }
		iterator begin() { return array; }
		const_iterator begin() const { return array; }
		iterator end() { return array+arr_size; }
		const_iterator end() const { return array+arr_size; }
		void clear()
		{
			for(iterator i = begin(); i != end(); i++) (i->second).~ValType();
			for (enumerate i = 0; i < arr_size; i++) array[i].first = std::numeric_limits<IndType>::max();
			//memset(array,0xff,sizeof(pair)*arr_size);
1180
			arr_size = 0;
Kirill Terekhov's avatar
Kirill Terekhov committed
1181
1182
		}
		enumerate capacity() {return arr_alloc;}
1183

Kirill Terekhov's avatar
Kirill Terekhov committed
1184
	};
1185
1186
1187
1188




Kirill Terekhov's avatar
Kirill Terekhov committed
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
	template<typename IndType,typename ValType>
	class interval
	{
	public:
		typedef ValType * iterator;
		typedef ValType const * const_iterator;
		//typedef const iterator const_iterator;
	private:
		ValType * array;
		IndType beg_index, end_index;
	public:
		void clear()
		{
			for (IndType i = beg_index; i < end_index; i++) (array[i]).~ValType();
			if (beg_index != end_index) free(array + beg_index);
			array = NULL;
			beg_index = end_index = 0;
		}
		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;
			}
			{
				ValType * tmp = array;
				array = other.array;
				other.array = tmp;
			}
		}
		interval()
		{
			beg_index = 0;
			end_index = 0;
			array = NULL;//static_cast<ValType *>(malloc(sizeof(ValType)*(end_index-beg_index)));
			//assert(array != NULL);
			//array = array - beg_index;
			//for(IndType i = beg_index; i != end_index; ++i) new (array+i) ValType();
		}
		interval(IndType beg)
		{
			beg_index = beg;
			end_index = beg_index;//+2;
			array = NULL; //static_cast<ValType *>(malloc(sizeof(ValType)*(end_index-beg_index)));
			//assert(array != NULL);
			//array = array - beg_index;
			//for(IndType i = beg_index; i != end_index; ++i) new (array+i) ValType();
		}
		interval(IndType beg, IndType end, ValType c = ValType())
		{
			beg_index = beg;
			end_index = end;
			if (beg != end)
			{
				array = static_cast<ValType *>(malloc(sizeof(ValType)*(end_index - beg_index)));
				assert(array != NULL);
				array = array - beg_index;
				for (IndType i = beg_index; i < end_index; ++i) new (array + i) ValType(c);
Kirill Terekhov's avatar
Kirill Terekhov committed
1251
1252

				//std::cout << __FUNCTION__ << " address " << array << std::endl;
Kirill Terekhov's avatar
Kirill Terekhov committed
1253
1254
1255
1256
1257
			}
			else array = NULL;
		}
		interval(const interval & other)
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
1258
			//std::cout << __FUNCTION__ << std::endl;
Kirill Terekhov's avatar
Kirill Terekhov committed
1259
1260
1261
1262
1263
1264
1265
			beg_index = other.beg_index;
			end_index = other.end_index;
			if( beg_index != end_index )
			{
				array = static_cast<ValType *>(malloc(sizeof(ValType)*(end_index-beg_index)));
				assert(array != NULL);
				array = array - beg_index;
1266
				for(IndType i = beg_index; i < end_index; ++i)
Kirill Terekhov's avatar
Kirill Terekhov committed
1267
1268
1269
1270
				{
					new (array+i) ValType(other.array[i]);
				}
				//std::cout << __FUNCTION__ << " address " << array << std::endl;
Kirill Terekhov's avatar
Kirill Terekhov committed
1271
1272
1273
1274
1275
			}
			else array = NULL;
		}
		~interval()
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
1276
			//std::cout << __FUNCTION__ << " delete address " << array << std::endl;
Kirill Terekhov's avatar
Kirill Terekhov committed
1277
1278
1279
1280
1281
1282
1283
1284
1285
			for(IndType i = beg_index; i < end_index; i++) (array[i]).~ValType();
			if( beg_index != end_index ) free(array+beg_index);
			array = NULL;
		}
		interval & operator =(interval const & other)
		{
			if( &other != this )
			{
				for(iterator i = begin(); i != end(); ++i) (*i).~ValType();
1286
				IndType old_beg_index = beg_index;
Kirill Terekhov's avatar
Kirill Terekhov committed
1287
1288
1289
1290
				beg_index = other.beg_index;
				end_index = other.end_index;
				if( beg_index != end_index )
				{
1291
					array = static_cast<ValType *>(realloc(array+old_beg_index,sizeof(ValType)*(end_index-beg_index)));
Kirill Terekhov's avatar
Kirill Terekhov committed
1292
1293
1294
					assert(array != NULL);
					array = array - beg_index;
					for(IndType i = beg_index; i < end_index; ++i) new (array+i) ValType(other.array[i]);
Kirill Terekhov's avatar
Kirill Terekhov committed
1295
					//std::cout << __FUNCTION__ << " address " << array << std::endl;
Kirill Terekhov's avatar
Kirill Terekhov committed
1296
				}
1297
				else
Kirill Terekhov's avatar
Kirill Terekhov committed
1298
				{
1299
					free(array+old_beg_index);
Kirill Terekhov's avatar
Kirill Terekhov committed
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
					array = NULL;
				}
			}
			return *this;
		}
		ValType & at(IndType row)
		{
			assert(row >= beg_index);
			assert(row < end_index);
			return array[row];
		}
		const ValType & at(IndType row) const
		{
			assert(row >= beg_index);
			assert(row < end_index);
			return array[row];
		}
		ValType & operator [](IndType row)
		{
			//std::cout << "pos: " << row << std::endl;
			/*
			if( row >= end_index )
			{
				IndType new_end_index = 1;
				IndType temp = row-beg_index;
				while( new_end_index <= temp ) new_end_index = new_end_index << 1;
				new_end_index += beg_index;
				//std::cout << "end: " << end_index << " new end: " << new_end_index << std::endl;
				array = static_cast<ValType *>(realloc(array,sizeof(ValType)*(new_end_index-beg_index)));
				IndType end = new_end_index-beg_index;
				for(IndType i = end_index-beg_index; i != end; ++i) new (array+i) ValType();
				end_index = new_end_index;
			}
			if( row >= last_index ) last_index = row+1;
			*/
			assert(row >= beg_index );
			assert(row < end_index );
			return array[row];
		}
		const ValType & operator [](IndType row) const
		{
			assert(row >= beg_index );
			assert(row < end_index );
			return array[row];
		}
		void set_interval_beg(IndType beg)
		{
			IndType shift = beg-beg_index;
			shift_interval(shift);
		}
		void set_interval_end(IndType end)
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
1352
			if( end == end_index ) return;
Kirill Terekhov's avatar
Kirill Terekhov committed
1353
1354
			if( beg_index != end )
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
1355
1356
1357
1358
1359
1360
1361
1362
1363
				ValType * array_new = static_cast<ValType *>(malloc(sizeof(ValType)*(end-beg_index)));
				assert(array_new != NULL);
				array_new = array_new - beg_index;
				for(IndType i = beg_index; i < std::min(end,end_index); ++i) new (array_new+i) ValType(array[i]);
				for(IndType i = end_index; i < end; ++i) new (array_new+i) ValType();
				for(IndType i = beg_index; i < end_index; ++i) array[i].~ValType();

				if( array != NULL ) free(array+beg_index);
				array = array_new;
Kirill Terekhov's avatar
Kirill Terekhov committed
1364
1365
1366
1367
1368
1369
1370
1371
			}
			else
			{
				free(array+beg_index);
				array =