gum::SequenceImplementation< Key, Alloc, Gen > Class Template Reference

The internal class for storing (ordered) sequences of objects. More...

#include <agrum/tools/core/sequence.h>

Collaboration diagram for gum::SequenceImplementation< Key, Alloc, Gen >:

Public Member Functions
template<typename OtherAlloc >
INLINE void	_copy_ (const SequenceImplementation< Key, OtherAlloc, Gen > &aSeq)
template<typename OtherAlloc >
INLINE	SequenceImplementation (const SequenceImplementation< Key, OtherAlloc, Gen > &aSeq)
template<typename OtherAlloc >
INLINE SequenceImplementation< Key, Alloc, Gen > &	operator= (const SequenceImplementation< Key, OtherAlloc, Gen > &aSeq)
template<typename... Args>
INLINE void	emplace (Args &&... args)
template<typename OtherAlloc >
INLINE bool	operator!= (const SequenceImplementation< Key, OtherAlloc, Gen > &k) const
template<typename OtherAlloc >
INLINE void	_copy_ (const SequenceImplementation< Key, OtherAlloc, true > &aSeq)
template<typename Key, typename Alloc>
	SequenceImplementation (const SequenceImplementation< Key, Alloc, true > &aSeq)
template<typename OtherAlloc >
	SequenceImplementation (const SequenceImplementation< Key, OtherAlloc, true > &aSeq)
template<typename Key, typename Alloc>
INLINE	SequenceImplementation (SequenceImplementation< Key, Alloc, true > &&aSeq)
template<typename OtherAlloc >
INLINE SequenceImplementation< Key, Alloc, true > &	operator= (const SequenceImplementation< Key, OtherAlloc, true > &aSeq)
template<typename OtherAlloc >
bool	operator== (const SequenceImplementation< Key, OtherAlloc, true > &k) const
template<typename OtherAlloc >
INLINE bool	operator!= (const SequenceImplementation< Key, OtherAlloc, true > &k) const
Destructor
	~SequenceImplementation () noexcept
	Class destructor. More...
Iterators
iterator_safe	beginSafe () const
	Returns a safe begin iterator. More...
iterator_safe	rbeginSafe () const
	Returns a safe rbegin iterator. More...
const iterator_safe &	endSafe () const noexcept
	Returns the safe end iterator. More...
const iterator_safe &	rendSafe () const noexcept
	Returns the safe rend iterator. More...
iterator	begin () const
	Returns an unsafe begin iterator. More...
iterator	rbegin () const
	Returns an unsafe rbegin iterator. More...
const iterator &	end () const noexcept
	Returns the unsafe end iterator. More...
const iterator &	rend () const noexcept
	Returns the unsafe rend iterator. More...
Operators
SequenceImplementation< Key, Alloc, Gen > &	operator<< (const Key &k)
	Insert k at the end of the sequence (synonym for insert). More...
SequenceImplementation< Key, Alloc, Gen > &	operator<< (Key &&k)
	Insert k at the end of the sequence (synonym for insert). More...
SequenceImplementation< Key, Alloc, Gen > &	operator>> (const Key &k)
	Remove k in the sequence (synonym for erase). More...
const Key &	operator[] (Idx i) const
	Returns the element at position i (synonym for atPos). More...
template<typename OtherAlloc >
bool	operator== (const SequenceImplementation< Key, OtherAlloc, Gen > &k) const
	Returns true if the content of k equals that of *this. More...
template<typename OtherAlloc >
bool	operator!= (const SequenceImplementation< Key, OtherAlloc, Gen > &k) const
	Returns true if the content of k is different from that of *this. More...
Accessors / Modifiers
void	clear ()
	Clear the sequence. More...
Size	size () const noexcept
	Returns the size of the sequence. More...
bool	empty () const noexcept
	Return true if empty. More...
bool	exists (const Key &k) const
	Check the existence of k in the sequence. More...
void	insert (const Key &k)
	Insert an element at the end of the sequence. More...
void	insert (Key &&k)
	Move an element at the end of the sequence. More...
template<typename... Args>
void	emplace (Args &&... args)
	Emplace a new element in the sequence. More...
void	erase (const Key &k)
	Remove an element from the sequence. More...
void	erase (const iterator_safe &k)
	Remove from the sequence the element pointed to by the iterator. More...
const Key &	atPos (Idx i) const
	Returns the object at the pos i. More...
Idx	pos (const Key &key) const
	Returns the position of the object passed in argument (if it exists). More...
void	setAtPos (Idx i, const Key &newKey)
	Change the value. More...
void	setAtPos (Idx i, Key &&newKey)
	Change the value. More...
void	swap (Idx i, Idx j)
	Swap index. More...
const Key &	front () const
	Returns the first element of the element. More...
const Key &	back () const
	Returns the last element of the sequence. More...
std::string	toString () const
	Displays the content of the sequence. More...
void	resize (Size new_size)
	Modifies the size of the internal structures of the sequence. More...

Public Types
using	value_type = Key
	Types for STL compliance. More...
using	reference = Key &
	Types for STL compliance. More...
using	const_reference = const Key &
	Types for STL compliance. More...
using	pointer = Key *
	Types for STL compliance. More...
using	const_pointer = const Key *
	Types for STL compliance. More...
