aGrUM  0.15.1
gum::Sequence< Key, Alloc > Class Template Reference

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

#include <agrum/core/sequence.h>

+ Inheritance diagram for gum::Sequence< Key, Alloc >:
+ Collaboration diagram for gum::Sequence< Key, Alloc >:

Public Member Functions

template<typename OtherAlloc >
INLINE Sequence (const Sequence< Key, OtherAlloc > &aSeq)
 
template<typename OtherAlloc >
INLINE Sequence< Key, Alloc > & operator= (const Sequence< Key, OtherAlloc > &aSeq)
 
bool operator== (const SequenceImplementation< Key, OtherAlloc, true > &k) const
 
INLINE bool operator!= (const SequenceImplementation< Key, OtherAlloc, Gen > &k) const
 
INLINE bool operator!= (const SequenceImplementation< Key, OtherAlloc, true > &k) const
 
INLINE void emplace (Args &&... args)
 
INLINE void __copy (const SequenceImplementation< Key, OtherAlloc, Gen > &aSeq)
 
INLINE void __copy (const SequenceImplementation< Key, OtherAlloc, true > &aSeq)
 
Constructors / Destructors
 Sequence (Size size_param=HashTableConst::default_size)
 Default constructor. More...
 
 Sequence (std::initializer_list< Key > list)
 Initializer list constructor. More...
 
 Sequence (const Sequence< Key, Alloc > &aSeq)
 Copy constructor. More...
 
template<typename OtherAlloc >
 Sequence (const Sequence< Key, OtherAlloc > &aSeq)
 Generalised copy constructor. More...
 
 Sequence (Sequence< Key, Alloc > &&aSeq)
 Move constructor. More...
 
 ~Sequence () noexcept
 Class destructor. More...
 
Operators
Sequence< Key, Alloc > & operator= (const Sequence< Key, Alloc > &aSeq)
 Copy operator. More...
 
template<typename OtherAlloc >
Sequence< Key, Alloc > & operator= (const Sequence< Key, OtherAlloc > &aSeq)
 Generalized opy operator. More...
 
Sequence< Key, Alloc > & operator= (Sequence< Key, Alloc > &&aSeq)
 Move operator. More...
 
Accessors / Modifiers
template<typename OtherAlloc >
Set< Key, Alloc > diffSet (const Sequence< Key, OtherAlloc > &seq) const
 Difference between two sequences as a Set<Key> = this \ seq. More...
 
Iterators
iterator_safe beginSafe () const
 Returns a safe begin iterator. More...
 
iterator_safe rbeginSafe () const
 Returns a safe rbegin iterator. More...
 
const iterator_safeendSafe () const noexcept
 Returns the safe end iterator. More...
 
const iterator_saferendSafe () 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 iteratorend () const noexcept
 Returns the unsafe end iterator. More...
 
const iteratorrend () 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...
 
bool operator== (const SequenceImplementation< Key, OtherAlloc, Gen > &k) const
 Returns true if the content of k equals that of *this. More...
 
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...
 
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 Implementation = SequenceImplementation< Key, Alloc, std::is_scalar< Key >::value >
 The gum::Sequence implementation. More...
 
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...
 

Detailed Description

template<typename Key, typename Alloc = std::allocator< Key >>
class gum::Sequence< Key, Alloc >

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

A gum::Sequence<Key> is quite similar to a std::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 gum::Sequence<Key> 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.

Usage example:
// creation of a sequence
Sequence<int> seq { 1, 2, 3, 4 };
Sequence<string> seq2;
// creation of safe iterators
SequenceIteratorSafe<int> iter1 = seq.beginSafe (); // points to 1
SequenceIteratorSafe<int> iter2 = iter1;
SequenceIteratorSafe<int> iter3 = std::move ( iter1 );
// creation of unsafe iterators
SequenceIterator<int> xiter1 = seq.begin (); // points to 1
SequenceIterator<int> xiter2 = xiter1;
SequenceIterator<int> xiter3 = std::move ( xiter1 );
// parsing the sequence
for ( auto iter = seq.begin (); iter != seq.end (); ++iter )
std::cout << *iter << std::endl;
for ( auto iter = seq.rbegin (); iter != seq.rend (); --iter )
std::cout << *iter << std::endl;
for ( auto iter = seq.begin (); iter != seq.end (); ++iter )
std::cout << iter->size () << std::endl;
Template Parameters
KeyThe elements type stored in the sequence.
AllocThe values allocator.

Definition at line 1022 of file sequence.h.

Member Typedef Documentation

◆ allocator_type

template<typename Key, typename Alloc = std::allocator< Key >>
using gum::Sequence< Key, Alloc >::allocator_type = Alloc

Types for STL compliance.

Definition at line 1034 of file sequence.h.

◆ const_iterator

template<typename Key, typename Alloc = std::allocator< Key >>
using gum::Sequence< Key, Alloc >::const_iterator = SequenceIterator< Key >

Types for STL compliance.

Definition at line 1036 of file sequence.h.

◆ const_iterator_safe

template<typename Key, typename Alloc = std::allocator< Key >>
using gum::Sequence< Key, Alloc >::const_iterator_safe = SequenceIteratorSafe< Key >

Types for STL compliance.

Definition at line 1038 of file sequence.h.

◆ const_pointer

template<typename Key, typename Alloc = std::allocator< Key >>
using gum::Sequence< Key, Alloc >::const_pointer = const Key*

Types for STL compliance.

Definition at line 1031 of file sequence.h.

