bijection.h

Go to the documentation of this file.

/****************************************************************************
 *   This file is part of the aGrUM/pyAgrum library.                        *
 *                                                                          *
 *   Copyright (c) 2005-2025 by                                             *
 *       - Pierre-Henri WUILLEMIN(_at_LIP6)                                 *
 *       - Christophe GONZALES(_at_AMU)                                     *
 *                                                                          *
 *   The aGrUM/pyAgrum library is free software; you can redistribute it    *
 *   and/or modify it under the terms of either :                           *
 *                                                                          *
 *    - the GNU Lesser General Public License as published by               *
 *      the Free Software Foundation, either version 3 of the License,      *
 *      or (at your option) any later version,                              *
 *    - the MIT license (MIT),                                              *
 *    - or both in dual license, as here.                                   *
 *                                                                          *
 *   (see https://agrum.gitlab.io/articles/dual-licenses-lgplv3mit.html)    *
 *                                                                          *
 *   This aGrUM/pyAgrum library is distributed in the hope that it will be  *
 *   useful, but WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,          *
 *   INCLUDING BUT NOT LIMITED TO THE WARRANTIES MERCHANTABILITY or FITNESS *
 *   FOR A PARTICULAR PURPOSE  AND NONINFRINGEMENT. IN NO EVENT SHALL THE   *
 *   AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER *
 *   LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,        *
 *   ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR  *
 *   OTHER DEALINGS IN THE SOFTWARE.                                        *
 *                                                                          *
 *   See LICENCES for more details.                                         *
 *                                                                          *
 *   SPDX-FileCopyrightText: Copyright 2005-2025                            *
 *       - Pierre-Henri WUILLEMIN(_at_LIP6)                                 *
 *       - Christophe GONZALES(_at_AMU)                                     *
 *   SPDX-License-Identifier: LGPL-3.0-or-later OR MIT                      *
 *                                                                          *
 *   Contact  : info_at_agrum_dot_org                                       *
 *   homepage : http://agrum.gitlab.io                                      *
 *   gitlab   : https://gitlab.com/agrumery/agrum                           *
 *                                                                          *
 ****************************************************************************/
 

#ifndef GUM_BIJECTION_H
#define GUM_BIJECTION_H
 
#include <iostream>
#include <sstream>
#include <string>
 
#include <agrum/base/core/hashTable.h>
 
#include <initializer_list>
#include <type_traits>
 
namespace gum {
 
#ifndef DOXYGEN_SHOULD_SKIP_THIS
 
  template < typename T1, typename T2 >
  class BijectionIteratorSafe;
  template < typename T1, typename T2 >
  class BijectionIterator;
  template < typename T1, typename T2, bool >
  class BijectionImplementation;
  template < typename T1, typename T2 >
  class Bijection;
 
#endif /* DOXYGEN_SHOULD_SKIP_THIS */
 
 
  // ===========================================================================
  // ===                NON SCALAR BIJECTION IMPLEMENTATION                  ===
  // ===========================================================================

  template < typename T1, typename T2, bool Gen >
  class BijectionImplementation {
    public:
    using type1_type            = T1;
    using type1_reference       = T1&;
    using type1_const_reference = const T1&;
    using type1_pointer         = T1*;
    using type1_const_pointer   = const T1*;
    using type2_type            = T2;
    using type2_reference       = T2&;
    using type2_const_reference = const T2&;
    using type2_pointer         = T2*;
    using type2_const_pointer   = const T2*;
    using size_type             = std::size_t;
    using difference_type       = std::ptrdiff_t;
    using iterator              = BijectionIterator< T1, T2 >;
    using const_iterator        = BijectionIterator< T1, T2 >;
    using iterator_safe         = BijectionIteratorSafe< T1, T2 >;
    using const_iterator_safe   = BijectionIteratorSafe< T1, T2 >;
 
    private:
    BijectionImplementation(Size size, bool resize_policy);

    BijectionImplementation(std::initializer_list< std::pair< T1, T2 > > list);

