container.hpp 113 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

17
//#define DEBUGMEM
Kirill Terekhov's avatar
Kirill Terekhov committed
18
19

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

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

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

Kirill Terekhov's avatar
Kirill Terekhov committed
58
//#define USE_OPTIMIZED_ARRAY_ALLOCATION
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
91
92
93
94
95
			_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; }
96
			const etype & operator *() const { return *e; }
Kirill Terekhov's avatar
Kirill Terekhov committed
97
98
			etype * operator ->() { return e; }
			_iterator & operator =(_iterator const & other) { e = other.e; return *this; }
Kirill Terekhov's avatar
Kirill Terekhov committed
99
100
101
102
103
104
			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
105
			operator void *() {return static_cast<void *> (e);}
Kirill Terekhov's avatar
Updates    
Kirill Terekhov committed
106
			operator const void *() const {return const_cast<const void *> (e);}
Kirill Terekhov's avatar
Kirill Terekhov committed
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
		};
		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
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
Updates    
Kirill Terekhov committed
127
			_reverse_iterator operator +(size_t n) const {return _reverse_iterator(e-n); }
Kirill Terekhov's avatar
Kirill Terekhov committed
128
			_reverse_iterator & operator +=(size_t n) { e-=n; return *this; }
Kirill Terekhov's avatar
Kirill Terekhov committed
129
130
131
132
133
134
			_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; }
135
			const etype & operator *() const { return *e; }
Kirill Terekhov's avatar
Kirill Terekhov committed
136
137
			etype * operator ->() { return e; }
			_reverse_iterator & operator =(_reverse_iterator const & other) { e = other.e; return *this;}
Kirill Terekhov's avatar
Kirill Terekhov committed
138
139
140
141
142
143
			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
144
			operator void *() {return static_cast<void *> (e);}
Kirill Terekhov's avatar
Updates    
Kirill Terekhov committed
145
			operator const void *() const {return static_cast<const void *> (e);}
Kirill Terekhov's avatar
Kirill Terekhov committed
146
147
148
149
		};
		typedef _reverse_iterator<element> reverse_iterator;
		typedef _reverse_iterator<const element> const_reverse_iterator;
	private:
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
150

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

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

			//unoptimized variant
#if !defined(USE_OPTIMIZED_ARRAY_ALLOCATION)
			if( m_size+1 > growth_formula(m_size) )
