Open
Graph Drawing
Framework

  v.2010.10
 
Overview Class Hierarchy Class Index Class List Members Namespaces Source Files

Public Member Functions | Private Member Functions | Static Private Member Functions | Private Attributes | Friends

ogdf::Array< E, INDEX > Class Template Reference

The parameterized class Array<E,INDEX> implements dynamic arrays of type E. More...

#include <ogdf/basic/Array.h>

Inheritance diagram for ogdf::Array< E, INDEX >:
ogdf::ArrayBuffer< E, INDEX >

List of all members.

Public Member Functions

 Array ()
 Creates an array with empty index set.
 Array (INDEX s)
 Creates an array with index set [0..s-1].
 Array (INDEX a, INDEX b)
 Creates an array with index set [a..b].
 Array (INDEX a, INDEX b, const E &x)
 Creates an array with index set [a..b] and initializes each element with x.
 Array (const Array< E > &A)
 Creates an array that is a copy of A.
 ~Array ()
INDEX low () const
 Returns the minimal array index.
INDEX high () const
 Returns the maximal array index.
INDEX size () const
 Returns the size (number of elements) of the array.
E * begin ()
 Returns a pointer to the first element.
const E * begin () const
 Returns a pointer to the first element.
E * end ()
 Returns a pointer to one past the last element.
const E * end () const
 Returns a pointer to one past the last element.
E * rbegin ()
 Returns a pointer to the last element.
const E * rbegin () const
 Returns a pointer to the last element.
E * rend ()
 Returns a pointer to one before the first element.
const E * rend () const
 Returns a pointer to one before the first element.
const E & operator[] (INDEX i) const
 Returns a reference to the element at position i.
E & operator[] (INDEX i)
 Returns a reference to the element at position i.
void swap (INDEX i, INDEX j)
 Swaps the elements at position i and j.
void init ()
 Reinitializes the array to an array with empty index set.
void init (INDEX s)
 Reinitializes the array to an array with index set [0..s-1].
void init (INDEX a, INDEX b)
 Reinitializes the array to an array with index set [a..b].
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.
Array< E, INDEX > & operator= (const Array< E, INDEX > &array2)
 Assignment operator.
void fill (const E &x)
 Sets all elements to x.
void fill (INDEX i, INDEX j, const E &x)
 Sets elements in the intervall [i..j] to x.
void grow (INDEX add, const E &x)
 Enlarges the array by add elements and sets new elements to x.
void grow (INDEX add)
 Enlarges the array by add elements.
void permute (INDEX l, INDEX r)
 Randomly permutes the subarray with index set [l..r].
void permute ()
 Randomly permutes the array.
int binarySearch (const E &x) const
 Performs a binary search for element x.
template<class COMPARER >
int binarySearch (const E &e, const COMPARER &comp) const
 Performs a binary search for element x with comparer comp.
int linearSearch (const E &e) const
 Performs a linear search for element x.
template<class COMPARER >
int linearSearch (const E &e, const COMPARER &comp) const
 Performs a linear search for element x with comparer comp.
void quicksort ()
 Sorts array using Quicksort.
void quicksort (INDEX l, INDEX r)
 Sorts subarray with index set [l..r] using Quicksort.
template<class COMPARER >
void quicksort (const COMPARER &comp)
 Sorts array using Quicksort and a user-defined comparer comp.
template<class COMPARER >
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.
void * operator new (size_t nBytes)
void * operator new (size_t, void *p)
void operator delete (void *p, size_t nBytes)

Private Member Functions

void construct (INDEX a, INDEX b)
 Allocates new array with index set [a..b].
void initialize ()
 Initializes elements with default constructor.
void initialize (const E &x)
 Initializes elements with x.
void deconstruct ()
 Deallocates array.
void copy (const Array< E, INDEX > &A)
 Constructs a new array which is a copy of A.

Static Private Member Functions

template<class COMPARER >
static void quicksortInt (E *pL, E *pR, const COMPARER &comp)
 Internal Quicksort implementation with comparer template.

Private Attributes

E * m_vpStart
 The virtual start of the array (address of A[0]).
E * m_pStart
 The real start of the array (address of A[m_low]).
E * m_pStop
 Successor of last element (address of A[m_high+1]).
INDEX m_low
 The lowest index.
INDEX m_high
 The highest index.

Friends

class ArrayBuffer

Detailed Description

template<class E, class INDEX = int>
class ogdf::Array< E, INDEX >

The parameterized class Array<E,INDEX> implements dynamic arrays of type E.

The template parameter E denotes the element type and the parameter INDEX denotes the index type. The index type must be chosen such that it can express the whole index range of the array instance, as well as its size. The default index type is int, other possible types are short and long long (on 64-bit systems).

