One Dimensional Arrays ( array )

Definition

An instance A of the parameterized data type array<E> is a mapping from an interval I = [a..b] of integers, the index set of A, to the set of variables of data type E, the element type of A. A(i) is called the element at position i. The array access operator (A[i]) checks its precondition (a < = i < = b). The check can be turned off by compiling with the flag -DLEDA_CHECKING_OFF.

#include < LEDA/array1.h >

Types

array<E>::item	the item type.
array<E>::value_type	the value type.

Creation

array<E>	A(int a, int b)	creates an instance A of type array<E> with index set [a..b].
array<E>	A(int n)	creates an instance A of type array<E> with index set [0..n - 1].
array<E>	A	creates an instance A of type array<E> with empty index set.

Special Constructors

array<E>	A(int low, E x, E y)	creates an instance A of type array<E> with index set [low, low + 1] initialized to [x, y].
array<E>	A(int low, E x, E y, E w)	creates an instance A of type array<E> with index set [low, low + 2] initialized to [x, y, w].
array<E>	A(int low, E x, E y, E z, E w)
		creates an instance A of type array<E> with index set [low, low + 3] initialized to [x, y, z, w].

Operations

Basic Operations

E&	A[int x]	returns A(x). Precondition a < = x < = b.
E&	A.get(int x)	returns A(x). Precondition a < = x < = b.
void	A.set(int x, E e)	sets A(x) = e. Precondition a < = x < = b.
void	A.copy(int x, array<E> B, int y)
		sets A(x) = B(y). Precondition a < = x < = b and B.low() < = y < = B.high().
void	A.copy(int x, int y)	sets A(x) = A(y). Precondition a < = x < = b and low() < = y < = high().
void	A.resize(int a, int b)	sets the index set of A to [a..b] such that for all i $\in$ [a..b] which are not contained in the old index set A(i) is set to the default value of type E.
void	A.resize(int n)	same as A.resize(0,n-1).
int	A.low()	returns the minimal index a of A.
int	A.high()	returns the maximal index b of A.
int	A.size()	returns the size (b - a + 1) of A.
void	A.init(E x)	assigns x to A[i] for every i $\in$ { a...b }.
bool	A.C_style()	returns true if the array has ``C-style'', i.e., the index set is [0..size - 1].
void	A.swap(int i, int j)	swaps the values of A[i] and A[j].
void	A.permute()	the elements of A are randomly permuted.
void	A.permute(int l, int h)	the elements of A[l..h] are randomly permuted.

Sorting and Searching

void	A.sort(int (*cmp)(E, E ))	sorts the elements of A, using function cmp to compare two elements, i.e., if (ina,..., inb) and (outa,..., outb) denote the values of the variables (A(a),..., A(b)) before and after the call of sort, then cmp(outi, outj) < = 0 for i < = j and there is a permutation $\pi$ of [a..b] such that outi = in$\pi$(i) for a < = i < = b.
void	A.sort()	sorts the elements of A according to the linear order of the element type E. Precondition A linear order on E must have been defined by compare(constE&, constE&).
void	A.sort(int (*cmp)(E, E ), int l, int h)
		sorts sub-array A[l..h] using compare function cmp.
void	A.sort(int l, int h)	sorts sub-array A[l..h] using the linear order on E.
int	A.unique()	removes duplicates from A by copying the unique elements of A to A[A.low()],..., A[h] and returns h (A.low()-1 if A is empty). Precondition A is sorted increasingly according to the default ordering of type E.
int	A.binary_search(int (*cmp)(E, E ), E x)
		performs a binary search for x. Returns i with A[i] = x if x in A, A.low() - 1 otherwise. Function cmp is used to compare two elements. Precondition A must be sorted according to cmp.
int	A.binary_search(E x)	as above but uses the default linear order on E.
int	A.binary_locate(int (*cmp)(E, E ), E x)
		Returns the maximal i with A[i] < = x or A.low()-1 if x < A[low]. Function cmp is used to compare elements. Precondition A must be sorted according to cmp.
int	A.binary_locate(E x)	as above but uses the default linear order on E.

Input and Output

void	A.read(istream& I)	reads b - a + 1 objects of type E from the input stream I into the array A using the operator>>(istream&,E&).
void	A.read()	calls A.read(cin) to read A from the standard input stream cin.
void	A.read(string s)	As above, uses string s as prompt.
void	A.print(ostream& O, char space = ' ')
		prints the contents of array A to the output stream O using operator<<(ostream&,const E&) to print each element. The elements are separated by character space.
void	A.print(char space = ' ')	calls A.print(cout, space) to print A on the standard output stream cout.
void	A.print(string s, char space = ' ')
		As above, uses string s as header.
ostream&	ostream& out << A	same as A.print(out); returns out.
istream&	istream& in >> array<E>& A
		same as A.read(in)); returns in.

Iteration STL compatible iterators are provided when compiled with -DLEDA_STL_ITERATORS (see LEDAROOT/demo/stl/array.c for an example).

Implementation

Arrays are implemented by C++vectors. The access operation takes time O(1), the sorting is realized by quicksort (time O(nlog n)) and the binary_search operation takes time O(log n), where n = b - a + 1. The space requirement is O(I*sizeof (E)).