504
505
506
507
508
509
510
			{
				void * tmp = realloc(m_arr,sizeof(element)*growth_formula(++m_size));
#if defined(DEBUGMEM)
				if( tmp == NULL ) {printf("%s:%d realloc return NULL\n",__FILE__,__LINE__);}
#endif
				m_arr = static_cast<element *>(tmp);
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
511
512
513
514
			else ++m_size;
#else
			//optimized for current growth_formula
			if( m_size < 2 )
515
516
517
518
519
520
521
			{
				void * tmp = realloc(m_arr,sizeof(element)*(++m_size));
#if defined(DEBUGMEM)
				if( tmp == NULL ) {printf("%s:%d realloc return NULL\n",__FILE__,__LINE__);}
#endif
				m_arr = static_cast<element *>(tmp);
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
522
			else if( ((m_size+1) & (m_size-1)) == 1 )
523
524
525
526
527
528
529
			{
				void * tmp = realloc(m_arr,sizeof(element)*(m_size++ << 1));
#if defined(DEBUGMEM)
				if( tmp == NULL ) {printf("%s:%d realloc return NULL\n",__FILE__,__LINE__);}
#endif
				m_arr = static_cast<element *>(tmp);
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
530
531
			else ++m_size;
#endif
Kirill Terekhov's avatar
Kirill Terekhov committed
532
533
534
535
536
			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
537
		void insert(iterator pos, size_type n, const element & x)
Kirill Terekhov's avatar
Kirill Terekhov committed
538
539
540
541
542
543
544
		{
			if( n > 0 )
			{
				if( static_cast<void *>(pos) == NULL)
				{
					assert(m_arr == NULL);
					pos = iterator(m_arr = static_cast<element *>(malloc(sizeof(element))));
545
546
547
#if defined(DEBUGMEM)
					if( m_arr == NULL ) {printf("%s:%d malloc return NULL\n",__FILE__,__LINE__);}
#endif
Kirill Terekhov's avatar
Kirill Terekhov committed
548
549
550
551
					assert(m_arr != NULL);
				}
				ptrdiff_t d = pos-begin();
				ptrdiff_t s = end()-pos;
Kirill Terekhov's avatar
Kirill Terekhov committed
552
553

				if( m_size+n > growth_formula(m_size) )
554
555
556
557
558
559
560
				{
					void * tmp = realloc(m_arr,sizeof(element)*growth_formula(m_size+n));
#if defined(DEBUGMEM)
					if( tmp == NULL ) {printf("%s:%d realloc return NULL\n",__FILE__,__LINE__);}
#endif
					m_arr = static_cast<element *>(tmp);
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
561
				m_size+=n;
Kirill Terekhov's avatar
Kirill Terekhov committed
562

Kirill Terekhov's avatar
Kirill Terekhov committed
563
564
				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
565
				for(size_type i = 0; i < n; i++) new (m_arr+d+i) element(x);
Kirill Terekhov's avatar
Kirill Terekhov committed
566
567
568
569
570
			}
		}
		template <class InputIterator>
		void insert(iterator pos, InputIterator first, InputIterator last)
		{
Kirill Terekhov's avatar
Kirill Terekhov committed
571
			size_type n = static_cast<size_type>(std::distance(first,last));
Kirill Terekhov's avatar
Kirill Terekhov committed
572
573
574
575
576
577
			if( n > 0 )
			{
				if( static_cast<void *>(pos) == NULL)
				{
					assert(m_arr == NULL);
					pos = iterator(m_arr = static_cast<element *>(malloc(sizeof(element))));
578
579
580
#if defined(DEBUGMEM)
					if( m_arr == NULL ) {printf("%s:%d malloc return NULL\n",__FILE__,__LINE__);}
#endif
Kirill Terekhov's avatar
Kirill Terekhov committed
581
582
583
584
					assert(m_arr != NULL);
				}
				ptrdiff_t d = pos-begin();
				ptrdiff_t s = end()-pos;
Kirill Terekhov's avatar
Kirill Terekhov committed
585
586

				if( m_size+n > growth_formula(m_size) )
587
588
589
590
591
592
593
				{
					void * tmp = realloc(m_arr,sizeof(element)*growth_formula(m_size+n));
#if defined(DEBUGMEM)
					if( tmp == NULL ) {printf("%s:%d realloc return NULL\n",__FILE__,__LINE__);}
#endif
					m_arr = static_cast<element *>(tmp);
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
594
				m_size+=n;
595

Kirill Terekhov's avatar
Kirill Terekhov committed
596
597
598
599
				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
600
					size_type i = 0;
Kirill Terekhov's avatar
Kirill Terekhov committed
601
602
603
604
605
606
607
608
					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
609
			ptrdiff_t n = static_cast<ptrdiff_t>(std::distance(first,last));
Kirill Terekhov's avatar
Kirill Terekhov committed
610
611
612
613
			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))));
614
615
616
#if defined(DEBUGMEM)
				if( m_arr == NULL ) {printf("%s:%d malloc return NULL\n",__FILE__,__LINE__);}
#endif
Kirill Terekhov's avatar
Kirill Terekhov committed
617
618
				assert(m_arr != NULL);
			}
619
			ptrdiff_t q = m_last-m_first;
Kirill Terekhov's avatar
Kirill Terekhov committed
620
621
622
623
624
			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 )
			{
625
				size_type gf = growth_formula(m_size+static_cast<size_type>(n-q));
Kirill Terekhov's avatar
Kirill Terekhov committed
626
				if( gf != growth_formula(m_size) )
627
628
629
630
631
632
633
				{
					void * tmp = realloc(m_arr,sizeof(element)*gf);
#if defined(DEBUGMEM)
					if( tmp == NULL ) {printf("%s:%d realloc return NULL\n",__FILE__,__LINE__);}
#endif
					m_arr = static_cast<element *>(tmp);
				}
634
				m_size+=static_cast<size_type>(n-q);
Kirill Terekhov's avatar
Kirill Terekhov committed
635
636
637
638
				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
639
				size_type i = 0;
Kirill Terekhov's avatar
Kirill Terekhov committed
640
641
642
				while(it != last) new (m_arr+d+i++) element(*it++);
			}
		}
