Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Classes | Public Types | Public Member Functions | Public Attributes | Static Public Attributes | Protected Member Functions | Static Protected Member Functions | Protected Attributes | Private Member Functions | List of all members
Aleph::MemArray< T > Class Template Reference

Simple, scalable and fast dynamic array. More...

#include <tpl_memArray.H>

Inherited by Aleph::ArrayQueue< int >, Aleph::ArrayQueue< Aleph::DynList< int > >, and Aleph::ArrayQueue< T >.

Collaboration diagram for Aleph::MemArray< T >:
[legend]

Classes

struct  Iterator
 Simple iterator on elements of array. More...
 

Public Types

using Item_Type = T
 

Public Member Functions

T * get_ptr () const noexcept
 Return the current base of array.
 
const size_t & get_dim () const noexcept
 Return the current dimension of array.
 
constexpr size_t capacity () const noexcept
 The type of element of array.
 
size_t size () const noexcept
 Return the number of elements.
 
bool is_empty () const noexcept
 Return true is the array is empty.
 
 MemArray (size_t _dim=Min_Dim)
 Construct an array con capacity equal or greater than _dim.
 
 ~MemArray ()
 
void swap (MemArray &a) noexcept
 Swap in constant time this with a
 
 MemArray (const MemArray &a)
 Construct a copy of a
 
 MemArray (MemArray &&a) noexcept
 Construct an array moved of rvalue a
 
MemArray & operator= (const MemArray &a)
 Assign by copy a to this
 
MemArray & operator= (MemArray &&a) noexcept
 Assign by moving a to this
 
void empty () noexcept
 Empties the container.
 
void clear () noexcept
 Alias for empty().
 
void empty_and_release ()
 Empty the array and release all memory.
 
T & put (const T &item)
 Put a copy of item at the end of sequence.
 
T & put (T &&item)
 Move item at the end of sequence.
 
T & push (const T &item)
 Push a copy of item at the beginning of sequence.
 
T & push (T &&item)
 Push a copy of item at the beginning of sequence.
 
T & top () const
 
T remove_first ()
 Remove the first item. Gap is closed.
 
T pop ()
 pop() the most recently pushed item
 
T & append (const T &item)
 
T & append (T &&item)
 
T & insert (const T &item)
 
T & insert (T &&item)
 
void putn (const size_t more)
 Reserve more additional logical slots in the array.
 
MemArray & append (const MemArray &a)
 
void reserve (const size_t cap)
 Reserves cap cells into the array.
 
T get (const size_t i=1)
 Remove i elements from the end.
 
T get_ne (const size_t i=1) noexcept
 
T remove_last ()
 
T & last () const
 Return a modifiable reference to the last element.
 
T & first () const
 Return a modifiable reference to the first element.
 
T & get_first () const
 
T & get_last () const
 
MemArray & reverse ()
 Reverse the order of items in array.
 
T & access (const size_t i) const noexcept
 Return a modifiable reference to the ith element.
 
T & operator[] (const size_t i) const
 Return a reference to the ith element.
 
T & operator() (const size_t i) const noexcept
 
template<class Operation >
bool traverse (Operation &operation)
 Traverse all the elements from index 0 to n - 1 and execute operation on each on them.
 
template<class Operation >
bool traverse (Operation &operation) const
 
template<class Operation >
bool traverse (Operation &&operation) const
 
template<class Operation >
bool traverse (Operation &&operation)
 
bool is_valid () const noexcept
 

Public Attributes

size_t contract_threshold
 

Static Public Attributes

static constexpr size_t Min_Dim = 4
 

Protected Member Functions

void allocate ()
 Allocate memory for the current dimension.
 
bool expand (const size_t first=0)
 Test is array is full and if affrimative, then expand the array twice as long and copy the content by swapping.
 
bool contract (const size_t first=0)
 Test if n is lesser than contract_threshold and eventually contract the array half long and copies its content.
 
void init_dim (size_t d)
 Initialize the dimension of the array to d or to the next two power if d is not a two power.
 

Static Protected Member Functions

static size_t next_power_of_two (const size_t requested)
 

Protected Attributes

T * ptr = nullptr
 
size_t dim = Min_Dim
 
size_t n = 0
 

Private Member Functions

void open_gap (size_t pos=0, size_t num_entries=1)
 
