Provides support for creating one-dimensional Array objects. More...

#include <jem/util/ArrayBuffer.h>

Public Types
typedef Array< T >::Iterator	Iterator
	A random access iterator type. More...

typedef Iterator	ConstIterator
	Read-only iterator type. More...

Public Member Functions
	ArrayBuffer ()
	Constructs an empty `ArrayBuffer`. More...

	ArrayBuffer (int n)
	Constructs an `ArrayBuffer` with a given size. More...

	ArrayBuffer (const Array< T > &buf)
	Constructs an `ArrayBuffer` with a given buffer array. More...

	ArrayBuffer (const Array< T > &buf, int n)
	Constructs an `ArrayBuffer` with a given buffer array and size. More...

	ArrayBuffer (const ArrayBuffer &rhs)
	Creates a deep copy of another `ArrayBuffer`. More...

template<class InputIterator >
	ArrayBuffer (InputIterator first, InputIterator last)
	Constructs an `ArrayBuffer` given two input iterators. More...

Iterator	begin () const
	Returns an iterator pointing to the begin of this `ArrayBuffer`. More...

Iterator	end () const
	Returns an iterator pointing to the end of this `ArrayBuffer`. More...

T &	front () const
	Returns a reference to the first element in this `ArrayBuffer`. More...

T &	back () const
	Returns a reference to the last element in this `ArrayBuffer`. More...

ArrayBuffer &	operator= (const ArrayBuffer &rhs)
	Copies another `ArrayBuffer`. More...

const ArrayBuffer &	operator= (T rhs) const
	Sets all elements in this `ArrayBuffer` to a given value. More...

void	swap (ArrayBuffer &rhs)
	Swaps the contents of this `ArrayBuffer` with another one. More...

T &	operator[] (int i) const
	Returns the element at a given index. More...

template<class S >
Array< T >	operator[] (const S &s) const
	Returns a slice of this `ArrayBuffer`. More...

void	pushBack (T item)
	Appends an element to this `ArrayBuffer`. More...

void	pushBack (T item, int n)
	Appends multiple copies of an element to this `ArrayBuffer`. More...

template<class InputIterator >
void	pushBack (InputIterator first, InputIterator last)
	Appends the elements between two input iterators to this `ArrayBuffer`. More...

void	popBack ()
	Deletes the last element in this `ArrayBuffer`. More...

void	popBack (int n)
	Deletes multiple elements at the end of this `ArrayBuffer`. More...

void	clear ()
	Deletes all elements from this `ArrayBuffer`. More...

void	resize (int n)
	Adjusts the size of this `ArrayBuffer`. More...

void	reserve (int cap)
	Sets the capacity of this `ArrayBuffer` to a given value. More...

void	setExpansionFactor (float x)
	Sets the expansion factor if this `ArrayBuffer` to a given value. More...

float	getExpansionFactor () const
	Returns the expansion factor of this `ArrayBuffer`. More...

void	trimToSize ()
	Sets the capacity to the size of this `ArrayBuffer`. More...

int	capacity () const
	Returns the capacity of this `ArrayBuffer`. More...

int	size () const
	Returns the size of this `ArrayBuffer`. More...

Array< T >	toArray () const
	Returns the contents of this `ArrayBuffer` as an array. More...

const Array< T > &	getBuffer () const
	Returns a reference to the buffer array. More...

Static Public Attributes
static const float	EXPANSION_FACTOR
	The default expansion factor. More...

Related Functions
(Note that these are not member functions.)
template<class T >
io::DataInput &	operator>> (io::DataInput &in, ArrayBuffer< T > &buf)
	`ArrayBuffer` de-serialization operator More...

template<class T >
io::DataOutput &	operator<< (io::DataOutput &out, const ArrayBuffer< T > &buf)
	`ArrayBuffer` serialization operator. More...

template<class T >
io::TextOutput &	operator<< (io::TextOutput &out, const ArrayBuffer< T > &buf)
	`ArrayBuffer` print operator. More...

template<class T >
void	swap (ArrayBuffer< T > &lhs, ArrayBuffer< T > &rhs)
	Interchanges two `ArrayBuffer` instances. More...

Detailed Description