using	size_type = std::size_t
	Types for STL compliance. More...
using	difference_type = std::ptrdiff_t
	Types for STL compliance. More...
using	allocator_type = Alloc
	Types for STL compliance. More...
using	iterator = SequenceIterator< Key >
	Types for STL compliance. More...
using	const_iterator = SequenceIterator< Key >
	Types for STL compliance. More...
using	iterator_safe = SequenceIteratorSafe< Key >
	Types for STL compliance. More...
using	const_iterator_safe = SequenceIteratorSafe< Key >
	Types for STL compliance. More...

Friends
template<typename K , typename A , bool >
class	SequenceImplementation
	Friends to speed up access. More...
class	SequenceIteratorSafe< Key >
	Friends to speed up access. More...
class	Sequence< Key, Alloc >
	Friends to speed up access. More...

Detailed Description

template<typename Key, typename Alloc, bool Gen>
class gum::SequenceImplementation< Key, Alloc, Gen >

The internal class for storing (ordered) sequences of objects.

A SequenceImplementation<Key,Alloc,bool Gen> is a specialized version of of a Sequence<Key,Alloc>. It shall not be used by itself but rather through the Sequence class. A SequenceImplementation is quite similar to a vector<Key> in that it stores an ordered set of elements. The main difference between these two data structures lies in the fact that, given a key, it is possible to retrieve from a SequenceImplementation the index in the vector where the key lies in O(1). As a result, it is not possible to insert a given element twice in the sequence, that is, all the Keys must be different.

When the Boolean template parameter gen is false, SequenceImplementation implements a very generic sequence. This allows having Sequences containing elements of virtually any class or type. When the Boolean gen is equal to true, the SequenceImplementation shall contain only scalar types (integers, floats, pointers, etc). As such, knowning that the element is a scalar enables to optimize the code of the sequences. Determining whether gen should be set to true or false is not left to the developper but is determined by the compiler itself at compile time.

Template Parameters

Key	The elements type stored in the sequence.
Alloc	The values allocator.
Gen	Used for meta-programation.

Definition at line 89 of file sequence.h.

Member Typedef Documentation

allocator_type

template<typename Key, typename Alloc, bool Gen>

using gum::SequenceImplementation< Key, Alloc, Gen >::allocator_type = Alloc

Types for STL compliance.

Definition at line 108 of file sequence.h.

const_iterator

template<typename Key, typename Alloc, bool Gen>

using gum::SequenceImplementation< Key, Alloc, Gen >::const_iterator = SequenceIterator< Key >

Types for STL compliance.

Definition at line 110 of file sequence.h.

const_iterator_safe

template<typename Key, typename Alloc, bool Gen>

using gum::SequenceImplementation< Key, Alloc, Gen >::const_iterator_safe = SequenceIteratorSafe< Key >

Types for STL compliance.

Definition at line 112 of file sequence.h.

const_pointer

template<typename Key, typename Alloc, bool Gen>

using gum::SequenceImplementation< Key, Alloc, Gen >::const_pointer = const Key*

Types for STL compliance.

Definition at line 105 of file sequence.h.

const_reference

template<typename Key, typename Alloc, bool Gen>

using gum::SequenceImplementation< Key, Alloc, Gen >::const_reference = const Key&

Types for STL compliance.

Definition at line 103 of file sequence.h.

difference_type

template<typename Key, typename Alloc, bool Gen>

using gum::SequenceImplementation< Key, Alloc, Gen >::difference_type = std::ptrdiff_t

Types for STL compliance.

Definition at line 107 of file sequence.h.

iterator

template<typename Key, typename Alloc, bool Gen>

using gum::SequenceImplementation< Key, Alloc, Gen >::iterator = SequenceIterator< Key >

Types for STL compliance.

Definition at line 109 of file sequence.h.

iterator_safe

template<typename Key, typename Alloc, bool Gen>

using gum::SequenceImplementation< Key, Alloc, Gen >::iterator_safe = SequenceIteratorSafe< Key >

Types for STL compliance.

Definition at line 111 of file sequence.h.

pointer

template<typename Key, typename Alloc, bool Gen>

using gum::SequenceImplementation< Key, Alloc, Gen >::pointer = Key*

Types for STL compliance.

Definition at line 104 of file sequence.h.

reference

template<typename Key, typename Alloc, bool Gen>

using gum::SequenceImplementation< Key, Alloc, Gen >::reference = Key&

Types for STL compliance.

Definition at line 102 of file sequence.h.

size_type

template<typename Key, typename Alloc, bool Gen>

using gum::SequenceImplementation< Key, Alloc, Gen >::size_type = std::size_t

Types for STL compliance.

Definition at line 106 of file sequence.h.

value_type

template<typename Key, typename Alloc, bool Gen>

using gum::SequenceImplementation< Key, Alloc, Gen >::value_type = Key

Types for STL compliance.

Definition at line 101 of file sequence.h.

Constructor & Destructor Documentation

SequenceImplementation() [1/9]

template<typename Key , typename Alloc >

INLINE gum::SequenceImplementation< Key, Alloc >::SequenceImplementation ( Size  size_param = HashTableConst::default_size )

private

Default constructor.

Parameters

size_param

The intial size of the gum::SequenceImplementation.

