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

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

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

Public Types

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

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

Private Member Functions
void	_update_end_ () noexcept
	A method to update the end iterator after changes in the sequence.
void	_copy_ (const SequenceImplementation< Key, Gen > &aSeq)
	Clears the current sequence and fill it with copies the element of aSeq.
void	_insert_ (HashTableBucket< Key, Idx > &&bucket)
	Insert an element at the end of the sequence.
Constructors
	SequenceImplementation (Size size_param=HashTableConst::default_size)
	Default constructor.
	SequenceImplementation (std::initializer_list< Key > list)
	Initializer list constructor.
	SequenceImplementation (const SequenceImplementation< Key, Gen > &aSeq)
	Copy constructor.
	SequenceImplementation (SequenceImplementation< Key, Gen > &&aSeq)
	Move constructor.
Private Operators
SequenceImplementation< Key, Gen > &	operator= (const SequenceImplementation< Key, Gen > &aSeq)
	Copy operator.
SequenceImplementation< Key, Gen > &	operator= (SequenceImplementation< Key, Gen > &&aSeq)
	Move operator.

Private Attributes
HashTable< Key, Idx >	_h_
	Keep track of the position of the element in v (for fast retrieval).
std::vector< Key * >	_v_
	The set of the elements stored into the sequence.
SequenceIteratorSafe< Key >	_end_safe_
	Stores the end iterator for fast access.
SequenceIteratorSafe< Key >	_rend_safe_
	Stores the rend iterator for fast access.

Friends

class	SequenceIteratorSafe< Key >
	Friends to speed up access.
class	Sequence< Key >
	Friends to speed up access.

Detailed Description

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

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

A SequenceImplementation<Key,bool Gen> is a specialized version of of a Sequence<Key>. 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.
Gen	Used for meta-programation.

Definition at line 109 of file sequence.h.

Member Typedef Documentation

◆ const_iterator

template<typename Key, bool Gen>

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

Types for STL compliance.

Definition at line 127 of file sequence.h.

◆ const_iterator_safe

template<typename Key, bool Gen>

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

Types for STL compliance.

Definition at line 129 of file sequence.h.

◆ const_pointer

template<typename Key, bool Gen>

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

Types for STL compliance.

Definition at line 123 of file sequence.h.

◆ const_reference

template<typename Key, bool Gen>

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

Types for STL compliance.

Definition at line 121 of file sequence.h.

◆ difference_type

template<typename Key, bool Gen>

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

Types for STL compliance.

Definition at line 125 of file sequence.h.

◆ iterator

template<typename Key, bool Gen>

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

Types for STL compliance.

Definition at line 126 of file sequence.h.

◆ iterator_safe

template<typename Key, bool Gen>

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

Types for STL compliance.

Definition at line 128 of file sequence.h.

◆ pointer

template<typename Key, bool Gen>

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

Types for STL compliance.

Definition at line 122 of file sequence.h.

◆ reference

template<typename Key, bool Gen>

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

Types for STL compliance.

Definition at line 120 of file sequence.h.

◆ size_type

template<typename Key, bool Gen>

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

Types for STL compliance.

Definition at line 124 of file sequence.h.

◆ value_type

template<typename Key, bool Gen>

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

Types for STL compliance.

Definition at line 119 of file sequence.h.

Constructor & Destructor Documentation

◆ SequenceImplementation() [1/4]

template<typename Key>

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

private

Default constructor.

Parameters

size_param The intial size of the gum::SequenceImplementation.

Definition at line 286 of file sequence_tpl.h.

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

Referenced by SequenceImplementation(), SequenceImplementation(), ~SequenceImplementation(), _copy_(), gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_(), operator!=(), operator=(), operator=(), operator==(), and operator>>().

Here is the caller graph for this function:

◆ SequenceImplementation() [2/4]

template<typename Key>

gum::SequenceImplementation< Key >::SequenceImplementation ( std::initializer_list< Key > list )

private

Initializer list constructor.

Parameters

list	The initializer list.

Definition at line 295 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_ ()
    }
  }

References SequenceImplementation(), _end_safe_, _rend_safe_, and insert().

Here is the call graph for this function:

◆ SequenceImplementation() [3/4]

template<typename Key, bool Gen>

