aGrUM  0.21.0
a C++ library for (probabilistic) graphical models
bijection.h
Go to the documentation of this file.
1 /**
2  *
3  * Copyright (c) 2005-2021 by Pierre-Henri WUILLEMIN(@LIP6) & Christophe GONZALES(@AMU)
4  * info_at_agrum_dot_org
5  *
6  * This library is free software: you can redistribute it and/or modify
7  * it under the terms of the GNU Lesser General Public License as published by
8  * the Free Software Foundation, either version 3 of the License, or
9  * (at your option) any later version.
10  *
11  * This library is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public License
17  * along with this library. If not, see <http://www.gnu.org/licenses/>.
18  *
19  */
20 
21 
22 /**
23  * @file
24  * @brief Set of pairs of elements with fast search for both elements.
25  *
26  * Bijections are some kind of sets of pairs (T1,T2) with the additional
27  * feature as compared to Sets: we can search very quickly T2's elements when
28  * knowing T1 and T1's elements when knowing T2.
29  *
30  * @author Christophe GONZALES(@AMU) and Jean-Philippe DUBUS
31  */
32 #ifndef GUM_BIJECTION_H
33 #define GUM_BIJECTION_H
34 
35 #include <initializer_list>
36 #include <iostream>
37 #include <sstream>
38 #include <string>
39 #include <type_traits>
40 
41 #include <agrum/tools/core/hashTable.h>
42 
43 namespace gum {
44 
45 #ifndef DOXYGEN_SHOULD_SKIP_THIS
46 
47  template < typename T1, typename T2 >
48  class BijectionIteratorSafe;
49  template < typename T1, typename T2 >
50  class BijectionIterator;
51  template < typename T1, typename T2, typename Alloc, bool >
52  class BijectionImplementation;
53  template < typename T1, typename T2, typename Alloc >
54  class Bijection;
55 
56 #endif /* DOXYGEN_SHOULD_SKIP_THIS */
57 
58 
59  // ===========================================================================
60  // === NON SCALAR BIJECTION IMPLEMENTATION ===
61  // ===========================================================================
62 
63  /**
64  * @class BijectionImplementation
65  * @headerfile bijection.h <agrum/tools/core/bijection.h>
66  * @brief A non scalar implementation of a Bijection.
67  * @ingroup bijection_group
68  *
69  * This class is designed for modeling a gum::Bijection between two sets, the
70  * idea is following :
71  * - We want to create a gum::Bjection relation between type T1 and type T2,
72  * - For x in T1, there exists only one y in T2 associated to x,
73  * - For y in T2, there exists only one x in T1 associated to y,
74  * - The user inserts all the (x, y) associations and can search efficiently
75  * the values thus associated.
76  *
77  * @tparam T1 The first type of elements in the gum::Bjection.
78  * @tparam T2 The second type of elements in the gum::Bjection.
79  * @tparam Alloc The allocator used for allocating memory.
80  * @tparam Gen If true, this will be replaced by a implementation omptimized
81  * for non-scalar types.
82  */
83  template < typename T1, typename T2, typename Alloc, bool Gen >
84  class BijectionImplementation {
85  public:
86  /// types for STL compliance
87  /// @{
88  using type1_type = T1;
89  using type1_reference = T1&;
90  using type1_const_reference = const T1&;
91  using type1_pointer = T1*;
92  using type1_const_pointer = const T1*;
93  using type2_type = T2;
94  using type2_reference = T2&;
95  using type2_const_reference = const T2&;
96  using type2_pointer = T2*;
97  using type2_const_pointer = const T2*;
98  using size_type = std::size_t;
99  using difference_type = std::ptrdiff_t;
100  using allocator_type = Alloc;
101  using iterator = BijectionIterator< T1, T2 >;
102  using const_iterator = BijectionIterator< T1, T2 >;
103  using iterator_safe = BijectionIteratorSafe< T1, T2 >;
104  using const_iterator_safe = BijectionIteratorSafe< T1, T2 >;
105  using allocator12_type = typename Alloc::template rebind< std::pair< T1, T2* > >::other;
106  using allocator21_type = typename Alloc::template rebind< std::pair< T2, T1* > >::other;
107  /// @}
108 
109  private:
110  /**
111  * @brief Default constructor: creates a gum::Bijection without any
112  * association.
113  * @param size The Bijection starting size.
114  * @param resize_policy If true, the gum::Bijection will resize itself
115  * automatically.
116  */
117  BijectionImplementation(Size size, bool resize_policy);
118 
119  /**
120  * @brief Initializer list constructor.
121  * @param list The initialize list.
122  */
123  BijectionImplementation(std::initializer_list< std::pair< T1, T2 > > list);
124 
125  /**
126  * @brief Copy constructor.
127  * @param toCopy Bijection to copy.
128  */
129  BijectionImplementation(const BijectionImplementation< T1, T2, Alloc, Gen >& toCopy);
130 
131  /**
132  * @brief Generalized copy constructor.
133  * @param toCopy Bijection to copy.
134  */
135  template < typename OtherAlloc >
136  BijectionImplementation(const BijectionImplementation< T1, T2, OtherAlloc, Gen >& toCopy);
137 
138  /**
139  * @brief Move constructor.
140  * @param from Bijection to move.
141  */
142  BijectionImplementation(BijectionImplementation< T1, T2, Alloc, Gen >&& from) noexcept;
143 
144  public:
145  // ============================================================================
146  /// @name Constructors/destructors
147  // ============================================================================
148  /// @{
149 
150  /**
151  * @brief Destructor.
152  */
153  ~BijectionImplementation();
154 
155  /// @}
156 
157  private:
158  /**
159  * @brief Copy operator.
160  * @param toCopy Bijection to copy.
161  * @return Returns the gum::Bijection in which the copy was made.
162  */
163  BijectionImplementation< T1, T2, Alloc, Gen >&
164  operator=(const BijectionImplementation< T1, T2, Alloc, Gen >& toCopy);
165 
166  /**
167  * @brief Generalized copy operator.
168  * @param toCopy Bijection to copy.
169  * @return Returns the gum::Bijection in which the copy was made.
170  */
171  template < typename OtherAlloc >
172  BijectionImplementation< T1, T2, Alloc, Gen >&
173  operator=(const BijectionImplementation< T1, T2, OtherAlloc, Gen >& toCopy);
174 
175  /**
176  * @brief Move operator.
177  * @param toCopy Bijection to move
178  * @return Returns the moved gum::Bijection in which the move was made.
179  */
180  BijectionImplementation< T1, T2, Alloc, Gen >&
181  operator=(BijectionImplementation< T1, T2, Alloc, Gen >&& toCopy);
182 
183  public:
184  // ============================================================================
185  /// @name Iterators
186  // ============================================================================
187  /// @{
188 
189  /**
190  * @brief Returns the unsafe iterator at the beginning of the
191  * gum::Bijection.
192  *
193  * Unsafe iterators are a little bit faster than safe ones. But this speed
194  * is at the expense of safety: if you point to an element that is deleted,
195  * then try to access it or trying to operate a ++ will most certainly
196  * result in a segfault. So, Unsafe iterators should only be used to parse
197  * gum::Bjection where no element is ever deleted. If unsure, prefer using
198  * safe iterators.
199  *
200  * Note that the notion of a beginning/end of a gum::Bjection is rather
201  * fuzzy.
202  * What is important here is that for an instance bij of this class:
203  *
204  * @code
205  * for(iterator iter = bij.begin(); iter != bij.end(); ++iter) {
206  * // will parse all the associations.
207  * }
208  * @endcode
209  */
210  iterator begin() const;
211 
212  /**
213  * @brief Returns the constant unsafe iterator at the beginning of the
214  * gum::Bjection.
215  *
216  * Unsafe iterators are a little bit faster than safe ones. But this speed
217  * is at the expense of safety: if you point to an element that is deleted,
218  * then try to access it or trying to operate a ++ will most certainly
219  * result in a segfault. So, Unsafe iterators should only be used to parse
220  * gum::Bjection where no element is ever deleted. If unsure, prefer using
221  * safe iterators.
222  *
223  * Note that the notion of a beginning/end of a gum::Bjection is rather
224  * fuzzy. What is important here is that for an instance bij of this
225  * class:
226  *
227  * @code
228  * for (iterator iter = bij.cbegin(); iter != bij.cend(); ++iter) {
229  * // will parse all the association
230  * }
231  * @endcode
232  */
233  const_iterator cbegin() const;
234 
235  /**
236  * @brief Returns the unsafe iterator at the end of the gum::Bijection.
237  *
238  * Unsafe iterators are a little bit faster than safe ones. But this speed
239  * is at the expense of safety: if you point to an element that is deleted,
240  * then try to access it or trying to operate a ++ will most certainly
241  * result in a segfault. So, Unsafe iterators should only be used to parse
242  * gum::Bijection where no element is ever deleted. If unsure, prefer using
243  * safe iterators.
244  *
245  * Note that the notion of a beginning/end of a gum::Bijection is rather
246  * fuzzy. What is important here is that for an instance bij of this
247  * class:
248  *
249  * @code
250  * for(iterator iter = bij.begin(); iter != bij.end(); ++iter) {
251  * // loops will parse all the associations
252  * }
253  * @endcode
254  */
255  const iterator& end() const noexcept;
256 
257  /**
258  * @brief Returns the constant iterator at the end of the gum::Bijection.
259  *
260  * Unsafe iterators are a little bit faster than safe ones. But this speed
261  * is at the expense of safety: if you point to an element that is deleted,
262  * then try to access it or trying to operate a ++ will most certainly
263  * result in a segfault. So, Unsafe iterators should only be used to parse
264  * gum::Bijection where no element is ever deleted. If unsure, prefer using
265  * safe iterators.
266  *
267  * Note that the notion of a beginning/end of a gum::Bijection is rather
268  * fuzzy.
269  * What is important here is that for an instance bij of this class:
270  *
271  * @code
272  * for (iterator iter = bij.cbegin(); iter != bij.cend(); ++iter) {
273  * // loops will parse all the associations
274  * }
275  * @endcode
276  */
277  const const_iterator& cend() const noexcept;
278 
279  /**
280  * @brief Returns the safe iterator at the beginning of the gum::Bijection.
281  *
282  * Safe iterators are slightly slower than unsafe iterators. However, they
283  * guarantee that no segmentation fault can ever occur when trying to
284  * access the element they point to or when applying a ++ operator. When no
285  * element of the gum::Bijection is to be deleted during the parsing of the
286  * gum::Bijection (as for instance when you parse the gum::Bijection to
287  * display its content), prefer using the unsafe iterators, which are a
288  * little bit faster and cannot, in this case, produce segfaults.
289  *
290  * Note that the notion of a beginning/end of a gum::Bijection is rather
291  * fuzzy. What is important here is that for an instance bij of this
292  * class:
293  *
294  * @code
295  * for (iterator iter = bij.beginSafe(); iter != bij.endSafe(); ++iter) {
296  * // loops will parse all the associations
297  * }
298  * @endcode
299  */
300  iterator_safe beginSafe() const;
301 
302  /**
303  * @brief Returns the constant safe iterator at the begining of the
304  * gum::Bijection.
305  *
306  * Safe iterators are slightly slower than unsafe iterators. However, they
307  * guarantee that no segmentation fault can ever occur when trying to
308  * access the element they point to or when applying a ++ operator. When no
309  * element of the gum::Bijection is to be deleted during the parsing of the
310  * gum::Bijection (as for instance when you parse the bijection to display
311  * its content), prefer using the unsafe iterators, which are a little bit
312  * faster and cannot, in this case, produce segfaults.
313  *
314  * Note that the notion of a beginning/end of a gum::Bijection is rather
315  * fuzzy. What is important here is that for an instance bij of this
316  * class:
317  *
318  * @code
319  * for (iterator iter = bij.cbeginSafe(); iter != bij.cendSafe(); ++iter) {
320  * // loops will parse all the associations
321  * }
322  * @endcode
323  */
324  const_iterator_safe cbeginSafe() const;
325 
326  /**
327  * @brief Returns the safe iterator at the end of the gum::Bijection.
328  *
329  * Safe iterators are slightly slower than unsafe iterators. However, they
330  * guarantee that no segmentation fault can ever occur when trying to
331  * access the element they point to or when applying a ++ operator. When no
332  * element of the gum::Bijection is to be deleted during the parsing of the
333  * gum::Bijection (as for instance when you parse the gum::Bijection to
334  * display its content), prefer using the unsafe iterators, which are a
335  * little bit faster and cannot, in this case, produce segfaults.
336  *
337  * Note that the notion of a beginning/end of a gum::Bijection is rather
338  * fuzzy.
339  * What is important here is that for an instance bij of this class:
340  *
341  * @code
342  * for (iterator iter = bij.beginSafe(); iter != bij.endSafe(); ++iter) {
343  * // loops will parse all the associations
344  * }
345  * @endcode
346  */
347  const iterator_safe& endSafe() const noexcept;
348 
349  /**
350  * @brief Returns the constant safe iterator at the end of the
351  * gum::Bijection.
352  *
353  * Safe iterators are slightly slower than unsafe iterators. However, they
354  * guarantee that no segmentation fault can ever occur when trying to
355  * access the element they point to or when applying a ++ operator. When no
356  * element of the gum::Bijection is to be deleted during the parsing of the
357  * gum::Bijection (as for instance when you parse the gum::Bijection to
358  * display its content), prefer using the unsafe iterators, which are a
359  * little bit faster and cannot, in this case, produce segfaults.
360  *
361  * Note that the notion of a beginning/end of a gum::Bijection is rather
362  * fuzzy. What is important here is that for an instance bij of this
363  * class:
364  *
365  * @code
366  * for (iterator iter = bij.cbeginSafe(); iter != bij.cendSafe(); ++iter) {
367  * // loops will parse all the associations
368  * }
369  * @endcode
370  */
371  const const_iterator_safe& cendSafe() const noexcept;
372 
373  /**
374  * @brief Returns the safe end iterator for other classes' statics.
375  *
376  * To reduce the gum::Bijection memory consumption (which are heavily used
377  * in aGrUM) while allowing fast for loops, end iterators are created just
378  * once as a static member of a non-template gum::Bijection. While this
379  * scheme is efficient and it works quite effectively, it has a drawback:
380  * other classes with static members using the
381  * BijectionImplementation::end() iterator may fail to work due to the well
382  * known "static initialization order fiasco" (see Marshall Cline's C++ FAQ
383  * for more details about this C++ feature).
384  *
385  * So what is the problem? Consider a class, say X, containing a
386  * gum::Bijection that stores all its elements in a convenient way. To
387  * reduce memory consumption, X::end iterator is a static member that is
388  * initialized with a gum::Bijection::end iterator. If the compiler decides
389  * to initialize X::end before initializing gum::Bijection::end, then
390  * X::end will be in an incoherent state.
391  *
392  * Unfortunately, we cannot know for sure in which order static members
393  * will be initialized (the order is a compiler's decision). Hence, we
394  * shall enfore the fact that gum::Bijection::end is initialized before
395  * X::end. Using method gum::Bijection::end4Statics will ensure this fact:
396  * it uses the C++ "construct on first use" idiom (see the C++ FAQ) that
397  * ensures that the order fiasco is avoided. More precisely, end4Statics
398  * uses a global variable that is the very end iterator used by all
399  * gum::Bijection. Now, this induces a small overhead. So, we also provide
400  * a gum::Bijection::end() method that returns the gum::Bijection::end
401  * iterator without this small overhead, but assuming that function
402  * end4Statics has already been called once (which is always the case) when
403  * a gum::Bijection has been created.
404  *
405  * So, to summarize: when initializing static members use endSafe4Statics()
406  * and in all the other cases, use endSafe().
407  */
408  static const iterator_safe& endSafe4Statics();
409 
410  /**
411  * @brief Returns the unsafe end iterator for other classes' statics.
412  *
413  * To reduce the gum::Bijection memory consumption (which are heavily used
414  * in aGrUM) while allowing fast for loops, end iterators are created just
415  * once as a static member of a non-template gum::Bijection. While this
416  * scheme is efficient and it works quite effectively, it has a drawback:
417  * other classes with static members using the
418  * BijectionImplementation::end() iterator may fail to work due to the well
419  * known "static initialization order fiasco" (see Marshall Cline's C++ FAQ
420  * for more details about this C++ feature).
421  *
422  * So what is the problem? Consider a class, say X, containing a
423  * gum::Bijection that stores all its elements in a convenient way. To
424  * reduce memory consumption, X::end iterator is a static member that is
425  * initialized with a gum::Bijection::end iterator. If the compiler decides
426  * to initialize X::end before initializing gum::Bijection::end, then
427  * X::end will be in an incoherent state.
428  *
429  * Unfortunately, we cannot know for sure in which order static members
430  * will be initialized (the order is a compiler's decision). Hence, we
431  * shall enfore the fact that gum::Bijection::end is initialized before
432  * X::end. Using method gum::Bijection::end4Statics will ensure this fact:
433  * it uses the C++ "construct on first use" idiom (see the C++ FAQ) that
434  * ensures that the order fiasco is avoided. More precisely, end4Statics
435  * uses a global variable that is the very end iterator used by all
436  * gum::Bijection. Now, this induces a small overhead. So, we also provide
437  * a gum::Bijection::end() method that returns the gum::Bijection::end
438  * iterator without this small overhead, but assuming that function
439  * end4Statics has already been called once (which is always the case) when
440  * a gum::Bijection has been created.
441  *
442  * So, to summarize: when initializing static members use end4Statics()
443  * and in all the other cases, use end().
444  */
445  static const iterator& end4Statics();
446 
447  /// @}
448  // ============================================================================
449  /// @name Accessors / Modifiers
450  // ============================================================================
451  /// @{
452 
453  /**
454  * @brief Returns the first value of a pair given its second value.
455  * @param second The second value of a pair in the gum::Bijection.
456  * @return Returns the first value of a pair given its second value.
457  * @throws NotFound Raised if the element cannot be found.
458  */
459  const T1& first(const T2& second) const;
460 
461  /**
462  * @brief Returns the first value of a pair given its second value or
463  * default_val if second is unfound.
464  * @param second The second value of a pair in the gum::Bijection.
465  * @param default_val The default value returned if second is not in the
466  * gum::Bijection.
467  * @return Returns the first value of a pair given its second value or
468  * default_val if second is not in the bjection.
469  */
470  const T1& firstWithDefault(const T2& second, const T1& default_val) const;
471 
472  /**
473  * @brief Returns the second value of a pair given its first value.
474  * @param first The first value of a pair in the gum::Bijection.
475  * @return Returns the second value of a pair given its first value.
476  * @throws NotFound Raised if the element cannot be found.
477  */
478  const T2& second(const T1& first) const;
479 
480  /**
481  * @brief Returns the second value of a pair given its first value or
482  * default_val if first is unfound.
483  * @param second The second value of a pair in the gum::Bijection.
484  * @param default_val The default value returned if first is not in the
485  * gum::Bijection.
486  * @return Returns the second value of a pair given its first value or
487  * default_val if first is not in the bjection.
488  */
489  const T2& secondWithDefault(const T1& second, const T2& default_val) const;
490 
491  /**
492  * @brief Returns true if first is the first element in a pair in the
493  * gum::Bijection.
494  * @param first The element tested for existence.
495  * @return Returns true if first is in the first element in a pair in the
496  * gum::Bijection.
497  */
498  bool existsFirst(const T1& first) const;
499 
500  /**
501  * @brief Returns true if second is the second element in a pair in the
502  * gum::Bijection.
503  * @param second The element tested for existence.
504  * @return Returns true if second is in the second element in a pair in the
505  * gum::Bijection.
506  */
507  bool existsSecond(const T2& second) const;
508 
509  /**
510  * @brief Inserts a new association in the gum::Bijection.
511  *
512  * The values are added by copy.
513  *
514  * @param first The first element of the pair to insert.
515  * @param second The second element of the pair to insert.
516  * @throws DuplicateElement Raised if the association already exists.
517  */
518  void insert(const T1& first, const T2& second);
519 
520  /**
521  * @brief Inserts a new association in the gum::Bijection.
522  *
523  * The values are moved in the gum::Bijection.
524  *
525  * @param first The first element of the pair to insert.
526  * @param second The second element of the pair to insert.
527  * @throws DuplicateElement Raised if the association already exists.
528  */
529  void insert(T1&& first, T2&& second);
530 
531  /**
532  * @brief Emplace a new element in the gum::Bijection.
533  *
534  * The emplace method allows to construct directly an element of type Key
535  * by passing to its constructor all the arguments it needs.
536  *
537  * @param args the arguments passed to the constructor
538  * @throws DuplicateElement exception is thrown if the association already
539  * exists
540  */
541  template < typename... Args >
542  void emplace(Args&&... args);
543 
544  /**
545  * @brief Removes all the associations from the gum::Bijection.
546  */
547  void clear();
548 
549  /**
550  * @brief Returns true if the gum::Bijection doesn't contain any
551  * association.
552  * @return Returns true if the gum::Bijection doesn't contain any
553  * association.
554  */
555  bool empty() const noexcept;
556 
557  /**
558  * @brief Returns the number of associations stored within the
559  * gum::Bijection.
560  * @return Returns the number of associations stored within the
561  * gum::Bijection.
562  */
563  Size size() const noexcept;
564 
565  /**
566  * @brief Erases an association containing the given first element.
567  *
568  * If the element cannot be found, nothing is done. In particular, no
569  * exception is raised.
570  *
571  * @param first The first element of a pair in the gum::Bijection.
572  */
573  void eraseFirst(const T1& first);
574 
575  /**
576  * @brief Erases an association containing the given second element.
577  *
578  * If the element cannot be found, nothing is done. In particular, no
579  * exception is raised.
580  *
581  * @param second The second element of a pair in the gum::Bijection.
582  */
583  void eraseSecond(const T2& second);
584 
585  /**
586  * @brief Returns a friendly representatin of the gum::Bijection.
587  * @return Returns a friendly representatin of the gum::Bijection.
588  */
589  std::string toString() const;
590 
591  /// @}
592  // ============================================================================
593  /// @name Fine tuning
594  // ============================================================================
595  /// @{
596 
597  /**
598  * @brief Returns the number of hashtables slots used.
599  * @return Returns the number of hashtables slots used.
600  */
601  Size capacity() const noexcept;
602 
603  /**
604  * @brief Manually resize the gum::Bijection.
605  *
606  * See gum::HashTable::resize(gum::Size)
607  *
608  * @param new_size The gum::Bijection new size.
609  */
610  void resize(Size new_size);
611 
612  /**
613  * @brief Change the gum::Bijection resizing policy.
614  *
615  * See gum::HashTable::setResizePolicy( const bool );
616  *
617  * @param new_policy If true, the gum::Bijection will resize automatically.
618  */
619  void setResizePolicy(const bool new_policy) noexcept;
620 
621  /**
622  * @brief Returns true if the resize policy is automatic.
623  *
624  * See gum::HashTable::resizePolicy().
625  *
626  * @return Returns true if the resize policy is automatic.
627  */
628  bool resizePolicy() const noexcept;
629 
630  /// @}
631 
632  private:
633  /// Alias for more readable code
634  /// @{
635  using HashTable12 = HashTable< T1, T2*, allocator12_type >;
636  using HashTable21 = HashTable< T2, T1*, allocator21_type >;
637  /// @}
638 
639  /// a friend to speed-up accesses
640  /// @{
641  friend class BijectionIteratorSafe< T1, T2 >;
642  friend class BijectionIterator< T1, T2 >;
643  friend class Bijection< T1, T2, Alloc >;
644  template < typename TT1, typename TT2, typename A, bool >
645  friend class BijectionImplementation;
646  /// @}
647 
648  // Below, we create the two gum::HashTable used by the gum::Bijection. Note
649  // that the values of these gum::HashTable are pointers. This enables to
650  // create only once objects (T1,T2). When using gum::Bijection with large
651  // size objects, this feature is of particular interest.
652 
653  /// The gum::HashTable associating T2 objects to T1 objects
654  HashTable12 _firstToSecond_;
655 
656  /// The gum::HashTable associating T1 objects to T2 objects
657  HashTable21 _secondToFirst_;
658 
659  /**
660  * @brief A function that performs a complete copy of another
661  * gum::Bijection.
662  * @warning this function assumes that "this" is an empty gum::Bijection.
663  * If it is not the case, use function clear() before calling _copy_.
664  *
665  * @param source The source from copied into this gum::Bijection.
666  * @tparam OtherAlloc The allocator used by source.
667  */
668  template < typename OtherAlloc >
669  void _copy_(const HashTable< T1, T2*, OtherAlloc >& source);
670 
671  /**
672  * @brief Inserts a new association into the gum::Bijection.
673  * @param first The first object in the association.
674  * @param second The second object in the association.
675  * @return Returns a pointer toward the inserted association.
676  */
677  typename HashTable12::value_type* _insert_(const T1& first, const T2& second);
678 
679  /**
680  * @brief Inserts a new association into the gum::Bijection.
681  * @param first The first object in the association.
682  * @param second The second object in the association.
683  * @return Returns a pointer toward the inserted association.
684  */
685  typename HashTable12::value_type* _insert_(T1&& first, T2&& second);
686  };
687 
688 #ifndef DOXYGEN_SHOULD_SKIP_THIS
689 
690  // ===========================================================================
691  // === SCALAR BIJECTION IMPLEMENTATION ===
692  // ===========================================================================
693 
694  /**
695  * @class BijectionImplementation
696  * @headerfile bijection.h <agrum/tools/core/bijection.h>
697  * @brief A non scalar implementation of a Bijection.
698  * @ingroup bijection_group
699  *
700  * This class is designed for modeling a gum::Bijection between two sets, the
701  * idea is following :
702  * - We want to create a gum::Bjection relation between type T1 and type T2,
703  * - For x in T1, there exists only one y in T2 associated to x,
704  * - For y in T2, there exists only one x in T1 associated to y,
705  * - The user inserts all the (x, y) associations and can search efficiently
706  * the values thus associated.
707  *
708  * This class differs from the previous one by being optimized for
709  * non-scalar types.
710  *
711  * @tparam T1 The first type of elements in the gum::Bjection.
712  * @tparam T2 The second type of elements in the gum::Bjection.
713  * @tparam Alloc The allocator used for allocating memory.
714  * @tparam Gen If true, this will be replaced by a implementation omptimized
715  * for non-scalar types.
716  */
717  template < typename T1, typename T2, typename Alloc >
718  class BijectionImplementation< T1, T2, Alloc, true > {
719  public:
720  /// types for STL compliance
721  /// @{
722  using type1_type = T1;
723  using type1_reference = T1&;
724  using type1_const_reference = const T1&;
725  using type1_pointer = T1*;
726  using type1_const_pointer = const T1*;
727  using type2_type = T2;
728  using type2_reference = T2&;
729  using type2_const_reference = const T2&;
730  using type2_pointer = T2*;
731  using type2_const_pointer = const T2*;
732  using size_type = std::size_t;
733  using difference_type = std::ptrdiff_t;
734  using allocator_type = Alloc;
735  using iterator = BijectionIterator< T1, T2 >;
736  using const_iterator = BijectionIterator< T1, T2 >;
737  using iterator_safe = BijectionIteratorSafe< T1, T2 >;
738  using const_iterator_safe = BijectionIteratorSafe< T1, T2 >;
739 
740  using allocator12_type = typename Alloc::template rebind< std::pair< T1, T2 > >::other;
741  using allocator21_type = typename Alloc::template rebind< std::pair< T2, T1 > >::other;
742  /// @}
743 
744  private:
745  /**
746  * @brief Default constructor: creates a gum::Bijection without any
747  * association.
748  * @param size The Bijection starting size.
749  * @param resize_policy If true, the gum::Bijection will resize itself
750  * automatically.
751  */
752  BijectionImplementation(Size size, bool resize_policy);
753 
754  /**
755  * @brief Initializer list constructor.
756  * @param list The initialize list.
757  */
758  BijectionImplementation(std::initializer_list< std::pair< T1, T2 > > list);
759 
760  /**
761  * @brief Copy constructor.
762  * @param toCopy Bijection to copy.
763  */
764  BijectionImplementation(const BijectionImplementation< T1, T2, Alloc, true >& toCopy);
765 
766  /**
767  * @brief Generalized copy constructor.
768  * @param toCopy Bijection to copy.
769  */
770  template < typename OtherAlloc >
771  BijectionImplementation(const BijectionImplementation< T1, T2, OtherAlloc, true >& toCopy);
772 
773  /**
774  * @brief Move constructor.
775  * @param from Bijection to move.
776  */
777  BijectionImplementation(BijectionImplementation< T1, T2, Alloc, true >&& from) noexcept;
778 
779  public:
780  // ============================================================================
781  /// @name Constructors/destructors
782  // ============================================================================
783  /// @{
784 
785  /**
786  * @brief Destructor.
787  */
788  ~BijectionImplementation();
789 
790  /// @}
791 
792  private:
793  /**
794  * @brief Copy operator.
795  * @param toCopy Bijection to copy.
796  * @return Returns the gum::Bijection in which the copy was made.
797  */
798  BijectionImplementation< T1, T2, Alloc, true >&
799  operator=(const BijectionImplementation< T1, T2, Alloc, true >& toCopy);
800 
801  /**
802  * @brief Generalized copy operator.
803  * @param toCopy Bijection to copy.
804  * @return Returns the gum::Bijection in which the copy was made.
805  */
806  template < typename OtherAlloc >
807  BijectionImplementation< T1, T2, Alloc, true >&
808  operator=(const BijectionImplementation< T1, T2, OtherAlloc, true >& toCopy);
809 
810  /**
811  * @brief Move operator.
812  * @param toCopy Bijection to move
813  * @return Returns the moved gum::Bijection in which the move was made.
814  */
815  BijectionImplementation< T1, T2, Alloc, true >&
816  operator=(BijectionImplementation< T1, T2, Alloc, true >&& from);
817 
818  public:
819  // ============================================================================
820  /// @name Iterators
821  // ============================================================================
822  /// @{
823 
824  /**
825  * @brief Returns the unsafe iterator at the beginning of the
826  * gum::Bijection.
827  *
828  * Unsafe iterators are a little bit faster than safe ones. But this speed
829  * is at the expense of safety: if you point to an element that is deleted,
830  * then try to access it or trying to operate a ++ will most certainly
831  * result in a segfault. So, Unsafe iterators should only be used to parse
832  * gum::Bjection where no element is ever deleted. If unsure, prefer using
833  * safe iterators.
834  *
835  * Note that the notion of a beginning/end of a gum::Bjection is rather
836  * fuzzy.
837  * What is important here is that for an instance bij of this class:
838  *
839  * @code
840  * for(iterator iter = bij.begin(); iter != bij.end(); ++iter) {
841  * // will parse all the associations.
842  * }
843  * @endcode
844  */
845  iterator begin() const;
846 
847  /**
848  * @brief Returns the constant unsafe iterator at the beginning of the
849  * gum::Bjection.
850  *
851  * Unsafe iterators are a little bit faster than safe ones. But this speed
852  * is at the expense of safety: if you point to an element that is deleted,
853  * then try to access it or trying to operate a ++ will most certainly
854  * result in a segfault. So, Unsafe iterators should only be used to parse
855  * gum::Bjection where no element is ever deleted. If unsure, prefer using
856  * safe iterators.
857  *
858  * Note that the notion of a beginning/end of a gum::Bjection is rather
859  * fuzzy. What is important here is that for an instance bij of this
860  * class:
861  *
862  * @code
863  * for (iterator iter = bij.cbegin(); iter != bij.cend(); ++iter) {
864  * // will parse all the association
865  * }
866  * @endcode
867  */
868  const_iterator cbegin() const;
869 
870  /**
871  * @brief Returns the unsafe iterator at the end of the gum::Bijection.
872  *
873  * Unsafe iterators are a little bit faster than safe ones. But this speed
874  * is at the expense of safety: if you point to an element that is deleted,
875  * then try to access it or trying to operate a ++ will most certainly
876  * result in a segfault. So, Unsafe iterators should only be used to parse
877  * gum::Bijection where no element is ever deleted. If unsure, prefer using
878  * safe iterators.
879  *
880  * Note that the notion of a beginning/end of a gum::Bijection is rather
881  * fuzzy. What is important here is that for an instance bij of this
882  * class:
883  *
884  * @code
885  * for(iterator iter = bij.begin(); iter != bij.end(); ++iter) {
886  * // loops will parse all the associations
887  * }
888  * @endcode
889  */
890  const iterator& end() const noexcept;
891 
892  /**
893  * @brief Returns the constant iterator at the end of the gum::Bijection.
894  *
895  * Unsafe iterators are a little bit faster than safe ones. But this speed
896  * is at the expense of safety: if you point to an element that is deleted,
897  * then try to access it or trying to operate a ++ will most certainly
898  * result in a segfault. So, Unsafe iterators should only be used to parse
899  * gum::Bijection where no element is ever deleted. If unsure, prefer using
900  * safe iterators.
901  *
902  * Note that the notion of a beginning/end of a gum::Bijection is rather
903  * fuzzy.
904  * What is important here is that for an instance bij of this class:
905  *
906  * @code
907  * for (iterator iter = bij.cbegin(); iter != bij.cend(); ++iter) {
908  * // loops will parse all the associations
909  * }
910  * @endcode
911  */
912  const const_iterator& cend() const noexcept;
913 
914  /**
915  * @brief Returns the safe iterator at the beginning of the gum::Bijection.
916  *
917  * Safe iterators are slightly slower than unsafe iterators. However, they
918  * guarantee that no segmentation fault can ever occur when trying to
919  * access the element they point to or when applying a ++ operator. When no
920  * element of the gum::Bijection is to be deleted during the parsing of the
921  * gum::Bijection (as for instance when you parse the gum::Bijection to
922  * display its content), prefer using the unsafe iterators, which are a
923  * little bit faster and cannot, in this case, produce segfaults.
924  *
925  * Note that the notion of a beginning/end of a gum::Bijection is rather
926  * fuzzy. What is important here is that for an instance bij of this
927  * class:
928  *
929  * @code
930  * for (iterator iter = bij.beginSafe(); iter != bij.endSafe(); ++iter) {
931  * // loops will parse all the associations
932  * }
933  * @endcode
934  */
935  iterator_safe beginSafe() const;
936 
937  /**
938  * @brief Returns the constant safe iterator at the begining of the
939  * gum::Bijection.
940  *
941  * Safe iterators are slightly slower than unsafe iterators. However, they
942  * guarantee that no segmentation fault can ever occur when trying to
943  * access the element they point to or when applying a ++ operator. When no
944  * element of the gum::Bijection is to be deleted during the parsing of the
945  * gum::Bijection (as for instance when you parse the bijection to display
946  * its content), prefer using the unsafe iterators, which are a little bit
947  * faster and cannot, in this case, produce segfaults.
948  *
949  * Note that the notion of a beginning/end of a gum::Bijection is rather
950  * fuzzy. What is important here is that for an instance bij of this
951  * class:
952  *
953  * @code
954  * for (iterator iter = bij.cbeginSafe(); iter != bij.cendSafe(); ++iter) {
955  * // loops will parse all the associations
956  * }
957  * @endcode
958  */
959  const_iterator_safe cbeginSafe() const;
960 
961  /**
962  * @brief Returns the safe iterator at the end of the gum::Bijection.
963  *
964  * Safe iterators are slightly slower than unsafe iterators. However, they
965  * guarantee that no segmentation fault can ever occur when trying to
966  * access the element they point to or when applying a ++ operator. When no
967  * element of the gum::Bijection is to be deleted during the parsing of the
968  * gum::Bijection (as for instance when you parse the gum::Bijection to
969  * display its content), prefer using the unsafe iterators, which are a
970  * little bit faster and cannot, in this case, produce segfaults.
971  *
972  * Note that the notion of a beginning/end of a gum::Bijection is rather
973  * fuzzy.
974  * What is important here is that for an instance bij of this class:
975  *
976  * @code
977  * for (iterator iter = bij.beginSafe(); iter != bij.endSafe(); ++iter) {
978  * // loops will parse all the associations
979  * }
980  * @endcode
981  */
982  const iterator_safe& endSafe() const noexcept;
983 
984  /**
985  * @brief Returns the constant safe iterator at the end of the
986  * gum::Bijection.
987  *
988  * Safe iterators are slightly slower than unsafe iterators. However, they
989  * guarantee that no segmentation fault can ever occur when trying to
990  * access the element they point to or when applying a ++ operator. When no
991  * element of the gum::Bijection is to be deleted during the parsing of the
992  * gum::Bijection (as for instance when you parse the gum::Bijection to
993  * display its content), prefer using the unsafe iterators, which are a
994  * little bit faster and cannot, in this case, produce segfaults.
995  *
996  * Note that the notion of a beginning/end of a gum::Bijection is rather
997  * fuzzy. What is important here is that for an instance bij of this
998  * class:
999  *
1000  * @code
1001  * for (iterator iter = bij.cbeginSafe(); iter != bij.cendSafe(); ++iter) {
1002  * // loops will parse all the associations
1003  * }
1004  * @endcode
1005  */
1006  const const_iterator_safe& cendSafe() const noexcept;
1007 
1008  /**
1009  * @brief Returns the safe end iterator for other classes' statics.
1010  *
1011  * To reduce the gum::Bijection memory consumption (which are heavily used
1012  * in aGrUM) while allowing fast for loops, end iterators are created just
1013  * once as a static member of a non-template gum::Bijection. While this
1014  * scheme is efficient and it works quite effectively, it has a drawback:
1015  * other classes with static members using the
1016  * BijectionImplementation::end() iterator may fail to work due to the well
1017  * known "static initialization order fiasco" (see Marshall Cline's C++ FAQ
1018  * for more details about this C++ feature).
1019  *
1020  * So what is the problem? Consider a class, say X, containing a
1021  * gum::Bijection that stores all its elements in a convenient way. To
1022  * reduce memory consumption, X::end iterator is a static member that is
1023  * initialized with a gum::Bijection::end iterator. If the compiler decides
1024  * to initialize X::end before initializing gum::Bijection::end, then
1025  * X::end will be in an incoherent state.
1026  *
1027  * Unfortunately, we cannot know for sure in which order static members
1028  * will be initialized (the order is a compiler's decision). Hence, we
1029  * shall enfore the fact that gum::Bijection::end is initialized before
1030  * X::end. Using method gum::Bijection::end4Statics will ensure this fact:
1031  * it uses the C++ "construct on first use" idiom (see the C++ FAQ) that
1032  * ensures that the order fiasco is avoided. More precisely, end4Statics
1033  * uses a global variable that is the very end iterator used by all
1034  * gum::Bijection. Now, this induces a small overhead. So, we also provide
1035  * a gum::Bijection::end() method that returns the gum::Bijection::end
1036  * iterator without this small overhead, but assuming that function
1037  * end4Statics has already been called once (which is always the case) when
1038  * a gum::Bijection has been created.
1039  *
1040  * So, to summarize: when initializing static members use endSafe4Statics()
1041  * and in all the other cases, use endSafe().
1042  */
1043  static const iterator_safe& endSafe4Statics();
1044 
1045  /**
1046  * @brief Returns the unsafe end iterator for other classes' statics.
1047  *
1048  * To reduce the gum::Bijection memory consumption (which are heavily used
1049  * in aGrUM) while allowing fast for loops, end iterators are created just
1050  * once as a static member of a non-template gum::Bijection. While this
1051  * scheme is efficient and it works quite effectively, it has a drawback:
1052  * other classes with static members using the
1053  * BijectionImplementation::end() iterator may fail to work due to the well
1054  * known "static initialization order fiasco" (see Marshall Cline's C++ FAQ
1055  * for more details about this C++ feature).
1056  *
1057  * So what is the problem? Consider a class, say X, containing a
1058  * gum::Bijection that stores all its elements in a convenient way. To
1059  * reduce memory consumption, X::end iterator is a static member that is
1060  * initialized with a gum::Bijection::end iterator. If the compiler decides
1061  * to initialize X::end before initializing gum::Bijection::end, then
1062  * X::end will be in an incoherent state.
1063  *
1064  * Unfortunately, we cannot know for sure in which order static members
1065  * will be initialized (the order is a compiler's decision). Hence, we
1066  * shall enfore the fact that gum::Bijection::end is initialized before
1067  * X::end. Using method gum::Bijection::end4Statics will ensure this fact:
1068  * it uses the C++ "construct on first use" idiom (see the C++ FAQ) that
1069  * ensures that the order fiasco is avoided. More precisely, end4Statics
1070  * uses a global variable that is the very end iterator used by all
1071  * gum::Bijection. Now, this induces a small overhead. So, we also provide
1072  * a gum::Bijection::end() method that returns the gum::Bijection::end
1073  * iterator without this small overhead, but assuming that function
1074  * end4Statics has already been called once (which is always the case) when
1075  * a gum::Bijection has been created.
1076  *
1077  * So, to summarize: when initializing static members use end4Statics()
1078  * and in all the other cases, use end().
1079  */
1080  static const iterator& end4Statics();
1081 
1082  /// @}
1083  // ============================================================================
1084  /// @name Accessors / Modifiers
1085  // ============================================================================
1086  /// @{
1087 
1088  /**
1089  * @brief Returns the first value of a pair given its second value.
1090  * @param second The second value of a pair in the gum::Bijection.
1091  * @return Returns the first value of a pair given its second value.
1092  * @throws NotFound Raised if the element cannot be found.
1093  */
1094  const T1& first(T2 second) const;
1095 
1096  /**
1097  * @brief Returns the first value of a pair given its second value or
1098  * default_val if second is unfound.
1099  * @param second The second value of a pair in the gum::Bijection.
1100  * @param default_val The default value returned if second is not in the
1101  * gum::Bijection.
1102  * @return Returns the first value of a pair given its second value or
1103  * default_val if second is not in the bjection.
1104  */
1105  const T1& firstWithDefault(T2 second, T1 default_val) const;
1106 
1107  /**
1108  * @brief Returns the second value of a pair given its first value.
1109  * @param first The first value of a pair in the gum::Bijection.
1110  * @return Returns the second value of a pair given its first value.
1111  * @throws NotFound Raised if the element cannot be found.
1112  */
1113  const T2& second(T1 first) const;
1114 
1115  /**
1116  * @brief Returns the second value of a pair given its first value or
1117  * default_val if first is unfound.
1118  * @param second The second value of a pair in the gum::Bijection.
1119  * @param default_val The default value returned if first is not in the
1120  * gum::Bijection.
1121  * @return Returns the second value of a pair given its first value or
1122  * default_val if first is not in the bjection.
1123  */
1124  const T2& secondWithDefault(T1 first, T2 default_val) const;
1125 
1126  /**
1127  * @brief Returns true if first is in the first element in a pair in the
1128  * gum::Bijection.
1129  * @param first The element tested for existence.
1130  * @return Returns true if first is in the first element in a pair in the
1131  * gum::Bijection.
1132  */
1133  bool existsFirst(T1 first) const;
1134 
1135  /**
1136  * @brief Returns true if second is in the second element in a pair in the
1137  * gum::Bijection.
1138  * @param first The element tested for existence.
1139  * @return Returns true if second is in the second element in a pair in the
1140  * gum::Bijection.
1141  */
1142  bool existsSecond(T2 second) const;
1143 
1144  /**
1145  * @brief Inserts a new association in the gum::Bijection.
1146  *
1147  * The values are added by copy.
1148  *
1149  * @param first The first element of the pair to insert.
1150  * @param second The second element of the pair to insert.
1151  * @throws DuplicateElement Raised if the association already exists.
1152  */
1153  void insert(T1 first, T2 second);
1154 
1155  /**
1156  * @brief Emplace a new element in the gum::Bijection.
1157  *
1158  * The emplace method allows to construct directly an element of type Key
1159  * by passing to its constructor all the arguments it needs.
1160  *
1161  * @param args the arguments passed to the constructor
1162  * @throws DuplicateElement exception is thrown if the association already
1163  * exists
1164  */
1165  template < typename... Args >
1166  void emplace(Args&&... args);
1167 
1168  /**
1169  * @brief Removes all the associations from the gum::Bijection.
1170  */
1171  void clear();
1172 
1173  /**
1174  * @brief Returns true if the gum::Bijection doesn't contain any
1175  * association.
1176  * @return Returns true if the gum::Bijection doesn't contain any
1177  * association.
1178  */
1179  bool empty() const noexcept;
1180 
1181  /**
1182  * @brief Returns the number of associations stored within the
1183  * gum::Bijection.
1184  * @return Returns the number of associations stored within the
1185  * gum::Bijection.
1186  */
1187  Size size() const noexcept;
1188 
1189  /**
1190  * @brief Erases an association containing the given first element.
1191  *
1192  * If the element cannot be found, nothing is done. In particular, no
1193  * exception is raised.
1194  *
1195  * @param first The first element of a pair in the gum::Bijection.
1196  */
1197  void eraseFirst(T1 first);
1198 
1199  /**
1200  * @brief Erases an association containing the given second element.
1201  *
1202  * If the element cannot be found, nothing is done. In particular, no
1203  * exception is raised.
1204  *
1205  * @param first The second element of a pair in the gum::Bijection.
1206  */
1207  void eraseSecond(T2 second);
1208 
1209  /**
1210  * @brief Returns a friendly representatin of the gum::Bijection.
1211  * @return Returns a friendly representatin of the gum::Bijection.
1212  */
1213  std::string toString() const;
1214 
1215  /// @}
1216  // ============================================================================
1217  /// @name Fine tuning
1218  // ============================================================================
1219  /// @{
1220 
1221  /**
1222  * @brief Returns the number of hashtables slots used.
1223  * @return Returns the number of hashtables slots used.
1224  */
1225  Size capacity() const noexcept;
1226 
1227  /**
1228  * @brief Manually resize the gum::Bijection.
1229  *
1230  * See gum::HashTable::resize(gum::Size)
1231  *
1232  * @param new_size The gum::Bijection new size.
1233  */
1234  void resize(Size new_size);
1235 
1236  /**
1237  * @brief Change the gum::Bijection resizing policy.
1238  *
1239  * See gum::HashTable::setResizePolicy( const bool );
1240  *
1241  * @param If true, the gum::Bijection will resize automatically.
1242  */
1243  void setResizePolicy(const bool new_policy) noexcept;
1244 
1245  /**
1246  * @brief Returns true if the resize policy is automatic.
1247  *
1248  * See gum::HashTable::resizePolicy().
1249  *
1250  * @return Returns true if the resize policy is automatic.
1251  */
1252  bool resizePolicy() const noexcept;
1253 
1254  /// @}
1255 
1256  private:
1257  /// Alias for more readable code
1258  /// @{
1259  using HashTable12 = HashTable< T1, T2, allocator12_type >;
1260  using HashTable21 = HashTable< T2, T1, allocator21_type >;
1261  /// @}
1262 
1263  /// a friend to speed-up accesses
1264  /// @{
1265  friend class BijectionIteratorSafe< T1, T2 >;
1266  friend class BijectionIterator< T1, T2 >;
1267  friend class Bijection< T1, T2, Alloc >;
1268  template < typename TT1, typename TT2, typename A, bool >
1269  friend class BijectionImplementation;
1270  /// @}
1271 
1272  // Below, we create the two gum::HashTable used by the gum::Bijection. Note
1273  // that the values of these gum::HashTable are pointers. This enables to
1274  // create only once objects (T1,T2). When using gum::Bijection with large
1275  // size objects, this feature is of particular interest.
1276 
1277  /// hashtable associating T2 scalars to T1 scalars
1278  HashTable12 _firstToSecond_;
1279 
1280  /// hashtable associating T1 scalars to T2 scalars
1281  HashTable21 _secondToFirst_;
1282 
1283  /**
1284  * @brief A function that performs a complete copy of another
1285  * gum::Bijection.
1286  * @warning this function assumes that "this" is an empty gum::Bijection.
1287  * If it is not the case, use function clear() before calling _copy_.
1288  *
1289  * @param source The source from copied into this gum::Bijection.
1290  * @tparam OtherAlloc The allocator used by source.
1291  */
1292  template < typename OtherAlloc >
1293  void _copy_(const HashTable< T1, T2, OtherAlloc >& f2s);
1294 
1295  /**
1296  * @brief Inserts a new association into the gum::Bijection.
1297  * @param first The first object in the association.
1298  * @param second The second object in the association.
1299  * @return Returns a pointer toward the inserted association.
1300  */
1301  void _insert_(const T1 first, const T2 second);
1302  };
1303 
1304 #endif /* DOXYGEN_SHOULD_SKIP_THIS */
1305 
1306  /**
1307  * @class BijectionIteratorStaticEnd
1308  * @headerfile bijection.h <agrum/tools/core/bijection.h>
1309  * @brief A class which creates the static iterator used by gim::Bijections.
1310  * @ingroup bijection_group
1311  *
1312  * The aim of using this class rather than just creating _BijectionIterEnd_
1313  * as a global variable is to prevent other classes to access and modify
1314  * _BijectionIterEnd_.
1315  */
1316  class BijectionIteratorStaticEnd {
1317  /// Friends that have access to the iterator
1318  template < typename T1, typename T2, typename Alloc, bool >
1319  friend class BijectionImplementation;
1320 
1321  private:
1322  /// The safe iterator used by everyone
1323  static const BijectionIteratorSafe< int, int >* _BijectionIterEndSafe_;
1324 
1325  /// The unsafe iterator used by everyone.
1326  static const BijectionIterator< int, int >* _BijectionIterEnd_;
1327 
1328  /**
1329  * @brief Creates (if needed) and returns the iterator
1330  * _BijectionIterEndSafe_
1331  * @return Returns _BijectionIterEndSafe_.
1332  */
1333  static const BijectionIteratorSafe< int, int >* endSafe4Statics();
1334 
1335  /**
1336  * @brief Creates (if needed) and returns the iterator _BijectionIterEnd_.
1337  * @return Returns _BijectionIterEnd_;
1338  */
1339  static const BijectionIterator< int, int >* end4Statics();
1340  };
1341 
1342  /**
1343  * @class BijectionIteratorGet
1344  * @headerfile bijection.h <agrum/tools/core/bijection.h>
1345  * @brief Dummy classes for discriminating scalars and non-scalars operators
1346  * and -> wihtout any overhead.
1347  * @ingroup bijection_group
1348  *
1349  * This will be used for scalar types.
1350  */
1351  template < bool gen >
1352  struct BijectionIteratorGet {
1353  /**
1354  * @brief Returns a refeence over a pointer.
1355  * @param x The pointer for which a reference is returned.
1356  * @return Returns a reference over x.
1357  */
1358  template < typename T >
1359  INLINE static const T& op_second(const T* x) {
1360  return *x;
1361  }
1362  };
1363 
1364  /**
1365  * @class BijectionIteratorGet
1366  * @headerfile bijection.h <agrum/tools/core/bijection.h>
1367  * @brief Dummy classes for discriminating scalars and non-scalars operators
1368  * and -> wihtout any overhead.
1369  * @ingroup bijection_group
1370  *
1371  * This will be used for non-scala types.
1372  */
1373  template <>
1374  struct BijectionIteratorGet< true > {
1375  /**
1376  * @brief Returns a reference.
1377  * @param x A reference.
1378  * @return Returns the reference x.
1379  */
1380  template < typename T >
1381  INLINE static const T& op_second(const T& x) {
1382  return x;
1383  }
1384  };
1385 
1386  // ===========================================================================
1387  // === BIJECTION SAFE ITERATORS ===
1388  // ===========================================================================
1389 
1390  /**
1391  * @class BijectionIteratorSafe
1392  * @headerfile bijection.h <agrum/tools/core/bijection.h>
1393  * @brief Safe iterators for bijectionIterator.
1394  * @ingroup bijection_group
1395  *
1396  * @tparam T1 The first type of elements in the gum::Bjection.
1397  * @tparam T2 The second type of elements in the gum::Bjection.
1398  */
1399  template < typename T1, typename T2 >
1400  class BijectionIteratorSafe {
1401  template < typename TT1, typename TT2, typename Alloc, bool >
1402  friend class BijectionImplementation;
1403 
1404  public:
1405  /// types for STL compliance
1406  /// @{
1407  using iterator_category = std::forward_iterator_tag;
1408  using type1_type = T1;
1409  using type1_reference = T1&;
1410  using type1_const_reference = const T1&;
1411  using type1_pointer = T1*;
1412  using type1_const_pointer = const T1*;
1413  using type2_type = T2;
1414  using type2_reference = T2&;
1415  using type2_const_reference = const T2&;
1416  using type2_pointer = T2*;
1417  using type2_const_pointer = const T2*;
1418  using difference_type = std::ptrdiff_t;
1419  /// @}
1420 
1421  private:
1422  /**
1423  * Dummy classes that will enable discriminate without overhead between
1424  * scalars and non-scalars functions second in iterators
1425  */
1426  using Getter
1427  = BijectionIteratorGet< std::is_scalar< T1 >::value && std::is_scalar< T2 >::value >;
1428 
1429  /**
1430  * @brief Begin constructor.
1431  * By default, the iterator points to the starting point of the
1432  * gum::Bijection.
1433  * @param bijection The gum::Bijection to iterate onto.
1434  */
1435  template < typename Alloc, bool Gen >
1436  BijectionIteratorSafe(const BijectionImplementation< T1, T2, Alloc, Gen >& bijection);
1437 
1438  public:
1439  // ============================================================================
1440  /// @name Constructors and destructors
1441  // ============================================================================
1442  /// @{
1443 
1444  /**
1445  * @brief Default constructor.
1446  */
1447  BijectionIteratorSafe() noexcept;
1448 
1449  /**
1450  * @brief Genereliazed default constructor.
1451  * @tparam Alloc The gum::Bijection allocator's type.
1452  */
1453  template < typename Alloc >
1454  BijectionIteratorSafe(const Bijection< T1, T2, Alloc >& bijection);
1455 
1456  /**
1457  * @brief Copy constructor.
1458  * @param from The gum::BijectionIteratorSafe to copy.
1459  */
1460  BijectionIteratorSafe(const BijectionIteratorSafe< T1, T2 >& from);
1461 
1462  /**
1463  * @brief Move constructor.
1464  * @param from The gum::BijectionIteratorSafe to move.
1465  */
1466  BijectionIteratorSafe(BijectionIteratorSafe< T1, T2 >&& from) noexcept;
1467 
1468  /**
1469  * @brief Class destructor.
1470  */
1471  ~BijectionIteratorSafe() noexcept;
1472 
1473  /// @}
1474  // ============================================================================
1475  /// @name Operators
1476  // ============================================================================
1477  /// @{
1478 
1479  /**
1480  * @brief Copy operator.
1481  * @param toCopy The gum::BijectionIteratorSafe to copy.
1482  * @return Returns this gum::BijectionIteratorSafe.
1483  */
1484  BijectionIteratorSafe< T1, T2 >& operator=(const BijectionIteratorSafe< T1, T2 >& toCopy);
1485 
1486  /**
1487  * @brief Move operator.
1488  * @param toMove The gum::BijectionIteratorSafe to move.
1489  * @return Returns this gum::BijectionIteratorSafe.
1490  */
1491  BijectionIteratorSafe< T1, T2 >& operator=(BijectionIteratorSafe< T1, T2 >&& toMove) noexcept;
1492 
1493  /**
1494  * @brief Go to the next association, if it exists.
1495  *
1496  * If the iterator points to end(), nothing happens.
1497  * @return Returns this gum::BijectionIteratorSafe.
1498  */
1499  BijectionIteratorSafe< T1, T2 >& operator++() noexcept;
1500 
1501  /**
1502  * @brief Moves the iterator by nb elements.
1503  *
1504  * If the iterator points to end(), nothing is done. If there are
1505  * nb or fewer elements to parse to reach the end of the bijection, then
1506  * this method makes the iterator point to
1507  * gum::BijectionIteratorSafe::end().
1508  *
1509  * @param nb The number of steps by wich the iterator moves.
1510  * @return Returns this gum::BijectionIteratorSafe.
1511  */
1512  BijectionIteratorSafe< T1, T2 >& operator+=(Size nb) noexcept;
1513 
1514  /**
1515  * @brief Returns a new iterator.
1516  *
1517  * If the iterator points to end(), the resulting iterator also points to
1518  * end (). If there are nb or fewer elements to parse to reach the end of
1519  * the bijection, then the resulting iterator points to
1520  * gum::BijectionIteratorSafe::end().
1521  *
1522  * @param nb The number of steps by wich the iterator moves.
1523  * @return Returns this gum::BijectionIteratorSafe.
1524  */
1525  BijectionIteratorSafe< T1, T2 > operator+(Size nb) noexcept;
1526 
1527  /**
1528  * @brief Inequality operator.
1529  * @param toCompare The gum::BijectionIteratorSafe to compare.
1530  * @return Returns true if they differ.
1531  */
1532  bool operator!=(const BijectionIteratorSafe< T1, T2 >& toCompare) const noexcept;
1533 
1534  /**
1535  * @brief Equality operator.
1536  * @param toCompare The gum::BijectionIteratorSafe to compare.
1537  * @return Returns true if they are equal.
1538  */
1539  bool operator==(const BijectionIteratorSafe< T1, T2 >& toCompare) const noexcept;
1540 
1541  /// @}
1542  // ============================================================================
1543  /// @name Accessors/Modifiers
1544  // ============================================================================
1545  /// @{
1546 
1547  /**
1548  * @brief Returns the first element of the current association.
1549  * @return Returns the first element of the current association.
1550  * @throws UndefinedIteratorValue Raised when the iterator does not point
1551  * to a valid element of the bijection.
1552  */
1553  const T1& first() const;
1554 
1555  /**
1556  * @brief Returns the second element of the current association.
1557  * @return Returns the second element of the current association.
1558  * @throws UndefinedIteratorValue Raised when the iterator does not point
1559  * to a valid element of the bijection.
1560  */
1561  const T2& second() const;
1562 
1563  /// @}
1564 
1565  private:
1566  /// Alias for one of the internal gum::HashTable of the gum::Bijection.
1567  using HashTable12 = typename std::conditional<
1568  std::is_scalar< T1 >::value && std::is_scalar< T2 >::value,
1569  HashTable< T1, T2, std::allocator< std::pair< T1, T2 > > >,
1570  HashTable< T1, T2*, std::allocator< std::pair< T1, T2* > > > >::type;
1571 
1572  /// Alias for one of the internal gum::HastTableIterator of the
1573  /// gum::Bijection.
1574  using HashIter = typename HashTable12::const_iterator_safe;
1575 
1576  /// The hashTable iterator that actually does all the job.
1577  HashIter _iter_;
1578  };
1579 
1580  // ===========================================================================
1581  // === BIJECTION UNSAFE ITERATORS ===
1582  // ===========================================================================
1583  /**
1584  * @class BijectionIterator
1585  * @headerfile bijection.h <agrum/tools/core/bijection.h>
1586  * @brief Unsafe iterators for bijection.
1587  * @ingroup bijection_group
1588  *
1589  * @tparam T1 The first type of elements in the gum::Bjection.
1590  * @tparam T2 The second type of elements in the gum::Bjection.
1591  */
1592  template < typename T1, typename T2 >
1593  class BijectionIterator {
1594  template < typename TT1, typename TT2, typename Alloc, bool >
1595  friend class BijectionImplementation;
1596 
1597  public:
1598  /// types for STL compliance
1599  /// @{
1600  using iterator_category = std::forward_iterator_tag;
1601  using type1_type = T1;
1602  using type1_reference = T1&;
1603  using type1_const_reference = const T1&;
1604  using type1_pointer = T1*;
1605  using type1_const_pointer = const T1*;
1606  using type2_type = T2;
1607  using type2_reference = T2&;
1608  using type2_const_reference = const T2&;
1609  using type2_pointer = T2*;
1610  using type2_const_pointer = const T2*;
1611  using difference_type = std::ptrdiff_t;
1612  /// @}
1613 
1614  private:
1615  /**
1616  * Dummy classes that will enable discriminate without overhead between
1617  * scalars and non-scalars functions second in iterators
1618  */
1619  using Getter
1620  = BijectionIteratorGet< std::is_scalar< T1 >::value && std::is_scalar< T2 >::value >;
1621 
1622  /**
1623  * @brief Begin constructor.
1624  * By default, the iterator points to the starting point of the bijection.
1625  */
1626  template < typename Alloc, bool Gen >
1627  BijectionIterator(const BijectionImplementation< T1, T2, Alloc, Gen >& bijection);
1628 
1629  public:
1630  // ============================================================================
1631  /// @name Constructors/destructors
1632  // ============================================================================
1633  /// @{
1634 
1635  /**
1636  * @brief Default constructor.
1637  */
1638  BijectionIterator() noexcept;
1639 
1640  /**
1641  * @brief Default constructor.
1642  * @param bijection The gum::Bijection to iterate onto.
1643  */
1644  template < typename Alloc >
1645  BijectionIterator(const Bijection< T1, T2, Alloc >& bijection);
1646 
1647  /**
1648  * @brief Copy constructor.
1649  * @param from The gum::BijectionIterator to copy.
1650  */
1651  BijectionIterator(const BijectionIterator< T1, T2 >& from);
1652 
1653  /**
1654  * @brief Move constructor.
1655  * @param from The gum::BijectionIterator to move.
1656  */
1657  BijectionIterator(BijectionIterator< T1, T2 >&& from) noexcept;
1658 
1659  /**
1660  * Class destructor.
1661  */
1662  ~BijectionIterator() noexcept;
1663 
1664  /// @}
1665  // ============================================================================
1666  /// @name Operators
1667  // ============================================================================
1668  /// @{
1669 
1670  /**
1671  * @brief Copy operator.
1672  * @param toCopy The gum::BijectionIterator to copy.
1673  * @return Returns this gum::BijectionIterator.
1674  */
1675  BijectionIterator< T1, T2 >& operator=(const BijectionIterator< T1, T2 >& toCopy);
1676 
1677  /**
1678  * @brief Move operator.
1679  * @param toMove The gum::BijectionIterator to move.
1680  * @return Returns this gum::BijectionIterator.
1681  */
1682  BijectionIterator< T1, T2 >& operator=(BijectionIterator< T1, T2 >&& toMove) noexcept;
1683 
1684  /**
1685  * @brief Go to the next association, if it exists.
1686  *
1687  * If the iterator points to gum::Bijection::end(), nothing is done.
1688  *
1689  * @return Return sthis gum::BijectionIterator.
1690  */
1691  BijectionIterator< T1, T2 >& operator++() noexcept;
1692 
1693  /**
1694  * @brief Moves the iterator by nb elements.
1695  *
1696  * If the iterator points to gum::Bijection::end(), nothing is done. If
1697  * there are nb or
1698  * fewer elements to parse to reach the end of the bijection, then this
1699  * method makes the iterator point to gum::Bijection::end().
1700  *
1701  * @param nb The number of steps by wich the iterator moves.
1702  * @return Returns this gum::BijectionIterator.
1703  */
1704  BijectionIterator< T1, T2 >& operator+=(Size nb) noexcept;
1705 
1706  /**
1707  * @brief Return a new iterator.
1708  *
1709  * If the iterator points to gum::Bijection::end(), the resulting iterator
1710  * also points to gum::Bijection::end(). If there are nb or fewer elements
1711  * to parse to reach the end of the gum::Bijection, then the resulting
1712  * iterator points to gum::Bijection::end().
1713  */
1714  BijectionIterator< T1, T2 > operator+(Size nb) noexcept;
1715 
1716  /**
1717  * @brief Inequality operator.
1718  * @param toCompare The gum::BijectionIteratorSafe to compare.
1719  * @return Returns true if they differ.
1720  */
1721  bool operator!=(const BijectionIterator< T1, T2 >& toCompare) const noexcept;
1722 
1723  /**
1724  * @brief Equality operator.
1725  * @param toCompare The gum::BijectionIteratorSafe to compare.
1726  * @return Returns true if they are equal.
1727  */
1728  bool operator==(const BijectionIterator< T1, T2 >& toCompare) const noexcept;
1729 
1730  /// @}
1731  // ============================================================================
1732  /// @name Accessors/Modifiers
1733  // ============================================================================
1734  /// @{
1735 
1736  /**
1737  * @brief Returns the first element of the current association.
1738  * @return Returns the first element of the current association.
1739  * @throws UndefinedIteratorValue Raised when the iterator does not point
1740  * to a valid element of the bijection.
1741  */
1742  const T1& first() const;
1743 
1744  /**
1745  * @brief Returns the second element of the current association.
1746  * @return Returns the second element of the current association.
1747  * @throws UndefinedIteratorValue Raised when the iterator does not point
1748  * to a valid element of the bijection.
1749  */
1750  const T2& second() const;
1751 
1752  /// @}
1753 
1754  private:
1755  /// Alias for one of the internal gum::HashTable of the gum::Bijection.
1756  using HashTable12 = typename std::conditional<
1757  std::is_scalar< T1 >::value && std::is_scalar< T2 >::value,
1758  HashTable< T1, T2, std::allocator< std::pair< T1, T2 > > >,
1759  HashTable< T1, T2*, std::allocator< std::pair< T1, T2* > > > >::type;
1760  using HashIter = typename HashTable12::const_iterator;
1761 
1762  /// The hashTable iterator that actually does all the job.
1763  HashIter _iter_;
1764  };
1765 
1766  /**
1767  * @class Bijection
1768  * @headerfile bijection.h <agrum/tools/core/bijection.h>
1769  * @brief Set of pairs of elements with fast search for both elements.
1770  * @ingroup basicstruct_group
1771  * @ingroup bijection_group
1772  *
1773  * This class is designed for modeling a gum::Bijection between two sets, the
1774  * idea is following :
1775  * - We want to create a gum::Bjection relation between type T1 and type T2,
1776  * - For x in T1, there exists only one y in T2 associated to x,
1777  * - For y in T2, there exists only one x in T1 associated to y,
1778  * - The user inserts all the (x, y) associations and can search efficiently
1779  * the values thus associated.
1780  *
1781  * @tparam T1 The first type of elements in the gum::Bjection.
1782  * @tparam T2 The second type of elements in the gum::Bjection.
1783  * @tparam Alloc The allocator used for allocating memory.
1784  */
1785  template < typename T1, typename T2, typename Alloc = std::allocator< T2 > >
1786  class Bijection:
1787  public BijectionImplementation< T1,
1788  T2,
1789  Alloc,
1790  std::is_scalar< T1 >::value && std::is_scalar< T2 >::value > {
1791  public:
1792  /// types for STL compliance
1793  /// @{
1794  using type1_type = T1;
1795  using type1_reference = T1&;
1796  using type1_const_reference = const T1&;
1797  using type1_pointer = T1*;
1798  using type1_const_pointer = const T1*;
1799  using type2_type = T2;
1800  using type2_reference = T2&;
1801  using type2_const_reference = const T2&;
1802  using type2_pointer = T2*;
1803  using type2_const_pointer = const T2*;
1804  using size_type = std::size_t;
1805  using difference_type = std::ptrdiff_t;
1806  using allocator_type = Alloc;
1807  using iterator = BijectionIterator< T1, T2 >;
1808  using const_iterator = BijectionIterator< T1, T2 >;
1809  using iterator_safe = BijectionIteratorSafe< T1, T2 >;
1810  using const_iterator_safe = BijectionIteratorSafe< T1, T2 >;
1811 
1812  using allocator1_type = typename Alloc::template rebind< T1* >::other;
1813  using allocator2_type = typename Alloc::template rebind< T2* >::other;
1814  /// @}
1815 
1816  /// The Implementation of this gum::Bijection.
1817  using Implementation
1818  = BijectionImplementation< T1,
1819  T2,
1820  Alloc,
1821  std::is_scalar< T1 >::value && std::is_scalar< T2 >::value >;
1822 
1823  // ============================================================================
1824  /// @name Constructors/destructors
1825  // ============================================================================
1826  /// @{
1827 
1828  /**
1829  * @brief Default constructor: creates a gum::Bijection without any
1830  * association.
1831  * @param size The gum::Bijection starting size.
1832  * @param resize_policy If tru, the gum::Bijection will be automatically
1833  * resized.
1834  */
1835  Bijection(Size size = HashTableConst::default_size,
1836  bool resize_policy = HashTableConst::default_resize_policy);
1837 
1838  /**
1839  * @brief Initializer list constructor.
1840  * @param list The initialisation list.
1841  */
1842  Bijection(std::initializer_list< std::pair< T1, T2 > > list);
1843 
1844  /**
1845  * @brief Copy constructor.
1846  * @param toCopy The gum::Bijection to copy.
1847  */
1848  Bijection(const Bijection< T1, T2, Alloc >& toCopy);
1849 
1850  /**
1851  * @brief Generalized copy constructor.
1852  * @param toCopy The gum::Bijection to copy.
1853  * @tparam The gum::Bijection to copy allocator's type.
1854  */
1855  template < typename OtherAlloc >
1856  Bijection(const Bijection< T1, T2, OtherAlloc >& toCopy);
1857 
1858  /**
1859  * @brief Move constructor.
1860  * @param from The gum::Bijection to move from.
1861  */
1862  Bijection(Bijection< T1, T2, Alloc >&& from) noexcept;
1863 
1864  /**
1865  * @brief Class destructor.
1866  */
1867  ~Bijection();
1868 
1869  /// @}
1870  // ============================================================================
1871  /// @name Operators
1872  // ============================================================================
1873  /// @{
1874 
1875  /**
1876  * @brief Copy operator.
1877  * @param toCopy The gum::Bijection to copy.
1878  * @return Returns this gum::Bijection.
1879  */
1880  Bijection< T1, T2, Alloc >& operator=(const Bijection< T1, T2, Alloc >& toCopy);
1881 
1882  /**
1883  * @brief Generalized copy operator.
1884  * @param toCopy The gum::Bijection to copy.
1885  * @tparam OtherAlloc The gum::Bijection to copy allocator's type.
1886  */
1887  template < typename OtherAlloc >
1888  Bijection< T1, T2, Alloc >& operator=(const Bijection< T1, T2, OtherAlloc >& toCopy);
1889 
1890  /**
1891  * @brief Move operator.
1892  * @param bij The gum::Bijection to move from.
1893  */
1894  Bijection< T1, T2, Alloc >& operator=(Bijection< T1, T2, Alloc >&& bij);
1895 
1896  /// @}
1897  };
1898 
1899  /**
1900  * @brief For friendly display of the content of the gum::Bijection.
1901  *
1902  * @param bijection The gum::Bijection to display.
1903  * @tparam T1 The first type of elements in the gum::Bjection.
1904  * @tparam T2 The second type of elements in the gum::Bjection.
1905  * @tparam Alloc The allocator used for allocating memory.
1906  * @return The stream in which the gum::Bijection is displayed.
1907  */
1908  template < typename T1, typename T2, typename Alloc >
1909  std::ostream& operator<<(std::ostream&, const Bijection< T1, T2, Alloc >& bijection);
1910 
1911 } /* namespace gum */
1912 
1913 
1914 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1915 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1916 extern template class gum::Bijection< int, int >;
1917 # endif
1918 #endif
1919 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1920 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1921 extern template class gum::Bijection< std::string, std::string >;
1922 # endif
1923 #endif
1924 
1925 
1926 // always include the template implementations
1927 #include <agrum/tools/core/bijection_tpl.h>
1928 
1929 #endif /* GUM_BIJECTION_H */
aGrUM 0.21.0
Sat Jul 24 2021 11:12:04
© PHW&CG&others - 2021
DoXyGeN 1.8.13