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 (packed_array &&a)
	Move another aray into me. 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...

packed_array &	operator= (packed_array &&a)
	Move another array. More...

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

void	fill (T value)
	Fill the entier array with the given value. 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 i) const
	Return an array entry. More...

return_type	operator[] (size_t i)
	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

void	swap (packed_array &o)
	Swap two arrays. More...

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 constexpr memory_size_type	memory_usage (memory_size_type size) noexcept
	Return the number of bytes required to create a data structure supporting a given number of elements. More...

static constexpr linear_memory_usage	memory_usage () noexcept

static constexpr memory_size_type	memory_fits (memory_size_type memory) noexcept
	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 89 of file packed_array.h.

Member Typedef Documentation

◆ const_iterator

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 251 of file packed_array.h.

◆ const_reverse_iterator

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 256 of file packed_array.h.

◆ iterator

template<typename T , int B>

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

Iterator over an array.

Definition at line 261 of file packed_array.h.

◆ reverse_iterator

template<typename T , int B>

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

Reverse iterator over an array.

Definition at line 266 of file packed_array.h.

◆ value_type

template<typename T , int B>

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

Type of values containd in the array.

Definition at line 246 of file packed_array.h.

Constructor & Destructor Documentation

◆ packed_array() [1/4]

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 290 of file packed_array.h.

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

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

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

◆ packed_array() [2/4]

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 298 of file packed_array.h.

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

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

◆ packed_array() [3/4]

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

a	The array to copy

Definition at line 304 of file packed_array.h.

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

◆ packed_array() [4/4]

template<typename T , int B>

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

inline

Move another aray into me.

Parameters

a	The array to copy

Definition at line 310 of file packed_array.h.

                                    : m_elements(a.m_elements), m_size(a.m_size) {
         a.m_elements = nullptr;
         a.m_size = 0;
     }

◆ ~packed_array()

template<typename T , int B>

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

inline

Free up all memory used by the array.

Definition at line 318 of file packed_array.h.

318 {resize(0);}

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

Member Function Documentation

◆ begin() [1/2]

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 444 of file packed_array.h.

444 {return iterator(m_elements,0);}

◆ begin() [2/2]

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 451 of file packed_array.h.

451 {return const_iterator(m_elements,0);}

◆ empty()

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 399 of file packed_array.h.

399 {return m_size ==0;}

◆ end() [1/2]

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 458 of file packed_array.h.

458 {return iterator(m_elements,m_size);}

◆ end() [2/2]

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 465 of file packed_array.h.

465 {return const_iterator(m_elements,m_size);}

◆ fill()

template<typename T , int B>

void tpie::packed_array< T, B >::fill ( T value )

inline

Fill the entier array with the given value.

Parameters

value the initialization element

Definition at line 365 of file packed_array.h.

                        {
         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;      
     }

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

◆ find() [1/2]

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 429 of file packed_array.h.

429 {return iterator(m_elements,i);}

◆ find() [2/2]

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 437 of file packed_array.h.

437 {return const_iterator(m_elements,i);}

◆ memory_coefficient()

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 272 of file packed_array.h.

                                       {
         return B/8.0;
     }

◆ memory_fits()

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

inlinestaticconstexprnoexceptinherited

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 118 of file util.h.

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

◆ memory_overhead()

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 280 of file packed_array.h.

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

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

◆ memory_usage()

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

inlinestaticconstexprnoexceptinherited

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 106 of file util.h.

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

◆ operator=() [1/2]

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

a	The array to copy from

Returns: a reference to this array

Definition at line 327 of file packed_array.h.

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

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

◆ operator=() [2/2]

template<typename T , int B>

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

inline

Move another array.

Definition at line 338 of file packed_array.h.

                                                 {
         resize(0);
         std::swap(m_elements, a.m_elements);
         std::swap(m_size, a.m_size);
         return *this;
     }

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

◆ operator[]() [1/2]

template<typename T , int B>

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

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 418 of file packed_array.h.

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

◆ operator[]() [2/2]

template<typename T , int B>

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

inline

Return an array entry.

Parameters

i	the index of the entry to return

Returns: the array entry

Definition at line 407 of file packed_array.h.

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

◆ resize() [1/2]

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 353 of file packed_array.h.

                           {
         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)):nullptr;
     }

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().

◆ resize() [2/2]

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
value	the initialization element

Definition at line 382 of file packed_array.h.

                                    {
         resize(s);
         fill(value);
     }

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

◆ size()

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 392 of file packed_array.h.

392 {return m_size;}

◆ swap()

template<typename T , int B>

void tpie::packed_array< T, B >::swap ( packed_array< T, B > & o )

inline

Swap two arrays.

Definition at line 477 of file packed_array.h.

                                 {
         std::swap(m_elements, o.m_elements);
         std::swap(m_size, o.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

◆ const_iterator

◆ const_reverse_iterator

◆ iterator

◆ reverse_iterator

◆ value_type

Constructor & Destructor Documentation

◆ packed_array() [1/4]

◆ packed_array() [2/4]

◆ packed_array() [3/4]

◆ packed_array() [4/4]

◆ ~packed_array()

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ fill()

◆ find() [1/2]

◆ find() [2/2]

◆ memory_coefficient()

◆ memory_fits()

◆ memory_overhead()

◆ memory_usage()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ resize() [1/2]

◆ resize() [2/2]

◆ size()

◆ swap()

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