Definition at line 287 of file sequence_tpl.h.

                                                                                          :
      _h_(size_param), _end_safe_{*this}, _rend_safe_{*this} {
    GUM_CONSTRUCTOR(SequenceImplementation);
    _rend_safe_._setAtRend_();
    _update_end_();
  }

SequenceImplementation() [2/9]

template<typename Key, typename Alloc >

INLINE gum::SequenceImplementation< Key, Alloc >::SequenceImplementation ( std::initializer_list< Key >  list )

private

Initializer list constructor.

Parameters

list	The initializer list.

Definition at line 296 of file sequence_tpl.h.

                                      :
      _end_safe_{*this},
      _rend_safe_{*this} {
    GUM_CONSTRUCTOR(SequenceImplementation);
    _rend_safe_._setAtRend_();
    for (const auto& elt: list) {
      insert(elt);   // performs the  _update_end_ ()
    }
  }

SequenceImplementation() [3/9]

template<typename Key, typename Alloc, bool Gen>

INLINE gum::SequenceImplementation< Key, Alloc, Gen >::SequenceImplementation ( const SequenceImplementation< Key, Alloc, Gen > &  aSeq )

private

Copy constructor.

Parameters

aSeq	The sequence the elements of which will be copied.

Warning

The elements of the newly constructed sequence are copies of those in aSeq.

Definition at line 309 of file sequence_tpl.h.

                                                            :
      _end_safe_{*this},
      _rend_safe_{*this} {
    GUM_CONS_CPY(SequenceImplementation);
    _rend_safe_._setAtRend_();
    _copy_(aSeq);   // performs the  _update_end_ ()
  }

SequenceImplementation() [4/9]

template<typename Key, typename Alloc, bool Gen>

template<typename OtherAlloc >

gum::SequenceImplementation< Key, Alloc, Gen >::SequenceImplementation ( const SequenceImplementation< Key, OtherAlloc, Gen > &  aSeq )

private

Generalised copy constructor.

Template Parameters

OtherAlloc

The other gum::SequenceImplementation allocator.

Parameters

aSeq	The sequence the elements of which will be copied.

Warning

The elements of the newly constructed sequence are copies of those in aSeq.

SequenceImplementation() [5/9]

template<typename Key, typename Alloc, bool Gen>

INLINE gum::SequenceImplementation< Key, Alloc, Gen >::SequenceImplementation ( SequenceImplementation< Key, Alloc, Gen > &&  aSeq )

private

Move constructor.

Parameters

aSeq	The gum::SequenceImplementation to move/

Definition at line 332 of file sequence_tpl.h.

                                                       :
      _h_(std::move(aSeq._h_)),
      _v_(std::move(aSeq._v_)), _end_safe_{*this}, _rend_safe_{*this} {
    GUM_CONS_MOV(SequenceImplementation);
    _rend_safe_._setAtRend_();
    _update_end_();
  }

~SequenceImplementation()

template<typename Key , typename Alloc >

gum::SequenceImplementation< Key, Alloc >::~SequenceImplementation ( )

noexcept

Class destructor.

Definition at line 343 of file sequence_tpl.h.

                                                                                     {
    GUM_DESTRUCTOR(SequenceImplementation);
  }

SequenceImplementation() [6/9]

template<typename Key, typename Alloc, bool Gen>

template<typename OtherAlloc >

INLINE gum::SequenceImplementation< Key, Alloc, Gen >::SequenceImplementation

(

const SequenceImplementation< Key, OtherAlloc, Gen > &

aSeq

)

Definition at line 321 of file sequence_tpl.h.

                                                                 :
      _end_safe_{*this},
      _rend_safe_{*this} {
    GUM_CONS_CPY(SequenceImplementation);
    _rend_safe_._setAtRend_();
    _copy_(aSeq);   // performs the  _update_end_ ()
  }

SequenceImplementation() [7/9]

template<typename Key, typename Alloc, bool Gen>

template<typename Key, typename Alloc>

gum::SequenceImplementation< Key, Alloc, Gen >::SequenceImplementation

(

const SequenceImplementation< Key, Alloc, true > &

aSeq

)

Definition at line 723 of file sequence_tpl.h.

                                                             :
      _h_(aSeq._h_),
      _v_(aSeq._v_), _end_safe_{*this}, _rend_safe_{*this} {
    GUM_CONS_CPY(SequenceImplementation);
    _rend_safe_._setAtRend_();
    _end_safe_._setAtEnd_();
  }

SequenceImplementation() [8/9]

template<typename Key, typename Alloc, bool Gen>

template<typename OtherAlloc >

gum::SequenceImplementation< Key, Alloc, Gen >::SequenceImplementation

(

const SequenceImplementation< Key, OtherAlloc, true > &

aSeq

)

Definition at line 735 of file sequence_tpl.h.

                                                                  :
      _h_(aSeq.size() / 2),
      _end_safe_{*this}, _rend_safe_{*this} {
    GUM_CONS_CPY(SequenceImplementation);
    _rend_safe_._setAtRend_();
    _copy_(aSeq);
  }

SequenceImplementation() [9/9]

template<typename Key, typename Alloc, bool Gen>

template<typename Key, typename Alloc>

INLINE gum::SequenceImplementation< Key, Alloc, Gen >::SequenceImplementation

