An array storring elements of type T using B bits to to store a element. More...

#include <tpie/packed_array.h>

Inherits tpie::linear_memory_base< packed_array< T, B > >.

Public Types
typedef size_t	storage_type

typedef T	value_type
	Type of values containd in the array. More...

typedef const_iter_base< true >	const_iterator
	Iterator over a const array. More...

typedef const_iter_base< false >	const_reverse_iterator
	Reverse iterator over a const array. More...

typedef iter_base< true >	iterator
	Iterator over an array. More...

typedef iter_base< false >	reverse_iterator
	Reverse iterator over an array. More...

Public Member Functions
	packed_array (size_t s=0)
	Construct array of given size. More...

	packed_array (size_t s, T value)
	Construct array of given size. More...

	packed_array (const packed_array &a)
	Construct a copy of another array. More...

	~packed_array ()
	Free up all memory used by the array. More...

packed_array &	operator= (const packed_array &a)
	Copy elements from another array into this. More...

void	resize (size_t s)
	Change the size of the array. More...

void	resize (size_t s, T value)
	Change the size of the array. More...

size_t	size () const
	Return the size of the array. More...

bool	empty () const
	Check if the array is empty. More...

T	operator[] (size_t t) const
	Return an array entry. More...

return_type	operator[] (size_t t)
	Return a object behaving like a reference to an array entry. More...

iterator	find (size_type i)
	Return an iterator to the i'th element of the array. More...

const_iterator	find (size_type i) const
	Return a const iterator to the i'th element of the array. More...

iterator	begin ()
	Return an iterator to the beginning of the array. More...

const_iterator	begin () const
	Return a const iterator to the beginning of the array. More...

iterator	end ()
	Return an iterator to the end of the array. More...

const_iterator	end () const
	Return a const iterator to the end of the array. More...

reverse_iterator	rbegin ()

const_reverse_iterator	rbegin () const

reverse_iterator	rend ()

const_reverse_iterator	rend () const

Static Public Member Functions
static double	memory_coefficient ()
	Return the memory coefficient of the structure. More...

static double	memory_overhead ()
	Return the memory overhead of the structure. More...

static stream_size_type	memory_usage (stream_size_type size)
	Return the number of bytes required to create a data structure supporting a given number of elements. More...

static memory_size_type	memory_fits (memory_size_type memory)
	Return the maximum number of elements that can be contained in in the structure when it is allowed to fill a given number of bytes. More...

Detailed Description

template<typename T, int B>
class tpie::packed_array< T, B >

An array storring elements of type T using B bits to to store a element.

T must be either bool or int. B must devide the word size, (XXX why?) in reality only 1, 2 or 4 seems usamle

Template Parameters

T	The type of elements to store in the array
B	The number of bits used to store a single element

Definition at line 87 of file packed_array.h.

Member Typedef Documentation

template<typename T , int B>

typedef const_iter_base<true> tpie::packed_array< T, B >::const_iterator

Iterator over a const array.

Definition at line 250 of file packed_array.h.

template<typename T , int B>

typedef const_iter_base<false> tpie::packed_array< T, B >::const_reverse_iterator

Reverse iterator over a const array.

Definition at line 255 of file packed_array.h.

template<typename T , int B>

typedef iter_base<true> tpie::packed_array< T, B >::iterator

Iterator over an array.

Definition at line 260 of file packed_array.h.

template<typename T , int B>

typedef iter_base<false> tpie::packed_array< T, B >::reverse_iterator

Reverse iterator over an array.

Definition at line 265 of file packed_array.h.

template<typename T , int B>

typedef T tpie::packed_array< T, B >::value_type

Type of values containd in the array.

Definition at line 245 of file packed_array.h.

Constructor & Destructor Documentation

template<typename T , int B>

tpie::packed_array< T, B >::packed_array ( size_t s = 0 )

inline

Construct array of given size.

The elements have undefined values

Parameters

s	The number of elements in the array

Definition at line 289 of file packed_array.h.

References tpie::packed_array< T, B >::resize().

Referenced by tpie::packed_array< T, B >::memory_overhead().

289 : m_elements(0), m_size(0) {resize(s);}

tpie::packed_array::resize

void resize(size_t s)

Change the size of the array.

Definition: packed_array.h:331

template<typename T , int B>

tpie::packed_array< T, B >::packed_array	(	size_t	s,
		T	value
	)

inline