◆ const_reference

template<typename Key, typename Alloc = std::allocator< Key >>
using gum::Sequence< Key, Alloc >::const_reference = const Key&

Types for STL compliance.

Definition at line 1029 of file sequence.h.

◆ difference_type

template<typename Key, typename Alloc = std::allocator< Key >>
using gum::Sequence< Key, Alloc >::difference_type = std::ptrdiff_t

Types for STL compliance.

Definition at line 1033 of file sequence.h.

◆ Implementation

template<typename Key, typename Alloc = std::allocator< Key >>
using gum::Sequence< Key, Alloc >::Implementation = SequenceImplementation< Key, Alloc, std::is_scalar< Key >::value >

The gum::Sequence implementation.

Definition at line 1043 of file sequence.h.

◆ iterator

template<typename Key, typename Alloc = std::allocator< Key >>
using gum::Sequence< Key, Alloc >::iterator = SequenceIterator< Key >

Types for STL compliance.

Definition at line 1035 of file sequence.h.

◆ iterator_safe

template<typename Key, typename Alloc = std::allocator< Key >>
using gum::Sequence< Key, Alloc >::iterator_safe = SequenceIteratorSafe< Key >

Types for STL compliance.

Definition at line 1037 of file sequence.h.

◆ pointer

template<typename Key, typename Alloc = std::allocator< Key >>
using gum::Sequence< Key, Alloc >::pointer = Key*

Types for STL compliance.

Definition at line 1030 of file sequence.h.

◆ reference

template<typename Key, typename Alloc = std::allocator< Key >>
using gum::Sequence< Key, Alloc >::reference = Key&

Types for STL compliance.

Definition at line 1028 of file sequence.h.

◆ size_type

template<typename Key, typename Alloc = std::allocator< Key >>
using gum::Sequence< Key, Alloc >::size_type = std::size_t

Types for STL compliance.

Definition at line 1032 of file sequence.h.

◆ value_type

template<typename Key, typename Alloc = std::allocator< Key >>
using gum::Sequence< Key, Alloc >::value_type = Key

Types for STL compliance.

Definition at line 1027 of file sequence.h.

Constructor & Destructor Documentation

◆ Sequence() [1/6]

template<typename Key , typename Alloc >
INLINE gum::Sequence< Key, Alloc >::Sequence ( Size  size_param = HashTableConst::default_size)

Default constructor.

Parameters
size_paramThe intial size of the gum::SequenceImplementation.

Definition at line 1099 of file sequence_tpl.h.

1099  :
1100  SequenceImplementation< Key, Alloc, std::is_scalar< Key >::value >(
1101  size_param) {
1102  // for debugging purposes
1103  GUM_CONSTRUCTOR(Sequence);
1104  }
Sequence(Size size_param=HashTableConst::default_size)
Default constructor.

◆ Sequence() [2/6]

template<typename Key, typename Alloc >
INLINE gum::Sequence< Key, Alloc >::Sequence ( std::initializer_list< Key >  list)

Initializer list constructor.

Parameters
listThe initializer list.

Definition at line 1108 of file sequence_tpl.h.

1108  :
1109  SequenceImplementation< Key, Alloc, std::is_scalar< Key >::value >(list) {
1110  // for debugging purposes
1111  GUM_CONSTRUCTOR(Sequence);
1112  }
Sequence(Size size_param=HashTableConst::default_size)
Default constructor.

◆ Sequence() [3/6]

template<typename Key, typename Alloc>
INLINE gum::Sequence< Key, Alloc >::Sequence ( const Sequence< Key, Alloc > &  aSeq)

Copy constructor.

Parameters
aSeqThe 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 1116 of file sequence_tpl.h.

1116  :
1117  SequenceImplementation< Key, Alloc, std::is_scalar< Key >::value >(aSeq) {
1118  // for debugging purposes
1119  GUM_CONS_CPY(Sequence);
1120  }
Sequence(Size size_param=HashTableConst::default_size)
Default constructor.

◆ Sequence() [4/6]

template<typename Key, typename Alloc = std::allocator< Key >>
template<typename OtherAlloc >
gum::Sequence< Key, Alloc >::Sequence ( const Sequence< Key, OtherAlloc > &  aSeq)

Generalised copy constructor.

Template Parameters
OtherAllocThe other gum::Sequence allocator.
Parameters
aSeqThe sequence the elements of which will be copied.
Warning
The elements of the newly constructed sequence are copies of those in aSeq.

◆ Sequence() [5/6]

template<typename Key, typename Alloc>
INLINE gum::Sequence< Key, Alloc >::Sequence ( Sequence< Key, Alloc > &&  aSeq)

Move constructor.

Parameters
aSeqThe gum::Sequence to move/

Definition at line 1134 of file sequence_tpl.h.

1134  :
1135  SequenceImplementation< Key, Alloc, std::is_scalar< Key >::value >(
1136  std::move(aSeq)) {
1137  // for debugging purposes
1138  GUM_CONS_MOV(Sequence);
1139  }
Sequence(Size size_param=HashTableConst::default_size)
Default constructor.

◆ ~Sequence()

template<typename Key , typename Alloc >
INLINE gum::Sequence< Key, Alloc >::~Sequence ( )
noexcept

Class destructor.

Definition at line 1143 of file sequence_tpl.h.

1143  {
1144  // for debugging purposes
1145  GUM_DESTRUCTOR(Sequence);
1146  }
Sequence(Size size_param=HashTableConst::default_size)
Default constructor.