void close_gap (size_t pos, size_t num_entries=1)
 

Detailed Description

template<typename T>
class Aleph::MemArray< T >

Simple, scalable and fast dynamic array.

MemArray implements a totally sequential dynamic array. That is, conditioned to memory availability, the array is stored in a contiguous chunk of memory. So, the access is direct and with exactly the same cost of accessing a normal array.

The array allows inserting and removing elements. These operations are conceived by the ends. The number of stored elements is called n.

The allocation technique obeys to "buddy system"; that is, the exact dimension of array always is an exact two power.

When the array is full, a new chunk twice as long is allocated and the current entries are moved (by move semantic if available).

When the number of entries descends to a contract_threshold the array is half long contracted.

Note
This class is not really conceived for managing a set. Instead, it is conceived as implementation support of single sequentially based set as stacks and queues.

Definition at line 135 of file tpl_memArray.H.

Member Typedef Documentation

◆ Item_Type

template<typename T >
using Aleph::MemArray< T >::Item_Type = T

Definition at line 279 of file tpl_memArray.H.

Constructor & Destructor Documentation

◆ MemArray() [1/3]

template<typename T >
Aleph::MemArray< T >::MemArray ( size_t  _dim = Min_Dim)
inline

Construct an array con capacity equal or greater than _dim.

Parameters
[in]_dimproposed dimension of array which could be adjusted to the next two power greater than _dim
Exceptions
bad_allocif there is not enough memory.

Definition at line 305 of file tpl_memArray.H.

References Aleph::MemArray< T >::allocate(), Aleph::blossom_maximum_cardinality_matching(), and Aleph::MemArray< T >::init_dim().

◆ ~MemArray()

template<typename T >
Aleph::MemArray< T >::~MemArray ( )
inline

Definition at line 313 of file tpl_memArray.H.

References Aleph::MemArray< T >::ptr.

◆ MemArray() [2/3]

template<typename T >
Aleph::MemArray< T >::MemArray ( const MemArray< T > &  a)
inline

Construct a copy of a

Definition at line 332 of file tpl_memArray.H.

References Aleph::MemArray< T >::allocate(), Aleph::MemArray< T >::n, and Aleph::MemArray< T >::ptr.

◆ MemArray() [3/3]

template<typename T >
Aleph::MemArray< T >::MemArray ( MemArray< T > &&  a)
inlinenoexcept

Construct an array moved of rvalue a

Definition at line 342 of file tpl_memArray.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::MemArray< T >::swap().

Member Function Documentation

◆ access()

template<typename T >
Aleph::MemArray< T >::access ( const size_t  i) const
inlinenoexcept

Return a modifiable reference to the ith element.

No bound_statics check is performed

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 680 of file tpl_memArray.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::MemArray< T >::ptr.

Referenced by Aleph::ArrayQueue< T >::complete_put(), Aleph::ArrayQueue< T >::front(), Aleph::ArrayQueue< T >::get(), Aleph::ArrayQueue< T >::getn(), Aleph::ArrayQueue< T >::put(), Aleph::ArrayQueue< T >::put(), Aleph::ArrayQueue< T >::rear_item(), and Aleph::ArrayQueue< T >::traverse().

◆ allocate()

template<typename T >
void Aleph::MemArray< T >::allocate ( )
inlineprotected

Allocate memory for the current dimension.

Definition at line 174 of file tpl_memArray.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::MemArray< T >::contract_threshold, Aleph::MemArray< T >::dim, Aleph::is_power_of_2(), and Aleph::MemArray< T >::ptr.

Referenced by Aleph::MemArray< T >::MemArray(), Aleph::MemArray< T >::MemArray(), and Aleph::MemArray< T >::empty_and_release().

◆ append() [1/3]

template<typename T >
MemArray & Aleph::MemArray< T >::append ( const MemArray< T > &  a)
inline

Definition at line 571 of file tpl_memArray.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::MemArray< T >::n, Aleph::MemArray< T >::ptr, Aleph::MemArray< T >::putn(), and Aleph::MemArray< T >::size().

◆ append() [2/3]

template<typename T >
T & Aleph::MemArray< T >::append ( const T &  item)
inline

Definition at line 501 of file tpl_memArray.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::MemArray< T >::ptr, and Aleph::MemArray< T >::put().