template<class T>
class jem::util::ArrayBuffer< T >

The template class ArrayBuffer represents a one-dimensional array that can grow and shrink. It is meant to be a helper class for creating array objects of type Array<T,1> of which the size is not known beforehand. Here is an example:

Array<int> readArray ( io::TextInput& in )
{
  ArrayBuffer<int>  buf;
  int               c;
  int               i;
  // Read integers until the end of the text input stream.
  for ( c = in.read(); c >= 0; c = in.read() )
  {
    in.pushBack ( c );
    in >> i;
    buf.pushBack ( i );
  }
  return buf.toArray ();
}

An ArrayBuffer encapsulates a one-dimensional Array object that is said to be the buffer array of the ArrayBuffer object. This buffer array contains the elements in the ArrayBuffer. It is automatically re-allocated whenever new elements are added to the ArrayBuffer and there is no more space in the buffer array. The buffer array is also re-allocated when the ArrayBuffer is given a size – by calling the resize() function – that exceeds the size of the buffer array.

The size of an ArrayBuffer – that is, the number of elements – does not have to equal to the size of its buffer array. The latter is generally larger than the former so that it is not necessary to re-allocate memory for each element that is added to an ArrayBuffer. The size of the buffer array is called the capacity of an ArrayBuffer. The ratio between the capacity and the size of an ArrayBuffer is controlled by its expansion factor. Each time an ArrayBuffer needs to re-allocate memory for additional elements, it multiplies its current capacity with its expansion factor to determine its new capacity. A larger expansion factor therefore leads to a more `aggressive' capacity growth.

Several member functions of the ArrayBuffer class return iterators, pointers and references that refer to an array element. Unless stated otherwise, these iterators, pointers and references are valid as long as the ArrayBuffer is not structurally modified, either by adding/removing elements, or by changing the capacity of the ArrayBuffer.

The facilities provided by the ArrayBuffer class is similar to those provided by the Flex class. They differ on two points. First, an ArrayBuffer can be converted to an Array with almost zero overhead; there is no need to allocate memory and copy the elements into a new object. Second, An ArrayBuffer calls the default constructor of all elements in its buffer array, even of the elements that are not actually in use. Likewise, an ArrayBuffer does not call the destructor of the elements that are removed until the buffer array is re-allocated. This means that the ArrayBuffer class is best used for types T that do not have a constructor or destructor, such as the primitive types int and double.

Note: Some member functions of the ArrayBuffer class return non-const references even though these functions are declared as a const members. The reason is that multiple ArrayBuffer objects and Array objects may point to the same data. Consequently, one can easily modify the elements in an ArrayBuffer object, even if that object is declared const.

See also: Flex.

Member Typedef Documentation

template<class T>

typedef Array<T>::Iterator jem::util::ArrayBuffer< T >::Iterator

A random access iterator type pointing to elements of type T. This iterator fulfills the requirements of the random access iterator category of the standard C++ library.

template<class T>

typedef Iterator jem::util::ArrayBuffer< T >::ConstIterator

This is an alias for the Iterator type. Like the Array class, the ArrayBuffer class does not provide a separate read-only iterator type since multiple ArrayBuffer and Array objects may refer to the same data. Thus, one can easily modify the elements in an ArrayBuffer object even if that object is declared constant.

Constructor & Destructor Documentation

template<class T>

jem::util::ArrayBuffer< T >::ArrayBuffer ( )

Constructs an empty ArrayBuffer. This constructor has the same effect as:

ArrayBuffer ( Array<T>() );

Postcondition: this->size() == 0 && this->capacity() == 0 && this->getExpansionFactor() == EXPANSION_FACTOR

template<class T>

jem::util::ArrayBuffer< T >::ArrayBuffer ( int n )

explicit

Constructs an ArrayBuffer with size n. This constructor has the same effect as:

ArrayBuffer ( Array<T>( n ) );

Parameters

n	- the size of this `ArrayBuffer`.

Precondition: n >= 0

Postcondition: this->size() == n && this->capacity() == n && this->getExpansionFactor() == EXPANSION_FACTOR

template<class T>

jem::util::ArrayBuffer< T >::ArrayBuffer ( const Array< T > & buf )

explicit

Constructs an ArrayBuffer that uses the array buf as its initial buffer array. The elements in this array become the initial elements in the newly created ArrayBuffer. This constructor has the same effect as:

ArrayBuffer ( buf, buf.size() );

Parameters

buf	- the initial buffer array of the newly created `ArrayBuffer`.

Postcondition: this->size() == buf.size() && this->capacity() == buf.size() && this->getExpansionFactor() == EXPANSION_FACTOR

template<class T>

jem::util::ArrayBuffer< T >::ArrayBuffer	(	const Array< T > &	buf,
		int	n
	)

Constructs an ArrayBuffer that uses the array buf as its initial buffer array. The first n elements in this array become the initial elements in the newly created ArrayBuffer. The buffer array is copied by reference. This means that if you modify the contents of the buffer array, you will also modify the contents of the ArrayBuffer.

Note that the array buf is the initial buffer array. A new array will be allocated when additional elements are added to the ArrayBuffer and the buffer array is not large enough.

Parameters

buf	- the initial buffer array.
n	- the initial size of the `ArrayBuffer`.

Precondition: n >= 0 && n <= buf.size()

Postcondition: this->size() == n && this->capacity() == buf.size() && this->getExpansionFactor() == EXPANSION_FACTOR

template<class T>

jem::util::ArrayBuffer< T >::ArrayBuffer ( const ArrayBuffer< T > & rhs )

Creates a deep copy of the rhs ArrayBuffer. That is, the newly created ArrayBuffer and the rhs ArrayBuffer point to distinct memory areas.

Parameters

rhs	- the `ArrayBuffer` to be copied.

Postcondition: this->size() == rhs.size() && this->capacity() == rhs.size() && this->getExpansionFactor() == rhs.getExpansionFactor()

template<class T>

template<class InputIterator >

jem::util::ArrayBuffer< T >::ArrayBuffer	(	InputIterator	first,
		InputIterator	last
	)

Constructs an ArrayBuffer containing copies of the elements between the input iterators first and last. This constructor has the same effect as:

ArrayBuffer ( Array<T>( first, last ) );

Parameters

first	- an input iterator pointing to the first element.
last	- an input iterator pointing one position past the last element.

Precondition: The expression *first can be converted to type T,
and the type T has a copy constructor,
and last is reachable from first.

Postcondition: this->size() == std::distance( first, last ) && this->capacity() == this->size() && this->getExpansionFactor() == EXPANSION_FACTOR

Member Function Documentation

template<class T>

Iterator jem::util::ArrayBuffer< T >::begin ( ) const

Returns an iterator pointing to the first element in this ArrayBuffer, or end() if this ArrayBuffer is empty. The iterator is valid as long as this ArrayBuffer is not structurally modified, either by adding/removing elements, or by changing the capacity of this ArrayBuffer.

Returns: toArray().begin()

template<class T>

Iterator jem::util::ArrayBuffer< T >::end ( ) const

Returns an iterator pointing to one position past the last element in this ArrayBuffer. The iterator is valid as long as this ArrayBuffer is not structurally modified.

Returns: toArray().end()

template<class T>

T& jem::util::ArrayBuffer< T >::front ( ) const

Returns a reference to the first element in this ArrayBuffer. The reference is valid as long as this ArrayBuffer is not structurally modified.

Precondition: size() > 0

Returns: toArray().front()

template<class T>

T& jem::util::ArrayBuffer< T >::back ( ) const

Returns a reference to the last element in this ArrayBuffer. The reference is valid as long as this ArrayBuffer is not structurally modified.

Precondition: size() > 0

Returns: toArray().back()

template<class T>

ArrayBuffer& jem::util::ArrayBuffer< T >::operator= ( const ArrayBuffer< T > & rhs )

Makes a deep copy of the rhs ArrayBuffer. This operator is equivalent with:

if ( size() != rhs.size() )
{
  resize ( rhs.size() );
}
toArray() = rhs.toArray();
return *this;

Parameters

rhs	- the `ArrayBuffer` to be copied.

Postcondition: this->size() == rhs.size() && this->getExpansionFactor() == rhs.getExpansionFactor()

Returns: *this

template<class T>

const ArrayBuffer& jem::util::ArrayBuffer< T >::operator= ( T rhs ) const

Sets all elements in this ArrayBuffer to the value rhs. This operator is equivalent with:

toArray() = rhs;
return *this;

Parameters

rhs	- an instance of type T.

Returns: *this

template<class T>

void jem::util::ArrayBuffer< T >::swap ( ArrayBuffer< T > & rhs )

Swaps the internal state of this ArrayBuffer with that of the rhs ArrayBuffer. Note that this function just swaps a few pointers; it does not swap the individual elements.

Parameters

rhs	- an `ArrayBuffer` instance.

template<class T>

T& jem::util::ArrayBuffer< T >::operator[] ( int i ) const

Returns a reference to the i-th element in this ArrayBuffer. The reference is valid as long as this ArrayBuffer is not structurally modified.

Parameters

i	- a valid index.

Precondition: i >= 0 && i < size()

Returns: toArray()[i]

template<class T>

template<class S >

Array<T> jem::util::ArrayBuffer< T >::operator[] ( const S & s ) const

Returns a one-dimensional Array object that refers to a section of this ArrayBuffer.

Parameters

s	- a `Slice` instance or an instance of a class derived from `Slice`.

Returns: toArray()[s]

template<class T>

void jem::util::ArrayBuffer< T >::pushBack ( T item )

Appends a copy of the object item to the end of this ArrayBuffer. The copy is created by calling the assignment operator of type T. If necessary, the capacity of this ArrayBuffer will be expanded by re-allocating the buffer array.

The time complexity of this function is O(1), provided that the capacity of this ArrayBuffer is large enough.

Parameters

item	- the object to be appended.

Precondition: The type T has an assignment operator.

Postcondition: back() == item

template<class T>

void jem::util::ArrayBuffer< T >::pushBack	(	T	item,
		int	n
	)

Appends n copies of the object item to the end of this ArrayBuffer. The copies are initialized by calling the assignment operator of type T. If necessary, the capacity of this ArrayBuffer will be expanded by re-allocating the buffer array.

The time complexity of this function is O(n), provided that the capacity of this ArrayBuffer is large enough.

Parameters

item	- the object to be copied and appended.
n	- the number of copies to be appended.

Precondition: n >= 0
and the type T has an assignment operator.

template<class T>

template<class InputIterator >

void jem::util::ArrayBuffer< T >::pushBack	(	InputIterator	first,
		InputIterator	last
	)

Appends copies of the elements between the input iterators first and last to the end of this ArrayBuffer. The copies are initialized by calling the assignment operator of type T. If necessary, the capacity of this ArrayBuffer will be expanded by re-allocating the buffer array.

Provided that the capacity of this ArrayBuffer is large enough, the time complexity of this function is O(n) with n the number elements between the two input iterators.

Parameters

first	- an input iterator pointing to the first element to be appended.
last	- an input iterator pointing one position past the lest element to be appended.

Precondition: The type T has an assignment operator,
and the expression *first can be converted to type T,
and last is reachable from first.

Warning: The iterators first and last should not point to elements in this ArrayBuffer, since this function invalidates all such iterators.

template<class T>

void jem::util::ArrayBuffer< T >::popBack ( )

Removes the last element from this ArrayBuffer. The destructor of the element is not called. The capacity of this ArrayBuffer is not modified.

The time complexity of this function is O(1).

Precondition: size() > 0

template<class T>

void jem::util::ArrayBuffer< T >::popBack ( int n )

Removes the last n elements from this ArrayBuffer. The destructors of the elements are not called. The capacity of this ArrayBuffer is not modified.

This function is equivalent with:

int i;
for ( i = 0; i < n; i++ )
{
  popBack();
}

The time complexity of this function is O(n).

Parameters

n	- the number of elements to be deleted.

Precondition: size() >= n

template<class T>

void jem::util::ArrayBuffer< T >::clear ( )

Deletes all elements in this ArrayBuffer. The destructors of the elements are not called. The capacity of this ArrayBuffer is not modified.

Postcondition: size() == 0

template<class T>

void jem::util::ArrayBuffer< T >::resize ( int n )

Sets the size of this ArrayBuffer to n. This function is equivalent with:

if ( n < size() )
{
  popBack ( size() - n );
}
else
{
  pushBack ( T(), n - size() );
}

Parameters

n	- the new size of this flex.

Precondition: n >= 0
and the type T has a default constructor.

Postcondition: size() == n

template<class T>

void jem::util::ArrayBuffer< T >::reserve ( int cap )

If cap is larger than the current capacity, then the capacity of this ArrayBuffer is increased to cap by re-allocating the buffer array. Otherwise, this function does nothing.

Parameters

cap	- the new capacity of this flex.

Postcondition: capacity() >= cap

template<class T>

void jem::util::ArrayBuffer< T >::setExpansionFactor ( float x )

Sets the expansion factor of this ArrayBuffer to the value x.

Parameters

x	- the new expansion factor of this `ArrayBuffer`.

Precondition: x >= 1.0

Postcondition: getExpansionFactor() == x

template<class T>

float jem::util::ArrayBuffer< T >::getExpansionFactor ( ) const

Returns the expansion factor of this ArrayBuffer.

Returns: The expansion factor of this ArrayBuffer.

template<class T>

void jem::util::ArrayBuffer< T >::trimToSize ( )

Re-allocates the buffer array so that its size is equal to the size of this ArrayBuffer.

Postcondition: capacity() == size()

template<class T>

int jem::util::ArrayBuffer< T >::capacity ( ) const

Returns the capacity of this ArrayBuffer.

Returns: getBuffer().size().

template<class T>

int jem::util::ArrayBuffer< T >::size ( ) const

Returns the number of elements stored in this ArrayBuffer.

Returns: The size of this ArrayBuffer.

template<class T>

Array<T> jem::util::ArrayBuffer< T >::toArray ( ) const

Returns an array containing the elements in this ArrayBuffer. The returned array points to the same data as this ArrayBuffer. This means that if you modify the elements in the returned array, you also modify the elements in this ArrayBuffer.

Returns: getBuffer()[ slice(BEGIN,size()) ]

template<class T>

const Array<T>& jem::util::ArrayBuffer< T >::getBuffer ( ) const

Returns a const-reference to the buffer array encapsulated by this ArrayBuffer. The reference remains valid until this ArrayBuffer is structurally modified.

Friends And Related Function Documentation

template<class T >

io::DataInput & operator>>	(	io::DataInput &	in,
		ArrayBuffer< T > &	buf
	)

Parameters

in	- a data input stream.
buf	- the `ArrayBuffer` to be read.

Returns: in

Exceptions

io::IOException	- if an IO error occurs.
io::SerializationException	- if the data input stream is corrupt.

Precondition: The type T defines a de-serialization operator.

template<class T >

io::DataOutput & operator<<	(	io::DataOutput &	out,
		const ArrayBuffer< T > &	buf
	)

Parameters

out	- a data output stream.
buf	- the `ArrayBuffer` to be written.

Returns: out

Exceptions

io::IOException - if an I/O error occurs.

Precondition: The type T defines a serialization operator.

template<class T >

io::TextOutput & operator<<	(	io::TextOutput &	out,
		const ArrayBuffer< T > &	buf
	)

Parameters

out	- a text output stream.
buf	- the `ArrayBuffer` to be printed.

Returns: out

Exceptions

io::IOException - if an I/O error occurs.

Precondition: The type T defines a print operator.

template<class T >

void swap	(	ArrayBuffer< T > &	lhs,
		ArrayBuffer< T > &	rhs
	)

lhs.swap ( rhs )

Parameters

lhs	- an `ArrayBuffer`.
rhs	- another `ArrayBuffer`.

Member Data Documentation

template<class T>

const float jem::util::ArrayBuffer< T >::EXPANSION_FACTOR

static

This floating point constant specifies the default expansion factor of an ArrayBuffer. Its current value is 1.5, but a different value may be used in a future version of Jem.

Public Types

Public Member Functions

Static Public Attributes

Related Functions

Detailed Description

template<class T> class jem::util::ArrayBuffer< T >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation

template<class T>
class jem::util::ArrayBuffer< T >