gum::SequenceImplementation< Key, Gen >::SequenceImplementation ( const SequenceImplementation< Key, 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 306 of file sequence_tpl.h.

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

References SequenceImplementation(), _copy_(), _end_safe_, and _rend_safe_.

Here is the call graph for this function:

◆ SequenceImplementation() [4/4]

template<typename Key, bool Gen>

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

private

Move constructor.

Parameters

aSeq	The gum::SequenceImplementation to move/

Definition at line 315 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>

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

noexcept

Class destructor.

Definition at line 325 of file sequence_tpl.h.

                                                                       {
    GUM_DESTRUCTOR(SequenceImplementation);
  }

References SequenceImplementation().

Referenced by gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Function Documentation

◆ _copy_()

template<typename Key, bool Gen>

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

private

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

Parameters

aSeq	The gum::SequenceImplementation to copy.

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_();
  }

References SequenceImplementation(), _h_, _update_end_(), _v_, clear(), and size().

Referenced by SequenceImplementation(), and gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _insert_()

template<typename Key, bool Gen>

void gum::SequenceImplementation< Key, 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.

Referenced by gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_().

Here is the caller graph for this function:

◆ _update_end_()

template<typename Key>

void gum::SequenceImplementation< Key >::_update_end_ ( )

privatenoexcept

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

Definition at line 259 of file sequence_tpl.h.

                                                                 {
    _end_safe_._setAtEnd_();
  }

References _end_safe_.

Referenced by _copy_(), gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_(), clear(), erase(), insert(), gum::SequenceImplementation< const gum::DiscreteVariable *, std::is_scalar< const gum::DiscreteVariable * >::value >::operator!=(), and gum::SequenceImplementation< const gum::DiscreteVariable *, std::is_scalar< const gum::DiscreteVariable * >::value >::operator>>().

Here is the caller graph for this function:

◆ atPos()

template<typename Key>

const Key & gum::SequenceImplementation< Key >::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 469 of file sequence_tpl.h.

                                                                  {
    if (i >= _h_.size()) {
      GUM_ERROR(OutOfBounds, "index " << i << " for a sequence of size" << _h_.size())
    }
 
    return *(_v_[i]);
  }

References _h_, and GUM_ERROR.

Referenced by gum::prm::StructuredInference< GUM_SCALAR >::_addEdgesInReducedGraph_(), gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_(), gum::prm::PRMClass< GUM_SCALAR >::_overloadReference_(), gum::Instantiation::_reorder_(), gum::prm::GSpan< GUM_SCALAR >::_subgraph_mining_(), back(), front(), operator[](), and swap().

Here is the caller graph for this function:

◆ back()

template<typename Key>

const Key & gum::SequenceImplementation< Key >::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 532 of file sequence_tpl.h.

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

References atPos(), and size().

Referenced by gum::prm::PRMFactory< GUM_SCALAR >::_buildSlotChain_(), gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_(), and gum::prm::PRMClass< GUM_SCALAR >::_overloadReference_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ begin()

template<typename Key>

SequenceIterator< Key > gum::SequenceImplementation< Key >::begin ( ) const

Returns an unsafe begin iterator.

Returns: Returns an unsafe begin iterator.

Definition at line 610 of file sequence_tpl.h.

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

Referenced by gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_(), and gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >::clean().

Here is the caller graph for this function:

◆ beginSafe()

template<typename Key>

SequenceIteratorSafe< Key > gum::SequenceImplementation< Key >::beginSafe ( ) const

Returns a safe begin iterator.

Returns: Returns a safe begin iterator.

Definition at line 584 of file sequence_tpl.h.

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

References SequenceIteratorSafe< Key >.

Referenced by gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ clear()

template<typename Key>

void gum::SequenceImplementation< Key >::clear ( )

Clear the sequence.

Definition at line 265 of file sequence_tpl.h.

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

References _h_, _update_end_(), and _v_.

Referenced by _copy_(), and gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ emplace()

template<typename Key>

template<typename... Args>

void gum::SequenceImplementation< Key >::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.

Definition at line 398 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);
    try {
      _v_.push_back(&new_key);
    } catch (...) {
      _h_.erase(new_key);
      throw;
    }
    _update_end_();
  }

References _h_, and _v_.

Referenced by gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_().

Here is the caller graph for this function:

◆ empty()

template<typename Key>

bool gum::SequenceImplementation< Key >::empty ( ) const

noexcept

Return true if empty.

Returns: Return true if empty.

Definition at line 65 of file sequence_tpl.h.

                                                                {
    return _h_.empty();
  }

References _h_.

Referenced by gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_().

Here is the caller graph for this function:

◆ end()

template<typename Key>

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

noexcept

Returns the unsafe end iterator.

Returns: Returns the unsafe end iterator.

Definition at line 616 of file sequence_tpl.h.

                                                                                        {
    return _end_safe_;
  }

References _end_safe_.

Referenced by gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_(), and gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >::clean().

Here is the caller graph for this function:

◆ endSafe()

template<typename Key>

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

noexcept