Referenced by MemArray_with_30_items::MemArray_with_30_items().

◆ append() [3/3]

template<typename T >
T & Aleph::MemArray< T >::append ( T &&  item)
inline

Definition at line 509 of file tpl_memArray.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::MemArray< T >::ptr, and Aleph::MemArray< T >::put().

◆ capacity()

template<typename T >
constexpr size_t Aleph::MemArray< T >::capacity ( ) const
inlineconstexprnoexcept

The type of element of array.

Return the capacity of array (its dimension)

Definition at line 282 of file tpl_memArray.H.

References Aleph::MemArray< T >::dim.

Referenced by Aleph::FlatMap< Key, T, Compare >::capacity(), Aleph::FlatSet< Key, Compare >::capacity(), Aleph::FlatMap< Key, T, Compare >::make_room(), print(), print(), TEST(), TEST(), and TEST_F().

◆ clear()

template<typename T >
void Aleph::MemArray< T >::clear ( )
inlinenoexcept

Alias for empty().

Exceptions
none
See also
empty()

Definition at line 394 of file tpl_memArray.H.

References Aleph::MemArray< T >::empty().

Referenced by Aleph::FlatSet< Key, Compare >::clear().

◆ close_gap()

template<typename T >
void Aleph::MemArray< T >::close_gap ( size_t  pos,
size_t  num_entries = 1 
)
inlineprivate

Definition at line 445 of file tpl_memArray.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::close_gap(), Aleph::MemArray< T >::get(), Aleph::MemArray< T >::n, and Aleph::MemArray< T >::ptr.

Referenced by Aleph::MemArray< T >::remove_first().

◆ contract()

template<typename T >
bool Aleph::MemArray< T >::contract ( const size_t  first = 0)
inlineprotected

Test if n is lesser than contract_threshold and eventually contract the array half long and copies its content.

contract(first) first testes n with contract_threshold. If it is lesser, then a new array half as long is allocated and the n elements from first are copied.

Parameters
[in]firstindex of first element
Returns
true if the array is reallocated

Definition at line 232 of file tpl_memArray.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::MemArray< T >::contract_threshold, Aleph::MemArray< T >::dim, Aleph::MemArray< T >::first(), Aleph::MemArray< T >::Min_Dim, Aleph::MemArray< T >::n, and Aleph::MemArray< T >::ptr.

Referenced by Aleph::ArrayQueue< T >::get(), Aleph::MemArray< T >::get(), Aleph::MemArray< T >::get_ne(), and Aleph::ArrayQueue< T >::getn().

◆ empty()

template<typename T >
void Aleph::MemArray< T >::empty ( )
inlinenoexcept

Empties the container.

The array size is set to zero, but the allocated memory is not released.

Exceptions
none

Definition at line 384 of file tpl_memArray.H.

References Aleph::MemArray< T >::n.

Referenced by Aleph::MemArray< T >::clear(), Aleph::FlatMap< Key, T, Compare >::empty(), and Aleph::FlatSet< Key, Compare >::empty().

◆ empty_and_release()

template<typename T >
void Aleph::MemArray< T >::empty_and_release ( )
inline

Empty the array and release all memory.

Definition at line 400 of file tpl_memArray.H.

References Aleph::MemArray< T >::allocate(), Aleph::blossom_maximum_cardinality_matching(), Aleph::MemArray< T >::dim, Aleph::MemArray< T >::Min_Dim, Aleph::MemArray< T >::n, and Aleph::MemArray< T >::ptr.

◆ expand()

template<typename T >
bool Aleph::MemArray< T >::expand ( const size_t  first = 0)
inlineprotected

Test is array is full and if affrimative, then expand the array twice as long and copy the content by swapping.

This method first allocates a chunck of 2*dim and then copies from first index the n contained entries to the new chunck.

Parameters
[in]firstindex where is found the first item of array
Returns
true if the array was full and then a new twice as long was allocated
Exceptions
bad_allocif there is no enough memory

Definition at line 192 of file tpl_memArray.H.

References ah_overflow_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::MemArray< T >::contract_threshold, Aleph::MemArray< T >::dim, Aleph::MemArray< T >::first(), Aleph::is_power_of_2(), Aleph::MemArray< T >::n, and Aleph::MemArray< T >::ptr.