◆ Sequence() [6/6]

template<typename Key, typename Alloc = std::allocator< Key >>
template<typename OtherAlloc >
INLINE gum::Sequence< Key, Alloc >::Sequence ( const Sequence< Key, OtherAlloc > &  aSeq)

Definition at line 1126 of file sequence_tpl.h.

1126  :
1127  SequenceImplementation< Key, Alloc, std::is_scalar< Key >::value >(aSeq) {
1128  // for debugging purposes
1129  GUM_CONS_CPY(Sequence);
1130  }
Sequence(Size size_param=HashTableConst::default_size)
Default constructor.

Member Function Documentation

◆ __copy() [1/2]

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

Definition at line 280 of file sequence_tpl.h.

281  {
282  clear();
283 
284  for (Size i = 0; i < aSeq.size(); ++i) {
285  Key& new_key = const_cast< Key& >(__h.insert(*(aSeq.__v[i]), i).first);
286  __v.push_back(&new_key);
287  }
288 
289  __update_end();
290  }
HashTable< Key, Idx, Alloc > __h
Keep track of the position of the element in v (for fast retrieval).
Definition: sequence.h:500
void __update_end() noexcept
A method to update the end iterator after changes in the sequence.
Definition: sequence_tpl.h:265
std::vector< Key *, typename Alloc::template rebind< Key * >::other > __v
The set of the elements stored into the sequence.
Definition: sequence.h:503
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:48
value_type & insert(const Key &key, const Val &val)
Adds a new element (actually a copy of this element) into the hash table.

◆ __copy() [2/2]

INLINE void gum::SequenceImplementation< Key, Alloc, Gen >::__copy ( const SequenceImplementation< Key, OtherAlloc, true > &  aSeq)
inherited

Definition at line 714 of file sequence_tpl.h.

715  {
716  clear();
717 
718  for (Size i = 0; i < aSeq.size(); ++i) {
719  __h.insert(aSeq.__v[i], i);
720  __v.push_back(aSeq.__v[i]);
721  }
722 
723  __update_end();
724  }
HashTable< Key, Idx, Alloc > __h
Keep track of the position of the element in v (for fast retrieval).
Definition: sequence.h:500
void __update_end() noexcept
A method to update the end iterator after changes in the sequence.
Definition: sequence_tpl.h:265
std::vector< Key *, typename Alloc::template rebind< Key * >::other > __v
The set of the elements stored into the sequence.
Definition: sequence.h:503
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:48
value_type & insert(const Key &key, const Val &val)
Adds a new element (actually a copy of this element) into the hash table.

◆ atPos()

INLINE const Key & gum::SequenceImplementation< Key, Alloc >::atPos ( Idx  i) const
inherited

Returns the object at the pos i.

Parameters
iThe position of the element to return.
Returns
Returns the object at the pos i.
Exceptions
NotFoundRaised if the element does not exist.

Definition at line 500 of file sequence_tpl.h.

Referenced by gum::prm::StructuredInference< GUM_SCALAR >::__addEdgesInReducedGraph(), gum::prm::PRMClass< double >::__overloadReference(), gum::Instantiation::__reorder(), gum::prm::GSpan< GUM_SCALAR >::__subgraph_mining(), and gum::MultiDimFunctionGraphManager< bool, ExactTerminalNodePolicy >::minimizeSize().

500  {
501  if (i >= __h.size()) {
502  GUM_ERROR(OutOfBounds,
503  "index " << i << " for a sequence of size" << __h.size());
504  }
505 
506  return *(__v[i]);
507  }
Size size() const noexcept
Returns the number of elements stored into the hashtable.
HashTable< Key, Idx, Alloc > __h
Keep track of the position of the element in v (for fast retrieval).
Definition: sequence.h:500
std::vector< Key *, typename Alloc::template rebind< Key * >::other > __v
The set of the elements stored into the sequence.
Definition: sequence.h:503
#define GUM_ERROR(type, msg)
Definition: exceptions.h:55

◆ back()

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

Returns the last element of the sequence.

Returns
Returns the last element of the sequence.
Exceptions
NotFoundRaised if the sequence is empty.

Definition at line 568 of file sequence_tpl.h.

Referenced by gum::prm::PRMFactory< GUM_SCALAR >::__buildSlotChain(), and gum::prm::PRMClass< double >::__overloadReference().

568  {
569  return atPos(size() - 1);
570  }
Size size() const noexcept
Returns the size of the sequence.
Definition: sequence_tpl.h:38
const Key & atPos(Idx i) const
Returns the object at the pos i.
Definition: sequence_tpl.h:500

◆ begin()

INLINE SequenceIterator< Key > gum::SequenceImplementation< Key, Alloc >::begin ( ) const
inherited

Returns an unsafe begin iterator.

Returns
Returns an unsafe begin iterator.

Definition at line 657 of file sequence_tpl.h.

657  {
658  return SequenceIterator< Key >{*this};
659  }

◆ beginSafe()

INLINE SequenceIteratorSafe< Key > gum::SequenceImplementation< Key, Alloc >::beginSafe ( ) const
inherited

Returns a safe begin iterator.

Returns
Returns a safe begin iterator.

Definition at line 627 of file sequence_tpl.h.

Referenced by gum::MultiDimFunctionGraphManager< bool, ExactTerminalNodePolicy >::minimizeSize().

◆ clear()

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

Clear the sequence.

Definition at line 271 of file sequence_tpl.h.