    BijectionImplementation(const BijectionImplementation< T1, T2, Gen >& toCopy);

    BijectionImplementation(BijectionImplementation< T1, T2, Gen >&& from) noexcept;
 
    public:
    // ============================================================================
    // ============================================================================

    ~BijectionImplementation();

 
    private:
    BijectionImplementation< T1, T2, Gen >&
        operator=(const BijectionImplementation< T1, T2, Gen >& toCopy);

    BijectionImplementation< T1, T2, Gen >&
        operator=(BijectionImplementation< T1, T2, Gen >&& toCopy);
 
    public:
    // ============================================================================
    // ============================================================================

    iterator begin() const;

    const_iterator cbegin() const;

    const iterator& end() const noexcept;

    const const_iterator& cend() const noexcept;

    iterator_safe beginSafe() const;

    const_iterator_safe cbeginSafe() const;

    const iterator_safe& endSafe() const noexcept;

    const const_iterator_safe& cendSafe() const noexcept;

 
    // ============================================================================
    // ============================================================================

    const T1& first(const T2& second) const;

    const T1& firstWithDefault(const T2& second, const T1& default_val) const;

    const T2& second(const T1& first) const;

    const T2& secondWithDefault(const T1& second, const T2& default_val) const;

    bool existsFirst(const T1& first) const;

    bool existsSecond(const T2& second) const;

    void insert(const T1& first, const T2& second);

    void insert(T1&& first, T2&& second);

    template < typename... Args >
    void emplace(Args&&... args);

    void clear();

    bool empty() const noexcept;

    Size size() const noexcept;

    void eraseFirst(const T1& first);

    void eraseSecond(const T2& second);

    std::string toString() const;

    // ============================================================================
    // ============================================================================

    Size capacity() const noexcept;

    void resize(Size new_size);

    void setResizePolicy(const bool new_policy) noexcept;

    bool resizePolicy() const noexcept;

 
    private:
    using HashTable12 = HashTable< T1, T2* >;
    using HashTable21 = HashTable< T2, T1* >;

    friend class BijectionIteratorSafe< T1, T2 >;
    friend class BijectionIterator< T1, T2 >;
    friend class Bijection< T1, T2 >;
    template < typename TT1, typename TT2, bool >
    friend class BijectionImplementation;
 
    // Below, we create the two gum::HashTable used by the gum::Bijection. Note
    // that the values of these gum::HashTable are pointers. This enables to
    // create only once objects (T1,T2). When using gum::Bijection with large
    // size objects, this feature is of particular interest.

    HashTable12 _firstToSecond_;

    HashTable21 _secondToFirst_;

    void _copy_(const HashTable< T1, T2* >& source);

    typename HashTable12::value_type* _insert_(const T1& first, const T2& second);

    typename HashTable12::value_type* _insert_(T1&& first, T2&& second);
  };
 
#ifndef DOXYGEN_SHOULD_SKIP_THIS
 
  // ===========================================================================
  // ===                  SCALAR BIJECTION IMPLEMENTATION                    ===
  // ===========================================================================

  template < typename T1, typename T2 >
  class BijectionImplementation< T1, T2, true > {
    public:
    using type1_type            = T1;
    using type1_reference       = T1&;
    using type1_const_reference = const T1&;
    using type1_pointer         = T1*;
    using type1_const_pointer   = const T1*;
    using type2_type            = T2;
    using type2_reference       = T2&;
    using type2_const_reference = const T2&;
    using type2_pointer         = T2*;
    using type2_const_pointer   = const T2*;
    using size_type             = std::size_t;
    using difference_type       = std::ptrdiff_t;
    using iterator              = BijectionIterator< T1, T2 >;
    using const_iterator        = BijectionIterator< T1, T2 >;
    using iterator_safe         = BijectionIteratorSafe< T1, T2 >;
    using const_iterator_safe   = BijectionIteratorSafe< T1, T2 >;
 
    private:
    BijectionImplementation(Size size, bool resize_policy);

    BijectionImplementation(std::initializer_list< std::pair< T1, T2 > > list);

