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.

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.
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 \dots 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 (in_a,...,in_b) and (out_a,...,out_b) denote the values of the variables (A(a),...,A(b)) before and after the call of sort, then cmp(out_i,out_j) <= 0 for i<= j and there is a permutation pi of [a..b] such that out_i=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(const E&, const E&).
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.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.

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(n log n)) and the binary_search operation takes time O(log n), where n = b-a+1. The space requirement is O(I* sizeof(E)).