271  {
272  __h.clear();
273  __v.clear();
274  __update_end();
275  }
HashTable< Key, Idx, Alloc > __h
Keep track of the position of the element in v (for fast retrieval).
Definition: sequence.h:500
void __update_end() noexcept
A method to update the end iterator after changes in the sequence.
Definition: sequence_tpl.h:265
void clear()
Removes all the elements in the hash table.
std::vector< Key *, typename Alloc::template rebind< Key * >::other > __v
The set of the elements stored into the sequence.
Definition: sequence.h:503

◆ diffSet()

template<typename Key, typename Alloc >
template<typename OtherAlloc >
Set< Key, Alloc > gum::Sequence< Key, Alloc >::diffSet ( const Sequence< Key, OtherAlloc > &  seq) const

Difference between two sequences as a Set<Key> = this \ seq.

Parameters
seqThe gum::Sequence to substract of this.
Returns
Returns the set difference : *this \ seq.

Definition at line 1176 of file sequence_tpl.h.

1177  {
1178  Set< Key, Alloc > res;
1179 
1180  for (iterator iter = this->begin(); iter != this->end(); ++iter) {
1181  if (!seq.exists(*iter)) res << *iter;
1182  }
1183 
1184  return res;
1185  }
iterator begin() const
Returns an unsafe begin iterator.
Definition: sequence_tpl.h:657
SequenceIterator< Key > iterator
Types for STL compliance.
Definition: sequence.h:1035
const iterator & end() const noexcept
Returns the unsafe end iterator.
Definition: sequence_tpl.h:664

◆ emplace() [1/2]

void gum::SequenceImplementation< Key, Alloc, Gen >::emplace ( Args &&...  args)
inherited

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
ArgsThe arguments types passed to the constructor.
Parameters
argsThe arguments passed to the constructor.
Exceptions
DuplicateElementRaised if the sequence contains already k.

◆ emplace() [2/2]

INLINE void gum::SequenceImplementation< Key, Alloc >::emplace ( Args &&...  args)
inherited

Definition at line 427 of file sequence_tpl.h.

427  {
428  Key key(std::forward< Args >(args)...);
429  Key& new_key =
430  const_cast< Key& >(__h.insert(std::move(key), __h.size()).first);
431  __v.push_back(&new_key);
432  __update_end();
433  }
Size size() const noexcept
Returns the number of elements stored into the hashtable.
HashTable< Key, Idx, Alloc > __h
Keep track of the position of the element in v (for fast retrieval).
Definition: sequence.h:500
void __update_end() noexcept
A method to update the end iterator after changes in the sequence.
Definition: sequence_tpl.h:265
std::vector< Key *, typename Alloc::template rebind< Key * >::other > __v
The set of the elements stored into the sequence.
Definition: sequence.h:503
value_type & insert(const Key &key, const Val &val)
Adds a new element (actually a copy of this element) into the hash table.

◆ empty()

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

Return true if empty.

Returns
Return true if empty.

Definition at line 44 of file sequence_tpl.h.

44  {
45  return __h.empty();
46  }
HashTable< Key, Idx, Alloc > __h
Keep track of the position of the element in v (for fast retrieval).
Definition: sequence.h:500
bool empty() const noexcept
Indicates whether the hash table is empty.

◆ end()

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

Returns the unsafe end iterator.

Returns
Returns the unsafe end iterator.

Definition at line 664 of file sequence_tpl.h.

664  {
665  return __end_safe;
666  }
SequenceIteratorSafe< Key > __end_safe
Stores the end iterator for fast access.
Definition: sequence.h:510

◆ endSafe()

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

Returns the safe end iterator.

Returns
Returns the safe end iterator.

Definition at line 634 of file sequence_tpl.h.

Referenced by gum::MultiDimFunctionGraphManager< bool, ExactTerminalNodePolicy >::minimizeSize().

634  {
635  return __end_safe;
636  }
SequenceIteratorSafe< Key > __end_safe
Stores the end iterator for fast access.
Definition: sequence.h:510

◆ erase() [1/2]

INLINE void gum::SequenceImplementation< Key, Alloc, Gen >::erase ( const Key &  k)
inherited

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
kThe element to remove.

Definition at line 453 of file sequence_tpl.h.

Referenced by gum::prm::PRMClass< double >::__overloadReference().

453  {
454  // get the position of the element to remove
455  Idx pos;
456 
457  try {
458  pos = __h[k];
459  } catch (NotFound&) { return; }
460 
461  // erase the element
462  __v.erase(__v.begin() + pos);
463  for (Idx i = pos, nb_elts = __h.size() - 1; i < nb_elts; ++i) {
464  --__h[*(__v[i])];
465  }
466  __h.erase(k);
467 
468  __update_end();
469  }
Idx pos(const Key &key) const
Returns the position of the object passed in argument (if it exists).
Definition: sequence_tpl.h:518
Size size() const noexcept
Returns the number of elements stored into the hashtable.
void erase(const Key &key)
Removes a given element from the hash table.
HashTable< Key, Idx, Alloc > __h
Keep track of the position of the element in v (for fast retrieval).
Definition: sequence.h:500
void __update_end() noexcept
A method to update the end iterator after changes in the sequence.
Definition: sequence_tpl.h:265
std::vector< Key *, typename Alloc::template rebind< Key * >::other > __v
The set of the elements stored into the sequence.
Definition: sequence.h:503

◆ erase() [2/2]