Definition at line 120 of file Array.h.

Constructor & Destructor Documentation

template<class E, class INDEX = int>
ogdf::Array< E, INDEX >::Array (  )  [inline]

Creates an array with empty index set.

Definition at line 123 of file Array.h.

template<class E, class INDEX = int>
ogdf::Array< E, INDEX >::Array ( INDEX  s  )  [inline, explicit]

Creates an array with index set [0..s-1].

Definition at line 126 of file Array.h.

template<class E, class INDEX = int>
ogdf::Array< E, INDEX >::Array ( INDEX  a,
INDEX  b 
) [inline]

Creates an array with index set [a..b].

Definition at line 131 of file Array.h.

template<class E, class INDEX = int>
ogdf::Array< E, INDEX >::Array ( INDEX  a,
INDEX  b,
const E &  x 
) [inline]

Creates an array with index set [a..b] and initializes each element with x.

Definition at line 136 of file Array.h.

template<class E, class INDEX = int>
ogdf::Array< E, INDEX >::Array ( const Array< E > &  A  )  [inline]

Creates an array that is a copy of A.

Definition at line 141 of file Array.h.

template<class E, class INDEX = int>
ogdf::Array< E, INDEX >::~Array (  )  [inline]

Definition at line 146 of file Array.h.

Member Function Documentation

template<class E, class INDEX = int>
E* ogdf::Array< E, INDEX >::begin (  )  [inline]

Returns a pointer to the first element.

Definition at line 160 of file Array.h.

template<class E, class INDEX = int>
const E* ogdf::Array< E, INDEX >::begin (  )  const [inline]

Returns a pointer to the first element.

Definition at line 163 of file Array.h.

template<class E, class INDEX = int>
int ogdf::Array< E, INDEX >::binarySearch ( const E &  x  )  const [inline]

Performs a binary search for element x.

Precondition:
The array must be sorted!
Returns:
the index of the found element, and low()-1 if not found.

Definition at line 281 of file Array.h.

template<class E, class INDEX = int>
template<class COMPARER >
int ogdf::Array< E, INDEX >::binarySearch ( const E &  e,
const COMPARER &  comp 
) const [inline]

Performs a binary search for element x with comparer comp.

Precondition:
The array must be sorted according to comp!
Returns:
the index of the found element, and low()-1 if not found.

Definition at line 291 of file Array.h.

template<class E , class INDEX>
void ogdf::Array< E, INDEX >::construct ( INDEX  a,
INDEX  b 
) [private]

Allocates new array with index set [a..b].

Definition at line 482 of file Array.h.

template<class E, class INDEX>
void ogdf::Array< E, INDEX >::copy ( const Array< E, INDEX > &  A  )  [private]

Constructs a new array which is a copy of A.

Definition at line 544 of file Array.h.

template<class E , class INDEX >
void ogdf::Array< E, INDEX >::deconstruct (  )  [private]

Deallocates array.

Definition at line 533 of file Array.h.

template<class E, class INDEX = int>
E* ogdf::Array< E, INDEX >::end (  )  [inline]

Returns a pointer to one past the last element.

Definition at line 166 of file Array.h.

template<class E, class INDEX = int>
const E* ogdf::Array< E, INDEX >::end (  )  const [inline]

Returns a pointer to one past the last element.

Definition at line 169 of file Array.h.

template<class E, class INDEX = int>
void ogdf::Array< E, INDEX >::fill ( const E &  x  )  [inline]

Sets all elements to x.

Definition at line 237 of file Array.h.

template<class E, class INDEX = int>
void ogdf::Array< E, INDEX >::fill ( INDEX  i,
INDEX  j,
const E &  x 
) [inline]

Sets elements in the intervall [i..j] to x.

Definition at line 244 of file Array.h.

template<class E, class INDEX>
void ogdf::Array< E, INDEX >::grow ( INDEX  add,
const E &  x 
)

Enlarges the array by add elements and sets new elements to x.

Note: address of array entries in memory may change!

Parameters:
add is the number of additional elements; add can be negative in order to shrink the array.
x is the inital value of all new elements.

Definition at line 433 of file Array.h.

template<class E, class INDEX>
void ogdf::Array< E, INDEX >::grow ( INDEX  add  ) 

Enlarges the array by add elements.

Note: address of array entries in memory may change!

Parameters:
add is the number of additional elements; add can be negative in order to shrink the array.

Definition at line 458 of file Array.h.

template<class E, class INDEX = int>
INDEX ogdf::Array< E, INDEX >::high (  )  const [inline]

Returns the maximal array index.

Definition at line 154 of file Array.h.