643
644
645
646
647
		template <class InputIterator>
		void assign(InputIterator first, InputIterator last)
		{
			replace(begin(),end(),first,last);
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
648
		template<class> friend class shell;
649
	};
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
650
651
652
#if defined(PACK_ARRAY)
#pragma pack(pop,r1)
#endif
Kirill Terekhov's avatar
Kirill Terekhov committed
653
654
655
656
	template<typename element>
	class shell
	{
	public:
Kirill Terekhov's avatar
Kirill Terekhov committed
657
		typedef typename array<element>::size_type size_type;
Kirill Terekhov's avatar
Kirill Terekhov committed
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
		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
673
			_iterator operator -(size_t n) const { return _iterator(e-n); }
Kirill Terekhov's avatar
Kirill Terekhov committed
674
			_iterator & operator -=(size_t n) { e-=n; return *this; }
Kirill Terekhov's avatar
Updates    
Kirill Terekhov committed
675
			_iterator operator +(size_t n) const { return _iterator(e+n); }
Kirill Terekhov's avatar
Kirill Terekhov committed
676
			_iterator & operator +=(size_t n) { e+=n; return *this; }
Kirill Terekhov's avatar
Kirill Terekhov committed
677
678
679
680
681
682
			_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; }
683
			const dtype & operator *() const { return *e; }
Kirill Terekhov's avatar
Kirill Terekhov committed
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
			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
711
			_reverse_iterator operator -(size_t n) const { return _reverse_iterator(e+n); }
Kirill Terekhov's avatar
Kirill Terekhov committed
712
			_reverse_iterator & operator -=(size_t n) { e+=n; return *this; }
Kirill Terekhov's avatar
Updates    
Kirill Terekhov committed
713
			_reverse_iterator operator +(size_t n) const {return _reverse_iterator(e-n); }
Kirill Terekhov's avatar
Kirill Terekhov committed
714
			_reverse_iterator & operator +=(size_t n) { e-=n; return *this; }
Kirill Terekhov's avatar
Kirill Terekhov committed
715
716
717
718
719
720
			_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; }
721
			const dtype & operator *() const { return *e; }
Kirill Terekhov's avatar
Kirill Terekhov committed
722
723
724
725
726
727
728
729
730
731
732
733
734
735
			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
736
		size_type * m_size;
Kirill Terekhov's avatar
Kirill Terekhov committed
737
		element * local_link;
Kirill Terekhov's avatar
Kirill Terekhov committed
738
		size_type local_size;
Kirill Terekhov's avatar
Kirill Terekhov committed
739
740
		bool fixed;
	public:
Kirill Terekhov's avatar
Kirill Terekhov committed
741
742
		__INLINE element * data() {return *m_arr;}
		__INLINE const element * data() const {return *m_arr;}
743
		shell() :local_link(NULL), local_size(0), m_arr(NULL), m_size(NULL), fixed(false) { }
Kirill Terekhov's avatar
Kirill Terekhov committed
744
		shell(array<element> & arr) //dynamic
745
			:local_link(NULL), local_size(0), m_arr(&arr.m_arr), m_size(&arr.m_size), fixed(false) {}
Kirill Terekhov's avatar
Kirill Terekhov committed
746
		shell(element * link, size_type size) //fixed
747
			:local_link(NULL),local_size(0), m_arr(&local_link), m_size(&local_size), fixed(true)
Kirill Terekhov's avatar
Kirill Terekhov committed
748
749
750
751
752
		{
			*m_arr = link;
			*m_size = size;
		}
		shell(const shell & other)