Returns the safe end iterator.

Returns: Returns the safe end iterator.

Definition at line 590 of file sequence_tpl.h.

                                                                                                {
    return _end_safe_;
  }

References _end_safe_, and SequenceIteratorSafe< Key >.

Referenced by gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ erase() [1/2]

template<typename Key>

void gum::SequenceImplementation< Key >::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 444 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_();
  }

References _h_, _update_end_(), _v_, pos(), and size().

Here is the call graph for this function:

◆ erase() [2/2]

template<typename Key, bool Gen>

void gum::SequenceImplementation< Key, 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 426 of file sequence_tpl.h.

                                                             {
    // get the position of the element to remove
    auto p = _h_.tryGet(k);
    if (!p) return;
    Idx pos = *p;
 
    // 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_();
  }

References _h_, and pos().

Referenced by gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_(), gum::prm::PRMClass< GUM_SCALAR >::_overloadReference_(), and operator>>().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ exists()

template<typename Key, bool Gen>

bool gum::SequenceImplementation< Key >::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 357 of file sequence_tpl.h.

                                                                    {
    return _h_.exists(k);
  }

References _h_.

Referenced by gum::prm::SVE< GUM_SCALAR >::_initElimOrder_(), gum::prm::SVED< GUM_SCALAR >::_initElimOrder_(), gum::prm::gspan::DFSTree< GUM_SCALAR >::_initialiaze_root_(), gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_(), gum::prm::GSpan< GUM_SCALAR >::_subgraph_mining_(), gum::prm::PRMFactory< GUM_SCALAR >::addAttribute(), gum::prm::gspan::SearchStrategy< GUM_SCALAR >::computeCost_(), and gum::Sequence< Key >::diffSet().

Here is the caller graph for this function:

◆ front()

template<typename Key>

const Key & gum::SequenceImplementation< Key >::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 526 of file sequence_tpl.h.

                                                             {
    return atPos(0);
  }

References atPos().

Referenced by gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ insert() [1/2]

template<typename Key, bool Gen>

void gum::SequenceImplementation< Key, 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 369 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);
    try {
      _v_.push_back(&new_key);
    } catch (...) {
      _h_.erase(new_key);
      throw;
    }
    _update_end_();
  }

Referenced by SequenceImplementation(), gum::prm::PRMFactory< GUM_SCALAR >::_buildSlotChain_(), gum::prm::SVE< GUM_SCALAR >::_initElimOrder_(), gum::prm::SVED< GUM_SCALAR >::_initElimOrder_(), gum::prm::gspan::DFSTree< GUM_SCALAR >::_initialiaze_root_(), gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_(), gum::prm::PRMClass< GUM_SCALAR >::_overloadReference_(), gum::prm::gspan::SearchStrategy< GUM_SCALAR >::computeCost_(), and gum::prm::gspan::DFSTree< GUM_SCALAR >::growPattern().

Here is the caller graph for this function:

◆ insert() [2/2]

template<typename Key, bool Gen>

void gum::SequenceImplementation< Key, 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 383 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);
    try {
      _v_.push_back(&new_key);
    } catch (...) {
      _h_.erase(new_key);
      throw;
    }
    _update_end_();
  }

References _h_, _update_end_(), and _v_.

Here is the call graph for this function:

◆ operator!=()

template<typename Key, bool Gen>

bool gum::SequenceImplementation< Key >::operator!= ( const SequenceImplementation< Key, 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.

Parameters

k	The other gum::SequenceImplementation.

Returns true if both gum::SequenceImplementation are not equal.

Definition at line 570 of file sequence_tpl.h.

                                                         {
    return !operator==(k);
  }

References SequenceImplementation(), and gum::operator==().

Referenced by gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ operator<<() [1/2]

template<typename Key, bool Gen>

SequenceImplementation< Key, Gen > & gum::SequenceImplementation< Key, 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 398 of file sequence_tpl.h.

                                                                                                 {
    insert(k);
    return *this;
  }

Referenced by gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_().

Here is the caller graph for this function:

◆ operator<<() [2/2]

template<typename Key, bool Gen>

SequenceImplementation< Key, Gen > & gum::SequenceImplementation< Key, 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 398 of file sequence_tpl.h.

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

◆ operator=() [1/2]

template<typename Key, bool Gen>

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

private

Copy operator.

Parameters

aSeq	The sequence to copy.

Returns: Returns a ref to this.

Definition at line 331 of file sequence_tpl.h.

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

References SequenceImplementation().

Referenced by gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_(), gum::Sequence< Key >::operator=(), and gum::Sequence< Key >::operator=().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ operator=() [2/2]

template<typename Key, bool Gen>

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

private

Move operator.

Parameters

aSeq	The sequence to move.

Returns: Returns a ref to this.

Definition at line 344 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;
  }