INLINE void gum::SequenceImplementation< Key, Alloc >::erase ( const iterator_safe k)
inherited

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
kThe iterator poiting to the element to remove.

Definition at line 474 of file sequence_tpl.h.

474  {
475  if (iter.pos() >= size()) return;
476 
477  // erase the element
478  Idx pos = iter.pos();
479  Key* key = __v[pos];
480  __v.erase(__v.begin() + pos);
481 
482  for (Idx i = pos, nb_elts = __h.size() - 1; i < nb_elts; ++i) {
483  --__h[*(__v[i])];
484  }
485  __h.erase(*key);
486 
487  __update_end();
488  }
Idx pos(const Key &key) const
Returns the position of the object passed in argument (if it exists).
Definition: sequence_tpl.h:518
Size size() const noexcept
Returns the number of elements stored into the hashtable.
Size size() const noexcept
Returns the size of the sequence.
Definition: sequence_tpl.h:38
void erase(const Key &key)
Removes a given element from the hash table.
HashTable< Key, Idx, Alloc > __h
Keep track of the position of the element in v (for fast retrieval).
Definition: sequence.h:500
void __update_end() noexcept
A method to update the end iterator after changes in the sequence.
Definition: sequence_tpl.h:265
std::vector< Key *, typename Alloc::template rebind< Key * >::other > __v
The set of the elements stored into the sequence.
Definition: sequence.h:503

◆ exists()

INLINE bool gum::SequenceImplementation< Key, Alloc >::exists ( const Key &  k) const
inherited

Check the existence of k in the sequence.

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

Parameters
kThe key to check for existence.
Returns
Returns true if k is in the gum::SequenceImplementation.

Definition at line 402 of file sequence_tpl.h.

Referenced by gum::prm::SVED< GUM_SCALAR >::__initElimOrder(), gum::prm::SVE< GUM_SCALAR >::__initElimOrder(), gum::prm::gspan::DFSTree< GUM_SCALAR >::__initialiaze_root(), gum::prm::GSpan< GUM_SCALAR >::__subgraph_mining(), gum::prm::gspan::SearchStrategy< GUM_SCALAR >::_computeCost(), gum::prm::PRMFactory< GUM_SCALAR >::addAttribute(), and gum::Sequence< NodeId >::diffSet().

402  {
403  return __h.exists(k);
404  }
bool exists(const Key &key) const
Checks whether there exists an element with a given key in the hashtable.
HashTable< Key, Idx, Alloc > __h
Keep track of the position of the element in v (for fast retrieval).
Definition: sequence.h:500

◆ front()

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

Returns the first element of the element.

Returns
Returns the first element of the element.
Exceptions
NotFoundRaised if the sequence is empty.

Definition at line 562 of file sequence_tpl.h.

562  {
563  return atPos(0);
564  }
const Key & atPos(Idx i) const
Returns the object at the pos i.
Definition: sequence_tpl.h:500

◆ insert() [1/2]

INLINE void gum::SequenceImplementation< Key, Alloc, Gen >::insert ( const Key &  k)
inherited

Insert an element at the end of the sequence.

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

Parameters
kThe element to insert.
Exceptions
DuplicateElementRaised if the sequence contains already k.

Definition at line 408 of file sequence_tpl.h.

Referenced by gum::prm::PRMFactory< GUM_SCALAR >::__buildSlotChain(), gum::prm::SVED< GUM_SCALAR >::__initElimOrder(), gum::prm::SVE< GUM_SCALAR >::__initElimOrder(), gum::prm::gspan::DFSTree< GUM_SCALAR >::__initialiaze_root(), gum::prm::PRMClass< double >::__overloadReference(), gum::prm::GSpan< GUM_SCALAR >::__sortPatterns(), gum::prm::gspan::SearchStrategy< GUM_SCALAR >::_computeCost(), gum::BarrenNodesFinder::barrenNodes(), gum::prm::gspan::DFSTree< GUM_SCALAR >::growPattern(), and gum::MultiDimFunctionGraphManager< bool, ExactTerminalNodePolicy >::minimizeSize().

408  {
409  // k will be added at the end. Insert the new key into the hashtable
410  Key& new_key = const_cast< Key& >(__h.insert(k, __h.size()).first);
411  __v.push_back(&new_key);
412  __update_end();
413  }
Size size() const noexcept
Returns the number of elements stored into the hashtable.
HashTable< Key, Idx, Alloc > __h
Keep track of the position of the element in v (for fast retrieval).
Definition: sequence.h:500
void __update_end() noexcept
A method to update the end iterator after changes in the sequence.
Definition: sequence_tpl.h:265
std::vector< Key *, typename Alloc::template rebind< Key * >::other > __v
The set of the elements stored into the sequence.
Definition: sequence.h:503
value_type & insert(const Key &key, const Val &val)
Adds a new element (actually a copy of this element) into the hash table.

◆ insert() [2/2]

INLINE void gum::SequenceImplementation< Key, Alloc, Gen >::insert ( Key &&  k)
inherited

Move an element at the end of the sequence.

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

Parameters
kThe element to insert.
Exceptions
DuplicateElementRaised if the sequence contains already k.

Definition at line 417 of file sequence_tpl.h.