    BijectionImplementation(const BijectionImplementation< T1, T2, true >& toCopy);

    BijectionImplementation(BijectionImplementation< T1, T2, true >&& from) noexcept;
 
    public:
    // ============================================================================
    // ============================================================================

    ~BijectionImplementation();

 
    private:
    BijectionImplementation< T1, T2, true >&
        operator=(const BijectionImplementation< T1, T2, true >& toCopy);

    BijectionImplementation< T1, T2, true >&
        operator=(BijectionImplementation< T1, T2, true >&& from);
 
    public:
    // ============================================================================
    // ============================================================================

    iterator begin() const;

    const_iterator cbegin() const;

    const iterator& end() const noexcept;

    const const_iterator& cend() const noexcept;

    iterator_safe beginSafe() const;

    const_iterator_safe cbeginSafe() const;

    const iterator_safe& endSafe() const noexcept;

    const const_iterator_safe& cendSafe() const noexcept;

 
    // ============================================================================
    // ============================================================================

    const T1& first(T2 second) const;

    const T1& firstWithDefault(T2 second, T1 default_val) const;

    const T2& second(T1 first) const;

    const T2& secondWithDefault(T1 first, T2 default_val) const;

    bool existsFirst(T1 first) const;

    bool existsSecond(T2 second) const;

    void insert(T1 first, T2 second);

    template < typename... Args >
    void emplace(Args&&... args);

    void clear();

    bool empty() const noexcept;

    Size size() const noexcept;

    void eraseFirst(T1 first);

    void eraseSecond(T2 second);

    std::string toString() const;

    // ============================================================================
    // ============================================================================

    Size capacity() const noexcept;

    void resize(Size new_size);

    void setResizePolicy(const bool new_policy) noexcept;

    bool resizePolicy() const noexcept;

 
    private:
    using HashTable12 = HashTable< T1, T2 >;
    using HashTable21 = HashTable< T2, T1 >;

    friend class BijectionIteratorSafe< T1, T2 >;
    friend class BijectionIterator< T1, T2 >;
    friend class Bijection< T1, T2 >;
    template < typename TT1, typename TT2, bool >
    friend class BijectionImplementation;
 
    // Below, we create the two gum::HashTable used by the gum::Bijection. Note
    // that the values of these gum::HashTable are pointers. This enables to
    // create only once objects (T1,T2). When using gum::Bijection with large
    // size objects, this feature is of particular interest.

    HashTable12 _firstToSecond_;

    HashTable21 _secondToFirst_;

    void _copy_(const HashTable< T1, T2 >& f2s);

    void _insert_(const T1 first, const T2 second);
  };
 
#endif /* DOXYGEN_SHOULD_SKIP_THIS */

  template < bool gen >
  struct BijectionIteratorGet {
    template < typename T >
    INLINE static const T& op_second(const T* x) {
      return *x;
    }
  };

  template <>
  struct BijectionIteratorGet< true > {
    template < typename T >
    INLINE static const T& op_second(const T& x) {
      return x;
    }
  };
 
  // ===========================================================================
  // ===                      BIJECTION SAFE ITERATORS                       ===
  // ===========================================================================

  template < typename T1, typename T2 >
  class BijectionIteratorSafe {
    template < typename TT1, typename TT2, bool >
    friend class BijectionImplementation;
 
    public:
    using iterator_category     = std::forward_iterator_tag;
    using type1_type            = T1;
    using type1_reference       = T1&;
    using type1_const_reference = const T1&;
    using type1_pointer         = T1*;
    using type1_const_pointer   = const T1*;
    using type2_type            = T2;
    using type2_reference       = T2&;
    using type2_const_reference = const T2&;
    using type2_pointer         = T2*;
    using type2_const_pointer   = const T2*;
    using difference_type       = std::ptrdiff_t;
 
    private:
    using Getter
        = BijectionIteratorGet< std::is_scalar< T1 >::value && std::is_scalar< T2 >::value >;

    template < bool Gen >
    BijectionIteratorSafe(const BijectionImplementation< T1, T2, Gen >& bijection);
 
