# OpenGraph DrawingFramework

v.2012.07

Array.h
Go to the documentation of this file.
1 /*
2  * $Revision: 2615$
3  *
4  * last checkin:
5  * $Author: gutwenger$
6  * $Date: 2012-07-16 14:23:36 +0200 (Mo, 16. Jul 2012)$
7  ***************************************************************/
8
45 #ifdef _MSC_VER
46 #pragma once
47 #endif
48
49 #ifndef OGDF_ARRAY_H
50 #define OGDF_ARRAY_H
51
52
53 #include <ogdf/basic/basic.h>
54
55
56 namespace ogdf {
57
59
84 #define forall_arrayindices(i, A) \
85  for(i = (A).low(); i<=(A).high(); ++i)
86
88
93 #define forall_rev_arrayindices(i, A) \
94  for(i = (A).high(); i>=(A).low(); --i)
95
96
97
99
106 template<class E, class INDEX = int> class Array {
107 public:
110  enum { maxSizeInsertionSort = 40 };
111
112
114  Array() { construct(0,-1); }
115
117  explicit Array(INDEX s) {
118  construct(0,s-1); initialize();
119  }
120
122  Array(INDEX a, INDEX b) {
123  construct(a,b); initialize();
124  }
125
127  Array(INDEX a, INDEX b, const E &x) {
128  construct(a,b); initialize(x);
129  }
130
132  Array(const Array<E> &A) {
133  copy(A);
134  }
135
136  // destruction
137  ~Array() {
138  deconstruct();
139  }
140
142  INDEX low() const { return m_low; }
143
145  INDEX high() const { return m_high; }
146
148  INDEX size() const { return m_high - m_low + 1; }
149
151  E *begin() { return m_pStart; }
152
154  const E *begin() const { return m_pStart; }
155
157  E *end() { return m_pStop; }
158
160  const E *end() const { return m_pStop; }
161
163  E *rbegin() { return m_pStop-1; }
164
166  const E *rbegin() const { return m_pStop-1; }
167
169  E *rend() { return m_pStart-1; }
170
172  const E *rend() const { return m_pStart-1; }
173
175  const E &operator[](INDEX i) const {
176  OGDF_ASSERT(m_low <= i && i <= m_high)
177  return m_vpStart[i];
178  }
179
181  E &operator[](INDEX i) {
182  OGDF_ASSERT(m_low <= i && i <= m_high)
183  return m_vpStart[i];
184  }
185
187  void swap(INDEX i, INDEX j) {
188  OGDF_ASSERT(m_low <= i && i <= m_high)
189  OGDF_ASSERT(m_low <= j && j <= m_high)
190
191  std::swap(m_vpStart[i], m_vpStart[j]);
192  }
193
195  void init() {
196  //init(0,-1);
197  deconstruct();
198  construct(0,-1);
199  }
200
202
205  void init(INDEX s) { init(0,s-1); }
206
208
211  void init(INDEX a, INDEX b) {
212  deconstruct();
213  construct(a,b);
214  initialize();
215  }
216
218  void init(INDEX a, INDEX b, const E &x) {
219  deconstruct();
220  construct(a,b);
221  initialize(x);
222  }
223
226  deconstruct();
227  copy(array2);
228  return *this;
229  }
230
232  void fill(const E &x) {
233  E *pDest = m_pStop;
234  while(pDest > m_pStart)
235  *--pDest = x;
236  }
237
239  void fill(INDEX i, INDEX j, const E &x) {
240  OGDF_ASSERT(m_low <= i && i <= m_high)
241  OGDF_ASSERT(m_low <= j && j <= m_high)
242
243  E *pI = m_vpStart + i, *pJ = m_vpStart + j+1;
244  while(pJ > pI)
245  *--pJ = x;
246  }
247
249
254  void grow(INDEX add, const E &x);
255
257
262
264  void permute (INDEX l, INDEX r);
265
267  void permute() {
268  permute(low(), high());
269  }
270
272
276  inline int binarySearch (const E& x) const {
277  return binarySearch(x, StdComparer<E>());
278  }
279
281
285  template<class COMPARER>
286  int binarySearch(const E& e, const COMPARER &comp) const {
287  if(size() < 2) {
288  if(size() == 1 && comp.equal(e, m_vpStart[low()]))
289  return low();
290  return low()-1;
291  }
292  int l = low();
293  int r = high();
294  do {
295  int m = (r + l)/2;
296  if(comp.greater(e, m_vpStart[m]))
297  l = m+1;
298  else
299  r = m;
300  } while(r>l);
301  return comp.equal(e, m_vpStart[l]) ? l : low()-1;
302  }
303
305
310  inline int linearSearch (const E& e) const {
311  int i;
312  for(i = size(); i-->0;)
313  if(e == m_pStart[i]) break;
314  return i+low(); }
315
317
322  template<class COMPARER>
323  int linearSearch(const E& e, const COMPARER &comp) const {
324  int i;
325  for(i = size(); i-->0;)
326  if(comp.equal(e, m_pStart[i])) break;
327  return i+low();
328  }
329
331  inline void quicksort() {
333  }
334
336  inline void quicksort(INDEX l, INDEX r) {
337  quicksort(l, r, StdComparer<E>());
338  }
339
341
344  template<class COMPARER>
345  inline void quicksort(const COMPARER &comp) {
346  if(low() < high())
347  quicksortInt(m_pStart,m_pStop-1,comp);
348  }
349
351
356  template<class COMPARER>
357  void quicksort(INDEX l, INDEX r, const COMPARER &comp) {
358  OGDF_ASSERT(low() <= l && l <= high())
359  OGDF_ASSERT(low() <= r && r <= high())
360  if(l < r)
361  quicksortInt(m_vpStart+l,m_vpStart+r,comp);
362  }
363
364  template<class F, class I> friend class ArrayBuffer; // for efficient ArrayBuffer::compact-method
365
366 private:
368  E *m_pStart;
369  E *m_pStop;
370  INDEX m_low;
371  INDEX m_high;
372
374  void construct(INDEX a, INDEX b);
375
377  void initialize();
378
380  void initialize(const E &x);
381
383  void deconstruct();
384
386  void copy(const Array<E,INDEX> &A);
387
389  template<class COMPARER>
390  static void quicksortInt(E *pL, E *pR, const COMPARER &comp) {
391  size_t s = pR-pL;
392
393  // use insertion sort for small instances
394  if (s < maxSizeInsertionSort) {
395  for (E *pI = pL+1; pI <= pR; pI++) {
396  E v = *pI;
397  E *pJ = pI;
398  while (--pJ >= pL && comp.less(v,*pJ)) {
399  *(pJ+1) = *pJ;
400  }
401  *(pJ+1) = v;
402  }
403  return;
404  }
405
406  E *pI = pL, *pJ = pR;
407  E x = *(pL+(s>>1));
408
409  do {
410  while (comp.less(*pI,x)) pI++;
411  while (comp.less(x,*pJ)) pJ--;
412  if (pI <= pJ) std::swap(*pI++,*pJ--);
413  } while (pI <= pJ);
414
415  if (pL < pJ) quicksortInt(pL,pJ,comp);
416  if (pI < pR) quicksortInt(pI,pR,comp);
417  }
418
420 }; // class Array
421
422
423
424
425 // enlarges array by add elements and sets new elements to x
426 template<class E, class INDEX>
427 void Array<E,INDEX>::grow(INDEX add, const E &x)
428 {
429  INDEX sOld = size(), sNew = sOld + add;
430
431  // expand allocated memory block
432  if(m_pStart != 0) {
433  E *p = (E *)realloc(m_pStart, sNew*sizeof(E));
435  m_pStart = p;
436  } else {
437  m_pStart = (E *)malloc(sNew*sizeof(E));
438  if (m_pStart == 0) OGDF_THROW(InsufficientMemoryException);
439  }
440
441  m_vpStart = m_pStart-m_low;
442  m_pStop = m_pStart+sNew;
444
445  // initialize new array entries
446  for (E *pDest = m_pStart+sOld; pDest < m_pStop; pDest++)
447  new (pDest) E(x);
448 }
449
450 // enlarges array by add elements (initialized with default constructor)
451 template<class E, class INDEX>
453 {
454  INDEX sOld = size(), sNew = sOld + add;
455
456  // expand allocated memory block
457  if(m_pStart != 0) {
458  E *p = (E *)realloc(m_pStart, sNew*sizeof(E));
460  m_pStart = p;
461  } else {
462  m_pStart = (E *)malloc(sNew*sizeof(E));
463  if (m_pStart == 0) OGDF_THROW(InsufficientMemoryException);
464  }
465
466  m_vpStart = m_pStart-m_low;
467  m_pStop = m_pStart+sNew;
469
470  // initialize new array entries
471  for (E *pDest = m_pStart+sOld; pDest < m_pStop; pDest++)
472  new (pDest) E;
473 }
474
475 template<class E, class INDEX>
476 void Array<E,INDEX>::construct(INDEX a, INDEX b)
477 {
478  m_low = a; m_high = b;
479  INDEX s = b-a+1;
480
481  if (s < 1) {
482  m_pStart = m_vpStart = m_pStop = 0;
483
484  } else {
485  m_pStart = (E *)malloc(s*sizeof(E));
486  if (m_pStart == 0) OGDF_THROW(InsufficientMemoryException);
487
488  m_vpStart = m_pStart - a;
489  m_pStop = m_pStart + s;
490  }
491 }
492
493
494 template<class E, class INDEX>
496 {
497  E *pDest = m_pStart;
498  try {
499  for (; pDest < m_pStop; pDest++)
500  new(pDest) E;
501  } catch (...) {
502  while(--pDest >= m_pStart)
503  pDest->~E();
504  free(m_pStart);
505  throw;
506  }
507 }
508
509
510 template<class E, class INDEX>
512 {
513  E *pDest = m_pStart;
514  try {
515  for (; pDest < m_pStop; pDest++)
516  new(pDest) E(x);
517  } catch (...) {
518  while(--pDest >= m_pStart)
519  pDest->~E();
520  free(m_pStart);
521  throw;
522  }
523 }
524
525
526 template<class E, class INDEX>
528 {
529  if (doDestruction((E*)0)) {
530  for (E *pDest = m_pStart; pDest < m_pStop; pDest++)
531  pDest->~E();
532  }
533  free(m_pStart);
534 }
535
536
537 template<class E, class INDEX>
539 {
540  construct(array2.m_low, array2.m_high);
541
542  if (m_pStart != 0) {
543  E *pSrc = array2.m_pStop;
544  E *pDest = m_pStop;
545  while(pDest > m_pStart)
546  //*--pDest = *--pSrc;
547  new (--pDest) E(*--pSrc);
548  }
549 }
550
551
552 // permutes array a from a[l] to a[r] randomly
553 template<class E, class INDEX>
554 void Array<E,INDEX>::permute (INDEX l, INDEX r)
555 {
556  OGDF_ASSERT(low() <= l && l <= high())
557  OGDF_ASSERT(low() <= r && r <= high())
558
559  E *pI = m_vpStart+l, *pStart = m_vpStart+l, *pStop = m_vpStart+r;
560  while(pI <= pStop)
561  std::swap(*pI++,*(pStart+randomNumber(0,r-l)));
562 }
563
564
565 // prints array a to output stream os using delimiter delim
566 template<class E, class INDEX>
567 void print(ostream &os, const Array<E,INDEX> &a, char delim = ' ')
568 {
569  for (int i = a.low(); i <= a.high(); i++) {
570  if (i > a.low()) os << delim;
571  os << a[i];
572  }
573 }
574
575
576 // output operator
577 template<class E, class INDEX>
578 ostream &operator<<(ostream &os, const ogdf::Array<E,INDEX> &a)
579 {
580  print(os,a);
581  return os;
582 }
583
584 } // end namespace ogdf
585
586
587 #endif