aGrUM  0.14.3
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 1019 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 1031 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 1033 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 1035 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 1028 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 1026 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 1030 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 1040 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 1032 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 1034 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 1027 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 1025 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 1029 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 1024 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 1096 of file sequence_tpl.h.

1096  :
1097  SequenceImplementation< Key, Alloc, std::is_scalar< Key >::value >(
1098  size_param) {
1099  // for debugging purposes
1100  GUM_CONSTRUCTOR(Sequence);
1101  }
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 1105 of file sequence_tpl.h.

1105  :
1106  SequenceImplementation< Key, Alloc, std::is_scalar< Key >::value >(list) {
1107  // for debugging purposes
1108  GUM_CONSTRUCTOR(Sequence);
1109  }
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 1113 of file sequence_tpl.h.

1113  :
1114  SequenceImplementation< Key, Alloc, std::is_scalar< Key >::value >(aSeq) {
1115  // for debugging purposes
1116  GUM_CONS_CPY(Sequence);
1117  }
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 1131 of file sequence_tpl.h.

1131  :
1132  SequenceImplementation< Key, Alloc, std::is_scalar< Key >::value >(
1133  std::move(aSeq)) {
1134  // for debugging purposes
1135  GUM_CONS_MOV(Sequence);
1136  }
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 1140 of file sequence_tpl.h.

1140  {
1141  // for debugging purposes
1142  GUM_DESTRUCTOR(Sequence);
1143  }
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 1123 of file sequence_tpl.h.

1123  :
1124  SequenceImplementation< Key, Alloc, std::is_scalar< Key >::value >(aSeq) {
1125  // for debugging purposes
1126  GUM_CONS_CPY(Sequence);
1127  }
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 277 of file sequence_tpl.h.

278  {
279  clear();
280 
281  for (Size i = 0; i < aSeq.size(); ++i) {
282  Key& new_key = const_cast< Key& >(__h.insert(*(aSeq.__v[i]), i).first);
283  __v.push_back(&new_key);
284  }
285 
286  __update_end();
287  }
HashTable< Key, Idx, Alloc > __h
Keep track of the position of the element in v (for fast retrieval).
Definition: sequence.h:497
void __update_end() noexcept
A method to update the end iterator after changes in the sequence.
Definition: sequence_tpl.h:262
std::vector< Key *, typename Alloc::template rebind< Key * >::other > __v
The set of the elements stored into the sequence.
Definition: sequence.h:500
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:45
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 711 of file sequence_tpl.h.

712  {
713  clear();
714 
715  for (Size i = 0; i < aSeq.size(); ++i) {
716  __h.insert(aSeq.__v[i], i);
717  __v.push_back(aSeq.__v[i]);
718  }
719 
720  __update_end();
721  }
HashTable< Key, Idx, Alloc > __h
Keep track of the position of the element in v (for fast retrieval).
Definition: sequence.h:497
void __update_end() noexcept
A method to update the end iterator after changes in the sequence.
Definition: sequence_tpl.h:262
std::vector< Key *, typename Alloc::template rebind< Key * >::other > __v
The set of the elements stored into the sequence.
Definition: sequence.h:500
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:45
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 497 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().

497  {
498  if (i >= __h.size()) {
499  GUM_ERROR(OutOfBounds,
500  "index " << i << " for a sequence of size" << __h.size());
501  }
502 
503  return *(__v[i]);
504  }
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:497
std::vector< Key *, typename Alloc::template rebind< Key * >::other > __v
The set of the elements stored into the sequence.
Definition: sequence.h:500
#define GUM_ERROR(type, msg)
Definition: exceptions.h:52

◆ 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 565 of file sequence_tpl.h.

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

565  {
566  return atPos(size() - 1);
567  }
Size size() const noexcept
Returns the size of the sequence.
Definition: sequence_tpl.h:35
const Key & atPos(Idx i) const
Returns the object at the pos i.
Definition: sequence_tpl.h:497

◆ 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 654 of file sequence_tpl.h.

654  {
655  return SequenceIterator< Key >{*this};
656  }

◆ 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 624 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 268 of file sequence_tpl.h.

268  {
269  __h.clear();
270  __v.clear();
271  __update_end();
272  }
HashTable< Key, Idx, Alloc > __h
Keep track of the position of the element in v (for fast retrieval).
Definition: sequence.h:497
void __update_end() noexcept
A method to update the end iterator after changes in the sequence.
Definition: sequence_tpl.h:262
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:500

◆ 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 1173 of file sequence_tpl.h.

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

◆ 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 424 of file sequence_tpl.h.