Referenced by Aleph::ArrayQueue< T >::put(), Aleph::MemArray< T >::put(), Aleph::ArrayQueue< T >::put(), Aleph::MemArray< T >::put(), and Aleph::ArrayQueue< T >::putn().

◆ first()

template<typename T >
Aleph::MemArray< T >::first ( ) const
inline

Return a modifiable reference to the first element.

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 649 of file tpl_memArray.H.

References ah_underflow_error_if, Aleph::MemArray< T >::n, and Aleph::MemArray< T >::ptr.

Referenced by Aleph::MemArray< T >::contract(), Aleph::MemArray< T >::expand(), and Aleph::MemArray< T >::get_first().

◆ get()

template<typename T >
Aleph::MemArray< T >::get ( const size_t  i = 1)
inline

Remove i elements from the end.

Return the value of the last removed element

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 608 of file tpl_memArray.H.

References ah_underflow_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::MemArray< T >::contract(), Aleph::MemArray< T >::n, and Aleph::MemArray< T >::ptr.

Referenced by Aleph::MemArray< T >::close_gap(), main(), Aleph::FlatMap< Key, T, Compare >::remove_at(), Aleph::FlatSet< Key, Compare >::remove_at(), Aleph::MemArray< T >::remove_last(), Aleph::FlatMap< Key, T, Compare >::sort_and_unique(), and Aleph::FlatSet< Key, Compare >::sort_and_unique().

◆ get_dim()

template<typename T >
const size_t & Aleph::MemArray< T >::get_dim ( ) const
inlinenoexcept

Return the current dimension of array.

Definition at line 155 of file tpl_memArray.H.

References Aleph::MemArray< T >::dim.

◆ get_first()

template<typename T >
T & Aleph::MemArray< T >::get_first ( ) const
inline

Definition at line 656 of file tpl_memArray.H.

References Aleph::MemArray< T >::first().

◆ get_last()

template<typename T >
T & Aleph::MemArray< T >::get_last ( ) const
inline

Definition at line 662 of file tpl_memArray.H.

References Aleph::MemArray< T >::last().

◆ get_ne()

template<typename T >
T Aleph::MemArray< T >::get_ne ( const size_t  i = 1)
inlinenoexcept

Definition at line 622 of file tpl_memArray.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::MemArray< T >::contract(), Aleph::MemArray< T >::n, and Aleph::MemArray< T >::ptr.

◆ get_ptr()

template<typename T >
T * Aleph::MemArray< T >::get_ptr ( ) const
inlinenoexcept

Return the current base of array.

Definition at line 149 of file tpl_memArray.H.

References Aleph::MemArray< T >::ptr.

Referenced by Aleph::FlatMap< Key, T, Compare >::begin(), Aleph::FlatSet< Key, Compare >::begin(), Aleph::FlatMap< Key, T, Compare >::begin(), Aleph::FlatSet< Key, Compare >::data(), Aleph::FlatMap< Key, T, Compare >::end(), Aleph::FlatSet< Key, Compare >::end(), Aleph::FlatMap< Key, T, Compare >::end(), Aleph::FlatMap< Key, T, Compare >::erase(), Aleph::FlatSet< Key, Compare >::insert(), Aleph::FlatMap< Key, T, Compare >::insert(), Aleph::FlatSet< Key, Compare >::insert(), Aleph::FlatMap< Key, T, Compare >::insert(), Aleph::FlatMap< Key, T, Compare >::insert_or_assign(), Aleph::FlatMap< Key, T, Compare >::insert_or_assign(), Aleph::FlatMap< Key, T, Compare >::keys(), Aleph::FlatMap< Key, T, Compare >::keys_data(), Aleph::FlatMap< Key, T, Compare >::make_room(), Aleph::FlatSet< Key, Compare >::make_room(), Aleph::FlatMap< Key, T, Compare >::operator==(), Aleph::FlatMap< Key, T, Compare >::operator[](), Aleph::FlatMap< Key, T, Compare >::operator[](), Aleph::FlatMap< Key, T, Compare >::remove_at(), Aleph::FlatSet< Key, Compare >::remove_at(), Aleph::FlatMap< Key, T, Compare >::sort_and_unique(), Aleph::FlatSet< Key, Compare >::sort_and_unique(), TEST_F(), Aleph::FlatMap< Key, T, Compare >::traverse(), Aleph::FlatMap< Key, T, Compare >::traverse(), and Aleph::FlatSet< Key, Compare >::traverse().