    public:
    // ============================================================================
    // ============================================================================

    explicit BijectionIteratorSafe() noexcept;
 
#ifndef DOXYGEN_SHOULD_SKIP_THIS
    // constructor for the static endSafe iterator
    // only bijection.cpp should use this constructor
    explicit consteval BijectionIteratorSafe(StaticInitializer init) noexcept : _iter_(init) {}
#endif   // DOXYGEN_SHOULD_SKIP_THIS

    BijectionIteratorSafe(const Bijection< T1, T2 >& bijection);

    BijectionIteratorSafe(const BijectionIteratorSafe< T1, T2 >& from);

    BijectionIteratorSafe(BijectionIteratorSafe< T1, T2 >&& from) noexcept;

    ~BijectionIteratorSafe() noexcept;

    // ============================================================================
    // ============================================================================

    BijectionIteratorSafe< T1, T2 >& operator=(const BijectionIteratorSafe< T1, T2 >& toCopy);

    BijectionIteratorSafe< T1, T2 >& operator=(BijectionIteratorSafe< T1, T2 >&& toMove) noexcept;

    BijectionIteratorSafe< T1, T2 >& operator++() noexcept;

    BijectionIteratorSafe< T1, T2 >& operator+=(Size nb) noexcept;

    BijectionIteratorSafe< T1, T2 > operator+(Size nb) noexcept;

    bool operator!=(const BijectionIteratorSafe< T1, T2 >& toCompare) const noexcept;

    bool operator==(const BijectionIteratorSafe< T1, T2 >& toCompare) const noexcept;

    // ============================================================================
    // ============================================================================

    const T1& first() const;

    const T2& second() const;

 
    private:
    using HashTable12 =
        typename std::conditional< std::is_scalar< T1 >::value && std::is_scalar< T2 >::value,
                                   HashTable< T1, T2 >,
                                   HashTable< T1, T2* > >::type;

    using HashIter = typename HashTable12::const_iterator_safe;

    HashIter _iter_;
  };
 
  // ===========================================================================
  // ===                     BIJECTION UNSAFE ITERATORS                      ===
  // ===========================================================================
  template < typename T1, typename T2 >
  class BijectionIterator {
    template < typename TT1, typename TT2, bool >
    friend class BijectionImplementation;
 
    public:
    using iterator_category     = std::forward_iterator_tag;
    using type1_type            = T1;
    using type1_reference       = T1&;
    using type1_const_reference = const T1&;
    using type1_pointer         = T1*;
    using type1_const_pointer   = const T1*;
    using type2_type            = T2;
    using type2_reference       = T2&;
    using type2_const_reference = const T2&;
    using type2_pointer         = T2*;
    using type2_const_pointer   = const T2*;
    using difference_type       = std::ptrdiff_t;
 
    private:
    using Getter
        = BijectionIteratorGet< std::is_scalar< T1 >::value && std::is_scalar< T2 >::value >;

    template < bool Gen >
    BijectionIterator(const BijectionImplementation< T1, T2, Gen >& bijection);
 
    public:
    // ============================================================================
    // ============================================================================

    explicit BijectionIterator() noexcept;
 
#ifndef DOXYGEN_SHOULD_SKIP_THIS
    // constructor for the static end iterator
    // only bijection.cpp should use this constructor
    explicit consteval BijectionIterator(StaticInitializer init) noexcept : _iter_(init) {}
#endif   // DOXYGEN_SHOULD_SKIP_THIS

    BijectionIterator(const Bijection< T1, T2 >& bijection);

    BijectionIterator(const BijectionIterator< T1, T2 >& from);

    BijectionIterator(BijectionIterator< T1, T2 >&& from) noexcept;

    ~BijectionIterator() noexcept;

    // ============================================================================
    // ============================================================================

    BijectionIterator< T1, T2 >& operator=(const BijectionIterator< T1, T2 >& toCopy);

    BijectionIterator< T1, T2 >& operator=(BijectionIterator< T1, T2 >&& toMove) noexcept;