417  {
418  // k will be added at the end. Insert the new key into the hashtable
419  Key& new_key = const_cast< Key& >(__h.insert(std::move(k), __h.size()).first);
420  __v.push_back(&new_key);
421  __update_end();
422  }
Size size() const noexcept
Returns the number of elements stored into the hashtable.
HashTable< Key, Idx, Alloc > __h
Keep track of the position of the element in v (for fast retrieval).
Definition: sequence.h:500
void __update_end() noexcept
A method to update the end iterator after changes in the sequence.
Definition: sequence_tpl.h:265
std::vector< Key *, typename Alloc::template rebind< Key * >::other > __v
The set of the elements stored into the sequence.
Definition: sequence.h:503
value_type & insert(const Key &key, const Val &val)
Adds a new element (actually a copy of this element) into the hash table.

◆ operator!=() [1/3]

bool gum::SequenceImplementation< Key, Alloc, Gen >::operator!= ( const SequenceImplementation< Key, OtherAlloc, Gen > &  k) const
inherited

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
OtherAllocThe other gum::SequenceImplementation allocator.
Parameters
kThe other gum::SequenceImplementation. Returns true if both gum::SequenceImplementation are not equal.

◆ operator!=() [2/3]

INLINE bool gum::SequenceImplementation< Key, Alloc, Gen >::operator!= ( const SequenceImplementation< Key, OtherAlloc, Gen > &  k) const
inherited

Definition at line 611 of file sequence_tpl.h.

611  {
612  return !operator==(k);
613  }
bool operator==(const SequenceImplementation< Key, OtherAlloc, Gen > &k) const
Returns true if the content of k equals that of *this.
Definition: sequence_tpl.h:596

◆ operator!=() [3/3]

INLINE bool gum::SequenceImplementation< Key, Alloc, Gen >::operator!= ( const SequenceImplementation< Key, OtherAlloc, true > &  k) const
inherited

Definition at line 1011 of file sequence_tpl.h.

1011  {
1012  return !operator==(k);
1013  }
bool operator==(const SequenceImplementation< Key, OtherAlloc, Gen > &k) const
Returns true if the content of k equals that of *this.
Definition: sequence_tpl.h:596

◆ operator<<() [1/2]

INLINE SequenceImplementation< Key, Alloc, Gen > & gum::SequenceImplementation< Key, Alloc, Gen >::operator<< ( const Key &  k)
inherited

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

Parameters
kThe key we wish to insert in the sequence.
Returns
Returns this gum::SequenceImplementation.
Exceptions
DuplicateElementRaised if the sequence contains already k.

Definition at line 438 of file sequence_tpl.h.

438  {
439  insert(k);
440  return *this;
441  }
void insert(const Key &k)
Insert an element at the end of the sequence.
Definition: sequence_tpl.h:408

◆ operator<<() [2/2]

INLINE SequenceImplementation< Key, Alloc, Gen > & gum::SequenceImplementation< Key, Alloc, Gen >::operator<< ( Key &&  k)
inherited

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

Parameters
kThe key we wish to insert in the sequence.
Returns
Returns this gum::SequenceImplementation.
Exceptions
DuplicateElementRaised if the sequence contains already k.

Definition at line 446 of file sequence_tpl.h.

446  {
447  insert(std::move(k));
448  return *this;
449  }
void insert(const Key &k)
Insert an element at the end of the sequence.
Definition: sequence_tpl.h:408

◆ operator=() [1/4]

template<typename Key, typename Alloc>
INLINE Sequence< Key, Alloc > & gum::Sequence< Key, Alloc >::operator= ( const Sequence< Key, Alloc > &  aSeq)

Copy operator.

Parameters
aSeqThe sequence to copy.
Returns
Returns a ref to this.

Definition at line 1151 of file sequence_tpl.h.

1151  {
1153  return *this;
1154  }
SequenceImplementation< Key, Alloc, Gen > & operator=(const SequenceImplementation< Key, Alloc, Gen > &aSeq)
Copy operator.
Definition: sequence_tpl.h:365

◆ operator=() [2/4]

template<typename Key, typename Alloc = std::allocator< Key >>
template<typename OtherAlloc >
Sequence< Key, Alloc >& gum::Sequence< Key, Alloc >::operator= ( const Sequence< Key, OtherAlloc > &  aSeq)

Generalized opy operator.

Template Parameters
otherallocThe other gum::sequenceimplementation allocator.
Parameters
aSeqThe sequence to copy.
Returns
Returns a ref to this.

◆ operator=() [3/4]

template<typename Key, typename Alloc>
INLINE Sequence< Key, Alloc > & gum::Sequence< Key, Alloc >::operator= ( Sequence< Key, Alloc > &&  aSeq)

Move operator.

Parameters
aSeqThe sequence to move.
Returns
Returns a ref to this.

Definition at line 1168 of file sequence_tpl.h.

1168  {
1169  Implementation::operator=(std::move(aSeq));
1170  return *this;
1171  }
SequenceImplementation< Key, Alloc, Gen > & operator=(const SequenceImplementation< Key, Alloc, Gen > &aSeq)
Copy operator.
Definition: sequence_tpl.h:365

◆ operator=() [4/4]

template<typename Key, typename Alloc = std::allocator< Key >>
template<typename OtherAlloc >
INLINE Sequence< Key, Alloc >& gum::Sequence< Key, Alloc >::operator= ( const Sequence< Key, OtherAlloc > &  aSeq)

Definition at line 1160 of file sequence_tpl.h.

1160  {
1162  return *this;
1163  }
SequenceImplementation< Key, Alloc, Gen > & operator=(const SequenceImplementation< Key, Alloc, Gen > &aSeq)
Copy operator.
Definition: sequence_tpl.h:365