(

SequenceImplementation< Key, Alloc, true > &&

aSeq

)

Definition at line 746 of file sequence_tpl.h.

                                                        :
      _h_(std::move(aSeq._h_)),
      _v_(std::move(aSeq._v_)), _end_safe_{*this}, _rend_safe_{*this} {
    GUM_CONS_MOV(SequenceImplementation);
    _rend_safe_._setAtRend_();
    _end_safe_._setAtEnd_();
  }

Member Function Documentation

_copy_() [1/3]

template<typename Key, typename Alloc, bool Gen>

template<typename OtherAlloc >

INLINE void gum::SequenceImplementation< Key, Alloc, Gen >::_copy_

(

const SequenceImplementation< Key, OtherAlloc, Gen > &

aSeq

)

Definition at line 273 of file sequence_tpl.h.

                                                                 {
    clear();

    for (Size i = 0; i < aSeq.size(); ++i) {
      Key& new_key = const_cast< Key& >(_h_.insert(*(aSeq._v_[i]), i).first);
      _v_.push_back(&new_key);
    }

    _update_end_();
  }

_copy_() [2/3]

template<typename Key, typename Alloc, bool Gen>

template<typename OtherAlloc >

void gum::SequenceImplementation< Key, Alloc, Gen >::_copy_ ( const SequenceImplementation< Key, OtherAlloc, Gen > &  aSeq )

private

Clears the current sequence and fill it with copies the element of aSeq.

Template Parameters

OtherAlloc

The other gum::SequenceImplementation allocator.

Parameters

aSeq	The gum::SequenceImplementation to copy.

_copy_() [3/3]

template<typename Key, typename Alloc, bool Gen>

template<typename OtherAlloc >

INLINE void gum::SequenceImplementation< Key, Alloc, Gen >::_copy_

(

const SequenceImplementation< Key, OtherAlloc, true > &

aSeq

)

Definition at line 687 of file sequence_tpl.h.

                                                                  {
    clear();

    for (Size i = 0; i < aSeq.size(); ++i) {
      _h_.insert(aSeq._v_[i], i);
      _v_.push_back(aSeq._v_[i]);
    }

    _update_end_();
  }

_insert_()

template<typename Key, typename Alloc, bool Gen>

void gum::SequenceImplementation< Key, Alloc, Gen >::_insert_ ( HashTableBucket< Key, Idx > &&  bucket )

private

Insert an element at the end of the sequence.

Parameters

bucket

The bucket holing the store to insert.

_update_end_()

template<typename Key , typename Alloc >

INLINE void gum::SequenceImplementation< Key, Alloc >::_update_end_ ( )

privatenoexcept

A method to update the end iterator after changes in the sequence.

Definition at line 258 of file sequence_tpl.h.

                                                                               {
    _end_safe_._setAtEnd_();
  }

atPos()

template<typename Key , typename Alloc >

INLINE const Key & gum::SequenceImplementation< Key, Alloc >::atPos

(

Idx

i

)

const

Returns the object at the pos i.

Parameters

i	The position of the element to return.

Returns

Returns the object at the pos i.

Exceptions

NotFound

Raised if the element does not exist.

Definition at line 483 of file sequence_tpl.h.

                                                                                {
    if (i >= _h_.size()) {
      GUM_ERROR(OutOfBounds, "index " << i << " for a sequence of size" << _h_.size())
    }

    return *(_v_[i]);
  }

back()

template<typename Key , typename Alloc >

INLINE const Key & gum::SequenceImplementation< Key, Alloc >::back

(

)

const

Returns the last element of the sequence.

Returns

Returns the last element of the sequence.

Exceptions

NotFound

Raised if the sequence is empty.

Definition at line 546 of file sequence_tpl.h.

                                                                          {
    return atPos(size() - 1);
  }

begin()

template<typename Key , typename Alloc >

INLINE SequenceIterator< Key > gum::SequenceImplementation< Key, Alloc >::begin

(

)

const

Returns an unsafe begin iterator.

Returns

Returns an unsafe begin iterator.

Definition at line 631 of file sequence_tpl.h.

                                                                                        {
    return SequenceIterator< Key >{*this};
  }

beginSafe()

template<typename Key , typename Alloc >

INLINE SequenceIteratorSafe< Key > gum::SequenceImplementation< Key, Alloc >::beginSafe

(

)

const

Returns a safe begin iterator.

Returns

Returns a safe begin iterator.

Definition at line 603 of file sequence_tpl.h.

                                                                                                {
    return SequenceIteratorSafe< Key >{*this};
  }

clear()

template<typename Key , typename Alloc >

INLINE void gum::SequenceImplementation< Key, Alloc >::clear

(

)

Clear the sequence.

Definition at line 264 of file sequence_tpl.h.

                                                               {
    _h_.clear();
    _v_.clear();
    _update_end_();
  }

emplace() [1/2]

template<typename Key, typename Alloc, bool Gen>

template<typename... Args>

void gum::SequenceImplementation< Key, Alloc, Gen >::emplace

(

Args &&...

args

)

Emplace a new element in the sequence.

The emplace is a method that allows to construct directly an element of type Key by passing to its constructor all the arguments it needs.

Template Parameters

Args	The arguments types passed to the constructor.