References SequenceImplementation(), _h_, and _v_.

Here is the call graph for this function:

◆ operator==()

template<typename Key, bool Gen>

bool gum::SequenceImplementation< Key >::operator== ( const SequenceImplementation< Key, 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.

Parameters

k	The other gum::SequenceImplementation.

Returns true if both gum::SequenceImplementation are equal.

Definition at line 557 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;
  }

References SequenceImplementation(), _v_, and size().

Referenced by gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ operator>>()

template<typename Key, bool Gen>

SequenceImplementation< Key, true > & gum::SequenceImplementation< Key >::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 462 of file sequence_tpl.h.

                                                                                                 {
    erase(k);
    return *this;
  }

References SequenceImplementation(), and erase().

Referenced by gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ operator[]()

template<typename Key>

const Key & gum::SequenceImplementation< Key >::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 479 of file sequence_tpl.h.

                                                                       {
    return atPos(i);
  }

References atPos().

Referenced by gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ pos()

template<typename Key, bool Gen>

Idx gum::SequenceImplementation< Key >::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 485 of file sequence_tpl.h.

                                                                  {
    return _h_[key];
  }

References _h_.

Referenced by gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_(), gum::prm::GSpan< GUM_SCALAR >::_subgraph_mining_(), gum::MultiDimArray< GUM_ELEMENT >::erase(), gum::MultiDimWithOffset< GUM_ELEMENT >::erase(), erase(), and erase().

Here is the caller graph for this function:

◆ rbegin()

template<typename Key>

SequenceIterator< Key > gum::SequenceImplementation< Key >::rbegin ( ) const

Returns an unsafe rbegin iterator.

Returns: Returns an unsafe rbegin iterator.

Definition at line 622 of file sequence_tpl.h.

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

References size().

Referenced by gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ rbeginSafe()

template<typename Key>

SequenceIteratorSafe< Key > gum::SequenceImplementation< Key >::rbeginSafe ( ) const

Returns a safe rbegin iterator.

Returns: Returns a safe rbegin iterator.

Definition at line 596 of file sequence_tpl.h.

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

References SequenceIteratorSafe< Key >, and size().

Referenced by gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ rend()

template<typename Key>

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

noexcept

Returns the unsafe rend iterator.

Returns: Returns the unsafe rend iterator.

Definition at line 630 of file sequence_tpl.h.

                                                                                         {
    return _rend_safe_;
  }

References _rend_safe_.

Referenced by gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_().

Here is the caller graph for this function:

◆ rendSafe()

template<typename Key>

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

noexcept

Returns the safe rend iterator.

Returns: Returns the safe rend iterator.

Definition at line 604 of file sequence_tpl.h.

                                                                                                 {
    return _rend_safe_;
  }

References _rend_safe_, and SequenceIteratorSafe< Key >.

Referenced by gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ resize()

template<typename Key>

void gum::SequenceImplementation< Key >::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 636 of file sequence_tpl.h.

                                                               {
    if (new_size < _h_.size()) return;
 
    _h_.resize(new_size);
    _v_.reserve(new_size);
  }

References _h_, and _v_.

Referenced by gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_().

Here is the caller graph for this function:

◆ setAtPos() [1/2]

template<typename Key, bool Gen>

void gum::SequenceImplementation< Key, 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 491 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;
  }

References _h_, and GUM_ERROR.

Referenced by gum::prm::PRMClass< GUM_SCALAR >::_inheritClass_(), and gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_().

Here is the caller graph for this function:

◆ setAtPos() [2/2]

template<typename Key, bool Gen>

void gum::SequenceImplementation< Key, 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 501 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;
  }

References _h_, _v_, and GUM_ERROR.

◆ size()

template<typename Key>

Size gum::SequenceImplementation< Key >::size ( ) const

noexcept

Returns the size of the sequence.

Returns: Returns the size of the sequence.

Definition at line 59 of file sequence_tpl.h.

                                                               {
    return _h_.size();
  }

References _h_.

Referenced by gum::prm::StructuredInference< GUM_SCALAR >::_addEdgesInReducedGraph_(), gum::prm::PRMFactory< GUM_SCALAR >::_buildSlotChain_(), _copy_(), gum::Instantiation::_init_(), gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_(), gum::prm::PRMClass< GUM_SCALAR >::_overloadReference_(), gum::Instantiation::_reorder_(), back(), gum::MultiDimArray< GUM_ELEMENT >::erase(), gum::MultiDimWithOffset< GUM_ELEMENT >::erase(), erase(), operator==(), rbegin(), and rbeginSafe().