753
			:local_link(NULL), local_size(0), m_arr(&local_link), m_size(&local_size),fixed(other.fixed)
Kirill Terekhov's avatar
Kirill Terekhov committed
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
		{
			if( fixed )
			{
				*m_size = *other.m_size;
				*m_arr = *other.m_arr;
			}
			else
			{
				m_size = other.m_size;
				m_arr = other.m_arr;
			}
		}
		~shell()
		{
		}
769
		__INLINE const element & operator [] (size_type n) const
Kirill Terekhov's avatar
Kirill Terekhov committed
770
771
772
773
		{
			assert(n < *m_size );
			return *((*m_arr)+n);
		}
774
		__INLINE element & operator [] (size_type n)
Kirill Terekhov's avatar
Kirill Terekhov committed
775
776
777
778
		{
			assert(n < *m_size );
			return *((*m_arr)+n);
		}
779
		__INLINE const element & at (size_type n) const
Kirill Terekhov's avatar
Kirill Terekhov committed
780
781
782
783
		{
			assert(n < *m_size );
			return *((*m_arr)+n);
		}
784
		__INLINE element & at (size_type n)
Kirill Terekhov's avatar
Kirill Terekhov committed
785
786
787
788
789
790
791
792
793
794
		{
			assert(n < *m_size );
			return *((*m_arr)+n);
		}
		shell & operator =(shell const & other)
		{
			fixed = other.fixed;
			if( fixed )
			{
				m_size = &local_size;
795
				m_arr = &local_link;
Kirill Terekhov's avatar
Kirill Terekhov committed
796
797
798
799
800
801
802
803
804
805
806
807
				*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
808
			assert( !fixed ); // array size is fixed
Kirill Terekhov's avatar
Kirill Terekhov committed
809
810
811
#if !defined(USE_OPTIMIZED_ARRAY_ALLOCATION)
			//unoptimized variant
			if( (*m_size)+1 > array<element>::growth_formula(*m_size) )
812
813
814
815
816
817
818
			{
				void * tmp = realloc(*m_arr,sizeof(element)*array<element>::growth_formula(++(*m_size)));
#if defined(DEBUGMEM)
				if( tmp == NULL ) {printf("%s:%d realloc return NULL\n",__FILE__,__LINE__);}
#endif				
				*m_arr = static_cast<element *>(tmp);
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
819
820
821
822
			else ++(*m_size);
#else
			//optimized for current growth_formula
			if( *m_size < 2 )
823
824
825
826
827
828
829
			{
				void * tmp = realloc(*m_arr,sizeof(element)*(++(*m_size)));
#if defined(DEBUGMEM)
				if( tmp == NULL ) {printf("%s:%d realloc return NULL\n",__FILE__,__LINE__);}
#endif
				*m_arr = static_cast<element *>(tmp);
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
830
			else if( (((*m_size)+1) & ((*m_size)-1)) == 1 )
831
832
833
834
835
836
837
			{
				void * tmp = realloc(*m_arr,sizeof(element)*((*m_size)++ << 1));
#if defined(DEBUGMEM)
				if( tmp == NULL ) {printf("%s:%d realloc return NULL\n",__FILE__,__LINE__);}
#endif
				*m_arr = static_cast<element *>(tmp);
			}
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
838
			else ++(*m_size);
Kirill Terekhov's avatar
Kirill Terekhov committed
839
#endif
Kirill Terekhov's avatar
Kirill Terekhov committed
840
841
842
843
844
			assert((*m_arr) != NULL);
			new ((*m_arr)+(*m_size)-1) element(e);
		}
		void pop_back()
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
845
			assert( !fixed ); // array size is fixed
Kirill Terekhov's avatar
Kirill Terekhov committed
846
847
848
849
			assert((*m_arr) != NULL);
			(*m_arr)[(*m_size)--].~element();
			if( (*m_size) > 0 )
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
850
851
852
853
#if !defined(USE_OPTIMIZED_ARRAY_ALLOCATION)
				//unoptimized variant
				size_type gf = array<element>::growth_formula(*m_size);
				if( (*m_size)+1 > gf )
854
855
856
857
858
859
860
				{
					void * tmp = realloc(m_arr,sizeof(element)*gf);
#if defined(DEBUGMEM)
					if( tmp == NULL ) {printf("%s:%d realloc return NULL\n",__FILE__,__LINE__);}
#endif
					*m_arr = static_cast<element *>(tmp);
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
861
862
#else
				if( (((*m_size)+1) & ((*m_size)-1)) == 1 || (*m_size) == 1)
863
864
865
866
867
868
869
				{
					void * tmp = realloc(*m_arr,sizeof(element)*(*m_size));
#if defined(DEBUGMEM)
					if( tmp == NULL ) {printf("%s:%d realloc return NULL\n",__FILE__,__LINE__);}
#endif
					*m_arr = static_cast<element *>(tmp);
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
870
#endif
Kirill Terekhov's avatar
Kirill Terekhov committed
871
872
873
874
875
876
877
878
				assert( (*m_arr) != NULL );
			}
			else
			{
				free(*m_arr);
				(*m_arr) = NULL;
			}
		}
879
		__INLINE element & back()
Kirill Terekhov's avatar
Kirill Terekhov committed
880
881
882
883
884
		{
			assert(*m_arr != NULL);
			assert(*m_size > 0 );
			return (*m_arr)[(*m_size)-1];
		}
885
		__INLINE const element & back() const
Kirill Terekhov's avatar
Kirill Terekhov committed
886
887
888
889
890
		{
			assert(*m_arr != NULL);
			assert(*m_size > 0 );
			return (*m_arr)[(*m_size)-1];
		}
891
		__INLINE element & front()
Kirill Terekhov's avatar
Kirill Terekhov committed
892
893
894
895
896
		{
			assert(*m_arr != NULL);
			assert(*m_size > 0 );
			return (*m_arr)[0];
		}
897
		__INLINE const element & front() const
Kirill Terekhov's avatar
Kirill Terekhov committed
898
899
900
901
902
		{
			assert(*m_arr != NULL);
			assert(*m_size > 0 );
			return (*m_arr)[0];
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
903
		__INLINE size_type capacity() { return array<element>::growth_formula(*m_size); }
Kirill Terekhov's avatar
Kirill Terekhov committed
904
		__INLINE bool empty() const { if( *m_size ) return false; return true; }
Kirill Terekhov's avatar
Kirill Terekhov committed
905
		void resize(size_type n, element c = element() )
Kirill Terekhov's avatar
Kirill Terekhov committed
906
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
907
			assert( !fixed ); // array size is fixed
Kirill Terekhov's avatar
Kirill Terekhov committed
908
			size_type oldsize = *m_size;
Kirill Terekhov's avatar
Kirill Terekhov committed
909
			*m_size = n;
Kirill Terekhov's avatar
Kirill Terekhov committed
910
			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
911
912
			if( *m_size > 0 )
			{
Kirill Terekhov's avatar
Kirill Terekhov committed
913
				if( array<element>::growth_formula(oldsize) != array<element>::growth_formula(*m_size) )
914
915
916
917
918
919
920
				{
					void * tmp = realloc(*m_arr,sizeof(element)*array<element>::growth_formula(*m_size));
#if defined(DEBUGMEM)
					if( tmp == NULL ) {printf("%s:%d realloc return NULL\n",__FILE__,__LINE__);}
#endif
					*m_arr = static_cast<element *>(tmp);
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
921
				assert( (*m_arr) != NULL );
Kirill Terekhov's avatar
Kirill Terekhov committed
922
				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
923
924
925
926
927
928
929
			}
			else
			{
				free(*m_arr);
				*m_arr = NULL;
			}
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
930
		__INLINE size_type size() const {return *m_size;}
931
932
		void clear()
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
933
			assert( !fixed ); // array size is fixed
Kirill Terekhov's avatar
Kirill Terekhov committed
934
			for(size_type i = 0; i < *m_size; i++) (*m_arr)[i].~element();
935
936
937
			*m_size = 0;
			if( *m_arr ) free(*m_arr);
			*m_arr = NULL;
Kirill Terekhov's avatar
Kirill Terekhov committed
938
939
940
941
		}
		void swap(shell<element> & other)
		{
			element * t_m_arr = *m_arr;
Kirill Terekhov's avatar
Kirill Terekhov committed
942
			size_type t_m_size = *m_size;
Kirill Terekhov's avatar
Kirill Terekhov committed
943
944
945
946
947
			*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
948
949
950
951
952
953
954
955
		__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); }
956
957
		iterator erase(iterator pos)
		{
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
963
964
965
			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
966
967
968
#if !defined(USE_OPTIMIZED_ARRAY_ALLOCATION)
				size_type gf = array<element>::growth_formula(*m_size);
				if( (*m_size)+1 > gf )
969
970
971
972
973
974
975
				{
					void * tmp = realloc(*m_arr,sizeof(element)*gf);
#if defined(DEBUGMEM)
					if( tmp == NULL ) {printf("%s:%d realloc return NULL\n",__FILE__,__LINE__);}
#endif
					*m_arr = static_cast<element *>(tmp);
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
976
977
#else
				if( (((*m_size)+1) & ((*m_size)-1)) == 1 || (*m_size) == 1)
978
979
980
981
982
983
984
				{
					void * tmp = realloc(*m_arr,sizeof(element)*(*m_size));
#if defined(DEBUGMEM)
					if( tmp == NULL ) {printf("%s:%d realloc return NULL\n",__FILE__,__LINE__);}
#endif
					*m_arr = static_cast<element *>(tmp);
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
985
#endif
Kirill Terekhov's avatar
Kirill Terekhov committed
986
987
988
989
990
991
992
993
994
995
996
				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
997
			assert( !fixed ); // array size is fixed
Kirill Terekhov's avatar
Kirill Terekhov committed
998
999
1000
1001
1002
1003
1004
			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 )
			{
1005
				if( s > 0 ) memmove(*m_arr+d,*m_arr+d+n,sizeof(element)*s);
Kirill Terekhov's avatar
Kirill Terekhov committed
1006
1007
				size_type gf = array<element>::growth_formula(*m_size);
				if( (*m_size)+n > gf )
1008
1009
1010
1011
1012
1013
1014
				{
					void * tmp = realloc(*m_arr,sizeof(element)*gf);
#if defined(DEBUGMEM)
					if( tmp == NULL ) {printf("%s:%d realloc return NULL\n",__FILE__,__LINE__);}
#endif
					*m_arr = static_cast<element *>(tmp);
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
				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
1026
			assert( !fixed ); // array size is fixed
Kirill Terekhov's avatar
Kirill Terekhov committed
1027
1028
1029
1030
			if( static_cast<void *>(pos) == NULL )
			{
				assert((*m_arr) == NULL);
				pos = iterator((*m_arr) = static_cast<element *>(malloc(sizeof(element))));
1031
1032
1033
#if defined(DEBUGMEM)
				if( *m_arr == NULL ) {printf("%s:%d malloc return NULL\n",__FILE__,__LINE__);}
#endif
Kirill Terekhov's avatar
Kirill Terekhov committed
1034
1035
1036
1037
				assert((*m_arr) != NULL);
			}
			ptrdiff_t d = pos-begin();
			ptrdiff_t s = end()-pos;
Kirill Terekhov's avatar
Kirill Terekhov committed
1038
1039
1040
1041

#if !defined(USE_OPTIMIZED_ARRAY_ALLOCATION)
			//unoptimized variant
			if( (*m_size)+1 > array<element>::growth_formula(*m_size) )
1042
1043
1044
1045
1046
1047
1048
			{
				void * tmp = realloc(*m_arr,sizeof(element)*array<element>::growth_formula(++(*m_size)));
#if defined(DEBUGMEM)
				if( tmp == NULL ) {printf("%s:%d realloc return NULL\n",__FILE__,__LINE__);}
#endif
				*m_arr = static_cast<element *>(tmp);
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
1049
1050
1051
1052
			else ++(*m_size);
#else
			//optimized for current growth_formula
			if( *m_size < 2 )
1053
1054
1055
1056
1057
1058
1059
			{
				void * tmp = realloc(*m_arr,sizeof(element)*(++(*m_size)));
#if defined(DEBUGMEM)
				if( tmp == NULL ) {printf("%s:%d realloc return NULL\n",__FILE__,__LINE__);}
#endif
				*m_arr = static_cast<element *>(tmp);
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
1060
			else if( (((*m_size)+1) & ((*m_size)-1)) == 1 )
1061
1062
1063
1064
1065
1066
1067
			{
				void * tmp = realloc(*m_arr,sizeof(element)*((*m_size)++ << 1));
#if defined(DEBUGMEM)
				if( tmp == NULL ) {printf("%s:%d realloc return NULL\n",__FILE__,__LINE__);}
#endif
				*m_arr = static_cast<element *>(tmp);
			}
Kirill Terekhov's avatar
Kirill Terekhov committed
1068
1069
			else ++(*m_size);
#endif
Kirill Terekhov's avatar
Kirill Terekhov committed
1070
1071
1072
1073
1074
			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
1075
		void insert(iterator pos, size_type n, const element & x)
Kirill Terekhov's avatar
Kirill Terekhov committed
1076
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
1077
			assert( !fixed ); // array size is fixed
Kirill Terekhov's avatar
Kirill Terekhov committed
1078
1079
1080
1081
1082
1083
			if( n > 0 )
			{
				if( static_cast<void *>(pos) == NULL)
				{
					assert((*m_arr) == NULL);
					pos = iterator((*m_arr) = static_cast<element *>(malloc(sizeof(element))));
1084
1085
1086
#if defined(DEBUGMEM)
					if( *m_arr == NULL ) {printf("%s:%d malloc return NULL\n",__FILE__,__LINE__);}
#endif
Kirill Terekhov's avatar
Kirill Terekhov committed
1087
1088
1089
1090
					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
1091
1092

				if( (*m_size)+n > array<element>::growth_formula(*m_size) )
1093
1094
1095
1096
1097
1098
1099
				{
					void * tmp = realloc(*m_arr,sizeof(element)*array<element>::growth_formula((*m_size)+n));
#if defined(DEBUGMEM)
					if( tmp == NULL ) {printf("%s:%d realloc return NULL\n",__FILE__,__LINE__);}
#endif
					*m_arr = static_cast<element *>(tmp);
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
1100
				(*m_size)+=n;
1101

Kirill Terekhov's avatar
Kirill Terekhov committed
1102
1103
				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
1104
				for(size_type i = 0; i < n; i++) new ((*m_arr)+d+i) element(x);
Kirill Terekhov's avatar
Kirill Terekhov committed
1105
1106
1107
1108
1109
			}
		}
		template <class InputIterator>
		void insert(iterator pos, InputIterator first, InputIterator last)
		{
Kirill Terekhov's avatar
Fixes    
Kirill Terekhov committed
1110
			assert( !fixed ); // array size is fixed
Kirill Terekhov's avatar
Kirill Terekhov committed
1111
			ptrdiff_t n = static_cast<ptrdiff_t>(std::distance(first,last));
Kirill Terekhov's avatar
Kirill Terekhov committed
1112
1113
1114
1115
1116
1117
			if( n > 0 )
			{
				if( static_cast<void *>(pos) == NULL)
				{
					assert((*m_arr) == NULL);
					pos = iterator((*m_arr) = static_cast<element *>(malloc(sizeof(element))));
1118
1119
1120
#if defined(DEBUGMEM)
					if( *m_arr == NULL ) {printf("%s:%d malloc return NULL\n",__FILE__,__LINE__);}
#endif
Kirill Terekhov's avatar
Kirill Terekhov committed
1121
1122
1123
1124
					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
1125
1126
1127


				if( (*m_size)+n > array<element>::growth_formula(*m_size) )
1128
1129
1130
1131
1132
1133
1134
				{
					void * tmp = realloc(*m_arr,sizeof(element)*array<element>::growth_formula((*m_size)+static_cast<size_type>(n)));
#if defined(DEBUGMEM)
					if( tmp == NULL ) {printf("%s:%d realloc return NULL\n",__FILE__,__LINE__);}
#endif
					*m_arr = static_cast<element *>(tmp);
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
1135
1136
				(*m_size)+=static_cast<size_type>(n);

Kirill Terekhov's avatar
Kirill Terekhov committed
1137
1138
1139
1140
				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
1141
					size_type i = 0;
Kirill Terekhov's avatar
Kirill Terekhov committed
1142
1143
1144
1145
1146
1147
1148
					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
1149
			ptrdiff_t n = static_cast<ptrdiff_t>(std::distance(first,last));
Kirill Terekhov's avatar
Kirill Terekhov committed
1150
1151
1152
1153
			if( static_cast<void *>(m_first) == NULL)
			{
				assert((*m_arr)==NULL);
				m_first = m_last = iterator((*m_arr) = static_cast<element *>(malloc(sizeof(element))));
1154
1155
1156
#if defined(DEBUGMEM)
				if( *m_arr == NULL ) {printf("%s:%d realloc return NULL\n",__FILE__,__LINE__);}
#endif
Kirill Terekhov's avatar
Kirill Terekhov committed
1157
1158
				assert((*m_arr)!=NULL);
			}
1159
			ptrdiff_t q = m_last-m_first;
Kirill Terekhov's avatar
Kirill Terekhov committed
1160
1161
1162
1163
1164
			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
1165
				assert( !fixed ); // array size is fixed
Kirill Terekhov's avatar
Kirill Terekhov committed
1166
1167
				size_type gf = array<element>::growth_formula((*m_size)+static_cast<size_type>(n-q));
				if( gf != array<element>::growth_formula(*m_size) )
1168
1169
1170
1171
1172
1173
1174
				{
					void * tmp = realloc(*m_arr,sizeof(element)*gf);
#if defined(DEBUGMEM)
					if( tmp == NULL ) {printf("%s:%d realloc return NULL\n",__FILE__,__LINE__);}
#endif
					*m_arr = static_cast<element *>(tmp);
				}
Kirill Terekhov's avatar
Kirill Terekhov committed
1175
				(*m_size)+=static_cast<size_type>(n-q);
Kirill Terekhov's avatar
Kirill Terekhov committed
1176
			}
1177
			if( s > 0 )
Kirill Terekhov's avatar
Kirill Terekhov committed
1178
				memmove((*m_arr)+d+n,(*m_arr)+d+q,sizeof(element)*s);
Kirill Terekhov's avatar
Kirill Terekhov committed
1179
1180
			{
				InputIterator it = first;
Kirill Terekhov's avatar
Kirill Terekhov committed
1181
				size_type i = 0;
Kirill Terekhov's avatar
Kirill Terekhov committed
1182
1183
1184
				while(it != last) new ((*m_arr)+d+i++) element(*it++);
			}
		}
1185
1186
1187
1188
1189
		template <class InputIterator>
		void assign(InputIterator first, InputIterator last)
		{
			replace(begin(),end(),first,last);
		}
Kirill Terekhov's avatar
Kirill Terekhov committed
1190
1191
1192
	};


1193
1194

	template <typename IndType,typename ValType>
Kirill Terekhov's avatar
Kirill Terekhov committed
1195
1196
1197
1198
1199
1200
1201
1202
	class sparse_data
	{
	public:
		typedef unsigned enumerate;
		static const enumerate prealloc = 4;
		typedef struct pair_t
		{
			IndType first;
1203
			ValType second;
Kirill Terekhov's avatar
Kirill Terekhov committed
1204
1205
1206
1207
1208
1209
			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:
1210
		static size_t comparator(const void * pa, const void *