Parameters

args	The arguments passed to the constructor.

Exceptions

DuplicateElement

Raised if the sequence contains already k.

emplace() [2/2]

template<typename Key , typename Alloc >

template<typename... Args>

INLINE void gum::SequenceImplementation< Key, Alloc >::emplace

(

Args &&...

args

)

Definition at line 412 of file sequence_tpl.h.

                                                                               {
    Key  key(std::forward< Args >(args)...);
    Key& new_key = const_cast< Key& >(_h_.insert(std::move(key), _h_.size()).first);
    _v_.push_back(&new_key);
    _update_end_();
  }

empty()

template<typename Key , typename Alloc >

INLINE bool gum::SequenceImplementation< Key, Alloc >::empty ( ) const

noexcept

Return true if empty.

Returns

Return true if empty.

Definition at line 43 of file sequence_tpl.h.

                                                                              {
    return _h_.empty();
  }

end()

template<typename Key , typename Alloc >

INLINE const SequenceIterator< Key > & gum::SequenceImplementation< Key, Alloc >::end ( ) const

noexcept

Returns the unsafe end iterator.

Returns

Returns the unsafe end iterator.

Definition at line 638 of file sequence_tpl.h.

                                                                             {
    return _end_safe_;
  }

endSafe()

template<typename Key , typename Alloc >

INLINE const SequenceIteratorSafe< Key > & gum::SequenceImplementation< Key, Alloc >::endSafe ( ) const

noexcept

Returns the safe end iterator.

Returns

Returns the safe end iterator.

Definition at line 610 of file sequence_tpl.h.

                                                                                 {
    return _end_safe_;
  }

erase() [1/2]

template<typename Key, typename Alloc , bool Gen>

INLINE void gum::SequenceImplementation< Key, Alloc, Gen >::erase

(

const Key &

k

)

Remove an element from the sequence.

If the element cannot be found, the function does nothing. In particular, it throws no exception. Complexity \(o(n)\) (need to change the position of at most the n elements).

Parameters

k	The element to remove.

Definition at line 437 of file sequence_tpl.h.

                                                                           {
    // get the position of the element to remove
    Idx pos;

    try {
      pos = _h_[k];
    } catch (NotFound&) { return; }

    // erase the element
    _v_.erase(_v_.begin() + pos);
    for (Idx i = pos, nb_elts = _h_.size() - 1; i < nb_elts; ++i) {
      --_h_[*(_v_[i])];
    }
    _h_.erase(k);

    _update_end_();
  }

erase() [2/2]

template<typename Key, typename Alloc >

INLINE void gum::SequenceImplementation< Key, Alloc >::erase

(

const iterator_safe &

k

)

Remove from the sequence the element pointed to by the iterator.

If the element cannot be found, the function does nothing. In particular, it throws no exception. Complexity \(o(n)\) (need to change the position of at most the n elements)

Parameters

k	The iterator poiting to the element to remove.

Definition at line 457 of file sequence_tpl.h.

                                                                                        {
    if (iter.pos() >= size()) return;

    // erase the element
    Idx  pos = iter.pos();
    Key* key = _v_[pos];
    _v_.erase(_v_.begin() + pos);

    for (Idx i = pos, nb_elts = _h_.size() - 1; i < nb_elts; ++i) {
      --_h_[*(_v_[i])];
    }
    _h_.erase(*key);

    _update_end_();
  }

exists()

template<typename Key, typename Alloc , bool Gen>

INLINE bool gum::SequenceImplementation< Key, Alloc >::exists

(

const Key &

k

)

const

Check the existence of k in the sequence.

The complexity is \(o(1)\).

Parameters

k	The key to check for existence.

Returns

Returns true if k is in the gum::SequenceImplementation.

Definition at line 387 of file sequence_tpl.h.

                                                                                  {
    return _h_.exists(k);
  }

front()

template<typename Key , typename Alloc >

INLINE const Key & gum::SequenceImplementation< Key, Alloc >::front

(

)

const

Returns the first element of the element.

Returns

Returns the first element of the element.

Exceptions

NotFound

Raised if the sequence is empty.

Definition at line 540 of file sequence_tpl.h.

                                                                           {
    return atPos(0);
  }

insert() [1/2]

template<typename Key, typename Alloc , bool Gen>

INLINE void gum::SequenceImplementation< Key, Alloc, Gen >::insert

(

const Key &

k

)

Insert an element at the end of the sequence.

The complexity is \(o(1)\).

Parameters

k	The element to insert.

Exceptions

DuplicateElement

Raised if the sequence contains already k.

Definition at line 393 of file sequence_tpl.h.

                                                                            {
    // k will be added at the end. Insert the new key into the hashtable
    Key& new_key = const_cast< Key& >(_h_.insert(k, _h_.size()).first);
    _v_.push_back(&new_key);
    _update_end_();
  }

insert() [2/2]

template<typename Key, typename Alloc , bool Gen>

INLINE void gum::SequenceImplementation< Key, Alloc, Gen >::insert

(

Key &&

k

)

Move an element at the end of the sequence.

The complexity is \(o(1)\).

Parameters

k	The element to insert.

Exceptions

DuplicateElement

Raised if the sequence contains already k.