    BijectionIterator< T1, T2 >& operator++() noexcept;

    BijectionIterator< T1, T2 >& operator+=(Size nb) noexcept;

    BijectionIterator< T1, T2 > operator+(Size nb) noexcept;

    bool operator!=(const BijectionIterator< T1, T2 >& toCompare) const noexcept;

    bool operator==(const BijectionIterator< T1, T2 >& toCompare) const noexcept;

    // ============================================================================
    // ============================================================================

    const T1& first() const;

    const T2& second() const;

 
    private:
    using HashTable12 =
        typename std::conditional< std::is_scalar< T1 >::value && std::is_scalar< T2 >::value,
                                   HashTable< T1, T2 >,
                                   HashTable< T1, T2* > >::type;
    using HashIter = typename HashTable12::const_iterator;

    HashIter _iter_;
  };

  template < typename T1, typename T2 >
  class Bijection:
      public BijectionImplementation< T1,
                                      T2,
                                      std::is_scalar< T1 >::value && std::is_scalar< T2 >::value > {
    public:
    using type1_type            = T1;
    using type1_reference       = T1&;
    using type1_const_reference = const T1&;
    using type1_pointer         = T1*;
    using type1_const_pointer   = const T1*;
    using type2_type            = T2;
    using type2_reference       = T2&;
    using type2_const_reference = const T2&;
    using type2_pointer         = T2*;
    using type2_const_pointer   = const T2*;
    using size_type             = std::size_t;
    using difference_type       = std::ptrdiff_t;
    using iterator              = BijectionIterator< T1, T2 >;
    using const_iterator        = BijectionIterator< T1, T2 >;
    using iterator_safe         = BijectionIteratorSafe< T1, T2 >;
    using const_iterator_safe   = BijectionIteratorSafe< T1, T2 >;

    using Implementation
        = BijectionImplementation< T1,
                                   T2,
                                   std::is_scalar< T1 >::value && std::is_scalar< T2 >::value >;
 
    // ============================================================================
    // ============================================================================

    Bijection(Size size          = HashTableConst::default_size,
              bool resize_policy = HashTableConst::default_resize_policy);

    Bijection(std::initializer_list< std::pair< T1, T2 > > list);

    Bijection(const Bijection< T1, T2 >& toCopy);

    Bijection(Bijection< T1, T2 >&& from) noexcept;

    ~Bijection();

    // ============================================================================
    // ============================================================================

    Bijection< T1, T2 >& operator=(const Bijection< T1, T2 >& toCopy);

    Bijection< T1, T2 >& operator=(Bijection< T1, T2 >&& bij);

  };
 
 
#ifndef DOXYGEN_SHOULD_SKIP_THIS
  // _static_Bijection_end_ is a 'constant' iterator initialized at compile time
  // that represents the end iterators for all bijections (whatever their
  // type). This global variable avoids creating the same iterators within every
  // Bijection instance (this would be quite inefficient as end is precisely
  // identical for all bijections). The same hold for safe end iterators.
  // The type of _Bijection_end_ is a pointer to void because C++ allows
  // pointers to void to be cast into pointers to other types (and conversely).
  // This avoids the painful strict-aliasing rule warning
  extern const BijectionIterator< int, int >     _static_Bijection_end_;
  extern const BijectionIteratorSafe< int, int > _static_Bijection_end_safe_;
 
  inline constexpr void* const _Bijection_end_      = (void* const)&_static_Bijection_end_;
  inline constexpr void* const _Bijection_end_safe_ = (void* const)&_static_Bijection_end_safe_;
#endif   // DOXYGEN_SHOULD_SKIP_THIS
 

  template < typename T1, typename T2 >
  std::ostream& operator<<(std::ostream&, const Bijection< T1, T2 >& bijection);
 
} /* namespace gum */
 
 
#ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
extern template class gum::Bijection< int, int >;
extern template class gum::Bijection< std::string, std::string >;
#endif
 
 
// always include the template implementations
#include <agrum/base/core/bijection_tpl.h>
 
#endif /* GUM_BIJECTION_H */