Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

Array.h
Go to the documentation of this file.
1 
33 #pragma once
34 
35 #include <ogdf/basic/comparer.h>
36 #include <ogdf/basic/memory.h>
37 #include <ogdf/basic/exceptions.h>
38 #include <ogdf/basic/Reverse.h>
39 #include <random>
40 #include <type_traits>
41 
42 
43 namespace ogdf {
44 
45 template<class E, class INDEX> class ArrayBuffer;
46 
47 template<class E, bool isConst> class ArrayReverseIteratorBase;
48 template<class E> using ArrayConstIterator = const E*;
49 template<class E> using ArrayIterator = E*;
52 
54 
62 template<class E, bool isConst> class ArrayReverseIteratorBase {
63  friend class ArrayReverseIteratorBase<E, !isConst>;
64 
67 
70 
71 public:
73  ArrayReverseIteratorBase(E *pX) : m_pX(pX) { }
74 
77  ArrayReverseIteratorBase(const E *pX) : m_pX(pX) { }
78 
81 
85 
89 
91  operator std::conditional<isConst, const E, E> *() const { return m_pX; }
92 
95  return m_pX == it.m_pX;
96  }
97 
100  return m_pX != it.m_pX;
101  }
102 
104  Elem &operator*() const { return *m_pX; }
105 
108  m_pX = it.m_pX;
109  return *this;
110  }
111 
114  m_pX--;
115  return *this;
116  }
117 
121  m_pX--;
122  return it;
123  }
124 
127  m_pX++;
128  return *this;
129  }
130 
134  m_pX++;
135  return it;
136  }
137 
140  m_pX -= rhs;
141  return *this;
142  }
143 
146  m_pX += rhs;
147  return *this;
148  }
149 
153  }
154 
158  const int &lhs, ArrayReverseIteratorBase<E, isConst> rhs) {
159  return ArrayReverseIteratorBase<E, isConst>(rhs.m_pX - lhs);
160  }
161 
165  }
166 
168  template<bool isArgConst>
170  return rhs.m_pX - m_pX;
171  }
172 
174  bool operator< (ArrayReverseIteratorBase<E, isConst> &it) const { return m_pX > it.m_pX; }
175 
177  bool operator> (ArrayReverseIteratorBase<E, isConst> &it) const { return m_pX < it.m_pX; }
178 
180  bool operator<=(ArrayReverseIteratorBase<E, isConst> &it) const { return m_pX >= it.m_pX; }
181 
183  bool operator>=(ArrayReverseIteratorBase<E, isConst> &it) const { return m_pX <= it.m_pX; }
184 
186  Elem &operator[](std::size_t idx) { return m_pX[-idx]; }
187 
189  const Elem &operator[](std::size_t idx) const { return m_pX[-idx]; }
190 
192 };
193 
195 
204 template<class E, class INDEX = int> class Array {
205 public:
208  static const int maxSizeInsertionSort = 40;
209 
211  using value_type = E;
213  using reference = E&;
215  using const_reference = const E&;
224 
226  Array() { construct(0,-1); }
227 
229  explicit Array(INDEX s) : Array(0, s - 1) { }
230 
232  Array(INDEX a, INDEX b) {
233  construct(a,b); initialize();
234  }
235 
237  Array(INDEX a, INDEX b, const E &x) {
238  construct(a,b); initialize(x);
239  }
240 
242 
245  Array(std::initializer_list<E> initList) {
246  construct(0, ((INDEX) initList.size()) - 1);
247  initialize(initList);
248  }
249 
251  Array(const Array<E,INDEX> &A) {
252  copy(A);
253  }
254 
256 
261  {
262  A.construct(0,-1);
263  }
264 
266  Array(const ArrayBuffer<E,INDEX> &A);
267 
269  ~Array() {
270  deconstruct();
271  }
272 
278 
280  INDEX low() const { return m_low; }
281 
283  INDEX high() const { return m_high; }
284 
286  INDEX size() const { return m_high - m_low + 1; }
287 
289  bool empty() const { return size() == 0; }
290 
292  const_reference operator[](INDEX i) const {
293  OGDF_ASSERT(m_low <= i);
294  OGDF_ASSERT(i <= m_high);
295  return m_vpStart[i];
296  }
297 
300  OGDF_ASSERT(m_low <= i);
301  OGDF_ASSERT(i <= m_high);
302  return m_vpStart[i];
303  }
304 
305 
307 
312 
314  iterator begin() { return m_pStart; }
315 
317  const_iterator begin() const { return m_pStart; }
318 
320  const_iterator cbegin() const { return m_pStart; }
321 
323  iterator end() { return m_pStop; }
324 
326  const_iterator end() const { return m_pStop; }
327 
329  const_iterator cend() const { return m_pStop; }
330 
333 
335  const_reverse_iterator rbegin() const { return m_pStop-1; }
336 
338  const_reverse_iterator crbegin() const { return m_pStop-1; }
339 
342 
344  const_reverse_iterator rend() const { return m_pStart-1; }
345 
347  const_reverse_iterator crend() const { return m_pStart-1; }
348 
349 
351 
356 
358  void init() {
359  deconstruct();
360  construct(0,-1);
361  }
362 
364 
367  void init(INDEX s) { init(0,s-1); }
368 
370 
373  void init(INDEX a, INDEX b) {
374  deconstruct();
375  construct(a,b);
376  initialize();
377  }
378 
380  void init(INDEX a, INDEX b, const E &x) {
381  deconstruct();
382  construct(a,b);
383  initialize(x);
384  }
385 
387  void fill(const E &x) {
388  E *pDest = m_pStop;
389  while(pDest > m_pStart)
390  *--pDest = x;
391  }
392 
394  void fill(INDEX i, INDEX j, const E &x) {
395  OGDF_ASSERT(m_low <= i);
396  OGDF_ASSERT(i <= m_high);
397  OGDF_ASSERT(m_low <= j);
398  OGDF_ASSERT(j <= m_high);
399 
400  E *pI = m_vpStart + i, *pJ = m_vpStart + j+1;
401  while(pJ > pI)
402  *--pJ = x;
403  }
404 
406 
411  void grow(INDEX add, const E &x);
412 
414 
418  void grow(INDEX add);
419 
421 
426  void resize(INDEX newSize, const E &x) { grow(newSize - size(), x); }
427 
429 
433  void resize(INDEX newSize) { grow(newSize - size()); }
434 
437  deconstruct();
438  copy(A);
439  return *this;
440  }
441 
443 
447  deconstruct();
448 
449  m_vpStart = A.m_vpStart;
450  m_pStart = A.m_pStart;
451  m_pStop = A.m_pStop;
452  m_low = A.m_low;
453  m_high = A.m_high;
454 
455  A.construct(0,-1);
456  return *this;
457  }
458 
462 
464  bool operator==(const Array<E, INDEX> &L) const {
465  if (size() != L.size()) {
466  return false;
467  }
468 
469  auto thisIterator = begin();
470  auto thatIterator = L.begin();
471 
472  while (thisIterator != end() && thatIterator != L.end()) {
473  if (*thisIterator != *thatIterator) {
474  return false;
475  }
476  ++thisIterator;
477  ++thatIterator;
478  }
479 
480  OGDF_ASSERT(thisIterator == end() && thatIterator == L.end());
481  return true;
482  }
483 
485  bool operator!=(const Array<E, INDEX> &L) const {
486  return !operator==(L);
487  }
488 
490 
495 
497  void swap(INDEX i, INDEX j) {
498  OGDF_ASSERT(m_low <= i);
499  OGDF_ASSERT(i <= m_high);
500  OGDF_ASSERT(m_low <= j);
501  OGDF_ASSERT(j <= m_high);
502 
503  std::swap(m_vpStart[i], m_vpStart[j]);
504  }
505 
507  void permute(INDEX l, INDEX r) {
508  std::minstd_rand rng(randomSeed());
509  permute(l, r, rng);
510  }
511 
513  void permute() {
514  permute(low(), high());
515  }
516 
523  template<class RNG>
524  void permute(INDEX l, INDEX r, RNG &rng);
525 
530  template<class RNG>
531  void permute(RNG &rng) {
532  if(!empty()) {
533  permute(low(), high(), rng);
534  }
535  }
536 
537 
539 
544 
546 
550  inline int binarySearch (const E& e) const {
551  return binarySearch(low(), high(), e, StdComparer<E>());
552  }
553 
555 
559  inline int binarySearch (INDEX l, INDEX r, const E& e) const {
560  return binarySearch(l, r, e, StdComparer<E>());
561  }
562 
564 
568  template<class COMPARER>
569  inline int binarySearch(const E& e, const COMPARER &comp) const {
570  return binarySearch(low(), high(), e, comp);
571  }
572 
574 
578  template<class COMPARER>
579  INDEX binarySearch(INDEX l, INDEX r, const E& e, const COMPARER &comp) const {
580  if(r<l) return low()-1;
581  while(r>l) {
582  INDEX m = (r + l)/2;
583  if(comp.greater(e, m_vpStart[m]))
584  l = m+1;
585  else
586  r = m;
587  }
588  return comp.equal(e, m_vpStart[l]) ? l : low()-1;
589  }
591 
596  inline INDEX linearSearch (const E& e) const {
597  int i;
598  for(i = size(); i-- > 0; )
599  if(e == m_pStart[i]) break;
600  return i+low(); }
601 
603 
608  template<class COMPARER>
609  INDEX linearSearch(const E& e, const COMPARER &comp) const {
610  int i;
611  for(i = size(); i-- > 0; )
612  if(comp.equal(e, m_pStart[i])) break;
613  return i+low();
614  }
615 
617  inline void quicksort() {
619  }
620 
622  inline void quicksort(INDEX l, INDEX r) {
623  quicksort(l, r, StdComparer<E>());
624  }
625 
627 
630  template<class COMPARER>
631  inline void quicksort(const COMPARER &comp) {
632  if(low() < high())
633  quicksortInt(m_pStart,m_pStop-1,comp);
634  }
635 
637 
642  template<class COMPARER>
643  void quicksort(INDEX l, INDEX r, const COMPARER &comp) {
644  OGDF_ASSERT(low() <= l);
645  OGDF_ASSERT(l <= high());
646  OGDF_ASSERT(low() <= r);
647  OGDF_ASSERT(r <= high());
648  if(l < r)
650  }
651 
653 
665 
667 
677  void leftShift(ArrayBuffer<INDEX, INDEX> &ind, const E& val) {
678  leftShift(ind);
679  fill(high()-ind.size(),high(),val);
680  }
681 
683 
684  template<class F, class I> friend class ArrayBuffer; // for efficient ArrayBuffer::compact-method
685 
686 private:
688  E *m_pStart;
689  E *m_pStop;
690  INDEX m_low;
691  INDEX m_high;
692 
694  void construct(INDEX a, INDEX b);
695 
697  void initialize();
698 
700  void initialize(const E &x);
701 
703  void initialize(std::initializer_list<E> initList);
704 
706  void deconstruct();
707 
709  void copy(const Array<E,INDEX> &A);
710 
712  void expandArray(INDEX add);
713 
715  template<typename EE = E,
716  typename std::enable_if<OGDF_TRIVIALLY_COPYABLE<EE>::value, int>::type = 0>
717  void expandArrayHelper(INDEX sOld, INDEX sNew) {
718  // If the element type is trivially copiable, just use realloc.
719  E *p = static_cast<E *>( realloc(m_pStart, sNew*sizeof(E)) );
720  if (p == nullptr) OGDF_THROW(InsufficientMemoryException);
721  m_pStart = p;
722  }
723 
725  template<typename EE = E,
726  typename std::enable_if<!OGDF_TRIVIALLY_COPYABLE<EE>::value, int>::type = 0>
727  void expandArrayHelper(INDEX sOld, INDEX sNew) {
728  // If the element type is not trivially copiable,
729  // allocate a new block, move the elements, and free the old block.
730  E *p = static_cast<E *>( malloc(sNew*sizeof(E)) );
731  if (p == nullptr) OGDF_THROW(InsufficientMemoryException);
732 
733  for (int i = 0; i < min(sOld,sNew); ++i) {
734  new (&p[i]) E(std::move(m_pStart[i]));
735  }
736 
737  deconstruct();
738  m_pStart = p;
739  }
740 
742  template<class COMPARER>
743  static void quicksortInt(E *pL, E *pR, const COMPARER &comp) {
744  size_t s = pR-pL;
745 
746  // use insertion sort for small instances
747  if (s < maxSizeInsertionSort) {
748  for (E *pI = pL+1; pI <= pR; pI++) {
749  E v = *pI;
750  E *pJ = pI;
751  while (--pJ >= pL && comp.less(v,*pJ)) {
752  *(pJ+1) = *pJ;
753  }
754  *(pJ+1) = v;
755  }
756  return;
757  }
758 
759  E *pI = pL, *pJ = pR;
760  E x = *(pL+(s>>1));
761 
762  do {
763  while (comp.less(*pI,x)) pI++;
764  while (comp.less(x,*pJ)) pJ--;
765  if (pI <= pJ) std::swap(*pI++,*pJ--);
766  } while (pI <= pJ);
767 
768  if (pL < pJ) quicksortInt(pL,pJ,comp);
769  if (pI < pR) quicksortInt(pI,pR,comp);
770  }
771 
773 };
774 
775 // enlarges storage for array and moves old entries
776 template<class E, class INDEX>
778 {
779  INDEX sOld = size(), sNew = sOld + add;
780 
781  // expand allocated memory block
782  if (m_pStart != nullptr) {
783  expandArrayHelper(sOld, sNew);
784  } else {
785  m_pStart = static_cast<E *>( malloc(sNew*sizeof(E)) );
786  if (m_pStart == nullptr) OGDF_THROW(InsufficientMemoryException);
787  }
788 
789  m_vpStart = m_pStart - m_low;
790  m_pStop = m_pStart + sNew;
791  m_high += add;
792 }
793 
794 // enlarges array by add elements and sets new elements to x
795 template<class E, class INDEX>
796 void Array<E,INDEX>::grow(INDEX add, const E &x)
797 {
798  if(add == 0) return;
799 
800  INDEX sOld = size();
801  expandArray(add);
802 
803  // initialize new array entries
804  for (E *pDest = m_pStart+sOld; pDest < m_pStop; pDest++)
805  new (pDest) E(x);
806 }
807 
808 // enlarges array by add elements (initialized with default constructor)
809 template<class E, class INDEX>
810 void Array<E,INDEX>::grow(INDEX add)
811 {
812  if(add == 0) return;
813 
814  INDEX sOld = size();
815  expandArray(add);
816 
817  // initialize new array entries
818  for (E *pDest = m_pStart+sOld; pDest < m_pStop; pDest++)
819  new (pDest) E;
820 }
821 
822 template<class E, class INDEX>
823 void Array<E,INDEX>::construct(INDEX a, INDEX b)
824 {
825  m_low = a; m_high = b;
826  INDEX s = b-a+1;
827 
828  if (s < 1) {
829  m_pStart = m_vpStart = m_pStop = nullptr;
830 
831  } else {
832  m_pStart = static_cast<E *>( malloc(s*sizeof(E)) );
833  if (m_pStart == nullptr) OGDF_THROW(InsufficientMemoryException);
834 
835  m_vpStart = m_pStart - a;
836  m_pStop = m_pStart + s;
837  }
838 }
839 
840 
841 template<class E, class INDEX>
843 {
844  E *pDest = m_pStart;
845  try {
846  for (; pDest < m_pStop; pDest++)
847  new(pDest) E;
848  } catch (...) {
849  while(--pDest >= m_pStart)
850  pDest->~E();
851  free(m_pStart);
852  throw;
853  }
854 }
855 
856 
857 template<class E, class INDEX>
859 {
860  E *pDest = m_pStart;
861  try {
862  for (; pDest < m_pStop; pDest++)
863  new(pDest) E(x);
864  } catch (...) {
865  while(--pDest >= m_pStart)
866  pDest->~E();
867  free(m_pStart);
868  throw;
869  }
870 }
871 
872 
873 template<class E, class INDEX>
874 void Array<E, INDEX>::initialize(std::initializer_list<E> initList)
875 {
876  E *pDest = m_pStart;
877  try {
878  for (const E &x : initList)
879  new(pDest++) E(x);
880  }
881  catch (...) {
882  while (--pDest >= m_pStart)
883  pDest->~E();
884  free(m_pStart);
885  throw;
886  }
887 }
888 
889 
890 template<class E, class INDEX>
892 {
893  if (!std::is_trivially_destructible<E>::value) {
894  for (E *pDest = m_pStart; pDest < m_pStop; pDest++)
895  pDest->~E();
896  }
897  free(m_pStart);
898 }
899 
900 
901 template<class E, class INDEX>
903 {
904  construct(array2.m_low, array2.m_high);
905 
906  if (m_pStart != nullptr) {
907  E *pSrc = array2.m_pStop;
908  E *pDest = m_pStop;
909  while(pDest > m_pStart)
910 #if 0
911  *--pDest = *--pSrc;
912 #endif
913  new (--pDest) E(*--pSrc);
914  }
915 }
916 
917 
918 // permutes array a from a[l] to a[r] randomly
919 template<class E, class INDEX>
920 template<class RNG>
921 void Array<E,INDEX>::permute (INDEX l, INDEX r, RNG &rng)
922 {
923  OGDF_ASSERT(low() <= l);
924  OGDF_ASSERT(l <= high());
925  OGDF_ASSERT(low() <= r);
926  OGDF_ASSERT(r <= high());
927 
928  std::uniform_int_distribution<int> dist(0,r-l);
929 
930  E *pI = m_vpStart+l, *pStart = m_vpStart+l, *pStop = m_vpStart+r;
931  while(pI <= pStop)
932  std::swap( *pI++, *(pStart + dist(rng)) );
933 }
934 
935 
937 template<class E, class INDEX>
938 void print(std::ostream &os, const Array<E,INDEX> &a, char delim = ' ')
939 {
940  for (int i = a.low(); i <= a.high(); i++) {
941  if (i > a.low()) os << delim;
942  os << a[i];
943  }
944 }
945 
946 
948 template<class E, class INDEX>
949 std::ostream &operator<<(std::ostream &os, const ogdf::Array<E,INDEX> &a)
950 {
951  print(os,a);
952  return os;
953 }
954 
955 }
956 
957 #include <ogdf/basic/ArrayBuffer.h>
958 
959 namespace ogdf {
960 
962 template<class E, class INDEX>
964  const INDEX nInd = ind.size();
965  if (nInd == 0) return;
966 
967  OGDF_ASSERT(ind[0] >= low());
968  OGDF_ASSERT(ind[0] <= high());
969 
970  INDEX j, current = ind[0];
971  for (INDEX i = 0; i < nInd - 1; i++) {
972  OGDF_ASSERT(ind[i+1] >= low());
973  OGDF_ASSERT(ind[i+1] <= high());
974 
975  const INDEX last = ind[i+1];
976  for(j = ind[i]+1; j < last; j++)
977  m_vpStart[current++] = m_vpStart[j];
978  }
979 
981  for (j = ind[nInd - 1]+1; j < size(); j++)
982  m_vpStart[current++] = m_vpStart[j];
983 }
984 
985 template<class E, class INDEX>
987  construct(0,-1);
988  A.compactCopy(*this);
989 }
990 
991 }
ogdf::Array::quicksort
void quicksort(INDEX l, INDEX r)
Sorts subarray with index set [l, ..., r] using Quicksort.
Definition: Array.h:622
ogdf::ArrayBuffer
An array that keeps track of the number of inserted elements; also usable as an efficient stack.
Definition: Array.h:45
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::ArrayReverseIteratorBase::operator=
ArrayReverseIteratorBase< E, isConst > & operator=(const ArrayReverseIteratorBase< E, isConst > &it)
Assignment operator.
Definition: Array.h:107
ogdf::Array::resize
void resize(INDEX newSize)
Resizes (enlarges or shrinks) the array to hold newSize elements.
Definition: Array.h:433
ogdf::Array::m_vpStart
E * m_vpStart
The virtual start of the array (address of A[0]).
Definition: Array.h:687
ArrayBuffer.h
Declaration and implementation of ArrayBuffer class.
ogdf::Array::m_high
INDEX m_high
The highest index.
Definition: Array.h:691
ogdf::Array::Array
Array(INDEX a, INDEX b, const E &x)
Creates an array with index set [a..b] and initializes each element with x.
Definition: Array.h:237
exceptions.h
Definition of exception classes.
ogdf::ArrayReverseIteratorBase::operator>
bool operator>(ArrayReverseIteratorBase< E, isConst > &it) const
Greater-than operator.
Definition: Array.h:177
ogdf::InsufficientMemoryException
Exception thrown when not enough memory is available to execute an algorithm.
Definition: exceptions.h:213
OGDF_ASSERT
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition: basic.h:41
ogdf::Array::operator!=
bool operator!=(const Array< E, INDEX > &L) const
Inequality operator.
Definition: Array.h:485
ogdf::ArrayReverseIteratorBase::ArrayReverseIteratorBase
ArrayReverseIteratorBase(const ArrayReverseIteratorBase< E, isConst > &it)
Copy constructor. clang10 does not see the above templated one match this case and requires it explic...
Definition: Array.h:88
ogdf::ArrayReverseIteratorBase::operator+=
ArrayReverseIteratorBase< E, isConst > & operator+=(const int &rhs)
Compound assignment operator (+).
Definition: Array.h:139
ogdf::ArrayReverseIteratorBase::operator!=
bool operator!=(const ArrayReverseIteratorBase< E, isConst > &it) const
Inequality operator.
Definition: Array.h:99
ogdf::StdComparer
Standard comparer (valid as a static comparer).
Definition: comparer.h:58
ogdf::Array::operator[]
reference operator[](INDEX i)
Returns a reference to the element at position i.
Definition: Array.h:299
ogdf::Array::Array
Array(INDEX s)
Creates an array with index set [0..s-1].
Definition: Array.h:229
ogdf::ArrayReverseIteratorBase::operator<
bool operator<(ArrayReverseIteratorBase< E, isConst > &it) const
Less-than operator.
Definition: Array.h:174
ogdf::Array::construct
void construct(INDEX a, INDEX b)
Allocates new array with index set [a, ..., b].
Definition: Array.h:823
ogdf::Array::initialize
void initialize()
Initializes elements with default constructor.
Definition: Array.h:842
ogdf::whaType::A
@ A
ogdf::ArrayIterator
E * ArrayIterator
Definition: Array.h:49
ogdf::Array::high
INDEX high() const
Returns the maximal array index.
Definition: Array.h:283
ogdf::Array::Array
Array(const Array< E, INDEX > &A)
Creates an array that is a copy of A.
Definition: Array.h:251
ogdf::ArrayReverseIteratorBase::ArrayReverseIteratorBase
ArrayReverseIteratorBase(E *pX)
Constructs an iterator that points to E* pX.
Definition: Array.h:73
ogdf::Array::swap
void swap(INDEX i, INDEX j)
Swaps the elements at position i and j.
Definition: Array.h:497
ogdf::Array::deconstruct
void deconstruct()
Deallocates array.
Definition: Array.h:891
ogdf::InOutPoint
Representation of an in- or outpoint.
Definition: IOPoints.h:42
ogdf::ArrayReverseIteratorBase
Random-access reverse iterator based on a pointer to an array element.
Definition: Array.h:47
ogdf::Array::leftShift
void leftShift(ArrayBuffer< INDEX, INDEX > &ind)
Removes the components listed in ind by shifting the remaining components to the left.
Definition: Array.h:963
ogdf::Array::permute
void permute()
Randomly permutes the array.
Definition: Array.h:513
ogdf::ArrayReverseIteratorBase::operator[]
const Elem & operator[](std::size_t idx) const
Const member access operator.
Definition: Array.h:189
ogdf::Array::Array
Array()
Creates an array with empty index set.
Definition: Array.h:226
ogdf::Array< ogdf::InOutPoint * >::iterator
ArrayIterator< ogdf::InOutPoint * > iterator
Provides a random-access iterator that can read or modify any element in an array.
Definition: Array.h:219
ogdf::ArrayReverseIteratorBase::operator-
ArrayReverseIteratorBase< E, isConst > operator-(const int &rhs)
Subtraction operator with int on the right-hand side.
Definition: Array.h:163
ogdf::Array::m_pStop
E * m_pStop
Successor of last element (address of A[m_high+1]).
Definition: Array.h:689
ogdf::Array::init
void init()
Reinitializes the array to an array with empty index set.
Definition: Array.h:358
ogdf::Array::end
const_iterator end() const
Returns a const iterator to one past the last element.
Definition: Array.h:326
OGDF_NEW_DELETE
#define OGDF_NEW_DELETE
Makes the class use OGDF's memory allocator.
Definition: memory.h:84
ogdf::ArrayReverseIteratorBase::operator--
ArrayReverseIteratorBase< E, isConst > & operator--()
Decrement operator (prefix).
Definition: Array.h:126
ogdf::Array::expandArray
void expandArray(INDEX add)
Used by grow() to enlarge the array.
Definition: Array.h:777
ogdf::Array::crend
const_reverse_iterator crend() const
Returns a const reverse iterator to one before the first element.
Definition: Array.h:347
ogdf::ArrayReverseIteratorBase::ArrayReverseIteratorBase
ArrayReverseIteratorBase(const E *pX)
Constructs an iterator that points to const E* pX.
Definition: Array.h:77
ogdf::Array::operator=
Array< E, INDEX > & operator=(Array< E, INDEX > &&A)
Assignment operator (move semantics).
Definition: Array.h:446
ogdf::Array::leftShift
void leftShift(ArrayBuffer< INDEX, INDEX > &ind, const E &val)
Removes the components listed in ind by shifting the remaining components to the left.
Definition: Array.h:677
ogdf::Array::permute
void permute(INDEX l, INDEX r)
Randomly permutes the subarray with index set [l..r].
Definition: Array.h:507
ogdf::Array::init
void init(INDEX a, INDEX b, const E &x)
Reinitializes the array to an array with index set [a..b] and sets all entries to x.
Definition: Array.h:380
ogdf::Array::m_low
INDEX m_low
The lowest index.
Definition: Array.h:690
r
int r[]
Definition: hierarchical-ranking.cpp:8
ogdf::Array::quicksort
void quicksort(INDEX l, INDEX r, const COMPARER &comp)
Sorts the subarray with index set [l, ..., r] using Quicksort and a user-defined comparer comp.
Definition: Array.h:643
ogdf::ArrayReverseIteratorBase::operator--
ArrayReverseIteratorBase< E, isConst > operator--(int)
Decrement operator (postfix).
Definition: Array.h:132
ogdf::Array::quicksortInt
static void quicksortInt(E *pL, E *pR, const COMPARER &comp)
Internal Quicksort implementation with comparer template.
Definition: Array.h:743
ogdf::ArrayReverseIteratorBase::operator-
int operator-(ArrayReverseIteratorBase< E, isArgConst > &rhs)
Subtraction operator.
Definition: Array.h:169
ogdf::ArrayReverseIteratorBase::operator+
ArrayReverseIteratorBase< E, isConst > operator+(const int &rhs)
Addition operator with int on the right-hand side.
Definition: Array.h:151
ogdf::Array::init
void init(INDEX s)
Reinitializes the array to an array with index set [0..s-1].
Definition: Array.h:367
backward::Color::type
type
Definition: backward.hpp:1716
ogdf::ArrayReverseIteratorBase::operator++
ArrayReverseIteratorBase< E, isConst > operator++(int)
Increment operator (postfix).
Definition: Array.h:119
OGDF_THROW
#define OGDF_THROW(CLASS)
Replacement for throw.
Definition: exceptions.h:65
ogdf::Array::binarySearch
int binarySearch(const E &e, const COMPARER &comp) const
Performs a binary search for element e with comparer comp.
Definition: Array.h:569
backward::details::move
const T & move(const T &v)
Definition: backward.hpp:243
ogdf::Array
The parameterized class Array implements dynamic arrays of type E.
Definition: Array.h:204
ogdf::Array::binarySearch
INDEX binarySearch(INDEX l, INDEX r, const E &e, const COMPARER &comp) const
Performs a binary search for element e within the array section [l, ..., r] with comparer comp.
Definition: Array.h:579
ogdf::ArrayReverseIteratorBase::operator++
ArrayReverseIteratorBase< E, isConst > & operator++()
Increment operator (prefix).
Definition: Array.h:113
ogdf::Array::Array
Array(Array< E, INDEX > &&A)
Creates an array containing the elements of A (move semantics).
Definition: Array.h:259
ogdf::Array::expandArrayHelper
void expandArrayHelper(INDEX sOld, INDEX sNew)
Used by expandArray() to reallocate the array elements.
Definition: Array.h:717
ogdf::Array::rbegin
reverse_iterator rbegin()
Returns an reverse iterator to the last element.
Definition: Array.h:332
ogdf::Array::rbegin
const_reverse_iterator rbegin() const
Returns a const reverse iterator to the last element.
Definition: Array.h:335
ogdf::Array::operator[]
const_reference operator[](INDEX i) const
Returns a reference to the element at position i.
Definition: Array.h:292
ogdf::ArrayReverseIteratorBase::operator+
friend ArrayReverseIteratorBase< E, isConst > operator+(const int &lhs, ArrayReverseIteratorBase< E, isConst > rhs)
Addition operator with int on the left-hand side. Returns the same result as addition with int on the...
Definition: Array.h:157
ogdf::ArrayBuffer::size
INDEX size() const
Returns number of elements in the buffer.
Definition: ArrayBuffer.h:122
ogdf::Array::fill
void fill(const E &x)
Sets all elements to x.
Definition: Array.h:387
ogdf::Array::init
void init(INDEX a, INDEX b)
Reinitializes the array to an array with index set [a..b].
Definition: Array.h:373
ogdf::ArrayReverseIteratorBase::ArrayReverseIteratorBase
ArrayReverseIteratorBase(const ArrayReverseIteratorBase< E, isArgConst > &it)
Constructs an iterator that is a copy of it.
Definition: Array.h:84
ogdf::Array::begin
const_iterator begin() const
Returns a const iterator to the first element.
Definition: Array.h:317
ogdf::operator<<
std::ostream & operator<<(std::ostream &os, const ogdf::Array< E, INDEX > &a)
Prints array a to output stream os.
Definition: Array.h:949
ogdf::Array::begin
iterator begin()
Returns an iterator to the first element.
Definition: Array.h:314
ogdf::ArrayReverseIteratorBase::operator*
Elem & operator*() const
Returns the element this iterator points to.
Definition: Array.h:104
ogdf::Array::rend
reverse_iterator rend()
Returns an reverse iterator to one before the first element.
Definition: Array.h:341
ogdf::Array::operator==
bool operator==(const Array< E, INDEX > &L) const
Equality operator.
Definition: Array.h:464
ogdf::ArrayReverseIteratorBase::operator<=
bool operator<=(ArrayReverseIteratorBase< E, isConst > &it) const
Less-than-or-equals operator.
Definition: Array.h:180
ogdf::Array::fill
void fill(INDEX i, INDEX j, const E &x)
Sets elements in the intervall [i..j] to x.
Definition: Array.h:394
ogdf::Array::end
iterator end()
Returns an iterator to one past the last element.
Definition: Array.h:323
ogdf::Array::quicksort
void quicksort(const COMPARER &comp)
Sorts array using Quicksort and a user-defined comparer comp.
Definition: Array.h:631
ogdf::Array::cend
const_iterator cend() const
Returns a const iterator to one past the last element.
Definition: Array.h:329
ogdf::ArrayReverseIteratorBase::operator[]
Elem & operator[](std::size_t idx)
Member access operator.
Definition: Array.h:186
ogdf::randomSeed
long unsigned int randomSeed()
Returns a random value suitable as initial seed for a random number engine.
ogdf::ArrayReverseIteratorBase::ArrayReverseIteratorBase
ArrayReverseIteratorBase()
Constructs an invalid iterator.
Definition: Array.h:80
Reverse.h
Implementation of the Reverse class for the reverse iteration of containers.
ogdf::Array::resize
void resize(INDEX newSize, const E &x)
Resizes (enlarges or shrinks) the array to hold newSize elements and sets new elements to x.
Definition: Array.h:426
ogdf::Array::m_pStart
E * m_pStart
The real start of the array (address of A[m_low]).
Definition: Array.h:688
ogdf::Array< ogdf::InOutPoint * >::const_iterator
ArrayConstIterator< ogdf::InOutPoint * > const_iterator
Provides a random-access iterator that can read a const element in an array.
Definition: Array.h:217
ogdf::ArrayReverseIteratorBase::Elem
typename std::conditional< isConst, const E, E >::type Elem
The underlying element, depending on isConst.
Definition: Array.h:66
ogdf::Array::operator=
Array< E, INDEX > & operator=(const Array< E, INDEX > &A)
Assignment operator.
Definition: Array.h:436
ogdf::Array::permute
void permute(RNG &rng)
Randomly permutes the array using random number generator rng.
Definition: Array.h:531
ogdf::Array::binarySearch
int binarySearch(const E &e) const
Performs a binary search for element e.
Definition: Array.h:550
ogdf::Array::crbegin
const_reverse_iterator crbegin() const
Returns a const reverse iterator to the last element.
Definition: Array.h:338
ogdf::Array::binarySearch
int binarySearch(INDEX l, INDEX r, const E &e) const
Performs a binary search for element e within the array section [l, ..., r] .
Definition: Array.h:559
ogdf::print
void print(std::ostream &os, const Array< E, INDEX > &a, char delim=' ')
Prints array a to output stream os using delimiter delim.
Definition: Array.h:938
ogdf::ArrayReverseIteratorBase::operator==
bool operator==(const ArrayReverseIteratorBase< E, isConst > &it) const
Equality operator.
Definition: Array.h:94
ogdf::Array::low
INDEX low() const
Returns the minimal array index.
Definition: Array.h:280
ogdf::Array::quicksort
void quicksort()
Sorts array using Quicksort.
Definition: Array.h:617
ogdf::Array::size
INDEX size() const
Returns the size (number of elements) of the array.
Definition: Array.h:286
ogdf::Array::grow
void grow(INDEX add, const E &x)
Enlarges the array by add elements and sets new elements to x.
Definition: Array.h:796
ogdf::Array::~Array
~Array()
Destruction.
Definition: Array.h:269
ogdf::ArrayReverseIteratorBase::m_pX
Elem * m_pX
The pointer to the array element.
Definition: Array.h:69
ogdf::Array::copy
void copy(const Array< E, INDEX > &A)
Constructs a new array which is a copy of A.
Definition: Array.h:902
ogdf::Array::maxSizeInsertionSort
static const int maxSizeInsertionSort
Threshold used by quicksort() such that insertion sort is called for instances smaller than maxSizeIn...
Definition: Array.h:208
ogdf::ArrayReverseIteratorBase::operator>=
bool operator>=(ArrayReverseIteratorBase< E, isConst > &it) const
Greater-than-or-equals operator.
Definition: Array.h:183
ogdf::ArrayReverseIteratorBase::operator-=
ArrayReverseIteratorBase< E, isConst > & operator-=(const int &rhs)
Compound assignment operator (-).
Definition: Array.h:145
ogdf::Array::linearSearch
INDEX linearSearch(const E &e, const COMPARER &comp) const
Performs a linear search for element e with comparer comp.
Definition: Array.h:609
comparer.h
Declarations for Comparer objects.
memory.h
Declaration of memory manager for allocating small pieces of memory.
ogdf::Array::linearSearch
INDEX linearSearch(const E &e) const
Performs a linear search for element e.
Definition: Array.h:596
ogdf::Array::Array
Array(INDEX a, INDEX b)
Creates an array with index set [a..b].
Definition: Array.h:232
ogdf::Array::empty
bool empty() const
Returns true iff there are no elements in the array.
Definition: Array.h:289
ogdf::Array::rend
const_reverse_iterator rend() const
Returns a const reverse iterator to one before the first element.
Definition: Array.h:344
ogdf::Array::Array
Array(std::initializer_list< E > initList)
Creates an array containing the elements in the initializer list initList.
Definition: Array.h:245
ogdf::Array::cbegin
const_iterator cbegin() const
Returns a const iterator to the first element.
Definition: Array.h:320
ogdf::ArrayConstIterator
const E * ArrayConstIterator
Definition: Array.h:48