Definition at line 402 of file sequence_tpl.h.

                                                                       {
    // k will be added at the end. Insert the new key into the hashtable
    Key& new_key = const_cast< Key& >(_h_.insert(std::move(k), _h_.size()).first);
    _v_.push_back(&new_key);
    _update_end_();
  }

operator!=() [1/3]

template<typename Key, typename Alloc, bool Gen>

template<typename OtherAlloc >

bool gum::SequenceImplementation< Key, Alloc, Gen >::operator!=

(

const SequenceImplementation< Key, OtherAlloc, Gen > &

k

)

const

Returns true if the content of k is different from that of *this.

Note that two sequences are equal if and only if they contain the same variables (using Key::operator==) in the same order.

Template Parameters

OtherAlloc

The other gum::SequenceImplementation allocator.

Parameters

k	The other gum::SequenceImplementation. Returns true if both gum::SequenceImplementation are not equal.

operator!=() [2/3]

template<typename Key, typename Alloc, bool Gen>

template<typename OtherAlloc >

INLINE bool gum::SequenceImplementation< Key, Alloc, Gen >::operator!=

(

const SequenceImplementation< Key, OtherAlloc, Gen > &

k

)

const

Definition at line 588 of file sequence_tpl.h.

                                                                    {
    return !operator==(k);
  }

operator!=() [3/3]

template<typename Key, typename Alloc, bool Gen>

template<typename OtherAlloc >

INLINE bool gum::SequenceImplementation< Key, Alloc, Gen >::operator!=

(

const SequenceImplementation< Key, OtherAlloc, true > &

k

)

const

Definition at line 971 of file sequence_tpl.h.

                                                                     {
    return !operator==(k);
  }

operator<<() [1/2]

template<typename Key, typename Alloc , bool Gen>

INLINE SequenceImplementation< Key, Alloc, Gen > & gum::SequenceImplementation< Key, Alloc, Gen >::operator<<

(

const Key &

k

)

Insert k at the end of the sequence (synonym for insert).

Parameters

k	The key we wish to insert in the sequence.

Returns

Returns this gum::SequenceImplementation.

Exceptions

DuplicateElement

Raised if the sequence contains already k.

Definition at line 422 of file sequence_tpl.h.

                                                                       {
    insert(k);
    return *this;
  }

operator<<() [2/2]

template<typename Key, typename Alloc , bool Gen>

INLINE SequenceImplementation< Key, Alloc, Gen > & gum::SequenceImplementation< Key, Alloc, Gen >::operator<<

(

Key &&

k

)

Insert k at the end of the sequence (synonym for insert).

Parameters

k	The key we wish to insert in the sequence.

Returns

Returns this gum::SequenceImplementation.

Exceptions

DuplicateElement

Raised if the sequence contains already k.

Definition at line 430 of file sequence_tpl.h.

                                                                  {
    insert(std::move(k));
    return *this;
  }

operator=() [1/5]

template<typename Key, typename Alloc, bool Gen>

INLINE SequenceImplementation< Key, Alloc, Gen > & gum::SequenceImplementation< Key, Alloc, Gen >::operator= ( const SequenceImplementation< Key, Alloc, Gen > &  aSeq )

private

Copy operator.

Parameters

aSeq	The sequence to copy.

Returns

Returns a ref to this.

Definition at line 350 of file sequence_tpl.h.

                                                               {
    // avoid self assignment
    if (&aSeq != this) {
      _copy_(aSeq);   // performs the  _update_end_ ()
    }

    return *this;
  }

operator=() [2/5]

template<typename Key, typename Alloc, bool Gen>

template<typename OtherAlloc >

SequenceImplementation< Key, Alloc, Gen >& gum::SequenceImplementation< Key, Alloc, Gen >::operator= ( const SequenceImplementation< Key, OtherAlloc, Gen > &  aSeq )

private

Generalized opy operator.

Template Parameters

OtherAlloc

The other gum::SequenceImplementation allocator.

Parameters

aSeq	The sequence to copy.

Returns

Returns a ref to this.

operator=() [3/5]

template<typename Key, typename Alloc, bool Gen>

INLINE SequenceImplementation< Key, Alloc, Gen > & gum::SequenceImplementation< Key, Alloc, Gen >::operator= ( SequenceImplementation< Key, Alloc, Gen > &&  aSeq )

private

Move operator.

Parameters

aSeq	The sequence to move.

Returns

Returns a ref to this.

Definition at line 373 of file sequence_tpl.h.

                                                          {
    // avoid self assignment
    if (&aSeq != this) {
      _h_ = std::move(aSeq._h_);
      _v_ = std::move(aSeq._v_);
      _update_end_();
    }

    return *this;
  }

operator=() [4/5]

template<typename Key, typename Alloc, bool Gen>

template<typename OtherAlloc >

INLINE SequenceImplementation< Key, Alloc, Gen >& gum::SequenceImplementation< Key, Alloc, Gen >::operator=

(

const SequenceImplementation< Key, OtherAlloc, Gen > &

aSeq

)

Definition at line 364 of file sequence_tpl.h.

                                                                    {
    _copy_(aSeq);   // performs the  _update_end_ ()
    return *this;
  }

operator=() [5/5]

template<typename Key, typename Alloc, bool Gen>

template<typename OtherAlloc >