424  {
425  Key key(std::forward< Args >(args)...);
426  Key& new_key =
427  const_cast< Key& >(__h.insert(std::move(key), __h.size()).first);
428  __v.push_back(&new_key);
429  __update_end();
430  }
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:497
void __update_end() noexcept
A method to update the end iterator after changes in the sequence.
Definition: sequence_tpl.h:262
std::vector< Key *, typename Alloc::template rebind< Key * >::other > __v
The set of the elements stored into the sequence.
Definition: sequence.h:500
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 41 of file sequence_tpl.h.

41  {
42  return __h.empty();
43  }
HashTable< Key, Idx, Alloc > __h
Keep track of the position of the element in v (for fast retrieval).
Definition: sequence.h:497
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 661 of file sequence_tpl.h.

661  {
662  return __end_safe;
663  }
SequenceIteratorSafe< Key > __end_safe
Stores the end iterator for fast access.
Definition: sequence.h:507

◆ 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 631 of file sequence_tpl.h.

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

631  {
632  return __end_safe;
633  }
SequenceIteratorSafe< Key > __end_safe
Stores the end iterator for fast access.
Definition: sequence.h:507

◆ 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 450 of file sequence_tpl.h.

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

450  {
451  // get the position of the element to remove
452  Idx pos;
453 
454  try {
455  pos = __h[k];
456  } catch (NotFound&) { return; }
457 
458  // erase the element
459  __v.erase(__v.begin() + pos);
460  for (Idx i = pos, nb_elts = __h.size() - 1; i < nb_elts; ++i) {
461  --__h[*(__v[i])];
462  }
463  __h.erase(k);
464 
465  __update_end();
466  }
Idx pos(const Key &key) const
Returns the position of the object passed in argument (if it exists).
Definition: sequence_tpl.h:515
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:497
void __update_end() noexcept
A method to update the end iterator after changes in the sequence.
Definition: sequence_tpl.h:262
std::vector< Key *, typename Alloc::template rebind< Key * >::other > __v
The set of the elements stored into the sequence.
Definition: sequence.h:500

◆ 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 471 of file sequence_tpl.h.

471  {
472  if (iter.pos() >= size()) return;
473 
474  // erase the element
475  Idx pos = iter.pos();
476  Key* key = __v[pos];
477  __v.erase(__v.begin() + pos);
478 
479  for (Idx i = pos, nb_elts = __h.size() - 1; i < nb_elts; ++i) {
480  --__h[*(__v[i])];
481  }
482  __h.erase(*key);
483 
484  __update_end();
485  }
Idx pos(const Key &key) const
Returns the position of the object passed in argument (if it exists).
Definition: sequence_tpl.h:515
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:35
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:497
void __update_end() noexcept
A method to update the end iterator after changes in the sequence.
Definition: sequence_tpl.h:262
std::vector< Key *, typename Alloc::template rebind< Key * >::other > __v
The set of the elements stored into the sequence.
Definition: sequence.h:500

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

399  {
400  return __h.exists(k);
401  }
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:497

◆ 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 559 of file sequence_tpl.h.

559  {
560  return atPos(0);
561  }
const Key & atPos(Idx i) const
Returns the object at the pos i.
Definition: sequence_tpl.h:497

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

405  {
406  // k will be added at the end. Insert the new key into the hashtable
407  Key& new_key = const_cast< Key& >(__h.insert(k, __h.size()).first);
408  __v.push_back(&new_key);
409  __update_end();
410  }
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:497
void __update_end() noexcept
A method to update the end iterator after changes in the sequence.
Definition: sequence_tpl.h:262
std::vector< Key *, typename Alloc::template rebind< Key * >::other > __v
The set of the elements stored into the sequence.
Definition: sequence.h:500
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 414 of file sequence_tpl.h.

414  {
415  // k will be added at the end. Insert the new key into the hashtable
416  Key& new_key = const_cast< Key& >(__h.insert(std::move(k), __h.size()).first);
417  __v.push_back(&new_key);
418  __update_end();
419  }
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:497
void __update_end() noexcept
A method to update the end iterator after changes in the sequence.
Definition: sequence_tpl.h:262
std::vector< Key *, typename Alloc::template rebind< Key * >::other > __v
The set of the elements stored into the sequence.
Definition: sequence.h:500
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 608 of file sequence_tpl.h.

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

◆ operator!=() [3/3]

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

Definition at line 1008 of file sequence_tpl.h.

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

◆ 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 435 of file sequence_tpl.h.