Here is the caller graph for this function:

◆ swap()

template<typename Key>

void gum::SequenceImplementation< Key >::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 511 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;
  }

References _h_, and atPos().

Referenced by gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ toString()

template<typename Key>

std::string gum::SequenceImplementation< Key >::toString ( ) const

Displays the content of the sequence.

Returns: The content of the sequence.

Definition at line 538 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 << std::format(" - {}:", i) << *_v_[i];
      }
    }
 
    stream << "]";
 
    return stream.str();
  }

References _h_, and _v_.

Referenced by gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_(), gum::operator<<(), gum::operator<<(), and gum::operator<<().

Here is the caller graph for this function:

◆ tryPos()

template<typename Key, bool Gen>

optional_ref< const Idx > gum::SequenceImplementation< Key >::tryPos ( const Key & k ) const

Returns a pointer to the position of k in the sequence, or nullptr if k is not found.

This avoids the double lookup of exists() + pos().

Parameters

k	The key to search for.

Returns: A pointer to the position (Idx), or nullptr if not found.

Definition at line 363 of file sequence_tpl.h.

                                                                                         {
    return _h_.tryGet(k);
  }

References _h_.

Referenced by gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::_insert_().

Here is the caller graph for this function:

◆ Sequence< Key >

template<typename Key, bool Gen>

friend class Sequence< Key >

friend

Friends to speed up access.

Definition at line 1372 of file sequence.h.

◆ SequenceIteratorSafe< Key >

template<typename Key, bool Gen>

friend class SequenceIteratorSafe< Key >

friend

Friends to speed up access.

Definition at line 1372 of file sequence.h.

Referenced by beginSafe(), endSafe(), rbeginSafe(), and rendSafe().

Member Data Documentation

◆ _end_safe_

template<typename Key, bool Gen>

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

private

Stores the end iterator for fast access.

Definition at line 509 of file sequence.h.

Referenced by SequenceImplementation(), SequenceImplementation(), _update_end_(), end(), and endSafe().

◆ _h_

template<typename Key, bool Gen>

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

private

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

Definition at line 499 of file sequence.h.

Referenced by _copy_(), atPos(), clear(), emplace(), empty(), erase(), erase(), exists(), insert(), operator=(), pos(), resize(), setAtPos(), setAtPos(), size(), swap(), toString(), and tryPos().

◆ _rend_safe_

template<typename Key, bool Gen>

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

private

Stores the rend iterator for fast access.

Definition at line 512 of file sequence.h.

Referenced by SequenceImplementation(), SequenceImplementation(), rend(), and rendSafe().

◆ _v_

template<typename Key, bool Gen>

std::vector< Key* > gum::SequenceImplementation< Key, Gen >::_v_

private

The set of the elements stored into the sequence.

Definition at line 502 of file sequence.h.

Referenced by _copy_(), clear(), emplace(), erase(), insert(), operator=(), operator==(), resize(), setAtPos(), and toString().

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

agrum/base/core/sequence.h
agrum/base/core/sequence_tpl.h

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ const_iterator_safe

◆ const_pointer

◆ const_reference

◆ difference_type

◆ iterator

◆ iterator_safe

◆ pointer

◆ reference

◆ size_type

◆ value_type

Constructor & Destructor Documentation

◆ SequenceImplementation() [1/4]

◆ SequenceImplementation() [2/4]

◆ SequenceImplementation() [3/4]

◆ SequenceImplementation() [4/4]

◆ ~SequenceImplementation()

Member Function Documentation

◆ _copy_()

◆ _insert_()

◆ _update_end_()

◆ atPos()

◆ back()

◆ begin()

◆ beginSafe()

◆ clear()

◆ emplace()

◆ empty()

◆ end()

◆ endSafe()

◆ erase() [1/2]

◆ erase() [2/2]

◆ exists()

◆ front()

◆ insert() [1/2]

◆ insert() [2/2]

◆ operator!=()

◆ operator<<() [1/2]

◆ operator<<() [2/2]

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ operator>>()

◆ operator[]()

◆ pos()

◆ rbegin()

◆ rbeginSafe()

◆ rend()

◆ rendSafe()

◆ resize()

◆ setAtPos() [1/2]

◆ setAtPos() [2/2]

◆ size()

◆ swap()

◆ toString()

◆ tryPos()

Friends And Related Symbol Documentation

◆ Sequence< Key >

◆ SequenceIteratorSafe< Key >

Member Data Documentation

◆ _end_safe_

◆ _h_

◆ _rend_safe_

◆ _v_