INMOST
Mathematical Modelling Toolkit
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
container.hpp
Go to the documentation of this file.
1 
2 #ifndef _CONTAINER_HPP
3 #define _CONTAINER_HPP
4 
5 
6 #include <stdlib.h>
7 #include <stddef.h>
8 #include <string.h>
9 #include <memory>
10 #include <new>
11 #include <iterator>
12 #include <cmath>
13 #include <assert.h>
14 #include <limits>
15 #include "inmost_common.h"
16 
17 //#define OUT_OF_RANGE
18 
19 //TODO
20 // 1. change to uniform size_type instead of size_t, make it INMOST_DATA_ENUM_TYPE
21 /*
22 template<class element, class T1> struct isInputRandomIterators
23 {
24  static void constraints(T1 a, T1 b) { ++a; (void)a++; a==a; a!=a; a-b; }
25  isInputRandomIterators() { void(*p)(T1,T1) = constraints; (void)p; }
26 };
27 
28 template<class element, class T1> struct isInputForwardIterators
29 {
30  static void constraints(T1 a) {++a; (void)a++; }
31  isInputForwardIterators() { void(*p)(T1) = constraints; (void)p; }
32 };
33 */
34 
35 namespace INMOST
36 {
37  //add more templates as needed
38  template<class T> struct make_unsigned;
39  template<> struct make_unsigned<char> {typedef unsigned char type;};
40  template<> struct make_unsigned<short> {typedef unsigned short type;};
41  template<> struct make_unsigned<int> {typedef unsigned int type;};
42  template<> struct make_unsigned<long> {typedef unsigned long type;};
43  template<> struct make_unsigned<long long> {typedef unsigned long long type;};
44  template<> struct make_unsigned<unsigned char> {typedef unsigned char type;};
45  template<> struct make_unsigned<unsigned short> {typedef unsigned short type;};
46  template<> struct make_unsigned<unsigned int> {typedef unsigned int type;};
47  template<> struct make_unsigned<unsigned long> {typedef unsigned long type;};
48  template<> struct make_unsigned<unsigned long long> {typedef unsigned long long type;};
49 
50 #define USE_OPTIMIZED_ARRAY_ALLOCATION
51 #if defined(PACK_ARRAY)
52 #pragma pack(push,r1,4)
53 #endif
54  // notice: array class would not properly support classes that contain self-references
55  // like std::map
56  // notice: next class shell have to implement same algorithms as array
57  template<typename element>//, typename enumerator = unsigned int>
58  class array
59  {
60  public:
61  typedef unsigned size_type;
63  template<typename etype>
64  class _iterator
65  {
66  private:
67  etype * e;
68  public:
69  typedef etype * pointer;
70  typedef etype & reference;
71  typedef etype value_type;
72  typedef ptrdiff_t difference_type;
73  typedef std::random_access_iterator_tag iterator_category;
74  _iterator():e(NULL){}
75  _iterator(etype * i):e(i){}
76  _iterator(const _iterator & other){e = other.e;}
77  ~_iterator() {};
78  _iterator operator -(size_t n) { return _iterator(e-n); }
79  _iterator & operator -=(size_t n) { e-=n; return *this; }
80  _iterator operator +(size_t n) { return _iterator(e+n); }
81  _iterator & operator +=(size_t n) { e+=n; return *this; }
82  _iterator & operator ++(){ ++e; return *this;}
83  _iterator operator ++(int){ return _iterator(e++); }
84  _iterator & operator --(){ --e; return *this; }
85  _iterator operator --(int){ return _iterator(e--); }
86  ptrdiff_t operator -(const _iterator & other) const {return e-other.e;}
87  etype & operator *() { return *e; }
88  etype * operator ->() { return e; }
89  _iterator & operator =(_iterator const & other) { e = other.e; return *this; }
90  bool operator ==(const _iterator & other) const { return e == other.e;}
91  bool operator !=(const _iterator & other) const { return e != other.e;}
92  bool operator <(const _iterator & other) const { return e < other.e;}
93  bool operator >(const _iterator & other) const { return e > other.e;}
94  bool operator <=(const _iterator & other) const { return e <= other.e;}
95  bool operator >=(const _iterator & other) const { return e >= other.e;}
96  operator void *() {return static_cast<void *> (e);}
97  operator const void *() {return const_cast<const void *> (e);}
98  };
99  typedef _iterator<element> iterator;
100  typedef _iterator<const element> const_iterator;
101  template<typename etype>
103  {
104  private:
105  etype * e;
106  public:
107  typedef etype * pointer;
108  typedef etype & reference;
109  typedef etype value_type;
110  typedef ptrdiff_t difference_type;
111  typedef std::random_access_iterator_tag iterator_category;
112  _reverse_iterator():e(NULL){}
113  _reverse_iterator(etype * i):e(i){}
114  _reverse_iterator(const _reverse_iterator & other){e = other.e;}
116  _reverse_iterator operator -(size_t n) { return _reverse_iterator(e+n); }
117  _reverse_iterator & operator -=(size_t n) { e+=n; return *this; }
119  _reverse_iterator & operator +=(size_t n) { e-=n; return *this; }
120  _reverse_iterator & operator ++(){ --e; return *this;}
122  _reverse_iterator & operator --(){ ++e; return *this; }
124  ptrdiff_t operator -(const _reverse_iterator & other) const {return other.e-e;}
125  etype & operator *() { return *e; }
126  etype * operator ->() { return e; }
127  _reverse_iterator & operator =(_reverse_iterator const & other) { e = other.e; return *this;}
128  bool operator ==(const _reverse_iterator & other) const { return e == other.e;}
129  bool operator !=(const _reverse_iterator & other) const { return e != other.e;}
130  bool operator <(const _reverse_iterator & other) const { return e < other.e;}
131  bool operator >(const _reverse_iterator & other) const { return e > other.e;}
132  bool operator <=(const _reverse_iterator & other) const { return e <= other.e;}
133  bool operator >=(const _reverse_iterator & other) const { return e >= other.e;}
134  operator void *() {return static_cast<void *> (e);}
135  };
136  typedef _reverse_iterator<element> reverse_iterator;
137  typedef _reverse_iterator<const element> const_reverse_iterator;
138  private:
139 
140  element * m_arr;
141  size_type m_size;
142 
143  //notice: push_back, pop_back, insert, erase are optimized for current growth_formula
144  __INLINE static size_type growth_formula(size_type future_size)
145  {
146  uenum v = static_cast<uenum>(future_size);
147  v--;
148  v|= (v>>1);
149  v|= (v>>2);
150  v|= (v>>4);
151  v|= (v>>8);
152  v|= (v>>16);
153  //TODO produces compiler warning
154  //if( sizeof(size_type) > 4 ) v|= (v>>32); //must be compile time brench
155  v++;
156  return static_cast<size_type>(v);
157  }
158  public:
159  __INLINE element * data() {return m_arr;}
160  __INLINE const element * data() const {return m_arr;}
161  array() {m_arr = NULL; m_size = 0;}
162  array(size_type n,element c = element())
163  {
164  m_size = n;
165  m_arr = static_cast<element *>(malloc(sizeof(element)*growth_formula(m_size)));
166  assert(m_arr != NULL);
167  for(size_type i = 0; i < m_size; i++) new (m_arr+i) element(c);
168  }
169  template<class InputIterator>
170  array(InputIterator first, InputIterator last)
171  {
172  //isInputForwardIterators<element,InputIterator>();
173  m_size = static_cast<size_type>(std::distance(first,last));
174  m_arr = static_cast<element *>(malloc(sizeof(element)*growth_formula(m_size)));
175  assert(m_arr != NULL);
176  {
177  size_type i = 0;
178  InputIterator it = first;
179  while(it != last) new (m_arr+i++) element(*it++);
180  }
181  }
182  array(const array & other)
183  {
184  m_size = other.m_size;
185  if( m_size )
186  {
187  m_arr = static_cast<element *>(malloc(sizeof(element)*growth_formula(m_size)));
188  assert(m_arr != NULL);
189  }
190  else m_arr = NULL;
191  for(size_type i = 0; i < m_size; i++) new (m_arr+i) element(other.m_arr[i]);
192  }
194  {
195  for(size_type i = 0; i < m_size; i++) m_arr[i].~element();
196  if( m_arr != NULL ) free(m_arr);
197  m_arr = NULL;
198  m_size = 0;
199  }
200  __INLINE const element & operator [] (size_type n) const
201  {
202  assert(n < m_size);
203  return m_arr[n];
204  }
206  {
207  assert(n < m_size);
208  return m_arr[n];
209  }
210  __INLINE const element & at (size_type n) const
211  {
212  assert(n < m_size);
213  return m_arr[n];
214  }
215  __INLINE element & at (size_type n)
216  {
217  assert(n < m_size);
218  return m_arr[n];
219  }
220  __INLINE element & at_safe (size_type n)
221  {
222  if( n >= m_size ) resize(n+1);
223  return m_arr[n];
224  }
225  array & operator =(array const & other)
226  {
227  if( this != &other )
228  {
229  for(size_type i = 0; i < m_size; i++) m_arr[i].~element();
230  if(m_arr != NULL )
231  {
232  free(m_arr);
233  m_arr = NULL;
234  }
235  if( other.m_arr != NULL )
236  {
237  m_size = other.m_size;
238  m_arr = static_cast<element *>(malloc(sizeof(element)*growth_formula(m_size)));
239  assert(m_arr != NULL);
240  memcpy(m_arr,other.m_arr,sizeof(element)*m_size);
241  }
242  }
243  return *this;
244  }
245  void push_back(const element & e)
246  {
247 #if !defined(USE_OPTIMIZED_ARRAY_ALLOCATION)
248  //unoptimized variant
249  if( m_size+1 > growth_formula(m_size) )
250  m_arr = static_cast<element *>(realloc(m_arr,sizeof(element)*growth_formula(++m_size)));
251  else ++m_size;
252 #else
253  //optimized for current growth_formula
254  if( m_size < 2 )
255  m_arr = static_cast<element *>(realloc(m_arr,sizeof(element)*(++m_size)));
256  else if( ((m_size+1) & (m_size-1)) == 1 )
257  m_arr = static_cast<element *>(realloc(m_arr,sizeof(element)*(m_size++ << 1)));
258  else m_size++;
259 #endif
260  assert(m_arr != NULL);
261  new (m_arr+m_size-1) element(e);
262  }
263  void pop_back()
264  {
265  assert(m_arr != NULL);
266  m_arr[m_size--].~element();
267  if( m_size > 0)
268  {
269 #if !defined(USE_OPTIMIZED_ARRAY_ALLOCATION)
270  //unoptimized variant
271  size_type gf = growth_formula(m_size);
272  if( m_size+1 > gf )
273  m_arr = static_cast<element *>(realloc(m_arr,sizeof(element)*gf));
274 #else
275  if( ((m_size+1) & (m_size-1)) == 1 || m_size == 1)
276  m_arr = static_cast<element *>(realloc(m_arr,sizeof(element)*m_size));
277 #endif
278  assert(m_arr != NULL);
279  }
280  else
281  {
282  free(m_arr);
283  m_arr = NULL;
284  }
285  }
286  __INLINE element & back()
287  {
288  assert(m_arr != NULL);
289  assert(m_size > 0);
290  return m_arr[m_size-1];
291  }
292  __INLINE const element & back() const
293  {
294  assert(m_arr != NULL);
295  assert(m_size > 0);
296  return m_arr[m_size-1];
297  }
298  __INLINE element & front()
299  {
300  assert(m_arr != NULL);
301  assert(m_size > 0);
302  return m_arr[0];
303  }
304  __INLINE const element & front() const
305  {
306  assert(m_arr != NULL);
307  assert(m_size > 0);
308  return m_arr[0];
309  }
310  __INLINE size_type capacity() { return m_size; }
311  __INLINE bool empty() const { if( m_size ) return false; return true; }
312  void resize(size_type n, element c = element() )
313  {
314  size_type oldsize = m_size;
315  m_size = n;
316  for(size_type i = m_size; i < oldsize; i++) m_arr[i].~element(); //delete elements, located over the size
317  if( m_size > 0 )
318  {
319  if( growth_formula(oldsize) != growth_formula(m_size) )
320  m_arr = static_cast<element *>(realloc(m_arr,sizeof(element)*growth_formula(m_size)));
321  assert(m_arr != NULL);
322  for(size_type i = oldsize; i < m_size; i++) new (m_arr+i) element(c); //initialize extra entities
323  }
324  else
325  {
326  free(m_arr);
327  m_arr = NULL;
328  }
329  }
330  __INLINE size_type size() const {return m_size;}
331  __INLINE size_type capacity() const {return growth_formula(m_size);}
332  void clear()
333  {
334  for(size_type i = 0; i < m_size; i++) m_arr[i].~element();
335  m_size = 0;
336  if( m_arr ) free(m_arr);
337  m_arr = NULL;
338  }
339  void swap(array<element> & other)
340  {
341  element * t_m_arr = m_arr;
342  size_type t_m_size = m_size;
343  m_arr = other.m_arr;
344  m_size = other.m_size;
345  other.m_arr = t_m_arr;
346  other.m_size = t_m_size;
347  }
348  __INLINE iterator begin() { return m_arr; }
349  __INLINE iterator end() { return m_arr+m_size; }
350  __INLINE const_iterator begin() const { return m_arr; }
351  __INLINE const_iterator end() const { return m_arr+m_size; }
352  __INLINE reverse_iterator rbegin() { return reverse_iterator(m_arr+m_size-1); }
354  __INLINE const_reverse_iterator rbegin() const { return const_reverse_iterator(m_arr+m_size-1); }
357  {
358  ptrdiff_t d = pos-begin();
359  ptrdiff_t s = iterator(m_arr+m_size-1)-pos;
360  (*pos).~element();
361  m_size--;
362  if( m_size > 0 )
363  {
364  if( s > 0 ) memmove(m_arr+d,m_arr+d+1,sizeof(element)*s);
365  //unoptimized variant
366 #if !defined(USE_OPTIMIZED_ARRAY_ALLOCATION)
367  size_type gf = growth_formula(m_size);
368  if( m_size+1 > gf )
369  m_arr = static_cast<element *>(realloc(m_arr,sizeof(element)*gf));
370 #else
371  if( ((m_size+1) & (m_size-1)) == 1 || m_size == 1)
372  m_arr = static_cast<element *>(realloc(m_arr,sizeof(element)*m_size));
373 #endif
374  assert(m_arr != NULL);
375  }
376  else
377  {
378  free(m_arr);
379  m_arr = NULL;
380  }
381  return m_arr+d;
382  }
384  {
385  ptrdiff_t d = b-begin();
386  ptrdiff_t s = end()-e;
387  ptrdiff_t n = e-b;
388  for(iterator i = b; i != e; i++) (*i).~element();
389  m_size -= n;
390  if( m_size > 0 )
391  {
392  if( s > 0 ) memmove(m_arr+d,m_arr+d+1,sizeof(element)*s);
393  size_type gf = growth_formula(m_size);
394  if( m_size+n > gf )
395  m_arr = static_cast<element *>(realloc(m_arr,sizeof(element)*gf));
396  assert(m_arr != NULL);
397  }
398  else
399  {
400  free(m_arr);
401  m_arr = NULL;
402  }
403  return m_arr+d;
404  }
405  iterator insert(iterator pos, const element & x)
406  {
407  if( static_cast<void *>(pos) == NULL)
408  {
409  assert(m_arr == NULL);
410  pos = iterator(m_arr = static_cast<element *>(malloc(sizeof(element))));
411  assert(m_arr != NULL);
412  }
413  ptrdiff_t d = pos-begin();
414  ptrdiff_t s = end()-pos;
415 
416  //unoptimized variant
417 #if !defined(USE_OPTIMIZED_ARRAY_ALLOCATION)
418  if( m_size+1 > growth_formula(m_size) )
419  m_arr = static_cast<element *>(realloc(m_arr,sizeof(element)*growth_formula(++m_size)));
420  else ++m_size;
421 #else
422  //optimized for current growth_formula
423  if( m_size < 2 )
424  m_arr = static_cast<element *>(realloc(m_arr,sizeof(element)*(++m_size)));
425  else if( ((m_size+1) & (m_size-1)) == 1 )
426  m_arr = static_cast<element *>(realloc(m_arr,sizeof(element)*(m_size++ << 1)));
427  else ++m_size;
428 #endif
429  assert(m_arr != NULL);
430  if( s > 0 ) memmove(m_arr+d+1,m_arr+d,sizeof(element)*s);
431  new (m_arr+d) element(x);
432  return m_arr+d;
433  }
434  void insert(iterator pos, size_type n, const element & x)
435  {
436  if( n > 0 )
437  {
438  if( static_cast<void *>(pos) == NULL)
439  {
440  assert(m_arr == NULL);
441  pos = iterator(m_arr = static_cast<element *>(malloc(sizeof(element))));
442  assert(m_arr != NULL);
443  }
444  ptrdiff_t d = pos-begin();
445  ptrdiff_t s = end()-pos;
446 
447  if( m_size+n > growth_formula(m_size) )
448  m_arr = static_cast<element *>(realloc(m_arr,sizeof(element)*growth_formula(m_size+n)));
449  m_size+=n;
450 
451  assert(m_arr != NULL);
452  if( s > 0 ) memmove(m_arr+d+n,m_arr+d,sizeof(element)*s);
453  for(size_type i = 0; i < n; i++) new (m_arr+d+i) element(x);
454  }
455  }
456  template <class InputIterator>
457  void insert(iterator pos, InputIterator first, InputIterator last)
458  {
459  size_type n = static_cast<size_type>(std::distance(first,last));
460  if( n > 0 )
461  {
462  if( static_cast<void *>(pos) == NULL)
463  {
464  assert(m_arr == NULL);
465  pos = iterator(m_arr = static_cast<element *>(malloc(sizeof(element))));
466  assert(m_arr != NULL);
467  }
468  ptrdiff_t d = pos-begin();
469  ptrdiff_t s = end()-pos;
470 
471  if( m_size+n > growth_formula(m_size) )
472  m_arr = static_cast<element *>(realloc(m_arr,sizeof(element)*growth_formula(m_size+n)));
473  m_size+=n;
474 
475  assert(m_arr != NULL);
476  if( s > 0 ) memmove(m_arr+d+n,m_arr+d,sizeof(element)*s);
477  {
478  InputIterator it = first;
479  size_type i = 0;
480  while(it != last) new (m_arr+d+i++) element(*it++);
481  }
482  }
483  }
484  template <class InputIterator>
485  void replace(iterator m_first, iterator m_last, InputIterator first, InputIterator last)
486  {
487  assert( m_size >= 0 );
488  ptrdiff_t n = static_cast<ptrdiff_t>(std::distance(first,last));
489  if( static_cast<void *>(m_first) == NULL && m_arr == NULL)
490  {
491  assert(m_arr == NULL);
492  m_first = m_last = iterator(m_arr = static_cast<element *>(malloc(sizeof(element))));
493  assert(m_arr != NULL);
494  }
495  ptrdiff_t q = m_last-m_first;
496  ptrdiff_t d = m_first-iterator(m_arr);
497  ptrdiff_t s = iterator(m_arr+m_size)-m_last;
498  for(iterator it = m_first; it != m_last; it++) (*it).~element();
499  if( n-q != 0 )
500  {
501  size_type gf = growth_formula(m_size+(n-q));
502  if( gf != growth_formula(m_size) )
503  m_arr = static_cast<element *>(realloc(m_arr,sizeof(element)*gf));
504  m_size+=(n-q);
505  if( s > 0 ) memmove(m_arr+d+n,m_arr+d+q,sizeof(element)*s);
506  }
507  {
508  InputIterator it = first;
509  size_type i = 0;
510  while(it != last) new (m_arr+d+i++) element(*it++);
511  }
512  }
513  template<class> friend class shell;
514  };
515 #if defined(PACK_ARRAY)
516 #pragma pack(pop,r1)
517 #endif
518  template<typename element>
519  class shell
520  {
521  public:
523  template<typename dtype>
524  class _iterator
525  {
526  private:
527  dtype * e;
528  public:
529  typedef dtype * pointer;
530  typedef dtype & reference;
531  typedef dtype value_type;
532  typedef ptrdiff_t difference_type;
533  typedef std::random_access_iterator_tag iterator_category;
534  _iterator():e(NULL){}
535  _iterator(dtype * i):e(i){}
536  _iterator(const _iterator & other){e = other.e;}
538  _iterator operator -(size_t n) { return _iterator(e-n); }
539  _iterator & operator -=(size_t n) { e-=n; return *this; }
540  _iterator operator +(size_t n) { return _iterator(e+n); }
541  _iterator & operator +=(size_t n) { e+=n; return *this; }
542  _iterator & operator ++(){ ++e; return *this;}
543  _iterator operator ++(int){ return _iterator(e++); }
544  _iterator & operator --(){ --e; return *this; }
545  _iterator operator --(int){ return _iterator(e--); }
546  ptrdiff_t operator -(const _iterator & other) const {return e-other.e;}
547  dtype & operator *() { return *e; }
548  dtype * operator ->() { return e; }
549  _iterator & operator =(_iterator const & other) { e = other.e; return *this; }
550  bool operator ==(const _iterator & other) { return e == other.e;}
551  bool operator !=(const _iterator & other) { return e != other.e;}
552  bool operator <(const _iterator & other) { return e < other.e;}
553  bool operator >(const _iterator & other) { return e > other.e;}
554  bool operator <=(const _iterator & other) { return e <= other.e;}
555  bool operator >=(const _iterator & other) { return e >= other.e;}
556  operator void *() {return static_cast<void *> (e);}
557  };
558  typedef _iterator<element> iterator;
559  typedef _iterator<const element> const_iterator;
560  template<typename dtype>
562  {
563  private:
564  dtype * e;
565  public:
566  typedef dtype * pointer;
567  typedef dtype & reference;
568  typedef dtype value_type;
569  typedef ptrdiff_t difference_type;
570  typedef std::random_access_iterator_tag iterator_category;
571  _reverse_iterator():e(NULL){}
572  _reverse_iterator(dtype * i):e(i){}
573  _reverse_iterator(const _reverse_iterator & other){e = other.e;}
575  _reverse_iterator operator -(size_t n) { return _reverse_iterator(e+n); }
576  _reverse_iterator & operator -=(size_t n) { e+=n; return *this; }
578  _reverse_iterator & operator +=(size_t n) { e-=n; return *this; }
579  _reverse_iterator & operator ++(){ --e; return *this;}
581  _reverse_iterator & operator --(){ ++e; return *this; }
583  ptrdiff_t operator -(const _reverse_iterator & other) const {return other.e-e;}
584  dtype & operator *() { return *e; }
585  dtype * operator ->() { return e; }
586  _reverse_iterator & operator =(_reverse_iterator const & other) { e = other.e; return *this;}
587  bool operator ==(const _reverse_iterator & other) { return e == other.e;}
588  bool operator !=(const _reverse_iterator & other) { return e != other.e;}
589  bool operator <(const _reverse_iterator & other) { return e < other.e;}
590  bool operator >(const _reverse_iterator & other) { return e > other.e;}
591  bool operator <=(const _reverse_iterator & other) { return e <= other.e;}
592  bool operator >=(const _reverse_iterator & other) { return e >= other.e;}
593  operator void *() {return static_cast<void *> (e);}
594  };
595  typedef _reverse_iterator<element> reverse_iterator;
596  typedef _reverse_iterator<const element> const_reverse_iterator;
597  private:
598  element ** m_arr;
599  size_type * m_size;
600  element * local_link;
601  size_type local_size;
602  bool fixed;
603  public:
604  __INLINE element * data() {return *m_arr;}
605  __INLINE const element * data() const {return *m_arr;}
606  shell() {m_arr = NULL; m_size = NULL; fixed = false;}
607  shell(array<element> & arr) //dynamic
608  {
609  m_arr = &arr.m_arr;
610  m_size = &arr.m_size;
611  fixed = false;
612  }
613  shell(element * link, size_type size) //fixed
614  {
615  m_arr = &local_link;
616  *m_arr = link;
617  m_size = &local_size;
618  *m_size = size;
619  fixed = true;
620  }
621  shell(const shell & other)
622  {
623  fixed = other.fixed;
624  if( fixed )
625  {
626  m_size = &local_size;
627  m_arr = &local_link;
628  *m_size = *other.m_size;
629  *m_arr = *other.m_arr;
630  }
631  else
632  {
633  m_size = other.m_size;
634  m_arr = other.m_arr;
635  }
636  }
638  {
639  }
640  __INLINE const element & operator [] (size_type n) const
641  {
642  assert(n < *m_size );
643  return *((*m_arr)+n);
644  }
646  {
647  assert(n < *m_size );
648  return *((*m_arr)+n);
649  }
650  __INLINE const element & at (size_type n) const
651  {
652  assert(n < *m_size );
653  return *((*m_arr)+n);
654  }
655  __INLINE element & at (size_type n)
656  {
657  assert(n < *m_size );
658  return *((*m_arr)+n);
659  }
660  shell & operator =(shell const & other)
661  {
662  fixed = other.fixed;
663  if( fixed )
664  {
665  m_size = &local_size;
666  m_arr = &local_link;
667  *m_size = *other.m_size;
668  *m_arr = *other.m_arr;
669  }
670  else
671  {
672  m_size = other.m_size;
673  m_arr = other.m_arr;
674  }
675  return *this;
676  }
677  void push_back(const element & e)
678  {
679  assert( !fixed ); // array size is fixed
680 #if !defined(USE_OPTIMIZED_ARRAY_ALLOCATION)
681  //unoptimized variant
682  if( (*m_size)+1 > array<element>::growth_formula(*m_size) )
683  *m_arr = static_cast<element *>(realloc(*m_arr,sizeof(element)*array<element>::growth_formula(++(*m_size))));
684  else ++(*m_size);
685 #else
686  //optimized for current growth_formula
687  if( *m_size < 2 )
688  *m_arr = static_cast<element *>(realloc(*m_arr,sizeof(element)*(++(*m_size))));
689  else if( (((*m_size)+1) & ((*m_size)-1)) == 1 )
690  *m_arr = static_cast<element *>(realloc(*m_arr,sizeof(element)*((*m_size)++ << 1)));
691  else ++(*m_size);
692 #endif
693  assert((*m_arr) != NULL);
694  new ((*m_arr)+(*m_size)-1) element(e);
695  }
696  void pop_back()
697  {
698  assert( !fixed ); // array size is fixed
699  assert((*m_arr) != NULL);
700  (*m_arr)[(*m_size)--].~element();
701  if( (*m_size) > 0 )
702  {
703 #if !defined(USE_OPTIMIZED_ARRAY_ALLOCATION)
704  //unoptimized variant
706  if( (*m_size)+1 > gf )
707  *m_arr = static_cast<element *>(realloc(m_arr,sizeof(element)*gf));
708 #else
709  if( (((*m_size)+1) & ((*m_size)-1)) == 1 || (*m_size) == 1)
710  *m_arr = static_cast<element *>(realloc(*m_arr,sizeof(element)*(*m_size)));
711 #endif
712  assert( (*m_arr) != NULL );
713  }
714  else
715  {
716  free(*m_arr);
717  (*m_arr) = NULL;
718  }
719  }
720  __INLINE element & back()
721  {
722  assert(*m_arr != NULL);
723  assert(*m_size > 0 );
724  return (*m_arr)[(*m_size)-1];
725  }
726  __INLINE const element & back() const
727  {
728  assert(*m_arr != NULL);
729  assert(*m_size > 0 );
730  return (*m_arr)[(*m_size)-1];
731  }
732  __INLINE element & front()
733  {
734  assert(*m_arr != NULL);
735  assert(*m_size > 0 );
736  return (*m_arr)[0];
737  }
738  __INLINE const element & front() const
739  {
740  assert(*m_arr != NULL);
741  assert(*m_size > 0 );
742  return (*m_arr)[0];
743  }
745  __INLINE bool empty() const { if( *m_size ) return false; return true; }
746  void resize(size_type n, element c = element() )
747  {
748  assert( !fixed ); // array size is fixed
749  size_type oldsize = *m_size;
750  *m_size = n;
751  for(size_type i = *m_size; i < oldsize; i++) (*m_arr)[i].~element(); //delete elements, located over the size
752  if( *m_size > 0 )
753  {
755  *m_arr = static_cast<element *>(realloc(*m_arr,sizeof(element)*array<element>::growth_formula(*m_size)));
756  assert( (*m_arr) != NULL );
757  for(size_type i = oldsize; i < *m_size; i++) new ((*m_arr)+i) element(c); //initialize extra entities
758  }
759  else
760  {
761  free(*m_arr);
762  *m_arr = NULL;
763  }
764  }
765  __INLINE size_type size() const {return *m_size;}
766  void clear()
767  {
768  assert( !fixed ); // array size is fixed
769  for(size_type i = 0; i < *m_size; i++) (*m_arr)[i].~element();
770  *m_size = 0;
771  if( *m_arr ) free(*m_arr);
772  *m_arr = NULL;
773  }
774  void swap(shell<element> & other)
775  {
776  element * t_m_arr = *m_arr;
777  size_type t_m_size = *m_size;
778  *m_arr = *other.m_arr;
779  *m_size = *other.m_size;
780  *other.m_arr = t_m_arr;
781  *other.m_size = t_m_size;
782  }
783  __INLINE iterator begin() { return *m_arr; }
784  __INLINE iterator end() { return *m_arr+(*m_size); }
785  __INLINE const_iterator begin() const { return *m_arr; }
786  __INLINE const_iterator end() const { return *m_arr+(*m_size); }
787  __INLINE reverse_iterator rbegin() { return reverse_iterator(*m_arr+(*m_size)-1); }
789  __INLINE const_reverse_iterator rbegin() const { return const_reverse_iterator(*m_arr+(*m_size)-1); }
792  {
793  assert( !fixed ); // array size is fixed
794  ptrdiff_t d = pos-begin();
795  ptrdiff_t s = iterator(*m_arr+(*m_size)-1)-pos;
796  (*pos).~element();
797  (*m_size)--;
798  if( (*m_size) > 0 )
799  {
800  if( s > 0 )memmove(*m_arr+d,*m_arr+d+1,sizeof(element)*s);
801 #if !defined(USE_OPTIMIZED_ARRAY_ALLOCATION)
803  if( (*m_size)+1 > gf )
804  *m_arr = static_cast<element *>(realloc(*m_arr,sizeof(element)*gf));
805 #else
806  if( (((*m_size)+1) & ((*m_size)-1)) == 1 || (*m_size) == 1)
807  *m_arr = static_cast<element *>(realloc(*m_arr,sizeof(element)*(*m_size)));
808 #endif
809  assert((*m_arr) != NULL);
810  }
811  else
812  {
813  free(*m_arr);
814  *m_arr = NULL;
815  }
816  return (*m_arr)+d;
817  }
819  {
820  assert( !fixed ); // array size is fixed
821  ptrdiff_t d = b-begin();
822  ptrdiff_t s = end()-e;
823  ptrdiff_t n = e-b;
824  for(iterator i = b; i != e; i++) (*i).~element();
825  (*m_size) -= n;
826  if( (*m_size) > 0 )
827  {
828  if( s > 0 ) memmove(*m_arr+d,*m_arr+d+n,sizeof(element)*s);
830  if( (*m_size)+n > gf )
831  *m_arr = static_cast<element *>(realloc(*m_arr,sizeof(element)*gf));
832  assert((*m_arr) != NULL);
833  }
834  else
835  {
836  free(*m_arr);
837  *m_arr = NULL;
838  }
839  return (*m_arr)+d;
840  }
841  iterator insert(iterator pos, const element & x)
842  {
843  assert( !fixed ); // array size is fixed
844  if( static_cast<void *>(pos) == NULL )
845  {
846  assert((*m_arr) == NULL);
847  pos = iterator((*m_arr) = static_cast<element *>(malloc(sizeof(element))));
848  assert((*m_arr) != NULL);
849  }
850  ptrdiff_t d = pos-begin();
851  ptrdiff_t s = end()-pos;
852 
853 #if !defined(USE_OPTIMIZED_ARRAY_ALLOCATION)
854  //unoptimized variant
855  if( (*m_size)+1 > array<element>::growth_formula(*m_size) )
856  *m_arr = static_cast<element *>(realloc(*m_arr,sizeof(element)*array<element>::growth_formula(++(*m_size))));
857  else ++(*m_size);
858 #else
859  //optimized for current growth_formula
860  if( *m_size < 2 )
861  *m_arr = static_cast<element *>(realloc(*m_arr,sizeof(element)*(++(*m_size))));
862  else if( (((*m_size)+1) & ((*m_size)-1)) == 1 )
863  *m_arr = static_cast<element *>(realloc(*m_arr,sizeof(element)*((*m_size)++ << 1)));
864  else ++(*m_size);
865 #endif
866  assert((*m_arr) != NULL);
867  if( s > 0 ) memmove((*m_arr)+d+1,(*m_arr)+d,sizeof(element)*s);
868  new ((*m_arr)+d) element(x);
869  return (*m_arr)+d;
870  }
871  void insert(iterator pos, size_type n, const element & x)
872  {
873  assert( !fixed ); // array size is fixed
874  if( n > 0 )
875  {
876  if( static_cast<void *>(pos) == NULL)
877  {
878  assert((*m_arr) == NULL);
879  pos = iterator((*m_arr) = static_cast<element *>(malloc(sizeof(element))));
880  assert((*m_arr) != NULL);
881  }
882  ptrdiff_t d = pos-iterator(*m_arr);
883  ptrdiff_t s = iterator((*m_arr)+(*m_size))-pos;
884 
885  if( (*m_size)+n > array<element>::growth_formula(*m_size) )
886  *m_arr = static_cast<element *>(realloc(*m_arr,sizeof(element)*array<element>::growth_formula((*m_size)+n)));
887  (*m_size)+=n;
888 
889  assert((*m_arr) != NULL);
890  if( s > 0 ) memmove((*m_arr)+d+n,(*m_arr)+d,sizeof(element)*s);
891  for(size_type i = 0; i < n; i++) new ((*m_arr)+d+i) element(x);
892  }
893  }
894  template <class InputIterator>
895  void insert(iterator pos, InputIterator first, InputIterator last)
896  {
897  assert( !fixed ); // array size is fixed
898  ptrdiff_t n = static_cast<ptrdiff_t>(std::distance(first,last));
899  if( n > 0 )
900  {
901  if( static_cast<void *>(pos) == NULL)
902  {
903  assert((*m_arr) == NULL);
904  pos = iterator((*m_arr) = static_cast<element *>(malloc(sizeof(element))));
905  assert((*m_arr) != NULL);
906  }
907  ptrdiff_t d = pos-iterator(*m_arr);
908  ptrdiff_t s = iterator((*m_arr)+(*m_size))-pos;
909 
910 
911  if( (*m_size)+n > array<element>::growth_formula(*m_size) )
912  *m_arr = static_cast<element *>(realloc(*m_arr,sizeof(element)*array<element>::growth_formula((*m_size)+static_cast<size_type>(n))));
913  (*m_size)+=static_cast<size_type>(n);
914 
915  assert((*m_arr) != NULL);
916  if( s > 0 ) memmove((*m_arr)+d+n,(*m_arr)+d,sizeof(element)*s);
917  {
918  InputIterator it = first;
919  size_type i = 0;
920  while(it != last) new ((*m_arr)+d+i++) element(*it++);
921  }
922  }
923  }
924  template <class InputIterator>
925  void replace(iterator m_first, iterator m_last, InputIterator first, InputIterator last)
926  {
927  ptrdiff_t n = static_cast<ptrdiff_t>(std::distance(first,last));
928  if( static_cast<void *>(m_first) == NULL)
929  {
930  assert((*m_arr)==NULL);
931  m_first = m_last = iterator((*m_arr) = static_cast<element *>(malloc(sizeof(element))));
932  assert((*m_arr)!=NULL);
933  }
934  ptrdiff_t q = m_last-m_first;
935  ptrdiff_t d = m_first-iterator(*m_arr);
936  ptrdiff_t s = iterator((*m_arr)+(*m_size))-m_last;
937  for(iterator it = m_first; it != m_last; it++) (*it).~element();
938  if( n-q != 0 )
939  {
940  assert( !fixed ); // array size is fixed
941  size_type gf = array<element>::growth_formula((*m_size)+static_cast<size_type>(n-q));
942  if( gf != array<element>::growth_formula(*m_size) )
943  *m_arr = static_cast<element *>(realloc(*m_arr,sizeof(element)*gf));
944  (*m_size)+=static_cast<size_type>(n-q);
945  }
946  if( s > 0 )
947  memmove((*m_arr)+d+n,(*m_arr)+d+q,sizeof(element)*s);
948  {
949  InputIterator it = first;
950  size_type i = 0;
951  while(it != last) new ((*m_arr)+d+i++) element(*it++);
952  }
953  }
954  };
955 
956 
957 
958  template <typename IndType,typename ValType>
960  {
961  public:
962  typedef unsigned enumerate;
963  static const enumerate prealloc = 4;
964  typedef struct pair_t
965  {
966  IndType first;
967  ValType second;
968  pair_t() :first(0),second(0.0) {}
969  pair_t(IndType first, ValType second) :first(0), second(0.0) {}
970  } pair;
971  typedef pair * iterator;
972  typedef const iterator const_iterator;
973  private:
974  static int comparator(const void * pa, const void * pb)
975  {
976  pair * a = (pair *)pa;
977  pair * b = (pair *)pb;
978  return a->first - b->first;
979  }
980  pair * array;
981  enumerate arr_size;
982  enumerate arr_alloc;
983  void test_allocate()
984  {
985  if( arr_size > arr_alloc )
986  {
987  enumerate old_arr_alloc = arr_alloc;
988  while(arr_size > arr_alloc) arr_alloc = arr_alloc << 1;
989  array = static_cast<pair *>(realloc(array,arr_alloc*sizeof(pair)));
990  assert(array != NULL);
991  for (enumerate i = old_arr_alloc; i < arr_alloc; i++) array[i].first = std::numeric_limits<IndType>::max();
992  //memset(array+old_arr_alloc,0xff,sizeof(pair)*(arr_alloc-old_arr_alloc));
993  }
994  }
995  public:
997  {
998  pair * tmp = array;
999  array = other.array;
1000  other.array = tmp;
1001  enumerate itmp = arr_size;
1002  arr_size = other.arr_size;
1003  other.arr_size = itmp;
1004  itmp = arr_alloc;
1005  arr_alloc = other.arr_alloc;
1006  other.arr_alloc = itmp;
1007  }
1009  {
1010  enumerate new_alloc = 1;
1011  while( new_alloc < size ) new_alloc = new_alloc << 1;
1012  array = static_cast<pair *>(realloc(array,new_alloc*sizeof(pair)));
1013  assert(array != NULL);
1014  for (enumerate i = arr_alloc; i < new_alloc; i++) array[i].first = std::numeric_limits<IndType>::max();
1015  //memset(array+arr_alloc,0xff,sizeof(pair)*(new_alloc-arr_alloc));
1016  arr_alloc = new_alloc;
1017  }
1018  iterator lower_bound(IndType ind)
1019  {
1020  /*
1021  if( arr_size < 16 )
1022  {
1023  for(enumerate i = 0; i < arr_size; i++)
1024  if( array[i].first >= ind ) return array+i;
1025  return array+arr_size;
1026  }
1027  */
1028  unsigned k = 0;
1029  for(unsigned b = arr_alloc >> 1; b ; b = b >> 1)
1030  {
1031  unsigned j = k | b;
1032  if( array[j].first <= ind ) k = j;
1033  }
1034  if( array[k].first < ind ) k++;
1035 
1036  return array+k;
1037  }
1038  iterator find(IndType ind)
1039  {
1040  iterator k = lower_bound(ind);
1041  if( k->first == ind ) return k;
1042  return end();
1043  }
1044  iterator insert(iterator pos, const IndType & x)
1045  {
1046  assert(pos == end() || x < pos->first);//check here that we don't break the order
1047  ptrdiff_t d = pos-array;
1048  ptrdiff_t s = arr_size-d;
1049  arr_size++;
1050  test_allocate();
1051  if( s ) memmove(array+d+1,array+d,sizeof(pair)*s);
1052  (array+d)->first = x;
1053  new (&(array[d].second)) ValType();
1054  return array+d;
1055  }
1056  void push_back(const pair & in)
1057  {
1058  assert(arr_size == 0 || in.first < (array+arr_size-1)->first);//check here that we don't break the order
1059  arr_size++;
1060  test_allocate();
1061  (array+arr_size-1)->first = in.first;
1062  (array+arr_size-1)->second = in.second;
1063  }
1065  {
1066  ptrdiff_t d = pos-array;
1067  ptrdiff_t s = (array+arr_size-1)-pos;
1068  (pos->second).~ValType();
1069  memmove(array+d,array+d+1,sizeof(pair)*s);
1070  arr_size--;
1071  return array+d;
1072  }
1073  sparse_data(pair * first, pair * last)
1074  {
1075  arr_size = last-first;
1076  arr_alloc = static_cast<enumerate>(prealloc);
1077  if( arr_size <= arr_alloc )
1078  array = static_cast<pair *>(malloc(arr_alloc*sizeof(pair)));
1079  else
1080  {
1081  array = NULL;
1082  test_allocate();
1083  }
1084  assert(array != NULL);
1085  memcpy(array,first,sizeof(pair)*arr_size);
1086  for (enumerate i = arr_alloc; i < arr_size; i++) array[i].first = std::numeric_limits<IndType>::max();
1087  //memset(array+arr_size,0xff,sizeof(pair)*(arr_alloc-arr_size));
1088  bool need_sort = false;
1089  for(enumerate k = 1; k < arr_size; k++)
1090  if( array[k].first < array[k-1].first )
1091  {
1092  need_sort = true;
1093  break;
1094  }
1095  if( need_sort ) qsort(array,sizeof(pair),arr_size,comparator);
1096  }
1098  {
1099  arr_size = 0;
1100  arr_alloc = static_cast<enumerate>(prealloc);
1101  array = static_cast<pair *>(malloc(sizeof(pair)*arr_alloc));
1102  assert(array != NULL);
1103  for (enumerate i = 0; i < arr_alloc; i++) array[i].first = std::numeric_limits<IndType>::max();
1104  //memset(array,0xff,sizeof(pair)*arr_alloc);
1105  }
1106  sparse_data(const sparse_data & other)
1107  {
1108  arr_size = other.arr_size;
1109  arr_alloc = other.arr_alloc;
1110  array = static_cast<pair *>(malloc(arr_alloc*sizeof(pair)));
1111  assert(array != NULL);
1112  memcpy(array,other.array,other.arr_alloc*sizeof(pair));
1113  }
1115  {
1116  for(iterator i = begin(); i != end(); i++) (i->second).~ValType();
1117  free(array);
1118  arr_size = arr_alloc = 0;
1119  }
1121  {
1122  if( &other != this )
1123  {
1124  for(iterator i = begin(); i != end(); i++) (i->second).~ValType();
1125  arr_size = other.arr_size;
1126  arr_alloc = other.arr_alloc;
1127  array = static_cast<pair *>(realloc(array,arr_alloc*sizeof(pair)));
1128  assert(array != NULL);
1129  memcpy(array,other.array,arr_alloc*sizeof(pair));
1130  }
1131  return *this;
1132  }
1133  ValType & operator [](IndType row)
1134  {
1135  iterator q = lower_bound(row);
1136  if( q != end() && q->first == row ) return q->second;
1137  return insert(q,row)->second;
1138  }
1139  ValType operator [](IndType row) const
1140  {
1141  iterator q = lower_bound(row);
1142  assert(q != end() && q->first == row);
1143  return q->second;
1144  }
1145  enumerate size() const { return arr_size; }
1146  bool empty() const {return size() == 0; }
1147  iterator begin() { return array; }
1148  const_iterator begin() const { return array; }
1149  iterator end() { return array+arr_size; }
1150  const_iterator end() const { return array+arr_size; }
1151  void clear()
1152  {
1153  for(iterator i = begin(); i != end(); i++) (i->second).~ValType();
1154  for (enumerate i = 0; i < arr_size; i++) array[i].first = std::numeric_limits<IndType>::max();
1155  //memset(array,0xff,sizeof(pair)*arr_size);
1156  arr_size = 0;
1157  }
1158  enumerate capacity() {return arr_alloc;}
1159 
1160  };
1161 
1162 
1163 
1164 
1165  template<typename IndType,typename ValType>
1166  class interval
1167  {
1168  public:
1169  typedef ValType * iterator;
1170  typedef ValType const * const_iterator;
1171  //typedef const iterator const_iterator;
1172  private:
1173  ValType * array;
1174  IndType beg_index, end_index;
1175  public:
1176  void clear()
1177  {
1178  for (IndType i = beg_index; i < end_index; i++) (array[i]).~ValType();
1179  if (beg_index != end_index) free(array + beg_index);
1180  array = NULL;
1181  beg_index = end_index = 0;
1182  }
1184  {
1185  {
1186  IndType tmp = beg_index;
1187  beg_index = other.beg_index;
1188  other.beg_index = tmp;
1189  tmp = end_index;
1190  end_index = other.end_index;
1191  other.end_index = tmp;
1192  }
1193  {
1194  ValType * tmp = array;
1195  array = other.array;
1196  other.array = tmp;
1197  }
1198  }
1200  {
1201  beg_index = 0;
1202  end_index = 0;
1203  array = NULL;//static_cast<ValType *>(malloc(sizeof(ValType)*(end_index-beg_index)));
1204  //assert(array != NULL);
1205  //array = array - beg_index;
1206  //for(IndType i = beg_index; i != end_index; ++i) new (array+i) ValType();
1207  }
1208  interval(IndType beg)
1209  {
1210  beg_index = beg;
1211  end_index = beg_index;//+2;
1212  array = NULL; //static_cast<ValType *>(malloc(sizeof(ValType)*(end_index-beg_index)));
1213  //assert(array != NULL);
1214  //array = array - beg_index;
1215  //for(IndType i = beg_index; i != end_index; ++i) new (array+i) ValType();
1216  }
1217  interval(IndType beg, IndType end, ValType c = ValType())
1218  {
1219  beg_index = beg;
1220  end_index = end;
1221  if (beg != end)
1222  {
1223  array = static_cast<ValType *>(malloc(sizeof(ValType)*(end_index - beg_index)));
1224  assert(array != NULL);
1225  array = array - beg_index;
1226  for (IndType i = beg_index; i < end_index; ++i) new (array + i) ValType(c);
1227 
1228  //std::cout << __FUNCTION__ << " address " << array << std::endl;
1229  }
1230  else array = NULL;
1231  }
1232  interval(const interval & other)
1233  {
1234  //std::cout << __FUNCTION__ << std::endl;
1235  beg_index = other.beg_index;
1236  end_index = other.end_index;
1237  if( beg_index != end_index )
1238  {
1239  array = static_cast<ValType *>(malloc(sizeof(ValType)*(end_index-beg_index)));
1240  assert(array != NULL);
1241  array = array - beg_index;
1242  for(IndType i = beg_index; i < end_index; ++i)
1243  {
1244  new (array+i) ValType(other.array[i]);
1245  }
1246  //std::cout << __FUNCTION__ << " address " << array << std::endl;
1247  }
1248  else array = NULL;
1249  }
1251  {
1252  //std::cout << __FUNCTION__ << " delete address " << array << std::endl;
1253  for(IndType i = beg_index; i < end_index; i++) (array[i]).~ValType();
1254  if( beg_index != end_index ) free(array+beg_index);
1255  array = NULL;
1256  }
1257  interval & operator =(interval const & other)
1258  {
1259  if( &other != this )
1260  {
1261  for(iterator i = begin(); i != end(); ++i) (*i).~ValType();
1262  beg_index = other.beg_index;
1263  end_index = other.end_index;
1264  if( beg_index != end_index )
1265  {
1266  array = static_cast<ValType *>(realloc(array+beg_index,sizeof(ValType)*(end_index-beg_index)));
1267  assert(array != NULL);
1268  array = array - beg_index;
1269  for(IndType i = beg_index; i < end_index; ++i) new (array+i) ValType(other.array[i]);
1270  //std::cout << __FUNCTION__ << " address " << array << std::endl;
1271  }
1272  else
1273  {
1274  free(array+beg_index);
1275  array = NULL;
1276  }
1277  }
1278  return *this;
1279  }
1280  ValType & at(IndType row)
1281  {
1282  assert(row >= beg_index);
1283  assert(row < end_index);
1284  return array[row];
1285  }
1286  const ValType & at(IndType row) const
1287  {
1288  assert(row >= beg_index);
1289  assert(row < end_index);
1290  return array[row];
1291  }
1292  ValType & operator [](IndType row)
1293  {
1294  //std::cout << "pos: " << row << std::endl;
1295  /*
1296  if( row >= end_index )
1297  {
1298  IndType new_end_index = 1;
1299  IndType temp = row-beg_index;
1300  while( new_end_index <= temp ) new_end_index = new_end_index << 1;
1301  new_end_index += beg_index;
1302  //std::cout << "end: " << end_index << " new end: " << new_end_index << std::endl;
1303  array = static_cast<ValType *>(realloc(array,sizeof(ValType)*(new_end_index-beg_index)));
1304  IndType end = new_end_index-beg_index;
1305  for(IndType i = end_index-beg_index; i != end; ++i) new (array+i) ValType();
1306  end_index = new_end_index;
1307  }
1308  if( row >= last_index ) last_index = row+1;
1309  */
1310  assert(row >= beg_index );
1311  assert(row < end_index );
1312  return array[row];
1313  }
1314  const ValType & operator [](IndType row) const
1315  {
1316  assert(row >= beg_index );
1317  assert(row < end_index );
1318  return array[row];
1319  }
1320  void set_interval_beg(IndType beg)
1321  {
1322  IndType shift = beg-beg_index;
1323  shift_interval(shift);
1324  }
1325  void set_interval_end(IndType end)
1326  {
1327  if( end == end_index ) return;
1328  if( beg_index != end )
1329  {
1330  ValType * array_new = static_cast<ValType *>(malloc(sizeof(ValType)*(end-beg_index)));
1331  assert(array_new != NULL);
1332  array_new = array_new - beg_index;
1333  for(IndType i = beg_index; i < std::min(end,end_index); ++i) new (array_new+i) ValType(array[i]);
1334  for(IndType i = end_index; i < end; ++i) new (array_new+i) ValType();
1335  for(IndType i = beg_index; i < end_index; ++i) array[i].~ValType();
1336 
1337  if( array != NULL ) free(array+beg_index);
1338  array = array_new;
1339  }
1340  else
1341  {
1342  free(array+beg_index);
1343  array = NULL;
1344  }
1345  end_index = end;
1346  }
1347 
1348  void shift_interval(IndType shift)
1349  {
1350  array = array + beg_index;
1351  beg_index += shift;
1352  end_index += shift;
1353  array = array - beg_index;
1354  }
1355  iterator begin() {return array+beg_index;}
1356  const_iterator begin() const {return array+beg_index;}
1357  //const_iterator begin() {return array;}
1358  iterator end() {return array + end_index;}
1359  const_iterator end() const {return array + end_index;}
1360  //const_iterator end() {return array + (end_index-end_index);}
1361  IndType get_interval_beg() const { return beg_index; }
1362  IndType get_interval_end() const { return end_index; }
1363  int size() const {return end_index - beg_index;}
1364  bool empty() const {return beg_index == end_index;}
1365  };
1366 
1367  //this version is safe for std::map
1368  /*
1369  template<typename IndType,typename ValType>
1370  class interval
1371  {
1372  public:
1373  typedef ValType * iterator;
1374  typedef ValType const * const_iterator;
1375  private:
1376  ValType * array;
1377  IndType beg_index, end_index, last_index;
1378  public:
1379  interval()
1380  {
1381  beg_index = 0;
1382  last_index = beg_index;
1383  end_index = 0;
1384  array = NULL;
1385  }
1386  interval(IndType beg)
1387  {
1388  beg_index = beg;
1389  last_index = beg_index;
1390  end_index = beg_index;
1391  array = NULL;
1392  }
1393  interval(IndType beg, IndType end)
1394  {
1395  beg_index = beg;
1396  last_index = end;
1397  end_index = end;
1398  if( end_index-beg_index > 0 )
1399  {
1400  array = static_cast<ValType *>(malloc(sizeof(ValType)*(end_index-beg_index)));
1401  assert(array != NULL);
1402  IndType cycle_end = end_index-beg_index;
1403  for(IndType i = 0; i != cycle_end; ++i) new (array+i) ValType();
1404  }
1405  else array = NULL;
1406  }
1407  interval(const interval & other)
1408  {
1409  beg_index = other.beg_index;
1410  last_index = other.last_index;
1411  end_index = other.end_index;
1412  array = static_cast<ValType *>(malloc(sizeof(ValType)*(end_index-beg_index)));
1413  assert(array != NULL);
1414  IndType end = end_index-beg_index;
1415  for(IndType i = 0; i != end; ++i)
1416  {
1417  //std::cout << this << " " << __FILE__ << ":" << __LINE__ << " call constructor " << i << " obj " << array+i << std::endl;
1418  new (array+i) ValType(other.array[i]);
1419  }
1420  }
1421  ~interval()
1422  {
1423  //for(iterator i = begin(); i != end(); ++i) (*i).~ValType();
1424  for(IndType i = 0; i < end_index-beg_index; i++) (array[i]).~ValType();
1425  free(array);
1426  }
1427  interval & operator =(interval const & other)
1428  {
1429  if( &other != this )
1430  {
1431  for(iterator i = begin(); i != end(); ++i) (*i).~ValType();
1432  beg_index = other.beg_index;
1433  last_index = other.last_index;
1434  end_index = other.end_index;
1435  array = static_cast<ValType *>(realloc(array,sizeof(ValType)*(end_index-beg_index)));
1436  assert(array != NULL);
1437  IndType end = end_index-beg_index;
1438  for(IndType i = 0; i != end; ++i)
1439  {
1440  //std::cout << this << " " << __FILE__ << ":" << __LINE__ << " call constructor " << i << " obj " << array+i << std::endl;
1441  new (array+i) ValType(other.array[i]);
1442  }
1443  }
1444  return *this;
1445  }
1446  ValType & operator [](IndType row)
1447  {
1448  //std::cout << "pos: " << row << std::endl;
1449  if( row >= end_index )
1450  {
1451  IndType new_end_index = 1;
1452  IndType temp = row-beg_index;
1453  while( new_end_index <= temp ) new_end_index = new_end_index << 1;
1454  new_end_index += beg_index;
1455  ValType * array_new = static_cast<ValType *>(malloc(sizeof(ValType)*(new_end_index-beg_index)));
1456  assert(array_new != NULL);
1457  for(IndType i = 0; i != end_index-beg_index; ++i)
1458  {
1459  new (array_new+i) ValType(*(array+i));
1460  (*(array+i)).~ValType();
1461  }
1462  IndType end = new_end_index-beg_index;
1463  for(IndType i = end_index-beg_index; i != end; ++i)
1464  {
1465  //std::cout << this << " " << __FILE__ << ":" << __LINE__ << " call constructor " << i << " obj " << array+i << std::endl;
1466  new (array_new+i) ValType();
1467  }
1468  end_index = new_end_index;
1469  free(array);
1470  array = array_new;
1471  }
1472  if( row >= last_index ) last_index = row+1;
1473  return array[row-beg_index];
1474  }
1475  const ValType & operator [](IndType row) const
1476  {
1477  assert(row >= beg_index );
1478  assert(row < end_index );
1479  return array[row-beg_index];
1480  }
1481  bool empty() const {return beg_index == last_index;}
1482  void set_interval_beg(IndType beg)
1483  {
1484  IndType shift = beg-beg_index;
1485  shift_interval(shift);
1486  }
1487  void set_interval_end(IndType end)
1488  {
1489 
1490  if( end > end_index )
1491  {
1492  ValType * array_new = static_cast<ValType *>(malloc(sizeof(ValType)*(end-beg_index)));
1493  assert(array_new != NULL);
1494  IndType cycle_end = end_index-beg_index;
1495  for(IndType i = 0; i != cycle_end; ++i)
1496  {
1497  new (array_new+i) ValType(*(array+i));
1498  (*(array+i)).~ValType();
1499  }
1500  cycle_end = end-beg_index;
1501  for(IndType i = end_index-beg_index; i != cycle_end; ++i)
1502  {
1503  //std::cout << this << " " << __FILE__ << ":" << __LINE__ << " call constructor " << i << " obj " << array+i << std::endl;
1504  new (array_new+i) ValType();
1505  }
1506  end_index = end;
1507  free(array);
1508  array = array_new;
1509  }
1510  last_index = end;
1511  }
1512 
1513  void shift_interval(IndType shift)
1514  {
1515  beg_index += shift;
1516  end_index += shift;
1517  last_index += shift;
1518  }
1519  iterator begin() {return array;}
1520  const_iterator begin() const {return array;}
1521  iterator end() {return array + (last_index-beg_index);}
1522 
1523  const_iterator end() const {return array + (last_index-beg_index);}
1524  IndType get_interval_beg() const { return beg_index; }
1525  IndType get_interval_end() const { return last_index; }
1526  int size() const {return last_index - beg_index;}
1527  };
1528  */
1529  template<typename element, unsigned int stacked>
1530  class dynarray
1531  {
1532  public:
1533  typedef size_t size_type;
1534  template<typename dtype>
1536  {
1537  private:
1538  dtype * e;
1539  public:
1540  typedef dtype * pointer;
1541  typedef dtype & reference;
1542  typedef dtype value_type;
1544  typedef std::random_access_iterator_tag iterator_category;
1545  _iterator():e(NULL){}
1546  _iterator(dtype * i):e(i){}
1547  _iterator(const _iterator & other){e = other.e;}
1550  _iterator & operator -=(size_type n) { e-=n; return *this; }
1552  _iterator & operator +=(size_type n) { e+=n; return *this; }
1553  _iterator & operator ++(){ ++e; return *this;}
1554  _iterator operator ++(int){ return _iterator(e++); }
1555  _iterator & operator --(){ --e; return *this; }
1556  _iterator operator --(int){ return _iterator(e--); }
1557  size_type operator -(const _iterator & other) const {return static_cast<size_type>(e-other.e);}
1558  dtype & operator *() { return *e; }
1559  dtype * operator ->() { return e; }
1560  _iterator & operator =(_iterator const & other) { e = other.e; return *this; }
1561  bool operator ==(const _iterator & other) { return e == other.e;}
1562  bool operator !=(const _iterator & other) { return e != other.e;}
1563  bool operator <(const _iterator & other) { return e < other.e;}
1564  bool operator >(const _iterator & other) { return e > other.e;}
1565  bool operator <=(const _iterator & other) { return e <= other.e;}
1566  bool operator >=(const _iterator & other) { return e >= other.e;}
1567  operator void *() {return static_cast<void *> (e);}
1568  void * cast_to_void(){return static_cast<void *>(e);}
1569  };
1570  typedef _iterator<element> iterator;
1571  typedef _iterator<const element> const_iterator;
1572  template<typename dtype>
1574  {
1575  private:
1576  dtype * e;
1577  public:
1578  typedef dtype * pointer;
1579  typedef dtype & reference;
1580  typedef dtype value_type;
1582  typedef std::random_access_iterator_tag iterator_category;
1583  _reverse_iterator():e(NULL){}
1584  _reverse_iterator(dtype * i):e(i){}
1585  _reverse_iterator(const _reverse_iterator & other){e = other.e;}
1588  _reverse_iterator & operator -=(size_type n) { e+=n; return *this; }
1590  _reverse_iterator & operator +=(size_type n) { e-=n; return *this; }
1591  _reverse_iterator & operator ++(){ --e; return *this;}
1593  _reverse_iterator & operator --(){ ++e; return *this; }
1595  size_type operator -(const _reverse_iterator & other) const {return static_cast<size_type>(other.e-e);}
1596  dtype & operator *() { return *e; }
1597  dtype * operator ->() { return e; }
1598  _reverse_iterator & operator =(_reverse_iterator const & other) { e = other.e; return *this;}
1599  bool operator ==(const _reverse_iterator & other) { return e == other.e;}
1600  bool operator !=(const _reverse_iterator & other) { return e != other.e;}
1601  bool operator <(const _reverse_iterator & other) { return e < other.e;}
1602  bool operator >(const _reverse_iterator & other) { return e > other.e;}
1603  bool operator <=(const _reverse_iterator & other) { return e <= other.e;}
1604  bool operator >=(const _reverse_iterator & other) { return e >= other.e;}
1605  operator void *() {return static_cast<void *> (e);}
1606  void * cast_to_void(){return static_cast<void *>(e);}
1607  };
1608  typedef _reverse_iterator<element> reverse_iterator;
1609  typedef _reverse_iterator<const element> const_reverse_iterator;
1610  private:
1611  element stack[stacked];
1612  element * pbegin;
1613  element * pend;
1614  element * preserved;
1615  void preallocate(size_type n)
1616  {
1617  if( n <= static_cast<size_type>(stacked) )
1618  {
1619  pbegin = stack;
1620  pend = pbegin + n;
1621  preserved = stack+static_cast<size_type>(stacked);
1622  }
1623  else
1624  {
1625  pbegin = static_cast<element *>(malloc(sizeof(element)*n));
1626  assert(pbegin != NULL);
1627  pend = pbegin+n;
1628  preserved = pbegin+n;
1629  }
1630  }
1631  public:
1632  __INLINE element * data() {return pbegin;}
1633  __INLINE const element * data() const {return pbegin;}
1635  {
1636  std::cout << "stack: " << &stack << std::endl;
1637  std::cout << "pbegin: " << pbegin << std::endl;
1638  std::cout << "pend: " << pend << std::endl;
1639  std::cout << "preserved: " << preserved << std::endl;
1640  std::cout << "size: " << pend-pbegin << std::endl;
1641  std::cout << "reserved: " << preserved-pbegin << std::endl;
1642  }
1644  {
1645  //std::cout << n << std::endl;
1646  size_type k = size();
1647  if( n > static_cast<size_type>(stacked) )
1648  {
1649  for(size_type i = n; i < k; i++) pbegin[i].~element();
1650  if( pbegin == stack )
1651  {
1652  pbegin = static_cast<element *>(malloc(sizeof(element)*n));
1653  assert(pbegin != NULL);
1654  for(size_type i = 0; i < k; i++)
1655  {
1656  new (pbegin+i) element(stack[i]);
1657  stack[i].~element();
1658  }
1659  }
1660  else
1661  {
1662  element * pbegin_new = static_cast<element *>(malloc(sizeof(element)*n));
1663  assert(pbegin_new != NULL);
1664  for(size_type i = 0; i < k; i++)
1665  {
1666  new (pbegin_new+i) element(pbegin[i]);
1667  pbegin[i].~element();
1668  }
1669  free(pbegin);
1670  pbegin = pbegin_new;
1671  }
1672  pend = pbegin+ (k < n ? k : n);
1673  preserved = pbegin + n;
1674  }
1675  /*
1676  else if( pbegin != stack )
1677  {
1678  memcpy(stack,pbegin,sizeof(element)*n);
1679  for(size_type i = n; i < k; i++) pbegin[i].~element();
1680  free(pbegin);
1681  pbegin = stack;
1682  pend = stack+n;
1683  preserved = stack+static_cast<size_type>(stacked);
1684  }
1685  */
1686  }
1688  {
1689  pbegin = pend = stack;
1690  preserved = stack+static_cast<size_type>(stacked);
1691  }
1692  dynarray(size_type n,element c = element())
1693  {
1694  preallocate(n);
1695  for(element * i = pbegin; i < pend; i++) new (i) element(c);
1696  }
1697  template<class InputIterator>
1698  dynarray(InputIterator first, InputIterator last)
1699  {
1700  size_type n = static_cast<size_type>(std::distance(first,last));
1701  preallocate(n);
1702  {
1703  InputIterator it = first;
1704  element * i = pbegin;
1705  while(it != last) {new (i++) element(*(it++));}
1706  }
1707  }
1708  dynarray(const dynarray & other)
1709  {
1710  //std::cout << __FUNCTION__ << std::endl;
1711  size_type n = other.size();
1712  preallocate(n);
1713  for(size_type k = 0; k < n; k++)
1714  new (pbegin+k) element(other.pbegin[k]);
1715  }
1716 
1718  {
1719  for(element * i = pbegin; i < pend; i++) (*i).~element();
1720  if( pbegin != stack ) free(pbegin);
1721  }
1722  dynarray & operator =(dynarray const & other)
1723  {
1724  if( this != &other )
1725  {
1726  size_type n = size();
1727  for(element * i = pbegin; i != pend; ++i) (*i).~element();
1728  if(pbegin != stack) free(pbegin);
1729  n = other.size();
1730  preallocate(n);
1731  for(size_type k = 0; k < n; k++)
1732  new (pbegin+k) element(other.pbegin[k]);
1733  }
1734  return *this;
1735  }
1736  __INLINE const element & operator [] (size_type n) const
1737  {
1738  assert(pbegin+n < pend);
1739  return pbegin[n];
1740  }
1742  {
1743  assert(pbegin+n < pend);
1744  return pbegin[n];
1745  }
1746  __INLINE const element & at (size_type n) const
1747  {
1748  assert(pbegin+n < pend);
1749  return pbegin[n];
1750  }
1751  __INLINE element & at (size_type n)
1752  {
1753  assert(pbegin+n < pend);
1754  return pbegin[n];
1755  }
1756 
1757  void push_back(const element & e)
1758  {
1759  if( pend == preserved ) reserve(capacity()*2);
1760  new (pend++) element(e);
1761  }
1762  void pop_back()
1763  {
1764  (*(pend--)).~element();
1765  }
1766  __INLINE element & back() {return *(pend-1);}
1767  __INLINE const element & back() const {return *(pend-1);}
1768  __INLINE element & front() {return *pbegin;}
1769  __INLINE const element & front() const {return *pbegin;}
1770  __INLINE size_type capacity() { return static_cast<size_type>(preserved-pbegin); }
1771  __INLINE bool empty() const { return pend==pbegin; }
1772  void resize(size_type n, element c = element() )
1773  {
1774  size_type oldsize = size();
1775  while( capacity() < n ) reserve(capacity()*2);
1776  for(element * i = pbegin+n; i < pbegin+oldsize; i++) (*i).~element(); //delete elements, located over the size
1777  for(element * i = pbegin+oldsize; i < pbegin+n; i++) new (i) element(c); //initialize extra entities
1778  pend = pbegin + n;
1779  }
1780  __INLINE size_type size() const {return static_cast<size_type>(pend-pbegin);}
1781  void clear()
1782  {
1783  for(element * i = pbegin; i < pend; i++) (*i).~element();
1784  pend = pbegin;
1785  //pbegin = pend = stack;
1786  //preserved = stack+static_cast<size_type>(stacked);
1787  }
1789  {
1790  size_type k = size(), n = other.size();
1791  if( n > static_cast<size_type>(stacked) ) free(other.pbegin);
1792  if( k > static_cast<size_type>(stacked) )
1793  {
1794  other.pbegin = pbegin;
1795  other.pend = pend;
1796  other.preserved = preserved;
1797  }
1798  else
1799  {
1800  memcpy(other.stack,stack,sizeof(element)*k);
1801  other.pbegin = other.stack;
1802  other.pend = other.stack+k;
1803  other.preserved = other.stack+static_cast<size_type>(stacked);
1804  }
1805  pbegin = pend = stack;
1806  preserved = stack+static_cast<size_type>(stacked);
1807  }
1809  {
1810  size_type k = size(), n = other.size();
1811  if( k <= static_cast<size_type>(stacked) && n <= static_cast<size_type>(stacked) )
1812  {
1813  char temp[stacked*sizeof(element)];
1814  memcpy(temp,stack,sizeof(element)*k);
1815  memcpy(stack,other.stack,sizeof(element)*n);
1816  memcpy(other.stack,temp,sizeof(element)*k);
1817  other.pend = other.pbegin+k;
1818  pend = pbegin+n;
1819  }
1820  else if( k <= static_cast<size_type>(stacked) && n > static_cast<size_type>(stacked) )
1821  {
1822  memcpy(other.stack,stack,sizeof(element)*k);
1823  pbegin = other.pbegin;
1824  pend = other.pend;
1825  preserved = other.preserved;
1826  other.pbegin = other.stack;
1827  other.pend = other.stack+k;
1828  other.preserved = other.stack+static_cast<size_type>(stacked);
1829  }
1830  else if( k > static_cast<size_type>(stacked) && n <= static_cast<size_type>(stacked) )
1831  {
1832  memcpy(stack,other.stack,sizeof(element)*n);
1833  other.pbegin = pbegin;
1834  other.pend = pend;
1835  other.preserved = preserved;
1836  pbegin = stack;
1837  pend = stack+n;
1838  preserved = stack+static_cast<size_type>(stacked);
1839  }
1840  else
1841  {
1842  element * temp;
1843  temp = pbegin;
1844  pbegin = other.pbegin;
1845  other.pbegin = temp;
1846  temp = pend;
1847  pend = other.pend;
1848  other.pend = temp;
1849  temp = preserved;
1850  preserved = other.preserved;
1851  other.preserved = temp;
1852  }
1853  }
1854  __INLINE iterator begin() { return pbegin; }
1855  __INLINE iterator end() { return pend; }
1856  __INLINE const_iterator begin() const { return pbegin; }
1857  __INLINE const_iterator end() const { return pend; }
1863  {
1864  ptrdiff_t d = pos-begin();
1865  ptrdiff_t s = (end()-pos)-1;
1866  (*pos).~element();
1867  if( s > 0 ) memmove(pbegin+d,pbegin+d+1,sizeof(element)*s);
1868  pend--;
1869  return pbegin+d;
1870  }
1872  {
1873  ptrdiff_t d = b-iterator(pbegin);
1874  ptrdiff_t s = iterator(pend)-e;
1875  ptrdiff_t n = e-b;
1876  for(iterator i = b; i != e; i++) (*i).~element();
1877  if( s > 0 ) memmove(pbegin+d,pbegin+d+1,sizeof(element)*s);
1878  pend -= n;
1879  return pbegin+d;
1880  }
1881  iterator insert(iterator pos, const element & x)
1882  {
1883  ptrdiff_t d = pos-iterator(pbegin);
1884  ptrdiff_t s = iterator(pend)-pos;
1885  if( pend == preserved ) reserve(capacity()*2);
1886  pend++;
1887  if( s > 0 ) memmove(pbegin+d+1,pbegin+d,sizeof(element)*s);
1888  new (pbegin+d) element(x);
1889  return pbegin+d;
1890  }
1891  void insert(iterator pos, size_type n, const element & x)
1892  {
1893  ptrdiff_t d = pos-iterator(pbegin);
1894  ptrdiff_t s = iterator(pend)-pos;
1895  while( capacity()-size() < n ) reserve(capacity()*2);
1896  if( s > 0 ) memmove(pbegin+d+n,pbegin+d,sizeof(element)*s);
1897  pend+=n;
1898  for(size_type i = 0; i < n; i++) new (pbegin+d+i) element(x);
1899  }
1900  template <class InputIterator>
1901  void insert(iterator pos, InputIterator first, InputIterator last)
1902  {
1903  ptrdiff_t n = static_cast<ptrdiff_t>(std::distance(first,last));
1904  ptrdiff_t d = pos-iterator(pbegin);
1905  ptrdiff_t s = iterator(pend)-pos;
1906  while( capacity() < size()+n ) reserve(capacity()*2);
1907  if( s > 0 ) memmove(pbegin+d+n,pbegin+d,sizeof(element)*s);
1908  {
1909  InputIterator it = first;
1910  element * i = pbegin+d;
1911  while(it != last) new (i++) element(*it++);
1912  }
1913  pend+=n;
1914  }
1915  };
1916 
1917  template<class key,class value, unsigned int stacked>
1918  class tiny_map
1919  {
1920  public:
1923  private:
1924  container inner_data;
1925  public:
1927  {
1928  public:
1930  iterator( const typename container::iterator & other) :container::iterator(other) {}
1931  };
1933  {
1934  public:
1937  };
1938  tiny_map() :inner_data() {}
1939  tiny_map(const tiny_map & other) :inner_data(other.inner_data) {}
1940  tiny_map & operator = (tiny_map const & other) {inner_data = other.inner_data; return *this;}
1942  const_iterator find(const key & x) const
1943  {
1944  for(const_iterator it = inner_data.begin(); it != inner_data.end(); ++it)
1945  if( it->first == x ) return it;
1946  return end();
1947  }
1948  iterator find(const key & x)
1949  {
1950  for(iterator it = inner_data.begin(); it != inner_data.end(); ++it)
1951  if( it->first == x ) return it;
1952  return end();
1953  }
1954  iterator begin() {return inner_data.begin();}
1955  iterator end() {return inner_data.end();}
1956  const_iterator begin() const {return inner_data.begin();}
1957  const_iterator end() const {return inner_data.end();}
1958  value & operator [](const key & x)
1959  {
1960  for(typename container::iterator it = inner_data.begin(); it != inner_data.end(); ++it)
1961  if( it->first == x ) return it->second;
1962  inner_data.push_back(std::pair<key,value>(x,value()));
1963  return inner_data.back().second;
1964  }
1965  size_type size() {return inner_data.size();}
1966  void clear() {inner_data.clear();}
1967  bool empty() const {return inner_data.empty();}
1968  iterator erase(iterator pos) {return inner_data.erase(typename container::iterator(pos));}
1969 
1970  };
1971 
1972 
1973  template<typename IndType, typename TValue, int HSize>
1975  {
1976  private:
1978  typedef typename inner_class::pair_t inner_type;
1979  typedef typename inner_class::iterator inner_iter;
1980  typedef inner_class inner_class_array[HSize];
1981  //typedef typename inner_class::reverse_iterator reverse_inner_iter;
1982  inner_class_array lists;
1983  IndType compute_pos(IndType key) {return (key*15637)%HSize;}
1984  public:
1985  template<typename dtype>
1987  {
1988  private:
1989  inner_class_array *lists;
1990  int cur_list;
1991  inner_iter it;
1992  public:
1993  typedef dtype * pointer;
1994  typedef dtype & reference;
1995  typedef dtype value_type;
1996  typedef ptrdiff_t difference_type;
1997  typedef std::bidirectional_iterator_tag iterator_category;
1998  _iterator(int cur_list, inner_iter it, inner_class_array * lists) :cur_list(cur_list), it(it), lists(lists) {}
1999  _iterator():cur_list(-1),it(NULL), lists(NULL){}
2000  _iterator(const _iterator & other){it = other.it; cur_list = other.cur_list; lists = other.lists;}
2003  {
2004  ++it;
2005  if(it == (*lists)[cur_list].end() )
2006  {
2007  do
2008  {
2009  ++cur_list;
2010  } while ((*lists)[cur_list].empty() && cur_list < HSize);
2011  if( cur_list < HSize )
2012  it = (*lists)[cur_list].begin();
2013  else
2014  it = NULL;
2015  }
2016  return *this;
2017  }
2018  _iterator operator ++(int){ _iterator ret = *this; ++(*this); return ret;}
2020  {
2021  --it;
2022  if(it == (*lists)[cur_list].begin()-1 )
2023  {
2024  do
2025  {
2026  --cur_list;
2027  } while((*lists)[cur_list].empty() && cur_list >= 0 );
2028  if( cur_list >= 0 )
2029  it = (*lists)[cur_list].end()-1;
2030  else
2031  it = NULL;
2032  }
2033  return *this;
2034  }
2035  _iterator operator --(int){ _iterator ret = *this; --(*this); return ret; }
2036  dtype & operator *() { return *it; }
2037  dtype * operator ->() { return &*it; }
2038  _iterator & operator =(_iterator const & other) {it = other.it; cur_list = other.cur_list; lists = other.lists; return *this; }
2039  bool operator ==(const _iterator & other) { return it == other.it;}
2040  bool operator !=(const _iterator & other) { return it != other.it;}
2041  bool operator <(const _iterator & other) { return it < other.it;}
2042  bool operator >(const _iterator & other) { return it > other.it;}
2043  bool operator <=(const _iterator & other) { return it <= other.it;}
2044  bool operator >=(const _iterator & other) { return it >= other.it;}
2045  };
2049  {
2050  int i = 0;
2051  while(lists[i].empty() && i < HSize) i++;
2052  return iterator(i,i < HSize ? lists[i].begin() : NULL,&lists);
2053  }
2054  iterator end() {return iterator(HSize,NULL,&lists);}
2055  /*
2056  template<typename dtype>
2057  class _reverse_iterator
2058  {
2059  private:
2060  inner_class_array * lists;
2061  int cur_list;
2062  inner_iter it;
2063  public:
2064  typedef dtype * pointer;
2065  typedef dtype & reference;
2066  typedef dtype value_type;
2067  typedef ptrdiff_t difference_type;
2068  typedef std::bidirectional_iterator_tag iterator_category;
2069  _reverse_iterator(int cur_list, inner_iter it, inner_class_array * lists) :cur_list(cur_list), it(it), lists(lists) {}
2070  _reverse_iterator():cur_list(-1),it(NULL), lists(NULL){}
2071  _reverse_iterator(const _reverse_iterator & other){it = other.it; cur_list = other.cur_list; lists = other.lists;}
2072  ~_reverse_iterator() {};
2073  _reverse_iterator & operator ++(){ ++it; if(it == (*lists)[cur_list]->rend() ) {--cur_list; if( cur_list >= 0 ) it = (*lists)[cur_list]->rbegin(); else it = NULL;} return *this;}
2074  _reverse_iterator operator ++(int){ _iterator ret = *this; ++(*this); return ret; }
2075  _reverse_iterator & operator --(){ --it; if(it == (*lists)[cur_list]->rbegin()-1 ) {++cur_list; if( cur_list < HSize ) it = (*lists)[cur_list]->rend()-1; else it = NULL;} return *this; }
2076  _reverse_iterator operator --(int){ _iterator ret = *this; --(*this); return ret; }
2077  dtype & operator *() { return *it; }
2078  dtype * operator ->() { return &*it; }
2079  _reverse_iterator & operator =(_reverse_iterator const & other) {it = other.it; return *this;}
2080  bool operator ==(const _reverse_iterator & other) { return it == other.it;}
2081  bool operator !=(const _reverse_iterator & other) { return it != other.it;}
2082  bool operator <(const _reverse_iterator & other) { return it < other.it;}
2083  bool operator >(const _reverse_iterator & other) { return it > other.it;}
2084  bool operator <=(const _reverse_iterator & other) { return it <= other.it;}
2085  bool operator >=(const _reverse_iterator & other) { return it >= other.it;}
2086  };
2087  typedef _reverse_iterator<inner_type> reverse_iterator;
2088  typedef _reverse_iterator<const inner_type> const_reverse_iterator;
2089  */
2090  public:
2091  TValue & operator [] (IndType key)
2092  {
2093  IndType pos = compute_pos(key);
2094  return lists[pos][key];
2095  }
2096  bool is_present(IndType key)
2097  {
2098  IndType pos = compute_pos(key);
2099  return lists[pos].find(key) != lists[pos].end();
2100  }
2101  IndType size()
2102  {
2103  IndType ret = 0;
2104  for(IndType i = 0; i < HSize; i++) ret += lists[i].size();
2105  return ret;
2106  }
2107  std::vector< std::pair<IndType, TValue> > serialize()
2108  {
2109  std::vector< std::pair<IndType, TValue> > ret;
2110  ret.resize(size());
2111  IndType q = 0;
2112  for(IndType i = 0; i < HSize; i++)
2113  {
2114  inner_iter it;
2115  for(it = lists[i].begin(); it != lists[i].end(); ++it)
2116  ret[q++] = std::make_pair(it->first,it->second);
2117  }
2118  return ret;
2119  }
2120  void clear()
2121  {
2122  for(IndType i = 0; i < HSize; i++) lists[i].clear();
2123  }
2124  };
2125 
2126 
2127 
2128  template<typename element, int block_bits>
2130  {
2131  public:
2132  typedef size_t size_type; //need signed type for reverse iterator? (reverse iterators commented)
2133  typedef make_unsigned<size_type>::type uenum; //this is required for right bit shifts not to create leading 1s
2134  private:
2135  static size_type const block_bits_mask = (1 << (block_bits)) - 1;
2136  static size_type const block_val = 1 << block_bits;
2137  static size_type const block_size = sizeof(element)*block_val;
2138  static size_type const fwd_alloc_chunk_bits = 6;
2139  static size_type const fwd_alloc_chunk_bits_mask = (1 << (fwd_alloc_chunk_bits))-1;
2140  static size_type const fwd_alloc_chunk_val = 1 << fwd_alloc_chunk_bits;
2141  static size_type const fwd_alloc_chunk_size = sizeof(element *)*fwd_alloc_chunk_val;
2142  element ** chunks;
2143  size_type m_size;
2144  //This neads static_cast to unsigned to
2145  __INLINE size_type GetChunkNumber(size_type k) const {return static_cast<uenum>(k) >> block_bits;}
2146  __INLINE size_type GetElementNumber(size_type k) const {return (k & block_bits_mask);}
2147  __INLINE element * access_block(size_type k) {return chunks[GetChunkNumber(k)];}
2148  __INLINE const element * access_block(size_type k) const {return chunks[GetChunkNumber(k)];}
2149  __INLINE element & access_element(size_type k) {return access_block(k)[GetElementNumber(k)];}
2150  __INLINE const element & access_element(size_type k) const {return access_block(k)[GetElementNumber(k)];}
2151  public:
2153  {
2154  assert(i < size());
2155  return access_element(i);
2156  }
2157  __INLINE const element & operator [] (size_type i) const
2158  {
2159  assert(i < size());
2160  return access_element(i);
2161  }
2162  __INLINE element & at(size_type i)
2163  {
2164  assert(i < size());
2165  return access_element(i);
2166  }
2167  __INLINE const element & at(size_type i) const
2168  {
2169  assert(i < size());
2170  return access_element(i);
2171  }
2172 
2173 
2174 
2175 
2176  class iterator
2177  {
2178  private:
2180  size_type pos;
2181  public:
2182  typedef element * pointer;
2183  typedef element & reference;
2184  typedef element value_type;
2185  typedef ptrdiff_t difference_type;
2186  typedef std::random_access_iterator_tag iterator_category;
2187  iterator(){pos = 0; link = NULL;}
2189  iterator(const iterator & other){link = other.link; pos = other.pos;}
2191  iterator operator -(size_type n) { return iterator(link,pos-n); }
2192  iterator & operator -=(size_type n) { pos-=n; return *this; }
2193  iterator operator +(size_type n) { return iterator(link,pos+n); }
2194  iterator & operator +=(size_type n) { pos+=n; return *this; }
2195  iterator & operator ++(){ ++pos; return *this;}
2196  iterator operator ++(int){ return iterator(link,pos++); }
2197  iterator & operator --(){ --pos; return *this; }
2198  iterator operator --(int){ return iterator(link,pos--); }
2199  ptrdiff_t operator -(const iterator & other) const {return pos-other.pos;}
2200  element & operator *() { return link->at(pos); }
2201  element * operator ->() { return &link->at(pos); }
2202  iterator & operator =(iterator const & other) { link = other.link; pos = other.pos; return *this; }
2203  bool operator ==(const iterator & other) { assert(link == other.link); return pos == other.pos;}
2204  bool operator !=(const iterator & other) { assert(link == other.link); return pos != other.pos;}
2205  bool operator <(const iterator & other) { assert(link == other.link); return pos < other.pos;}
2206  bool operator >(const iterator & other) { assert(link == other.link); return pos > other.pos;}
2207  bool operator <=(const iterator & other) { assert(link == other.link); return pos <= other.pos;}
2208  bool operator >=(const iterator & other) { assert(link == other.link); return pos >= other.pos;}
2209  };
2210 
2212  {
2213  private:
2214  const chunk_array<element,block_bits> * const link;
2215  size_type pos;
2216  public:
2217  typedef element * pointer;
2218  typedef element & reference;
2219  typedef element value_type;
2220  typedef ptrdiff_t difference_type;
2221  typedef std::random_access_iterator_tag iterator_category;
2222  const_iterator(){pos = 0; link = NULL;}
2223  const_iterator(const chunk_array<element,block_bits> * c, size_type pos):link(c),pos(pos){}
2224  const_iterator(const const_iterator & other) :link(other.link) {pos = other.pos;}
2227  const_iterator & operator -=(size_type n) { pos-=n; return *this; }
2229  const_iterator & operator +=(size_type n) { pos+=n; return *this; }
2230  const_iterator & operator ++(){ ++pos; return *this;}
2231  const_iterator operator ++(int){ return const_iterator(link,pos++); }
2232  const_iterator & operator --(){ --pos; return *this; }
2233  const_iterator operator --(int){ return const_iterator(link,pos--); }
2234  ptrdiff_t operator -(const const_iterator & other) const {return pos-other.pos;}
2235  const element & operator *() { return link->at(pos); }
2236  const element * operator ->() { return &link->at(pos); }
2237  const_iterator & operator =(const_iterator const & other) { link = other.link; pos = other.pos; return *this; }
2238  bool operator ==(const const_iterator & other) { assert(link == other.link); return pos == other.pos;}
2239  bool operator !=(const const_iterator & other) { assert(link == other.link); return pos != other.pos;}
2240  bool operator <(const const_iterator & other) { assert(link == other.link); return pos < other.pos;}
2241  bool operator >(const const_iterator & other) { assert(link == other.link); return pos > other.pos;}
2242  bool operator <=(const const_iterator & other) { assert(link == other.link); return pos <= other.pos;}
2243  bool operator >=(const const_iterator & other) { assert(link == other.link); return pos >= other.pos;}
2244  };
2245 
2246  void inner_resize(size_type new_size)
2247  {
2248  //~ size_type oldnchunks = m_size /chunk;
2249  size_type oldnchunks2 = (static_cast<uenum>(m_size) >> block_bits) + ( (m_size & block_bits_mask) ? 1 : 0);
2250  size_type oldn = (static_cast<uenum>(oldnchunks2) >> fwd_alloc_chunk_bits) + ( (oldnchunks2 & fwd_alloc_chunk_bits_mask) ? 1 : 0);
2251  //~ size_type newnchunks = new_size/chunk;
2252  size_type newnchunks2 = (static_cast<uenum>(new_size) >> block_bits) + ( (new_size & block_bits_mask)? 1 : 0);
2253  size_type newn = (static_cast<uenum>(newnchunks2) >> fwd_alloc_chunk_bits) + ( (newnchunks2 & fwd_alloc_chunk_bits_mask) ? 1 : 0);
2254 
2255  //~ std::cout << "new " << new_size << " " << newn << " " << newnchunks2 << " old " << m_size << " " << oldn << " " << oldnchunks2 << " block " << block << " chunk " << chunk << std::endl;
2256 
2257  for(size_type q = new_size; q < m_size; q++)
2258  access_element(q).~element();
2259  for(size_type q = newnchunks2; q < oldnchunks2; q++)
2260  {
2261  assert(chunks[q] != NULL);
2262  free(chunks[q]);
2263  chunks[q] = NULL;
2264  }
2265  if( newn != oldn )
2266  {
2267  if( newn > 0 )
2268  {
2269  chunks = (element **) realloc(chunks,fwd_alloc_chunk_size*newn);
2270  assert(chunks != NULL);
2271  if( newn > oldn ) memset(chunks+oldn*fwd_alloc_chunk_val,0,fwd_alloc_chunk_size*(newn-oldn));
2272  }
2273  else
2274  {
2275  free(chunks);
2276  chunks = NULL;
2277  }
2278  }
2279  for(size_type q = oldnchunks2; q < newnchunks2; q++)
2280  {
2281  assert(chunks[q] == NULL);
2282  chunks[q] = (element *)malloc(block_size);
2283  assert(chunks[q] != NULL);
2284  }
2285  //for(size_type q = m_size; q < new_size; q++) new (&access_element(q)) element();
2286  }
2287  public:
2288 
2290  {
2291  size_type chunks = ((static_cast<uenum>(m_size)>>block_bits) + ((m_size & block_bits_mask)? 1 : 0));
2292  return chunks*block_val;
2293  }
2294  size_type size() const {return m_size;}
2295  bool empty() const {return size() == 0;}
2296  void clear()
2297  {
2298  for(size_type q = 0; q < m_size; q++) access_element(q).~element();
2299  size_type cend = (static_cast<uenum>(m_size) >> block_bits) + ((m_size & block_bits_mask)? 1 : 0);
2300  for(size_type q = 0; q < cend; q++)
2301  {
2302  free(chunks[q]);
2303  chunks[q] = NULL;
2304  }
2305  free(chunks);
2306  chunks = NULL;
2307  m_size = 0;
2308  }
2310  {
2311  m_size = 0;
2312  chunks = NULL;
2313  }
2314  chunk_array(const chunk_array & other)
2315  {
2316  chunks = NULL;
2317  m_size = 0;
2318  inner_resize(other.size());
2319  for(size_type k = 0; k < other.size(); k++)
2320  new(&access_element(k)) element(other.access_element(k));
2321  m_size = other.size();
2322  }
2324  {
2325  if( this != &other )
2326  {
2327  clear();
2328  inner_resize(other.size());
2329  for(size_type k = 0; k < other.size(); k++)
2330  new(&access_element(k)) element(other.access_element(k));
2331  m_size = other.size();
2332  }
2333  return *this;
2334  }
2335  /*for future
2336  chunk_array & operator =(chunk_array && other)
2337  {
2338  if( this != &other )
2339  {
2340  clear();
2341  chunks = other.chunks;
2342  m_size = other.m_size;
2343  other.chunks = NULL;
2344  other.m_size = 0;
2345  }
2346  return *this;
2347  }
2348  */
2350  {
2351  clear();
2352  }
2353 
2354  element & front() { assert(!empty()); return access_element(0);}
2355  element & back() { assert(!empty()); return access_element(size()-1);}
2356  const element & front() const { assert(!empty()); return access_element(0);}
2357  const element & back() const { assert(!empty()); return access_element(size()-1);}
2358  void pop_back()
2359  {
2360  assert(!empty());
2361  //access_element(m_size-1).~element();
2362  inner_resize(m_size-1);
2363  m_size--;
2364  }
2365  void push_back(const element & e)
2366  {
2367  inner_resize(m_size+1);
2368  new (&access_element(m_size)) element(e);
2369  m_size++;
2370  }
2371  void resize(size_type n, const element & e = element())
2372  {
2373  inner_resize(n);
2374  for(size_type k = m_size; k < n; k++)
2375  new (&access_element(k)) element(e);
2376  m_size = n;
2377  }
2378 
2379  iterator erase(iterator pos)
2380  {
2381  //destruct current
2382  //(*pos).~element();
2383  iterator it = pos, jt = it++;
2384  while(it != end()) (*jt++) = (*it++);//std::move(*jt++);
2385  //destruct last
2386  //access_element(m_size-1).~element();
2387  inner_resize(m_size-1);
2388  m_size--;
2389  return pos;
2390  }
2391 
2392  iterator begin() {return iterator(this,0);}
2393  iterator end() {return iterator(this,m_size);}
2394  const_iterator begin() const {return const_iterator(this,0);}
2395  const_iterator end() const {return const_iterator(this,m_size);}
2396 
2397  //~ reverse_iterator rbegin() {return reverse_iterator(this,m_size-1);}
2398  //~ reverse_iterator rend() {return reverse_iterator(this,-1);}
2399  //~ const_reverse_iterator rbegin() const {return const_reverse_iterator(this,m_size-1);}
2400  //~ const_reverse_iterator rend() const {return const_reverse_iterator(this,-1);}
2401 
2402  //don't need other standard functions?
2403  };
2404 
2405 
2406  template<int block_bits>
2408  {
2409  public:
2410  typedef size_t size_type;
2411  typedef make_unsigned<size_type>::type uenum; //this is required for right shift not to create leading 1s
2412  private:
2413  static size_type const block_bits_mask = (1 << (block_bits)) - 1;
2414  static size_type const block_val = 1 << block_bits;
2415  static size_type const block_size = sizeof(char)*block_val;
2416  static size_type const fwd_alloc_chunk_bits = 6;
2417  static size_type const fwd_alloc_chunk_bits_mask = (1 << (fwd_alloc_chunk_bits))-1;
2418  static size_type const fwd_alloc_chunk_val = 1 << fwd_alloc_chunk_bits;
2419  static size_type const fwd_alloc_chunk_size = sizeof(char *)*fwd_alloc_chunk_val;
2420  char ** chunks;
2421  size_type record_size;
2422  size_type m_size;
2423 
2424  __INLINE size_type GetChunkNumber(size_type k) const {return static_cast<uenum>(k) >> block_bits;}
2425  __INLINE size_type GetElementNumber(size_type k) const {return (k & block_bits_mask) * record_size;}
2426  __INLINE char * access_block(size_type k) {return chunks[GetChunkNumber(k)];}
2427  __INLINE const char * access_block(size_type k) const {return chunks[GetChunkNumber(k)];}
2428  __INLINE char & access_element(size_type k) {return access_block(k)[GetElementNumber(k)];}
2429  __INLINE const char & access_element(size_type k) const {return access_block(k)[GetElementNumber(k)];}
2430  public:
2432  {
2433  assert(i < size());
2434  return access_element(i);
2435  }
2436  __INLINE const char & operator [] (size_type i) const
2437  {
2438  assert(i < size());
2439  return access_element(i);
2440  }
2441  __INLINE char & at(size_type i)
2442  {
2443  assert(i < size());
2444  return access_element(i);
2445  }
2446  __INLINE const char & at(size_type i) const
2447  {
2448  assert(i < size());
2449  return access_element(i);
2450  }
2451  void inner_resize(size_type new_size)
2452  {
2453  size_type oldnchunks2 = (static_cast<uenum>(m_size) >> block_bits) + ( (m_size & block_bits_mask) ? 1 : 0);
2454  size_type oldn = (static_cast<uenum>(oldnchunks2) >> fwd_alloc_chunk_bits) + ( (oldnchunks2 & fwd_alloc_chunk_bits_mask) ? 1 : 0);
2455  size_type newnchunks2 = (static_cast<uenum>(new_size) >> block_bits) + ( (new_size & block_bits_mask)? 1 : 0);
2456  size_type newn = (static_cast<uenum>(newnchunks2) >> fwd_alloc_chunk_bits) + ( (newnchunks2 & fwd_alloc_chunk_bits_mask) ? 1 : 0);
2457  for(size_type q = newnchunks2; q < oldnchunks2; q++)
2458  {
2459  assert(chunks[q] != NULL);
2460  free(chunks[q]);
2461  chunks[q] = NULL;
2462  }
2463  if( newn != oldn )
2464  {
2465  if( newn > 0 )
2466  {
2467  chunks = reinterpret_cast<char **>(realloc(chunks,fwd_alloc_chunk_size*newn));
2468  assert(chunks != NULL);
2469  if( newn > oldn ) memset(chunks+oldn*fwd_alloc_chunk_val,0,fwd_alloc_chunk_size*(newn-oldn));
2470  }
2471  else
2472  {
2473  free(chunks);
2474  chunks = NULL;
2475  }
2476  }
2477  for(size_type q = oldnchunks2; q < newnchunks2; q++)
2478  {
2479  assert(chunks[q] == NULL);
2480  chunks[q] = static_cast<char *>(malloc(block_size*record_size));
2481  memset(chunks[q],0,block_size*record_size);
2482  assert(chunks[q] != NULL);
2483  }
2484  }
2485  public:
2486 
2488  {
2489  size_type nchunks = ((static_cast<uenum>(m_size)>>block_bits) + ((m_size & block_bits_mask)? 1 : 0));
2490  return nchunks*block_val*record_size;
2491  }
2492  size_type size() const {return m_size;}
2493  bool empty() const {return size() == 0;}
2494  void clear()
2495  {
2496  size_type nchunks = ((static_cast<uenum>(m_size)>>block_bits) + ((m_size & block_bits_mask)? 1 : 0));
2497  for(size_type q = 0; q < nchunks; q++)
2498  {
2499  free(chunks[q]);
2500  chunks[q] = NULL;
2501  }
2502  free(chunks);
2503  chunks = NULL;
2504  m_size = 0;
2505  }
2506  chunk_bulk_array(size_type set_record_size = 1)
2507  {
2508  record_size = set_record_size;
2509  m_size = 0;
2510  chunks = NULL;
2511  }
2513  {
2514  chunks = NULL;
2515  record_size = other.record_size;
2516  m_size = 0;
2517  inner_resize(other.size());
2518  size_type nchunks = ((static_cast<uenum>(m_size)>>block_bits) + ((m_size & block_bits_mask)? 1 : 0));
2519  for(size_type k = 0; k < nchunks; k++) memcpy(chunks[k],other.chunks[k],block_size*record_size);
2520  m_size = other.size();
2521  }
2523  {
2524  if( this != &other )
2525  {
2526  clear();
2527  record_size = other.record_size;
2528  inner_resize(other.size());
2529  size_type nchunks = ((static_cast<uenum>(m_size)>>block_bits) + ((m_size & block_bits_mask)? 1 : 0));
2530  for(size_type k = 0; k < nchunks; k++) memcpy(chunks[k],other.chunks[k],block_size*record_size);
2531  m_size = other.size();
2532  }
2533  return *this;
2534  }
2537  {
2538  inner_resize(n);
2539  m_size = n;
2540  }
2541  };
2542 }
2543 
2544 #endif
__INLINE const element & front() const
Definition: container.hpp:304
bool operator<(const _iterator &other)
Definition: container.hpp:552
chunk_bulk_array(size_type set_record_size=1)
Definition: container.hpp:2506
__INLINE const element & operator[](size_type n) const
Definition: container.hpp:640
__INLINE iterator begin()
Definition: container.hpp:1854
const_iterator operator-(size_type n)
Definition: container.hpp:2226
const_iterator begin() const
Definition: container.hpp:1148
const_iterator begin() const
Definition: container.hpp:1356
iterator & operator+=(size_type n)
Definition: container.hpp:2194
_iterator operator-(size_t n)
Definition: container.hpp:78
iterator(const iterator &other)
Definition: container.hpp:2189
_reverse_iterator & operator-=(size_t n)
Definition: container.hpp:117
bool operator!=(const _iterator &other)
Definition: container.hpp:551
__INLINE const element & at(size_type n) const
Definition: container.hpp:650
void pop_back()
Definition: container.hpp:263
void set_interval_end(IndType end)
Definition: container.hpp:1325
bool operator>=(const iterator &other)
Definition: container.hpp:2208
__INLINE iterator end()
Definition: container.hpp:784
std::random_access_iterator_tag iterator_category
Definition: container.hpp:1544
__INLINE const element & back() const
Definition: container.hpp:1767
_reverse_iterator & operator+=(size_t n)
Definition: container.hpp:119
bool operator!=(const _iterator &other) const
Definition: container.hpp:91
__INLINE reverse_iterator rend()
Definition: container.hpp:353
__INLINE size_type capacity() const
Definition: container.hpp:331
void insert(iterator pos, InputIterator first, InputIterator last)
Definition: container.hpp:1901
struct INMOST::sparse_data::pair_t pair
_reverse_iterator(const _reverse_iterator &other)
Definition: container.hpp:573
const_iterator end() const
Definition: container.hpp:1957
__INLINE reverse_iterator rend()
Definition: container.hpp:788
bool operator>(const _iterator &other)
Definition: container.hpp:2042
iterator erase(iterator b, iterator e)
Definition: container.hpp:1871
dynarray< std::pair< key, value >, stacked >::size_type size_type
Definition: container.hpp:1922
bool operator!=(const const_iterator &other)
Definition: container.hpp:2239
__INLINE const_reverse_iterator rend() const
Definition: container.hpp:355
__INLINE element & front()
Definition: container.hpp:1768
bool operator!=(const _iterator &other)
Definition: container.hpp:1562
__INLINE reverse_iterator rbegin()
Definition: container.hpp:1858
void swap(shell< element > &other)
Definition: container.hpp:774
TValue & operator[](IndType key)
Definition: container.hpp:2091
_iterator & operator++()
Definition: container.hpp:542
std::random_access_iterator_tag iterator_category
Definition: container.hpp:1582
_reverse_iterator< element > reverse_iterator
Definition: container.hpp:1608
iterator begin()
Definition: container.hpp:1355
__INLINE const_reverse_iterator rbegin() const
Definition: container.hpp:1860
_iterator & operator--()
Definition: container.hpp:544
static const enumerate prealloc
Definition: container.hpp:963
_reverse_iterator & operator--()
Definition: container.hpp:122
interval & operator=(interval const &other)
Definition: container.hpp:1257
iterator insert(iterator pos, const IndType &x)
Definition: container.hpp:1044
const_iterator(const typename container::const_iterator &other)
Definition: container.hpp:1936
void resize(size_type n, element c=element())
Definition: container.hpp:746
__INLINE iterator end()
Definition: container.hpp:1855
iterator erase(iterator pos)
Definition: container.hpp:1968
void push_back(const pair &in)
Definition: container.hpp:1056
size_type size()
Definition: container.hpp:1965
__INLINE const element & front() const
Definition: container.hpp:1769
shell(element *link, size_type size)
Definition: container.hpp:613
array & operator=(array const &other)
Definition: container.hpp:225
_reverse_iterator & operator=(_reverse_iterator const &other)
Definition: container.hpp:586
sparse_data & operator=(sparse_data const &other)
Definition: container.hpp:1120
std::random_access_iterator_tag iterator_category
Definition: container.hpp:2186
tiny_map(const tiny_map &other)
Definition: container.hpp:1939
bool operator>=(const _iterator &other) const
Definition: container.hpp:95
__INLINE const_iterator begin() const
Definition: container.hpp:785
_iterator & operator++()
Definition: container.hpp:82
const ValType & at(IndType row) const
Definition: container.hpp:1286
__INLINE element & back()
Definition: container.hpp:286
__INLINE element & operator[](size_type i)
Definition: container.hpp:2152
unsigned size_type
Definition: container.hpp:61
bool operator>(const _iterator &other)
Definition: container.hpp:553
iterator insert(iterator pos, const element &x)
Definition: container.hpp:1881
void insert(iterator pos, size_type n, const element &x)
Definition: container.hpp:434
size_type size() const
Definition: container.hpp:2294
bool operator<=(const _iterator &other)
Definition: container.hpp:1565
_iterator< inner_type > iterator
Definition: container.hpp:2046
iterator lower_bound(IndType ind)
Definition: container.hpp:1018
__INLINE const element * data() const
Definition: container.hpp:605
tiny_map & operator=(tiny_map const &other)
Definition: container.hpp:1940
void reserve(enumerate size)
Definition: container.hpp:1008
_reverse_iterator & operator=(_reverse_iterator const &other)
Definition: container.hpp:127
bool operator<(const _reverse_iterator &other)
Definition: container.hpp:1601
const_iterator(const chunk_array< element, block_bits > *c, size_type pos)
Definition: container.hpp:2223
sparse_data(const sparse_data &other)
Definition: container.hpp:1106
std::random_access_iterator_tag iterator_category
Definition: container.hpp:73
__INLINE const_iterator end() const
Definition: container.hpp:786
_iterator & operator=(_iterator const &other)
Definition: container.hpp:2038
__INLINE const char & at(size_type i) const
Definition: container.hpp:2446
__INLINE const element & operator[](size_type n) const
Definition: container.hpp:1736
_iterator< element > iterator
Definition: container.hpp:99
dynarray & operator=(dynarray const &other)
Definition: container.hpp:1722
_reverse_iterator operator-(size_t n)
Definition: container.hpp:575
__INLINE const_iterator begin() const
Definition: container.hpp:1856
__INLINE element * data()
Definition: container.hpp:604
iterator operator-(size_type n)
Definition: container.hpp:2191
_reverse_iterator< element > reverse_iterator
Definition: container.hpp:595
_reverse_iterator(const _reverse_iterator &other)
Definition: container.hpp:1585
bool operator>(const _reverse_iterator &other)
Definition: container.hpp:1602
bool operator==(const _iterator &other)
Definition: container.hpp:1561
bool operator!=(const _reverse_iterator &other) const
Definition: container.hpp:129
__INLINE element & at(size_type i)
Definition: container.hpp:2162
void resize(size_type n, element c=element())
Definition: container.hpp:1772
dynarray(const dynarray &other)
Definition: container.hpp:1708
bool empty() const
Definition: container.hpp:2295
__INLINE element & back()
Definition: container.hpp:720
bool operator<=(const _iterator &other) const
Definition: container.hpp:94
bool is_present(IndType key)
Definition: container.hpp:2096
const iterator const_iterator
Definition: container.hpp:972
__INLINE element & at(size_type n)
Definition: container.hpp:655
bool operator<(const _iterator &other)
Definition: container.hpp:2041
bool operator==(const _reverse_iterator &other)
Definition: container.hpp:1599
int size() const
Definition: container.hpp:1363
__INLINE const element * data() const
Definition: container.hpp:1633
assert(m_arr!=NULL)
bool operator<=(const const_iterator &other)
Definition: container.hpp:2242
_iterator< element > iterator
Definition: container.hpp:558
void pop_back()
Definition: container.hpp:696
void swap(sparse_data< IndType, ValType > &other)
Definition: container.hpp:996
interval(const interval &other)
Definition: container.hpp:1232
bool operator==(const const_iterator &other)
Definition: container.hpp:2238
__INLINE iterator end()
Definition: container.hpp:349
bool operator!=(const _reverse_iterator &other)
Definition: container.hpp:588
_iterator< element > iterator
Definition: container.hpp:1570
void push_back(const element &e)
Definition: container.hpp:2365
ValType const * const_iterator
Definition: container.hpp:1170
void replace(iterator m_first, iterator m_last, InputIterator first, InputIterator last)
Definition: container.hpp:485
__INLINE const_iterator begin() const
Definition: container.hpp:350
_iterator operator-(size_t n)
Definition: container.hpp:538
_iterator< const element > const_iterator
Definition: container.hpp:100
bool operator>=(const _iterator &other)
Definition: container.hpp:2044
_reverse_iterator< const element > const_reverse_iterator
Definition: container.hpp:1609
void resize(size_type n)
Definition: container.hpp:2536
iterator erase(iterator pos)
Definition: container.hpp:1862
_reverse_iterator & operator--()
Definition: container.hpp:581
_iterator & operator-=(size_t n)
Definition: container.hpp:539
_iterator & operator+=(size_t n)
Definition: container.hpp:81
iterator insert(iterator pos, const element &x)
Definition: container.hpp:405
__INLINE element & front()
Definition: container.hpp:298
_reverse_iterator & operator++()
Definition: container.hpp:579
size_type capacity() const
Definition: container.hpp:2487
_reverse_iterator operator-(size_t n)
Definition: container.hpp:116
void swap(array< element > &other)
Definition: container.hpp:339
void set_interval_beg(IndType beg)
Definition: container.hpp:1320
bool operator>=(const _iterator &other)
Definition: container.hpp:1566
void move(dynarray< element, stacked > &other)
Definition: container.hpp:1788
bool operator<=(const iterator &other)
Definition: container.hpp:2207
chunk_bulk_array & operator=(chunk_bulk_array const &other)
Definition: container.hpp:2522
bool operator==(const _iterator &other) const
Definition: container.hpp:90
bool operator!=(const _iterator &other)
Definition: container.hpp:2040
_reverse_iterator & operator++()
Definition: container.hpp:1591
void resize(size_type n, element c=element())
Definition: container.hpp:312
bool operator>(const _reverse_iterator &other)
Definition: container.hpp:590
iterator end()
Definition: container.hpp:1955
_reverse_iterator operator+(size_t n)
Definition: container.hpp:577
bool operator<=(const _iterator &other)
Definition: container.hpp:554
_iterator< const inner_type > const_iterator
Definition: container.hpp:2047
iterator erase(iterator pos)
Definition: container.hpp:356
_iterator(const _iterator &other)
Definition: container.hpp:76
bool operator<=(const _reverse_iterator &other)
Definition: container.hpp:591
bool operator<(const const_iterator &other)
Definition: container.hpp:2240
__INLINE element & front()
Definition: container.hpp:732
const_iterator(const const_iterator &other)
Definition: container.hpp:2224
void replace(iterator m_first, iterator m_last, InputIterator first, InputIterator last)
Definition: container.hpp:925
__INLINE bool empty() const
Definition: container.hpp:745
_iterator & operator=(_iterator const &other)
Definition: container.hpp:1560
ValType & operator[](IndType row)
Definition: container.hpp:1292
void push_back(const element &e)
Definition: container.hpp:677
bool operator>=(const const_iterator &other)
Definition: container.hpp:2243
__INLINE size_type capacity()
Definition: container.hpp:744
__INLINE const_reverse_iterator rend() const
Definition: container.hpp:1861
__INLINE size_type capacity()
Definition: container.hpp:1770
bool operator==(const iterator &other)
Definition: container.hpp:2203
array(InputIterator first, InputIterator last)
Definition: container.hpp:170
chunk_array(const chunk_array &other)
Definition: container.hpp:2314
bool operator>(const _iterator &other) const
Definition: container.hpp:93
void swap(dynarray< element, stacked > &other)
Definition: container.hpp:1808
shell & operator=(shell const &other)
Definition: container.hpp:660
std::random_access_iterator_tag iterator_category
Definition: container.hpp:2221
dynarray< std::pair< key, value >, stacked > container
Definition: container.hpp:1921
__INLINE element & at(size_type n)
Definition: container.hpp:215
iterator(const typename container::iterator &other)
Definition: container.hpp:1930
const element & back() const
Definition: container.hpp:2357
__INLINE iterator begin()
Definition: container.hpp:783
bool operator<(const _iterator &other)
Definition: container.hpp:1563
__INLINE const element & back() const
Definition: container.hpp:292
interval(IndType beg)
Definition: container.hpp:1208
iterator erase(iterator pos)
Definition: container.hpp:1064
_iterator & operator-=(size_type n)
Definition: container.hpp:1550
bool operator>(const const_iterator &other)
Definition: container.hpp:2241
_iterator(const _iterator &other)
Definition: container.hpp:1547
__INLINE size_type size() const
Definition: container.hpp:765
_iterator & operator=(_iterator const &other)
Definition: container.hpp:89
__INLINE const_reverse_iterator rend() const
Definition: container.hpp:790
shell(const shell &other)
Definition: container.hpp:621
void insert(iterator pos, InputIterator first, InputIterator last)
Definition: container.hpp:895
bool operator<=(const _reverse_iterator &other) const
Definition: container.hpp:132
__INLINE element & back()
Definition: container.hpp:1766
bool empty() const
Definition: container.hpp:1146
std::random_access_iterator_tag iterator_category
Definition: container.hpp:533
make_unsigned< size_type >::type uenum
Definition: container.hpp:2133
__INLINE const element & operator[](size_type n) const
Definition: container.hpp:200
_iterator< const element > const_iterator
Definition: container.hpp:559
__INLINE const_reverse_iterator rbegin() const
Definition: container.hpp:354
const_iterator & operator=(const_iterator const &other)
Definition: container.hpp:2237
const_iterator begin() const
Definition: container.hpp:2394
const_iterator end() const
Definition: container.hpp:1359
chunk_array & operator=(chunk_array const &other)
Definition: container.hpp:2323
void insert(iterator pos, size_type n, const element &x)
Definition: container.hpp:1891
bool empty() const
Definition: container.hpp:1364
bool operator>=(const _reverse_iterator &other)
Definition: container.hpp:592
bool operator<(const _reverse_iterator &other) const
Definition: container.hpp:130
pair_t(IndType first, ValType second)
Definition: container.hpp:969
array< element >::size_type size_type
Definition: container.hpp:522
bool operator==(const _iterator &other)
Definition: container.hpp:550
_reverse_iterator & operator--()
Definition: container.hpp:1593
iterator begin()
Definition: container.hpp:1954
__INLINE bool empty() const
Definition: container.hpp:311
IndType get_interval_beg() const
Definition: container.hpp:1361
__INLINE size_type size() const
Definition: container.hpp:1780
_iterator & operator+=(size_t n)
Definition: container.hpp:541
bool operator==(const _reverse_iterator &other) const
Definition: container.hpp:128
_reverse_iterator & operator=(_reverse_iterator const &other)
Definition: container.hpp:1598
#define __INLINE
Definition: inmost_common.h:75
void insert(iterator pos, size_type n, const element &x)
Definition: container.hpp:871
size_type size() const
Definition: container.hpp:2492
__INLINE size_type size() const
Definition: container.hpp:330
ValType * iterator
Definition: container.hpp:1169
const_iterator & operator-=(size_type n)
Definition: container.hpp:2227
IndType get_interval_end() const
Definition: container.hpp:1362
__INLINE reverse_iterator rbegin()
Definition: container.hpp:352
__INLINE element * data()
Definition: container.hpp:1632
__INLINE reverse_iterator rbegin()
Definition: container.hpp:787
_iterator operator+(size_t n)
Definition: container.hpp:80
make_unsigned< size_type >::type uenum
Definition: container.hpp:2411
bool operator>=(const _iterator &other)
Definition: container.hpp:555
_iterator< const element > const_iterator
Definition: container.hpp:1571
bool operator==(const _reverse_iterator &other)
Definition: container.hpp:587
__INLINE char & operator[](size_type i)
Definition: container.hpp:2431
_reverse_iterator & operator++()
Definition: container.hpp:120
make_unsigned< size_type >::type uenum
Definition: container.hpp:62
_iterator(const _iterator &other)
Definition: container.hpp:2000
iterator find(IndType ind)
Definition: container.hpp:1038
const_iterator operator+(size_type n)
Definition: container.hpp:2228
ValType & at(IndType row)
Definition: container.hpp:1280
size_type capacity() const
Definition: container.hpp:2289
value & operator[](const key &x)
Definition: container.hpp:1958
std::vector< std::pair< IndType, TValue > > serialize()
Definition: container.hpp:2107
iterator insert(iterator pos, const element &x)
Definition: container.hpp:841
chunk_bulk_array(const chunk_bulk_array &other)
Definition: container.hpp:2512
void reserve(size_type n)
Definition: container.hpp:1643
void push_back(const element &e)
Definition: container.hpp:245
_reverse_iterator< const element > const_reverse_iterator
Definition: container.hpp:137
void inner_resize(size_type new_size)
Definition: container.hpp:2451
_reverse_iterator< element > reverse_iterator
Definition: container.hpp:136
const_iterator end() const
Definition: container.hpp:1150
_iterator & operator=(_iterator const &other)
Definition: container.hpp:549
__INLINE const element & at(size_type n) const
Definition: container.hpp:1746
__INLINE iterator begin()
Definition: container.hpp:348
_iterator operator-(size_type n)
Definition: container.hpp:1549
_reverse_iterator< const element > const_reverse_iterator
Definition: container.hpp:596
__INLINE const_iterator end() const
Definition: container.hpp:351
__INLINE const element & front() const
Definition: container.hpp:738
std::random_access_iterator_tag iterator_category
Definition: container.hpp:570
iterator erase(iterator b, iterator e)
Definition: container.hpp:383
bool operator!=(const iterator &other)
Definition: container.hpp:2204
const element & front() const
Definition: container.hpp:2356
_reverse_iterator operator-(size_type n)
Definition: container.hpp:1587
bool empty() const
Definition: container.hpp:1967
bool operator>(const _iterator &other)
Definition: container.hpp:1564
void push_back(const element &e)
Definition: container.hpp:1757
iterator end()
Definition: container.hpp:1358
bool operator==(const _iterator &other)
Definition: container.hpp:2039
bool operator<(const _reverse_iterator &other)
Definition: container.hpp:589
_iterator(int cur_list, inner_iter it, inner_class_array *lists)
Definition: container.hpp:1998
__INLINE const element & at(size_type n) const
Definition: container.hpp:210
__INLINE char & at(size_type i)
Definition: container.hpp:2441
_iterator(const _iterator &other)
Definition: container.hpp:536
_reverse_iterator & operator+=(size_t n)
Definition: container.hpp:578
void shift_interval(IndType shift)
Definition: container.hpp:1348
shell(array< element > &arr)
Definition: container.hpp:607
ValType & operator[](IndType row)
Definition: container.hpp:1133
bool operator>=(const _reverse_iterator &other) const
Definition: container.hpp:133
const_iterator find(const key &x) const
Definition: container.hpp:1942
void insert(iterator pos, InputIterator first, InputIterator last)
Definition: container.hpp:457
void resize(size_type n, const element &e=element())
Definition: container.hpp:2371
enumerate size() const
Definition: container.hpp:1145
iterator operator+(size_type n)
Definition: container.hpp:2193
_iterator operator+(size_type n)
Definition: container.hpp:1551
bool operator<=(const _reverse_iterator &other)
Definition: container.hpp:1603
__INLINE reverse_iterator rend()
Definition: container.hpp:1859
__INLINE size_type capacity()
Definition: container.hpp:310
enumerate capacity()
Definition: container.hpp:1158
iterator erase(iterator pos)
Definition: container.hpp:791
_iterator & operator+=(size_type n)
Definition: container.hpp:1552
bool operator<(const _iterator &other) const
Definition: container.hpp:92
bool operator>(const iterator &other)
Definition: container.hpp:2206
__INLINE const element * data() const
Definition: container.hpp:160
__INLINE element * data()
Definition: container.hpp:159
dynarray(InputIterator first, InputIterator last)
Definition: container.hpp:1698
std::random_access_iterator_tag iterator_category
Definition: container.hpp:111
iterator erase(iterator b, iterator e)
Definition: container.hpp:818
_reverse_iterator & operator-=(size_t n)
Definition: container.hpp:576
_reverse_iterator operator+(size_type n)
Definition: container.hpp:1589
_iterator & operator-=(size_t n)
Definition: container.hpp:79
void inner_resize(size_type new_size)
Definition: container.hpp:2246
array(const array &other)
Definition: container.hpp:182
bool operator!=(const _reverse_iterator &other)
Definition: container.hpp:1600
__INLINE bool empty() const
Definition: container.hpp:1771
std::bidirectional_iterator_tag iterator_category
Definition: container.hpp:1997
__INLINE const element & at(size_type i) const
Definition: container.hpp:2167
sparse_data(pair *first, pair *last)
Definition: container.hpp:1073
bool operator>(const _reverse_iterator &other) const
Definition: container.hpp:131
__INLINE element & at(size_type n)
Definition: container.hpp:1751
iterator(chunk_array< element, block_bits > *c, size_type pos)
Definition: container.hpp:2188
bool operator>=(const _reverse_iterator &other)
Definition: container.hpp:1604
bool operator<(const iterator &other)
Definition: container.hpp:2205
__INLINE const_iterator end() const
Definition: container.hpp:1857
iterator erase(iterator pos)
Definition: container.hpp:2379
const_iterator & operator+=(size_type n)
Definition: container.hpp:2229
const_iterator begin() const
Definition: container.hpp:1956
_reverse_iterator(const _reverse_iterator &other)
Definition: container.hpp:114
__INLINE const_reverse_iterator rbegin() const
Definition: container.hpp:789
void swap(interval< IndType, ValType > &other)
Definition: container.hpp:1183
__INLINE const element & back() const
Definition: container.hpp:726
iterator & operator=(iterator const &other)
Definition: container.hpp:2202
bool operator<=(const _iterator &other)
Definition: container.hpp:2043
__INLINE element & at_safe(size_type n)
Definition: container.hpp:220
iterator find(const key &x)
Definition: container.hpp:1948
_reverse_iterator & operator+=(size_type n)
Definition: container.hpp:1590
_iterator & operator--()
Definition: container.hpp:84
_reverse_iterator operator+(size_t n)
Definition: container.hpp:118
iterator & operator-=(size_type n)
Definition: container.hpp:2192
_iterator operator+(size_t n)
Definition: container.hpp:540
_reverse_iterator & operator-=(size_type n)
Definition: container.hpp:1588
const_iterator end() const
Definition: container.hpp:2395