template<class E, class INDEX = int>
void ogdf::Array< E, INDEX >::init ( INDEX  s  )  [inline]

Reinitializes the array to an array with index set [0..s-1].

Notice that the elements contained in the array get discarded!

Reimplemented in ogdf::ArrayBuffer< E, INDEX >, ogdf::ArrayBuffer< int >, and ogdf::ArrayBuffer< ABA_CONSTRAINT * >.

Definition at line 210 of file Array.h.

template<class E, class INDEX = int>
void ogdf::Array< E, INDEX >::init ( INDEX  a,
INDEX  b 
) [inline]

Reinitializes the array to an array with index set [a..b].

Notice that the elements contained in the array get discarded!

Definition at line 216 of file Array.h.

template<class E, class INDEX = int>
void ogdf::Array< E, INDEX >::init ( INDEX  a,
INDEX  b,
const E &  x 
) [inline]

Reinitializes the array to an array with index set [a..b] and sets all entries to x.

Definition at line 223 of file Array.h.

template<class E, class INDEX = int>
void ogdf::Array< E, INDEX >::init (  )  [inline]

Reinitializes the array to an array with empty index set.

Reimplemented in ogdf::ArrayBuffer< E, INDEX >, ogdf::ArrayBuffer< int >, and ogdf::ArrayBuffer< ABA_CONSTRAINT * >.

Definition at line 204 of file Array.h.

template<class E , class INDEX >
void ogdf::Array< E, INDEX >::initialize (  )  [private]

Initializes elements with default constructor.

Definition at line 501 of file Array.h.

template<class E, class INDEX >
void ogdf::Array< E, INDEX >::initialize ( const E &  x  )  [private]

Initializes elements with x.

Definition at line 517 of file Array.h.

template<class E, class INDEX = int>
int ogdf::Array< E, INDEX >::linearSearch ( const E &  e  )  const [inline]

Performs a linear search for element x.

Warning: This method has linear running time! Note that the linear search runs from back to front.

Returns:
the index of the found element, and low()-1 if not found.

Reimplemented in ogdf::ArrayBuffer< E, INDEX >, ogdf::ArrayBuffer< int >, and ogdf::ArrayBuffer< ABA_CONSTRAINT * >.

Definition at line 315 of file Array.h.

template<class E, class INDEX = int>
template<class COMPARER >
int ogdf::Array< E, INDEX >::linearSearch ( const E &  e,
const COMPARER &  comp 
) const [inline]

Performs a linear search for element x with comparer comp.

Warning: This method has linear running time! Note that the linear search runs from back to front.

Returns:
the index of the found element, and low()-1 if not found.

Reimplemented in ogdf::ArrayBuffer< E, INDEX >, ogdf::ArrayBuffer< int >, and ogdf::ArrayBuffer< ABA_CONSTRAINT * >.

Definition at line 328 of file Array.h.

template<class E, class INDEX = int>
INDEX ogdf::Array< E, INDEX >::low (  )  const [inline]

Returns the minimal array index.

Definition at line 151 of file Array.h.

template<class E, class INDEX = int>
void ogdf::Array< E, INDEX >::operator delete ( void *  p,
size_t  nBytes 
) [inline]

Definition at line 425 of file Array.h.

template<class E, class INDEX = int>
void* ogdf::Array< E, INDEX >::operator new ( size_t  nBytes  )  [inline]

Definition at line 425 of file Array.h.

template<class E, class INDEX = int>
void* ogdf::Array< E, INDEX >::operator new ( size_t  ,
void *  p 
) [inline]

Definition at line 425 of file Array.h.

template<class E, class INDEX = int>
Array<E,INDEX>& ogdf::Array< E, INDEX >::operator= ( const Array< E, INDEX > &  array2  )  [inline]

Assignment operator.

Definition at line 230 of file Array.h.

template<class E, class INDEX = int>
const E& ogdf::Array< E, INDEX >::operator[] ( INDEX  i  )  const [inline]

Returns a reference to the element at position i.

Reimplemented in ogdf::ArrayBuffer< E, INDEX >, ogdf::ShellingOrderSet, ogdf::ArrayBuffer< int >, and ogdf::ArrayBuffer< ABA_CONSTRAINT * >.

Definition at line 184 of file Array.h.

template<class E, class INDEX = int>
E& ogdf::Array< E, INDEX >::operator[] ( INDEX  i  )  [inline]

Returns a reference to the element at position i.

Reimplemented in ogdf::ArrayBuffer< E, INDEX >, ogdf::ShellingOrderSet, ogdf::ArrayBuffer< int >, and ogdf::ArrayBuffer< ABA_CONSTRAINT * >.

Definition at line 190 of file Array.h.