Construct array of given size.

Parameters

s	The number of elements in the array
value	Each entry of the array is initialized with this value

Definition at line 297 of file packed_array.h.

References tpie::packed_array< T, B >::resize().

297 : m_elements(0), m_size(0) {resize(s,value);}

tpie::packed_array::resize

void resize(size_t s)

Change the size of the array.

Definition: packed_array.h:331

template<typename T , int B>

tpie::packed_array< T, B >::packed_array ( const packed_array< T, B > & a )

inline

Construct a copy of another array.

Parameters

other The array to copy

Definition at line 303 of file packed_array.h.

303 : m_elements(0), m_size(0) {*this=a;}

template<typename T , int B>

tpie::packed_array< T, B >::~packed_array ( )

inline

Free up all memory used by the array.

Definition at line 308 of file packed_array.h.

References tpie::packed_array< T, B >::resize().

308 {resize(0);}

tpie::packed_array::resize

void resize(size_t s)

Change the size of the array.

Definition: packed_array.h:331

Member Function Documentation

template<typename T , int B>

iterator tpie::packed_array< T, B >::begin ( )

inline

Return an iterator to the beginning of the array.

Returns: an iterator tho the beginning of the array

Definition at line 412 of file packed_array.h.

412 {return iterator(m_elements,0);}

tpie::packed_array::iterator

iter_base< true > iterator

Iterator over an array.

Definition: packed_array.h:260

template<typename T , int B>

const_iterator tpie::packed_array< T, B >::begin ( ) const

inline

Return a const iterator to the beginning of the array.

Returns: a const iterator tho the beginning of the array

Definition at line 419 of file packed_array.h.

419 {return const_iterator(m_elements,0);}

tpie::packed_array::const_iterator

const_iter_base< true > const_iterator

Iterator over a const array.

Definition: packed_array.h:250

template<typename T , int B>

bool tpie::packed_array< T, B >::empty ( ) const

inline

Check if the array is empty.

Returns: true if and only if size is 0

Definition at line 367 of file packed_array.h.

367 {return m_size ==0;}

template<typename T , int B>

iterator tpie::packed_array< T, B >::end ( )

inline

Return an iterator to the end of the array.

Returns: an iterator tho the end of the array

Definition at line 426 of file packed_array.h.

426 {return iterator(m_elements,m_size);}

tpie::packed_array::iterator

iter_base< true > iterator

Iterator over an array.

Definition: packed_array.h:260

template<typename T , int B>

const_iterator tpie::packed_array< T, B >::end ( ) const

inline

Return a const iterator to the end of the array.

Returns: a const iterator tho the end of the array

Definition at line 433 of file packed_array.h.

433 {return const_iterator(m_elements,m_size);}

tpie::packed_array::const_iterator

const_iter_base< true > const_iterator

Iterator over a const array.

Definition: packed_array.h:250

template<typename T , int B>

iterator tpie::packed_array< T, B >::find ( size_type i )

inline

Return an iterator to the i'th element of the array.

Parameters

i	the index of the element we want an iterator to

Returns: an iterator to the i'th element

Definition at line 397 of file packed_array.h.

397 {return iterator(m_elements,i);}

tpie::packed_array::iterator

iter_base< true > iterator

Iterator over an array.

Definition: packed_array.h:260

template<typename T , int B>

const_iterator tpie::packed_array< T, B >::find ( size_type i ) const

inline

Return a const iterator to the i'th element of the array.

Parameters

i	the index of the element we want an iterator to

Returns: a const iterator to the i'th element

Definition at line 405 of file packed_array.h.

405 {return const_iterator(m_elements,i);}

tpie::packed_array::const_iterator

const_iter_base< true > const_iterator

Iterator over a const array.

Definition: packed_array.h:250

template<typename T , int B>

static double tpie::packed_array< T, B >::memory_coefficient ( )

inlinestatic

Return the memory coefficient of the structure.

Allocating a structure with n elements will use at most $\lfloor \mathrm{memory\_coefficient} \cdot n + \mathrm{memory\_overhead} \rfloor$ bytes. This does not include memory overhead incurred if the structure is allocated using new.

Returns: The memory coefficient of the structure.

Definition at line 271 of file packed_array.h.

                                              {
         return B/8.0;
     }

static memory_size_type tpie::linear_memory_base< packed_array< T, B > >::memory_fits ( memory_size_type memory )