435  {
436  insert(k);
437  return *this;
438  }
void insert(const Key &k)
Insert an element at the end of the sequence.
Definition: sequence_tpl.h:405

◆ 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 443 of file sequence_tpl.h.

443  {
444  insert(std::move(k));
445  return *this;
446  }
void insert(const Key &k)
Insert an element at the end of the sequence.
Definition: sequence_tpl.h:405

◆ 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 1148 of file sequence_tpl.h.

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

◆ 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 1165 of file sequence_tpl.h.

1165  {
1166  Implementation::operator=(std::move(aSeq));
1167  return *this;
1168  }
SequenceImplementation< Key, Alloc, Gen > & operator=(const SequenceImplementation< Key, Alloc, Gen > &aSeq)
Copy operator.
Definition: sequence_tpl.h:362

◆ 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 1157 of file sequence_tpl.h.

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

◆ 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 593 of file sequence_tpl.h.

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

◆ operator==() [2/2]

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

Definition at line 993 of file sequence_tpl.h.

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

◆ 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 490 of file sequence_tpl.h.

490  {
491  erase(k);
492  return *this;
493  }
void erase(const Key &k)
Remove an element from the sequence.
Definition: sequence_tpl.h:450

◆ 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 509 of file sequence_tpl.h.

509  {
510  return atPos(i);
511  }
const Key & atPos(Idx i) const
Returns the object at the pos i.
Definition: sequence_tpl.h:497

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

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

◆ 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 668 of file sequence_tpl.h.

668  {
669  SequenceIterator< Key > it{*this};
670  it.__setPos(size() - 1);
671  return it;
672  }
Size size() const noexcept
Returns the size of the sequence.
Definition: sequence_tpl.h:35

◆ 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 638 of file sequence_tpl.h.

638  {
639  SequenceIteratorSafe< Key > it{*this};
640  it.__setPos(size() - 1);
641  return it;
642  }
Size size() const noexcept
Returns the size of the sequence.
Definition: sequence_tpl.h:35

◆ 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 677 of file sequence_tpl.h.

677  {
678  return __rend_safe;
679  }
SequenceIteratorSafe< Key > __rend_safe
Stores the rend iterator for fast access.
Definition: sequence.h:510

◆ 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 647 of file sequence_tpl.h.

647  {
648  return __rend_safe;
649  }
SequenceIteratorSafe< Key > __rend_safe
Stores the rend iterator for fast access.
Definition: sequence.h:510

◆ 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 683 of file sequence_tpl.h.

683  {
684  if (new_size < __h.size()) return;
685 
686  __h.resize(new_size);
687  __v.reserve(new_size);
688  }
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:497
std::vector< Key *, typename Alloc::template rebind< Key * >::other > __v
The set of the elements stored into the sequence.
Definition: sequence.h:500

◆ 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 522 of file sequence_tpl.h.

523  {
524  if (i >= __h.size()) { GUM_ERROR(NotFound, "index too large"); }
525 
526  Key& new_key = const_cast< Key& >(__h.insert(newKey, i).first);
527  __h.erase(*(__v[i]));
528  __v[i] = &new_key;
529  }
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:497
std::vector< Key *, typename Alloc::template rebind< Key * >::other > __v
The set of the elements stored into the sequence.
Definition: sequence.h:500
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:52

◆ 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 533 of file sequence_tpl.h.

534  {
535  if (i >= __h.size()) { GUM_ERROR(NotFound, "index too large"); }
536 
537  Key& new_key = const_cast< Key& >(__h.insert(std::move(newKey), i).first);
538  __h.erase(*(__v[i]));
539  __v[i] = &new_key;
540  }
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:497
std::vector< Key *, typename Alloc::template rebind< Key * >::other > __v
The set of the elements stored into the sequence.
Definition: sequence.h:500
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:52

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

35  {
36  return __h.size();
37  }
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:497

◆ 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 544 of file sequence_tpl.h.

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

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

◆ 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 571 of file sequence_tpl.h.

Referenced by gum::operator<<().

571  {
572  std::stringstream stream;
573  stream << "[";
574 
575  if (!__h.empty()) {
576  stream << 0 << ":" << *__v[0];
577 
578  for (Idx i = 1; i < __h.size(); ++i) {
579  stream << " - " << i << ":" << *__v[i];
580  }
581  }
582 
583  stream << "]";
584 
585  std::string res = stream.str();
586  return res;
587  }
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:497
std::vector< Key *, typename Alloc::template rebind< Key * >::other > __v
The set of the elements stored into the sequence.
Definition: sequence.h:500
bool empty() const noexcept
Indicates whether the hash table is empty.

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