template<class E, class INDEX = int>
void ogdf::Array< E, INDEX >::permute (  )  [inline]

Randomly permutes the array.

Definition at line 272 of file Array.h.

template<class E , class INDEX>
void ogdf::Array< E, INDEX >::permute ( INDEX  l,
INDEX  r 
)

Randomly permutes the subarray with index set [l..r].

Definition at line 560 of file Array.h.

template<class E, class INDEX = int>
template<class COMPARER >
void ogdf::Array< E, INDEX >::quicksort ( const COMPARER &  comp  )  [inline]

Sorts array using Quicksort and a user-defined comparer comp.

Parameters:
A is the array to be sorted.
comp is a user-defined comparer; C must be a class providing a less(x,y) method.

Definition at line 351 of file Array.h.

template<class E, class INDEX = int>
void ogdf::Array< E, INDEX >::quicksort ( INDEX  l,
INDEX  r 
) [inline]

Sorts subarray with index set [l..r] using Quicksort.

Definition at line 341 of file Array.h.

template<class E, class INDEX = int>
void ogdf::Array< E, INDEX >::quicksort (  )  [inline]

Sorts array using Quicksort.

Definition at line 336 of file Array.h.

template<class E, class INDEX = int>
template<class COMPARER >
void ogdf::Array< E, INDEX >::quicksort ( INDEX  l,
INDEX  r,
const COMPARER &  comp 
) [inline]

Sorts the subarray with index set [l..r] using Quicksort and a user-defined comparer comp.

Parameters:
l is the left-most position in the range to be sorted.
r is the right-most position in the range to be sorted.
comp is a user-defined comparer; C must be a class providing a less(x,y) method.

Definition at line 363 of file Array.h.

template<class E, class INDEX = int>
template<class COMPARER >
static void ogdf::Array< E, INDEX >::quicksortInt ( E *  pL,
E *  pR,
const COMPARER &  comp 
) [inline, static, private]

Internal Quicksort implementation with comparer template.

Definition at line 396 of file Array.h.

template<class E, class INDEX = int>
const E* ogdf::Array< E, INDEX >::rbegin (  )  const [inline]

Returns a pointer to the last element.

Definition at line 175 of file Array.h.

template<class E, class INDEX = int>
E* ogdf::Array< E, INDEX >::rbegin (  )  [inline]

Returns a pointer to the last element.

Definition at line 172 of file Array.h.

template<class E, class INDEX = int>
const E* ogdf::Array< E, INDEX >::rend (  )  const [inline]

Returns a pointer to one before the first element.

Definition at line 181 of file Array.h.

template<class E, class INDEX = int>
E* ogdf::Array< E, INDEX >::rend (  )  [inline]

Returns a pointer to one before the first element.

Definition at line 178 of file Array.h.

template<class E, class INDEX = int>
INDEX ogdf::Array< E, INDEX >::size (  )  const [inline]

Returns the size (number of elements) of the array.

Reimplemented in ogdf::ArrayBuffer< E, INDEX >, ogdf::ArrayBuffer< int >, and ogdf::ArrayBuffer< ABA_CONSTRAINT * >.

Definition at line 157 of file Array.h.

template<class E, class INDEX = int>
void ogdf::Array< E, INDEX >::swap ( INDEX  i,
INDEX  j 
) [inline]

Swaps the elements at position i and j.

Definition at line 196 of file Array.h.

Friends And Related Function Documentation

template<class E, class INDEX = int>
friend class ArrayBuffer [friend]

Definition at line 370 of file Array.h.

Member Data Documentation

template<class E, class INDEX = int>
INDEX ogdf::Array< E, INDEX >::m_high [private]

The highest index.

Definition at line 377 of file Array.h.

template<class E, class INDEX = int>
INDEX ogdf::Array< E, INDEX >::m_low [private]

The lowest index.

Definition at line 376 of file Array.h.

template<class E, class INDEX = int>
E* ogdf::Array< E, INDEX >::m_pStart [private]

The real start of the array (address of A[m_low]).

Definition at line 374 of file Array.h.

template<class E, class INDEX = int>
E* ogdf::Array< E, INDEX >::m_pStop [private]

Successor of last element (address of A[m_high+1]).

Definition at line 375 of file Array.h.

template<class E, class INDEX = int>
E* ogdf::Array< E, INDEX >::m_vpStart [private]

The virtual start of the array (address of A[0]).

Definition at line 373 of file Array.h.

The documentation for this class was generated from the following file:
© 1999-2010 by oreas GmbH, © 2005-2010 by Technische Universität Dortmund, University of Jena and University of Cologne.

Generated on Wed Oct 20 2010 11:14:11 by doxygen 1.7.1.