inlinestaticinherited

Return the maximum number of elements that can be contained in in the structure when it is allowed to fill a given number of bytes.

Parameters

memory The number of bytes the structure is allowed to occupy

Returns: The number of elements that will fit in the structure

Definition at line 93 of file util.h.

                                                                         {
         return static_cast<memory_size_type>(
             floor((memory - child_t::memory_overhead()) / child_t::memory_coefficient()));
     }

template<typename T , int B>

static double tpie::packed_array< T, B >::memory_overhead ( )

inlinestatic

Return the memory overhead of the structure.

See also: memory_coefficient()

Returns: The memory overhead.

Definition at line 279 of file packed_array.h.

References tpie::packed_array< T, B >::packed_array().

                                     {
         return (double)sizeof(packed_array)+(double)sizeof(storage_type);
     }   

static stream_size_type tpie::linear_memory_base< packed_array< T, B > >::memory_usage ( stream_size_type size )

inlinestaticinherited

Return the number of bytes required to create a data structure supporting a given number of elements.

Parameters

size	The number of elements to support

Returns: The amount of memory required in bytes

Definition at line 81 of file util.h.

                                                                        {
         return static_cast<stream_size_type>(
             floor(static_cast<double>(size) * child_t::memory_coefficient() + child_t::memory_overhead()));
     }

template<typename T , int B>

packed_array& tpie::packed_array< T, B >::operator= ( const packed_array< T, B > & a )

inline

Copy elements from another array into this.

Note this array is resized to the size of other

Parameters

other The array to copy from

Returns: a reference to this array

Definition at line 317 of file packed_array.h.

References tpie::packed_array< T, B >::resize().

                                                      {
         resize(a.m_size);
         for(size_t i=0;i<words(m_size);++i)
             m_elements[i] = a.m_elements[i];
         return *this;
     }

template<typename T , int B>

T tpie::packed_array< T, B >::operator[] ( size_t t ) const

inline

Return an array entry.

Parameters

i	the index of the entry to return

Returns: the array entry

Definition at line 375 of file packed_array.h.

                                        {
         assert(t < m_size);
         return static_cast<T>((m_elements[high(t)] >> low(t))&mask());
     }   

template<typename T , int B>

return_type tpie::packed_array< T, B >::operator[] ( size_t t )

inline

Return a object behaving like a reference to an array entry.

Parameters

i	the index of the entry to return

Returns: The object behaving like a reference

Definition at line 386 of file packed_array.h.

                                             {
         assert(t < m_size);
         return return_type(m_elements+high(t), low(t));
     }

template<typename T , int B>

void tpie::packed_array< T, B >::resize ( size_t s )

inline

Change the size of the array.

All elements are lost, after resize the value of the entries is undefined

Parameters

s	the new size of the array

Definition at line 331 of file packed_array.h.

References tpie::tpie_delete_array().

Referenced by tpie::packed_array< T, B >::operator=(), tpie::packed_array< T, B >::packed_array(), tpie::packed_array< T, B >::resize(), and tpie::packed_array< T, B >::~packed_array().

                           {
         if (s == m_size) return;
         tpie_delete_array(m_elements, words(m_size));
         m_size = s;
         m_elements = m_size?tpie_new_array<storage_type>(words(m_size)):0;
     }

template<typename T , int B>

void tpie::packed_array< T, B >::resize	(	size_t	s,
		T	value
	)

inline

Change the size of the array.

All elements are lost, after resize the value of the entries is initialized by a copy of elm

Parameters

s	the new size of the array
elm	the initialization element

Definition at line 346 of file packed_array.h.

References tpie::packed_array< T, B >::resize().

                                    {
         resize(s);
         storage_type x=0;
         for (size_t i=0; i < perword(); ++i) 
             x = (x << B) + ((storage_type)value & mask());
         for (size_t i=0; i < words(m_size); ++i)
             m_elements[i] = x;
     }

template<typename T , int B>

size_t tpie::packed_array< T, B >::size ( ) const

inline

Return the size of the array.

Returns: the size of the array

Definition at line 360 of file packed_array.h.

360 {return m_size;}

The documentation for this class was generated from the following file:

packed_array.h

TPIE

Public Types

Public Member Functions

Static Public Member Functions

Detailed Description

template<typename T, int B> class tpie::packed_array< T, B >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

template<typename T, int B>
class tpie::packed_array< T, B >