INLINE SequenceImplementation< Key, Alloc, true >& gum::SequenceImplementation< Key, Alloc, Gen >::operator=

(

const SequenceImplementation< Key, OtherAlloc, true > &

aSeq

)

Definition at line 776 of file sequence_tpl.h.

                                                                     {
    _copy_(aSeq);
    return *this;
  }

operator==() [1/2]

template<typename Key, typename Alloc , bool Gen>

template<typename OtherAlloc >

bool gum::SequenceImplementation< Key, Alloc, Gen >::operator==

(

const SequenceImplementation< Key, OtherAlloc, Gen > &

k

)

const

Returns true if the content of k equals that of *this.

Note that two sequences are equal if and only if they contain the same Keys (using Key::operator==) in the same order.

Template Parameters

OtherAlloc

The other gum::SequenceImplementation allocator.

Parameters

k	The other gum::SequenceImplementation. Returns true if both gum::SequenceImplementation are equal.

Definition at line 573 of file sequence_tpl.h.

                                                                    {
    if (size() != k.size())
      return false;
    else {
      for (Idx i = 0; i < size(); ++i)
        if (*_v_[i] != *(k._v_[i])) return false;
    }

    return true;
  }

operator==() [2/2]

template<typename Key, typename Alloc, bool Gen>

template<typename OtherAlloc >

bool gum::SequenceImplementation< Key, Alloc, Gen >::operator==

(

const SequenceImplementation< Key, OtherAlloc, true > &

k

)

const

Definition at line 956 of file sequence_tpl.h.

                                                                     {
    if (size() != k.size())
      return false;
    else {
      for (Idx i = 0; i < size(); ++i)
        if (_v_[i] != k._v_[i]) return false;
    }

    return true;
  }

operator>>()

template<typename Key, typename Alloc , bool Gen>

INLINE SequenceImplementation< Key, Alloc, true > & gum::SequenceImplementation< Key, Alloc >::operator>>

(

const Key &

k

)

Remove k in the sequence (synonym for erase).

If the element cannot be found, the function does nothing. In particular, it throws no exception.

Parameters

k	The key we wish to remove.

Returns

Returns this gum::SequenceImplementation.

Definition at line 476 of file sequence_tpl.h.

                                                                       {
    erase(k);
    return *this;
  }

operator[]()

template<typename Key , typename Alloc >

INLINE const Key & gum::SequenceImplementation< Key, Alloc >::operator[]

(

Idx

i

)

const

Returns the element at position i (synonym for atPos).

Parameters

i	The position of the element to return.

Returns

Returns the element at position i.

Exceptions

OutOfBounds

Raised if the element does not exist.

Definition at line 493 of file sequence_tpl.h.

                                                                                     {
    return atPos(i);
  }

pos()

template<typename Key, typename Alloc , bool Gen>

INLINE Idx gum::SequenceImplementation< Key, Alloc >::pos

(

const Key &

key

)

const

Returns the position of the object passed in argument (if it exists).

Parameters

key	The element for which the positon is returned.

Returns

Returns the position of the object passed in argument.

Exceptions

NotFound

Raised if the element does not exist.

Definition at line 499 of file sequence_tpl.h.

                                                                                {
    return _h_[key];
  }

rbegin()

template<typename Key , typename Alloc >

INLINE SequenceIterator< Key > gum::SequenceImplementation< Key, Alloc >::rbegin

(

)

const

Returns an unsafe rbegin iterator.

Returns

Returns an unsafe rbegin iterator.

Definition at line 644 of file sequence_tpl.h.

                                                                                         {
    SequenceIterator< Key > it{*this};
    it._setPos_(size() - 1);
    return it;
  }

rbeginSafe()

template<typename Key , typename Alloc >

INLINE SequenceIteratorSafe< Key > gum::SequenceImplementation< Key, Alloc >::rbeginSafe

(

)

const

Returns a safe rbegin iterator.

Returns

Returns a safe rbegin iterator.

Definition at line 616 of file sequence_tpl.h.

                                                                                                 {
    SequenceIteratorSafe< Key > it{*this};
    it._setPos_(size() - 1);
    return it;
  }

rend()

template<typename Key , typename Alloc >

INLINE const SequenceIterator< Key > & gum::SequenceImplementation< Key, Alloc >::rend ( ) const

noexcept

Returns the unsafe rend iterator.

Returns

Returns the unsafe rend iterator.

Definition at line 653 of file sequence_tpl.h.

                                                                              {
    return _rend_safe_;
  }

rendSafe()

template<typename Key , typename Alloc >

INLINE const SequenceIteratorSafe< Key > & gum::SequenceImplementation< Key, Alloc >::rendSafe ( ) const

noexcept

Returns the safe rend iterator.

Returns

Returns the safe rend iterator.

Definition at line 625 of file sequence_tpl.h.

                                                                                  {
    return _rend_safe_;
  }

resize()

template<typename Key , typename Alloc >

INLINE void gum::SequenceImplementation< Key, Alloc >::resize

(

Size

new_size

)

Modifies the size of the internal structures of the sequence.

This function is provided for optimization issues. When you know you will have to insert elements into the sequence, it may be faster to use this function prior to the additions because it will change once and for all the sizes of all the internal containers. Note that if you provide a size that is smaller than the number of elements of the sequence, the function will not modify anything.