◆ operator==() [1/2]

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

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
OtherAllocThe other gum::SequenceImplementation allocator.
Parameters
kThe other gum::SequenceImplementation. Returns true if both gum::SequenceImplementation are equal.

Definition at line 596 of file sequence_tpl.h.

596  {
597  if (size() != k.size())
598  return false;
599  else {
600  for (Idx i = 0; i < size(); ++i)
601  if (*__v[i] != *(k.__v[i])) return false;
602  }
603 
604  return true;
605  }
Size size() const noexcept
Returns the size of the sequence.
Definition: sequence_tpl.h:38
std::vector< Key *, typename Alloc::template rebind< Key * >::other > __v
The set of the elements stored into the sequence.
Definition: sequence.h:503

◆ operator==() [2/2]

bool gum::SequenceImplementation< Key, Alloc, Gen >::operator== ( const SequenceImplementation< Key, OtherAlloc, true > &  k) const
inherited

Definition at line 996 of file sequence_tpl.h.

996  {
997  if (size() != k.size())
998  return false;
999  else {
1000  for (Idx i = 0; i < size(); ++i)
1001  if (__v[i] != k.__v[i]) return false;
1002  }
1003 
1004  return true;
1005  }
Size size() const noexcept
Returns the size of the sequence.
Definition: sequence_tpl.h:38
std::vector< Key *, typename Alloc::template rebind< Key * >::other > __v
The set of the elements stored into the sequence.
Definition: sequence.h:503

◆ operator>>()

INLINE SequenceImplementation< Key, Alloc, true > & gum::SequenceImplementation< Key, Alloc >::operator>> ( const Key &  k)
inherited

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
kThe key we wish to remove.
Returns
Returns this gum::SequenceImplementation.

Definition at line 493 of file sequence_tpl.h.

493  {
494  erase(k);
495  return *this;
496  }
void erase(const Key &k)
Remove an element from the sequence.
Definition: sequence_tpl.h:453

◆ operator[]()

INLINE const Key & gum::SequenceImplementation< Key, Alloc >::operator[] ( Idx  i) const
inherited

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

Parameters
iThe position of the element to return.
Returns
Returns the element at position i.
Exceptions
OutOfBoundsRaised if the element does not exist.

Definition at line 512 of file sequence_tpl.h.

512  {
513  return atPos(i);
514  }
const Key & atPos(Idx i) const
Returns the object at the pos i.
Definition: sequence_tpl.h:500

◆ pos()

INLINE Idx gum::SequenceImplementation< Key, Alloc >::pos ( const Key &  key) const
inherited

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

Parameters
keyThe element for which the positon is returned.
Returns
Returns the position of the object passed in argument.
Exceptions
NotFoundRaised if the element does not exist.

Definition at line 518 of file sequence_tpl.h.

Referenced by gum::prm::GSpan< GUM_SCALAR >::__subgraph_mining(), gum::MultiDimWithOffset< GUM_SCALAR >::erase(), gum::MultiDimArray< GUM_SCALAR >::erase(), and gum::MultiDimFunctionGraphManager< bool, ExactTerminalNodePolicy >::minimizeSize().

518  {
519  return __h[key];
520  }
HashTable< Key, Idx, Alloc > __h
Keep track of the position of the element in v (for fast retrieval).
Definition: sequence.h:500

◆ rbegin()

INLINE SequenceIterator< Key > gum::SequenceImplementation< Key, Alloc >::rbegin ( ) const
inherited

Returns an unsafe rbegin iterator.

Returns
Returns an unsafe rbegin iterator.

Definition at line 671 of file sequence_tpl.h.

671  {
672  SequenceIterator< Key > it{*this};
673  it.__setPos(size() - 1);
674  return it;
675  }
Size size() const noexcept
Returns the size of the sequence.
Definition: sequence_tpl.h:38

◆ rbeginSafe()

INLINE SequenceIteratorSafe< Key > gum::SequenceImplementation< Key, Alloc >::rbeginSafe ( ) const
inherited

Returns a safe rbegin iterator.

Returns
Returns a safe rbegin iterator.

Definition at line 641 of file sequence_tpl.h.

641  {
642  SequenceIteratorSafe< Key > it{*this};
643  it.__setPos(size() - 1);
644  return it;
645  }
Size size() const noexcept
Returns the size of the sequence.
Definition: sequence_tpl.h:38

◆ rend()

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

Returns the unsafe rend iterator.

Returns
Returns the unsafe rend iterator.

Definition at line 680 of file sequence_tpl.h.

680  {
681  return __rend_safe;
682  }
SequenceIteratorSafe< Key > __rend_safe
Stores the rend iterator for fast access.
Definition: sequence.h:513

◆ rendSafe()

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

Returns the safe rend iterator.

Returns
Returns the safe rend iterator.

Definition at line 650 of file sequence_tpl.h.

650  {
651  return __rend_safe;
652  }
SequenceIteratorSafe< Key > __rend_safe
Stores the rend iterator for fast access.
Definition: sequence.h:513

◆ resize()

INLINE void gum::SequenceImplementation< Key, Alloc >::resize ( Size  new_size)
inherited

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_sizeThe internal structure new size.

Definition at line 686 of file sequence_tpl.h.

686  {
687  if (new_size < __h.size()) return;
688 
689  __h.resize(new_size);
690  __v.reserve(new_size);
691  }
void resize(Size new_size)
Changes the number of slots in the &#39;nodes&#39; vector of the hash table.
Size size() const noexcept
Returns the number of elements stored into the hashtable.
HashTable< Key, Idx, Alloc > __h
Keep track of the position of the element in v (for fast retrieval).
Definition: sequence.h:500
std::vector< Key *, typename Alloc::template rebind< Key * >::other > __v
The set of the elements stored into the sequence.
Definition: sequence.h:503