◆ init_dim()

template<typename T >
void Aleph::MemArray< T >::init_dim ( size_t  d)
inlineprotected

Initialize the dimension of the array to d or to the next two power if d is not a two power.

If d is 0 then d is set to Min_Dim.

Parameters
[in]dthe proposed dimension of array

Definition at line 267 of file tpl_memArray.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::MemArray< T >::dim, Aleph::is_power_of_2(), Aleph::MemArray< T >::Min_Dim, and Aleph::MemArray< T >::next_power_of_two().

Referenced by Aleph::MemArray< T >::MemArray().

◆ insert() [1/2]

template<typename T >
T & Aleph::MemArray< T >::insert ( const T &  item)
inline

Definition at line 516 of file tpl_memArray.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::MemArray< T >::ptr, and Aleph::MemArray< T >::push().

◆ insert() [2/2]

template<typename T >
T & Aleph::MemArray< T >::insert ( T &&  item)
inline

Definition at line 524 of file tpl_memArray.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::MemArray< T >::ptr, and Aleph::MemArray< T >::push().

◆ is_empty()

template<typename T >
bool Aleph::MemArray< T >::is_empty ( ) const
inlinenoexcept

Return true is the array is empty.

Definition at line 294 of file tpl_memArray.H.

References Aleph::MemArray< T >::n.

