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