◆ setAtPos() [1/2]

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

Change the value.

Parameters
iThe element's position.
newKeyThe element's new value.
Exceptions
NotFoundRaised if the element does not exist.
DuplicateElementRaised if newKey alreay exists.

Definition at line 525 of file sequence_tpl.h.

526  {
527  if (i >= __h.size()) { GUM_ERROR(NotFound, "index too large"); }
528 
529  Key& new_key = const_cast< Key& >(__h.insert(newKey, i).first);
530  __h.erase(*(__v[i]));
531  __v[i] = &new_key;
532  }
Size size() const noexcept
Returns the number of elements stored into the hashtable.
void erase(const Key &key)
Removes a given element from the hash table.
HashTable< Key, Idx, Alloc > __h
Keep track of the position of the element in v (for fast retrieval).
Definition: sequence.h:500
std::vector< Key *, typename Alloc::template rebind< Key * >::other > __v
The set of the elements stored into the sequence.
Definition: sequence.h:503
value_type & insert(const Key &key, const Val &val)
Adds a new element (actually a copy of this element) into the hash table.
#define GUM_ERROR(type, msg)
Definition: exceptions.h:55

◆ setAtPos() [2/2]

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

Change the value.

Parameters
iThe element's position.
newKeyThe element's new value.
Exceptions
NotFoundRaised if the element does not exist.
DuplicateElementRaised if newKey alreay exists.

Definition at line 536 of file sequence_tpl.h.

537  {
538  if (i >= __h.size()) { GUM_ERROR(NotFound, "index too large"); }
539 
540  Key& new_key = const_cast< Key& >(__h.insert(std::move(newKey), i).first);
541  __h.erase(*(__v[i]));
542  __v[i] = &new_key;
543  }
Size size() const noexcept
Returns the number of elements stored into the hashtable.
void erase(const Key &key)
Removes a given element from the hash table.
HashTable< Key, Idx, Alloc > __h
Keep track of the position of the element in v (for fast retrieval).
Definition: sequence.h:500
std::vector< Key *, typename Alloc::template rebind< Key * >::other > __v
The set of the elements stored into the sequence.
Definition: sequence.h:503
value_type & insert(const Key &key, const Val &val)
Adds a new element (actually a copy of this element) into the hash table.
#define GUM_ERROR(type, msg)
Definition: exceptions.h:55

◆ size()

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

Returns the size of the sequence.

Returns
Returns the size of the sequence.

Definition at line 38 of file sequence_tpl.h.

Referenced by gum::prm::StructuredInference< GUM_SCALAR >::__addEdgesInReducedGraph(), gum::prm::PRMFactory< GUM_SCALAR >::__buildSlotChain(), gum::Instantiation::__init(), gum::prm::PRMClass< double >::__overloadReference(), gum::Instantiation::__reorder(), gum::MultiDimWithOffset< GUM_SCALAR >::erase(), and gum::MultiDimArray< GUM_SCALAR >::erase().

38  {
39  return __h.size();
40  }
Size size() const noexcept
Returns the number of elements stored into the hashtable.
HashTable< Key, Idx, Alloc > __h
Keep track of the position of the element in v (for fast retrieval).
Definition: sequence.h:500

◆ swap()

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

Swap index.

Parameters
iThe index of the first elt to swap.
jThe index of the other elt to swap.

Definition at line 547 of file sequence_tpl.h.

Referenced by gum::MultiDimFunctionGraphManager< bool, ExactTerminalNodePolicy >::minimizeSize().

547  {
548  if (i == j) return;
549 
550  Key& ki = const_cast< Key& >(atPos(i));
551  Key& kj = const_cast< Key& >(atPos(j));
552 
553  __h[ki] = j;
554  __h[kj] = i;
555 
556  __v[i] = &kj;
557  __v[j] = &ki;
558  }
HashTable< Key, Idx, Alloc > __h
Keep track of the position of the element in v (for fast retrieval).
Definition: sequence.h:500
std::vector< Key *, typename Alloc::template rebind< Key * >::other > __v
The set of the elements stored into the sequence.
Definition: sequence.h:503
const Key & atPos(Idx i) const
Returns the object at the pos i.
Definition: sequence_tpl.h:500

◆ toString()

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

Displays the content of the sequence.

Returns
The content of the sequence.

Definition at line 574 of file sequence_tpl.h.

Referenced by gum::operator<<().

574  {
575  std::stringstream stream;
576  stream << "[";
577 
578  if (!__h.empty()) {
579  stream << 0 << ":" << *__v[0];
580 
581  for (Idx i = 1; i < __h.size(); ++i) {
582  stream << " - " << i << ":" << *__v[i];
583  }
584  }
585 
586  stream << "]";
587 
588  std::string res = stream.str();
589  return res;
590  }
Size size() const noexcept
Returns the number of elements stored into the hashtable.
HashTable< Key, Idx, Alloc > __h
Keep track of the position of the element in v (for fast retrieval).
Definition: sequence.h:500
std::vector< Key *, typename Alloc::template rebind< Key * >::other > __v
The set of the elements stored into the sequence.
Definition: sequence.h:503
bool empty() const noexcept
Indicates whether the hash table is empty.

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