Referenced by Aleph::FlatMap< Key, T, Compare >::is_empty(), Aleph::FlatSet< Key, Compare >::is_empty(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST_F().

◆ is_valid()

template<typename T >
bool Aleph::MemArray< T >::is_valid ( ) const
inlinenoexcept

Definition at line 743 of file tpl_memArray.H.

References Aleph::MemArray< T >::ptr.

◆ last()

template<typename T >
Aleph::MemArray< T >::last ( ) const
inline

Return a modifiable reference to the last element.

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 642 of file tpl_memArray.H.

References ah_underflow_error_if, Aleph::MemArray< T >::n, and Aleph::MemArray< T >::ptr.

Referenced by Aleph::MemArray< T >::get_last().

◆ next_power_of_two()

template<typename T >
static size_t Aleph::MemArray< T >::next_power_of_two ( const size_t  requested)
inlinestaticprotected

Definition at line 161 of file tpl_memArray.H.

References ah_overflow_error_if, and Aleph::blossom_maximum_cardinality_matching().

Referenced by Aleph::MemArray< T >::init_dim(), and Aleph::MemArray< T >::reserve().

◆ open_gap()

template<typename T >
void Aleph::MemArray< T >::open_gap ( size_t  pos = 0,
size_t  num_entries = 1 
)
inlineprivate

Definition at line 439 of file tpl_memArray.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::MemArray< T >::n, Aleph::open_gap(), Aleph::MemArray< T >::ptr, and Aleph::MemArray< T >::putn().

Referenced by Aleph::MemArray< T >::push(), and Aleph::MemArray< T >::push().

◆ operator()()

template<typename T >
T & Aleph::MemArray< T >::operator() ( const size_t  i) const
inlinenoexcept

Definition at line 697 of file tpl_memArray.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::MemArray< T >::dim, and Aleph::MemArray< T >::ptr.

◆ operator=() [1/2]

template<typename T >
MemArray & Aleph::MemArray< T >::operator= ( const MemArray< T > &  a)
inline

Assign by copy a to this

Definition at line 349 of file tpl_memArray.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::MemArray< T >::contract_threshold, Aleph::MemArray< T >::dim, Aleph::MemArray< T >::n, and Aleph::MemArray< T >::ptr.

◆ operator=() [2/2]

template<typename T >
MemArray & Aleph::MemArray< T >::operator= ( MemArray< T > &&  a)
inlinenoexcept

Assign by moving a to this

Definition at line 372 of file tpl_memArray.H.

References Aleph::MemArray< T >::swap().

◆ operator[]()

template<typename T >
T & Aleph::MemArray< T >::operator[] ( const size_t  i) const
inline

Return a reference to the ith element.

Throws out_of_range if i is out of range

Definition at line 688 of file tpl_memArray.H.

References ah_out_of_range_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::MemArray< T >::n, and Aleph::MemArray< T >::ptr.

◆ pop()

template<typename T >
T Aleph::MemArray< T >::pop ( )
inline

pop() the most recently pushed item

Definition at line 495 of file tpl_memArray.H.

References Aleph::MemArray< T >::remove_first().

◆ push() [1/2]

template<typename T >
Aleph::MemArray< T >::push ( const T &  item)
inline

Push a copy of item at the beginning of sequence.

The array expands if this is already full

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 454 of file tpl_memArray.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::MemArray< T >::open_gap(), and Aleph::MemArray< T >::ptr.

Referenced by Aleph::MemArray< T >::insert(), and Aleph::MemArray< T >::insert().

◆ push() [2/2]

template<typename T >
Aleph::MemArray< T >::push ( T &&  item)
inline

Push a copy of item at the beginning of sequence.

The array expands if this is already full

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 467 of file tpl_memArray.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::MemArray< T >::open_gap(), and Aleph::MemArray< T >::ptr.

◆ put() [1/2]

template<typename T >
Aleph::MemArray< T >::put ( const T &  item)
inline

Put a copy of item at the end of sequence.

The array expands if this is already full

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 415 of file tpl_memArray.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::MemArray< T >::expand(), Aleph::MemArray< T >::n, and Aleph::MemArray< T >::ptr.

Referenced by Aleph::FlatMap< Key, T, Compare >::FlatMap(), Aleph::FlatSet< Key, Compare >::FlatSet(), Aleph::MemArray< T >::append(), Aleph::MemArray< T >::append(), and main().

◆ put() [2/2]

template<typename T >
Aleph::MemArray< T >::put ( T &&  item)
inline

Move item at the end of sequence.

The array expands if this is already full

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 428 of file tpl_memArray.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::MemArray< T >::expand(), Aleph::MemArray< T >::n, and Aleph::MemArray< T >::ptr.

◆ putn()

template<typename T >
void Aleph::MemArray< T >::putn ( const size_t  more)
inline

Reserve more additional logical slots in the array.

putn(more) only adjusts the logical size and grows the backing storage if necessary; it does not value-initialize the new entries. Callers must assign to the returned positions before reading them.

Parameters
[in]morenumber of cells to reserve
Exceptions
bad_allocif there is no enough memory

Definition at line 540 of file tpl_memArray.H.

References ah_overflow_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::MemArray< T >::contract_threshold, Aleph::MemArray< T >::dim, Aleph::MemArray< T >::n, and Aleph::MemArray< T >::ptr.

Referenced by Aleph::MemArray< T >::append(), Aleph::FlatMap< Key, T, Compare >::make_room(), Aleph::FlatSet< Key, Compare >::make_room(), and Aleph::MemArray< T >::open_gap().

◆ remove_first()

template<typename T >
T Aleph::MemArray< T >::remove_first ( )
inline

Remove the first item. Gap is closed.

Definition at line 485 of file tpl_memArray.H.

References ah_underflow_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::MemArray< T >::close_gap(), Aleph::MemArray< T >::n, and Aleph::MemArray< T >::ptr.

Referenced by Aleph::MemArray< T >::pop().

◆ remove_last()

template<typename T >
T Aleph::MemArray< T >::remove_last ( )
inline

Definition at line 636 of file tpl_memArray.H.

References Aleph::MemArray< T >::get().

◆ reserve()

template<typename T >
void Aleph::MemArray< T >::reserve ( const size_t  cap)
inline

Reserves cap cells into the array.

Parameters
[in]capnew dimension
Exceptions
bad_allocif there is no enough memory

Definition at line 588 of file tpl_memArray.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::MemArray< T >::contract_threshold, Aleph::MemArray< T >::dim, Aleph::is_power_of_2(), Aleph::MemArray< T >::n, Aleph::MemArray< T >::next_power_of_two(), and Aleph::MemArray< T >::ptr.

Referenced by Aleph::FlatMap< Key, T, Compare >::make_room(), Aleph::FlatMap< Key, T, Compare >::reserve(), and Aleph::FlatSet< Key, Compare >::reserve().

◆ reverse()

template<typename T >
MemArray & Aleph::MemArray< T >::reverse ( )
inline

Reverse the order of items in array.

Definition at line 668 of file tpl_memArray.H.

References Aleph::MemArray< T >::n, and Aleph::MemArray< T >::ptr.

◆ size()

template<typename T >
size_t Aleph::MemArray< T >::size ( ) const
inlinenoexcept

Return the number of elements.

Definition at line 288 of file tpl_memArray.H.

References Aleph::MemArray< T >::n.

Referenced by Aleph::MemArray< T >::append(), Aleph::FlatSet< Key, Compare >::end(), Aleph::FlatSet< Key, Compare >::get_last(), Aleph::FlatMap< Key, T, Compare >::lower_idx(), Aleph::FlatSet< Key, Compare >::lower_idx(), Aleph::FlatMap< Key, T, Compare >::make_room(), Aleph::FlatSet< Key, Compare >::make_room(), Aleph::FlatMap< Key, T, Compare >::match_at(), Aleph::FlatSet< Key, Compare >::match_at(), print(), print(), Aleph::FlatMap< Key, T, Compare >::remove_at(), Aleph::FlatSet< Key, Compare >::remove_at(), Aleph::FlatMap< Key, T, Compare >::size(), Aleph::FlatSet< Key, Compare >::size(), Aleph::FlatMap< Key, T, Compare >::sort_and_unique(), Aleph::FlatSet< Key, Compare >::sort_and_unique(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST_F(), Aleph::FlatSet< Key, Compare >::traverse(), Aleph::FlatMap< Key, T, Compare >::upper_idx(), and Aleph::FlatSet< Key, Compare >::upper_idx().

◆ swap()

template<typename T >
void Aleph::MemArray< T >::swap ( MemArray< T > &  a)
inlinenoexcept

Swap in constant time this with a

Definition at line 323 of file tpl_memArray.H.

References Aleph::MemArray< T >::contract_threshold, Aleph::MemArray< T >::dim, Aleph::MemArray< T >::n, and Aleph::MemArray< T >::ptr.

Referenced by Aleph::MemArray< T >::MemArray(), Aleph::MemArray< T >::operator=(), Aleph::ArrayQueue< T >::swap(), Aleph::FlatMap< Key, T, Compare >::swap(), and Aleph::FlatSet< Key, Compare >::swap().

◆ top()

template<typename T >
T & Aleph::MemArray< T >::top ( ) const
inline

Definition at line 477 of file tpl_memArray.H.

References ah_underflow_error_if, Aleph::MemArray< T >::n, and Aleph::MemArray< T >::ptr.

◆ traverse() [1/4]

template<typename T >
template<class Operation >
bool Aleph::MemArray< T >::traverse ( Operation &&  operation)
inline

Definition at line 738 of file tpl_memArray.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ traverse() [2/4]

template<typename T >
template<class Operation >
bool Aleph::MemArray< T >::traverse ( Operation &&  operation) const
inline

Definition at line 731 of file tpl_memArray.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ traverse() [3/4]

template<typename T >
template<class Operation >
Aleph::MemArray< T >::traverse ( Operation &  operation)
inline

Traverse all the elements from index 0 to n - 1 and execute operation on each on them.

Parameters
[in]operationto be performed on each element
Returns
true if operation was executed on all elements; false otherwise.

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 712 of file tpl_memArray.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::MemArray< T >::n, and Aleph::MemArray< T >::ptr.

Referenced by Aleph::MemArray< T >::traverse().

◆ traverse() [4/4]

template<typename T >
template<class Operation >
bool Aleph::MemArray< T >::traverse ( Operation &  operation) const
inline

Definition at line 724 of file tpl_memArray.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::MemArray< T >::traverse().

Member Data Documentation

◆ contract_threshold

template<typename T >
size_t Aleph::MemArray< T >::contract_threshold
mutable

Definition at line 146 of file tpl_memArray.H.

Referenced by Aleph::MemArray< T >::allocate(), Aleph::MemArray< T >::contract(), Aleph::MemArray< T >::expand(), Aleph::MemArray< T >::operator=(), Aleph::MemArray< T >::putn(), Aleph::MemArray< T >::reserve(), and Aleph::MemArray< T >::swap().

◆ dim

template<typename T >
size_t Aleph::MemArray< T >::dim = Min_Dim
protected

Definition at line 142 of file tpl_memArray.H.

Referenced by Aleph::MemArray< T >::allocate(), Aleph::MemArray< T >::capacity(), Aleph::MemArray< T >::contract(), Aleph::MemArray< T >::empty_and_release(), Aleph::MemArray< T >::expand(), Aleph::ArrayQueue< T >::front(), Aleph::MemArray< T >::get_dim(), Aleph::ArrayQueue< T >::increase_index(), Aleph::MemArray< T >::init_dim(), Aleph::MemArray< T >::operator()(), Aleph::MemArray< T >::operator=(), Aleph::MemArray< T >::putn(), Aleph::ArrayQueue< T >::putn(), Aleph::ArrayQueue< T >::rear_item(), Aleph::MemArray< T >::reserve(), and Aleph::MemArray< T >::swap().

◆ Min_Dim

template<typename T >
constexpr size_t Aleph::MemArray< T >::Min_Dim = 4
staticconstexpr

Definition at line 138 of file tpl_memArray.H.

Referenced by Aleph::MemArray< T >::contract(), Aleph::MemArray< T >::empty_and_release(), and Aleph::MemArray< T >::init_dim().

◆ n

template<typename T >
size_t Aleph::MemArray< T >::n = 0
protected

Definition at line 143 of file tpl_memArray.H.

Referenced by Aleph::MemArray< T >::MemArray(), Aleph::MemArray< T >::append(), Aleph::MemArray< T >::close_gap(), Aleph::ArrayQueue< T >::complete_put(), Aleph::MemArray< T >::contract(), Aleph::MemArray< T >::empty(), Aleph::MemArray< T >::empty_and_release(), Aleph::MemArray< T >::expand(), Aleph::MemArray< T >::first(), Aleph::ArrayQueue< T >::front(), Aleph::ArrayQueue< T >::get(), Aleph::MemArray< T >::get(), Aleph::MemArray< T >::get_ne(), Aleph::ArrayQueue< T >::getn(), Aleph::MemArray< T >::is_empty(), Aleph::MemArray< T >::last(), Aleph::MemArray< T >::open_gap(), Aleph::MemArray< T >::operator=(), Aleph::MemArray< T >::operator[](), Aleph::MemArray< T >::put(), Aleph::MemArray< T >::put(), Aleph::MemArray< T >::putn(), Aleph::ArrayQueue< T >::putn(), Aleph::ArrayQueue< T >::rear(), Aleph::ArrayQueue< T >::recenter_indices(), Aleph::MemArray< T >::remove_first(), Aleph::MemArray< T >::reserve(), Aleph::MemArray< T >::reverse(), Aleph::MemArray< T >::size(), Aleph::MemArray< T >::swap(), Aleph::MemArray< T >::top(), Aleph::ArrayQueue< T >::traverse(), and Aleph::MemArray< T >::traverse().

◆ ptr

template<typename T >
T* Aleph::MemArray< T >::ptr = nullptr
protected

Definition at line 141 of file tpl_memArray.H.

Referenced by Aleph::MemArray< T >::MemArray(), Aleph::MemArray< T >::~MemArray(), Aleph::MemArray< T >::access(), Aleph::MemArray< T >::allocate(), Aleph::MemArray< T >::append(), Aleph::MemArray< T >::append(), Aleph::MemArray< T >::append(), Aleph::MemArray< T >::close_gap(), Aleph::MemArray< T >::contract(), Aleph::MemArray< T >::empty_and_release(), Aleph::MemArray< T >::expand(), Aleph::MemArray< T >::first(), Aleph::MemArray< T >::get(), Aleph::MemArray< T >::get_ne(), Aleph::MemArray< T >::get_ptr(), Aleph::MemArray< T >::insert(), Aleph::MemArray< T >::insert(), Aleph::MemArray< T >::is_valid(), Aleph::MemArray< T >::last(), Aleph::MemArray< T >::open_gap(), Aleph::MemArray< T >::operator()(), Aleph::MemArray< T >::operator=(), Aleph::MemArray< T >::operator[](), Aleph::MemArray< T >::push(), Aleph::MemArray< T >::push(), Aleph::MemArray< T >::put(), Aleph::MemArray< T >::put(), Aleph::MemArray< T >::putn(), Aleph::MemArray< T >::remove_first(), Aleph::MemArray< T >::reserve(), Aleph::MemArray< T >::reverse(), Aleph::MemArray< T >::swap(), Aleph::MemArray< T >::top(), and Aleph::MemArray< T >::traverse().

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