Parameters

new_size

The internal structure new size.

Definition at line 659 of file sequence_tpl.h.

                                                                             {
    if (new_size < _h_.size()) return;

    _h_.resize(new_size);
    _v_.reserve(new_size);
  }

setAtPos() [1/2]

template<typename Key, typename Alloc , bool Gen>

INLINE void gum::SequenceImplementation< Key, Alloc, Gen >::setAtPos	(	Idx	i,
		const Key &	newKey
	)

Change the value.

Parameters

i	The element's position.
newKey	The element's new value.

Exceptions

NotFound	Raised if the element does not exist.
DuplicateElement	Raised if newKey alreay exists.

Definition at line 505 of file sequence_tpl.h.

                                                                                          {
    if (i >= _h_.size()) { GUM_ERROR(NotFound, "index too large") }

    Key& new_key = const_cast< Key& >(_h_.insert(newKey, i).first);
    _h_.erase(*(_v_[i]));
    _v_[i] = &new_key;
  }

setAtPos() [2/2]

template<typename Key, typename Alloc , bool Gen>

INLINE void gum::SequenceImplementation< Key, Alloc, Gen >::setAtPos	(	Idx	i,
		Key &&	newKey
	)

Change the value.

Parameters

i	The element's position.
newKey	The element's new value.

Exceptions

NotFound	Raised if the element does not exist.
DuplicateElement	Raised if newKey alreay exists.

Definition at line 515 of file sequence_tpl.h.

                                                                                     {
    if (i >= _h_.size()) { GUM_ERROR(NotFound, "index too large") }

    Key& new_key = const_cast< Key& >(_h_.insert(std::move(newKey), i).first);
    _h_.erase(*(_v_[i]));
    _v_[i] = &new_key;
  }

size()

template<typename Key , typename Alloc >

INLINE Size gum::SequenceImplementation< Key, Alloc >::size ( ) const

noexcept

Returns the size of the sequence.

Returns

Returns the size of the sequence.

Definition at line 37 of file sequence_tpl.h.

                                                                             {
    return _h_.size();
  }

swap()

template<typename Key , typename Alloc >

INLINE void gum::SequenceImplementation< Key, Alloc >::swap	(	Idx	i,
		Idx	j
	)

Swap index.

Parameters

i	The index of the first elt to swap.
j	The index of the other elt to swap.

Definition at line 525 of file sequence_tpl.h.

                                                                          {
    if (i == j) return;

    Key& ki = const_cast< Key& >(atPos(i));
    Key& kj = const_cast< Key& >(atPos(j));

    _h_[ki] = j;
    _h_[kj] = i;

    _v_[i] = &kj;
    _v_[j] = &ki;
  }

toString()

template<typename Key , typename Alloc >

std::string gum::SequenceImplementation< Key, Alloc >::toString

(

)

const

Displays the content of the sequence.

Returns

The content of the sequence.

Definition at line 552 of file sequence_tpl.h.

                                                                      {
    std::stringstream stream;
    stream << "[";

    if (!_h_.empty()) {
      stream << 0 << ":" << *_v_[0];

      for (Idx i = 1; i < _h_.size(); ++i) {
        stream << " - " << i << ":" << *_v_[i];
      }
    }

    stream << "]";

    std::string res = stream.str();
    return res;
  }

Friends And Related Function Documentation

SequenceImplementation

template<typename Key, typename Alloc, bool Gen>

template<typename K , typename A , bool >

friend class SequenceImplementation

friend

Friends to speed up access.

Definition at line 93 of file sequence.h.

Sequence< Key, Alloc >

template<typename Key, typename Alloc, bool Gen>

friend class Sequence< Key, Alloc >

friend

Friends to speed up access.

Definition at line 95 of file sequence.h.

SequenceIteratorSafe< Key >

template<typename Key, typename Alloc, bool Gen>

friend class SequenceIteratorSafe< Key >

friend

Friends to speed up access.

Definition at line 94 of file sequence.h.

Member Data Documentation

_end_safe_

template<typename Key, typename Alloc, bool Gen>

SequenceIteratorSafe< Key > gum::SequenceImplementation< Key, Alloc, Gen >::_end_safe_

private

Stores the end iterator for fast access.

Definition at line 508 of file sequence.h.

_h_

template<typename Key, typename Alloc, bool Gen>

HashTable< Key, Idx, Alloc > gum::SequenceImplementation< Key, Alloc, Gen >::_h_

private

Keep track of the position of the element in v (for fast retrieval).

Definition at line 498 of file sequence.h.

_rend_safe_

template<typename Key, typename Alloc, bool Gen>

SequenceIteratorSafe< Key > gum::SequenceImplementation< Key, Alloc, Gen >::_rend_safe_

private

Stores the rend iterator for fast access.

Definition at line 511 of file sequence.h.

_v_

template<typename Key, typename Alloc, bool Gen>

std::vector< Key*, typename Alloc::template rebind< Key* >::other > gum::SequenceImplementation< Key, Alloc, Gen >::_v_

private

The set of the elements stored into the sequence.

Definition at line 501 of file sequence.h.

---

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

• agrum/tools/core/sequence.h
• agrum/tools/core/sequence_tpl.h