sharedAVLTree.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_SHARED_AVL_TREE_H
#define GUM_SHARED_AVL_TREE_H
 
#include <agrum/agrum.h>
 
#include <agrum/base/core/AVLTree.h>
 
#ifndef DOXYGEN_SHOULD_SKIP_THIS
 
namespace gum {
 
  template < typename Val, typename Cmp >
  class SharedAVLTreeIterator;
  template < typename Val, typename Cmp >
  class SharedAVLTreeIteratorSafe;
 
  template < typename Val, typename Cmp >
  class SharedAVLTreeReverseIterator;
  template < typename Val, typename Cmp >
  class SharedAVLTreeReverseIteratorSafe;

  template < typename Val, typename Cmp = std::less< Val > >
  class SharedAVLTree: private AVLTree< Val, Cmp > {
    public:
    using value_type            = Val;
    using reference             = Val&;
    using const_reference       = const Val&;
    using pointer               = Val*;
    using const_pointer         = const Val*;
    using iterator              = SharedAVLTreeIterator< Val, Cmp >;
    using iterator_safe         = SharedAVLTreeIteratorSafe< Val, Cmp >;
    using reverse_iterator      = SharedAVLTreeReverseIterator< Val, Cmp >;
    using reverse_iterator_safe = SharedAVLTreeReverseIteratorSafe< Val, Cmp >;
    using AVLNode               = AVLTreeNode< Val >;
 
    // ============================================================================
    // ============================================================================

    explicit SharedAVLTree(const Cmp& compare = Cmp());

    SharedAVLTree(SharedAVLTree< Val, Cmp >&& from) noexcept;

    ~SharedAVLTree();

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

    SharedAVLTree< Val, Cmp >& operator=(SharedAVLTree< Val, Cmp >&& from);

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

    using AVLTree< Val, Cmp >::size;

    using AVLTree< Val, Cmp >::empty;

    using AVLTree< Val, Cmp >::contains;

    using AVLTree< Val, Cmp >::exists;


    AVLNode* highestNode() const noexcept;


    using AVLTree< Val, Cmp >::highestValue;


    AVLNode* lowestNode() const noexcept;


    using AVLTree< Val, Cmp >::lowestValue;

    void insert(AVLNode* node);


    void erase(AVLNode* node);


    void erase(iterator_safe& iter);


    void erase(reverse_iterator_safe& iter);

    using AVLTree< Val, Cmp >::clear;

    using AVLTree< Val, Cmp >::toString;

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

    iterator begin() const;

    constexpr const iterator& end() const;

    reverse_iterator rbegin() const;

    constexpr const reverse_iterator& rend() const;

    iterator_safe beginSafe();

    constexpr const iterator_safe& endSafe() const;

    reverse_iterator_safe rbeginSafe();

    constexpr const reverse_iterator_safe& rendSafe() const;

 
 
    private:
    SharedAVLTree(const SharedAVLTree< Val, Cmp >& from)                        = delete;
    SharedAVLTree< Val, Cmp >& operator=(const SharedAVLTree< Val, Cmp >& from) = delete;
 

    friend iterator;
    friend reverse_iterator;
    friend iterator_safe;
    friend reverse_iterator_safe;
  };

  template < typename Val, typename Cmp = std::less< Val > >
  class SharedAVLTreeIterator: protected AVLTreeIterator< Val, Cmp > {
    public:
    using iterator_category = std::bidirectional_iterator_tag;
    using AVLNode           = AVLTreeNode< Val >;
    using value_type        = AVLNode;
    using reference         = value_type&;
    using const_reference   = const value_type&;
    using pointer           = value_type*;
    using const_pointer     = const value_type*;
 
 
    // ============================================================================
    // ============================================================================

    explicit SharedAVLTreeIterator(const SharedAVLTree< Val, Cmp >& tree,
                                   const bool                       begin = true) noexcept;
 
#  ifndef DOXYGEN_SHOULD_SKIP_THIS
    // constructor for the static end iterator
    // only AVLTree.cpp should use this constructor
    explicit consteval SharedAVLTreeIterator(StaticInitializer init) noexcept :
        AVLTreeIterator< Val, Cmp >(init) {}
#  endif   // DOXYGEN_SHOULD_SKIP_THIS

    SharedAVLTreeIterator(const SharedAVLTreeIterator< Val, Cmp >& from) noexcept;

    SharedAVLTreeIterator(SharedAVLTreeIterator< Val, Cmp >&& from) noexcept;

    ~SharedAVLTreeIterator() noexcept;

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

    SharedAVLTreeIterator< Val, Cmp >&
        operator=(const SharedAVLTreeIterator< Val, Cmp >& from) noexcept;

    SharedAVLTreeIterator< Val, Cmp >& operator=(SharedAVLTreeIterator< Val, Cmp >&& from) noexcept;

    bool operator==(const SharedAVLTreeIterator< Val, Cmp >& from) const;

    bool operator!=(const SharedAVLTreeIterator< Val, Cmp >& from) const;


    SharedAVLTreeIterator< Val, Cmp >& operator++() noexcept;


    SharedAVLTreeIterator< Val, Cmp >& operator+=(const Size k) noexcept;


    SharedAVLTreeIterator< Val, Cmp >& operator--() noexcept;


    SharedAVLTreeIterator< Val, Cmp >& operator-=(const Size k) noexcept;

    const_reference operator*() const;

    const_pointer operator->() const;


    friend AVLTree< Val, Cmp >;
    friend SharedAVLTree< Val, Cmp >;
  };

  template < typename Val, typename Cmp = std::less< Val > >
  class SharedAVLTreeIteratorSafe: protected AVLTreeIteratorSafe< Val, Cmp > {
    public:
    using iterator_category = std::bidirectional_iterator_tag;
    using AVLNode           = AVLTreeNode< Val >;
    using value_type        = AVLNode;
    using reference         = value_type&;
    using const_reference   = const value_type&;
    using pointer           = value_type*;
    using const_pointer     = const value_type*;
 
 
    // ============================================================================
    // ============================================================================

    explicit SharedAVLTreeIteratorSafe(SharedAVLTree< Val, Cmp >& tree, const bool rbegin = true);
 
#  ifndef DOXYGEN_SHOULD_SKIP_THIS
    // constructor for the static endSafe iterator
    // only AVLTree.cpp should use this constructor
    explicit consteval SharedAVLTreeIteratorSafe(StaticInitializer init) noexcept :
        AVLTreeIteratorSafe< Val, Cmp >(init) {}
#  endif   // DOXYGEN_SHOULD_SKIP_THIS

    SharedAVLTreeIteratorSafe(const SharedAVLTreeIteratorSafe< Val, Cmp >& from);

    SharedAVLTreeIteratorSafe(SharedAVLTreeIteratorSafe< Val, Cmp >&& from);

    ~SharedAVLTreeIteratorSafe() noexcept;

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

    SharedAVLTreeIteratorSafe< Val, Cmp >&
        operator=(const SharedAVLTreeIteratorSafe< Val, Cmp >& from);

    SharedAVLTreeIteratorSafe< Val, Cmp >& operator=(SharedAVLTreeIteratorSafe< Val, Cmp >&& from);

    bool operator==(const SharedAVLTreeIteratorSafe< Val, Cmp >& from) const;

    bool operator!=(const SharedAVLTreeIteratorSafe< Val, Cmp >& from) const;


    SharedAVLTreeIteratorSafe< Val, Cmp >& operator++() noexcept;


    SharedAVLTreeIteratorSafe< Val, Cmp >& operator+=(const Size k) noexcept;


    SharedAVLTreeIteratorSafe< Val, Cmp >& operator--() noexcept;


    SharedAVLTreeIteratorSafe< Val, Cmp >& operator-=(const Size k) noexcept;

    const_reference operator*() const;

    const_pointer operator->() const;

 
 
    protected:
    friend AVLTree< Val, Cmp >;
    friend SharedAVLTree< Val, Cmp >;
  };

  template < typename Val, typename Cmp = std::less< Val > >
  class SharedAVLTreeReverseIterator: protected SharedAVLTreeIterator< Val, Cmp > {
    public:
    using iterator_category = std::bidirectional_iterator_tag;
    using AVLNode           = AVLTreeNode< Val >;
    using value_type        = AVLNode;
    using reference         = value_type&;
    using const_reference   = const value_type&;
    using pointer           = value_type*;
    using const_pointer     = const value_type*;
 
 
    // ============================================================================
    // ============================================================================

    explicit SharedAVLTreeReverseIterator(const SharedAVLTree< Val, Cmp >& tree,
                                          const bool                       rbegin = true) noexcept;
 
#  ifndef DOXYGEN_SHOULD_SKIP_THIS
    // constructor for the static rend iterator
    // only AVLTree.cpp should use this constructor
    explicit consteval SharedAVLTreeReverseIterator(StaticInitializer init) noexcept :
        SharedAVLTreeIterator< Val, Cmp >(init) {}
#  endif   // DOXYGEN_SHOULD_SKIP_THIS

    SharedAVLTreeReverseIterator(const SharedAVLTreeReverseIterator< Val, Cmp >& from) noexcept;

    SharedAVLTreeReverseIterator(SharedAVLTreeReverseIterator< Val, Cmp >&& from) noexcept;

    ~SharedAVLTreeReverseIterator() noexcept;

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

    SharedAVLTreeReverseIterator< Val, Cmp >&
        operator=(const SharedAVLTreeReverseIterator< Val, Cmp >& from) noexcept;

    SharedAVLTreeReverseIterator< Val, Cmp >&
        operator=(SharedAVLTreeReverseIterator< Val, Cmp >&& from) noexcept;

    bool operator==(const SharedAVLTreeReverseIterator< Val, Cmp >& from) const;

    bool operator!=(const SharedAVLTreeReverseIterator< Val, Cmp >& from) const;


    SharedAVLTreeReverseIterator< Val, Cmp >& operator++() noexcept;


    SharedAVLTreeReverseIterator< Val, Cmp >& operator+=(const Size k) noexcept;


    SharedAVLTreeReverseIterator< Val, Cmp >& operator--() noexcept;


    SharedAVLTreeReverseIterator< Val, Cmp >& operator-=(const Size k) noexcept;

    using SharedAVLTreeIterator< Val, Cmp >::operator*;

    using SharedAVLTreeIterator< Val, Cmp >::operator->;

 
 
    protected:
    friend AVLTree< Val, Cmp >;
    friend SharedAVLTree< Val, Cmp >;
  };

  template < typename Val, typename Cmp = std::less< Val > >
  class SharedAVLTreeReverseIteratorSafe: protected SharedAVLTreeIteratorSafe< Val, Cmp > {
    public:
    using iterator_category = std::bidirectional_iterator_tag;
    using AVLNode           = AVLTreeNode< Val >;
    using value_type        = AVLNode;
    using reference         = value_type&;
    using const_reference   = const value_type&;
    using pointer           = value_type*;
    using const_pointer     = const value_type*;
 
 
    // ============================================================================
    // ============================================================================

    explicit SharedAVLTreeReverseIteratorSafe(SharedAVLTree< Val, Cmp >& tree,
                                              const bool                 rbegin = true);
 
#  ifndef DOXYGEN_SHOULD_SKIP_THIS
    // constructor for the static rendSafe iterator
    // only AVLTree.cpp should use this constructor
    explicit consteval SharedAVLTreeReverseIteratorSafe(StaticInitializer init) noexcept :
        SharedAVLTreeIteratorSafe< Val, Cmp >(init) {}
#  endif   // DOXYGEN_SHOULD_SKIP_THIS

    SharedAVLTreeReverseIteratorSafe(const SharedAVLTreeReverseIteratorSafe< Val, Cmp >& from);

    SharedAVLTreeReverseIteratorSafe(SharedAVLTreeReverseIteratorSafe< Val, Cmp >&& from);

    ~SharedAVLTreeReverseIteratorSafe() noexcept;

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

    SharedAVLTreeReverseIteratorSafe< Val, Cmp >&
        operator=(const SharedAVLTreeReverseIteratorSafe< Val, Cmp >& from);

    SharedAVLTreeReverseIteratorSafe< Val, Cmp >&
        operator=(SharedAVLTreeReverseIteratorSafe< Val, Cmp >&& from);

    bool operator==(const SharedAVLTreeReverseIteratorSafe< Val, Cmp >& from) const;

    bool operator!=(const SharedAVLTreeReverseIteratorSafe< Val, Cmp >& from) const;


    SharedAVLTreeReverseIteratorSafe< Val, Cmp >& operator++() noexcept;


    SharedAVLTreeReverseIteratorSafe< Val, Cmp >& operator+=(const Size k) noexcept;


    SharedAVLTreeReverseIteratorSafe< Val, Cmp >& operator--() noexcept;


    SharedAVLTreeReverseIteratorSafe< Val, Cmp >& operator-=(const Size k) noexcept;

    using SharedAVLTreeIteratorSafe< Val, Cmp >::operator*;

    using SharedAVLTreeIteratorSafe< Val, Cmp >::operator->;

 
    protected:
    friend AVLTree< Val, Cmp >;
    friend SharedAVLTree< Val, Cmp >;
  };

  template < typename Val, typename Cmp >
  std::ostream& operator<<(std::ostream& stream, const SharedAVLTree< Val, Cmp >& tree) {
    return stream << tree.toString();
  }
 
 
#  ifndef DOXYGEN_SHOULD_SKIP_THIS
  // _static_SharedAVLTree_end_ is a 'constant' iterator initialized at compile time
  // that represents the end iterators for all shared AVL trees (whatever their
  // type). This global variable avoids creating the same iterators within every
  // shared AVL tree instance (this would be quite inefficient as end is precisely
  // identical for all AVL trees). The same hold for reverse and safe end iterators.
  // The type of _SharedAVLTree_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 SharedAVLTreeIterator< int, std::less< int > >        _static_SharedAVLTree_end_;
  extern const SharedAVLTreeReverseIterator< int, std::less< int > > _static_SharedAVLTree_rend_;
  extern const SharedAVLTreeIteratorSafe< int, std::less< int > > _static_SharedAVLTree_end_safe_;
  extern const SharedAVLTreeReverseIteratorSafe< int, std::less< int > >
      _static_SharedAVLTree_rend_safe_;
 
  inline constexpr void* const _SharedAVLTree_end_  = (void* const)&_static_SharedAVLTree_end_;
  inline constexpr void* const _SharedAVLTree_rend_ = (void* const)&_static_SharedAVLTree_rend_;
  inline constexpr void* const _SharedAVLTree_end_safe_
      = (void* const)&_static_SharedAVLTree_end_safe_;
  inline constexpr void* const _SharedAVLTree_rend_safe_
      = (void* const)&_static_SharedAVLTree_rend_safe_;
#  endif   // DOXYGEN_SHOULD_SKIP_THIS
 
 
}   // namespace gum
 
// always include the implementation of the templates
#  include <agrum/base/core/sharedAVLTree_tpl.h>
 
#endif   // DOXYGEN_SHOULD_SKIP_THIS
 
#endif   // GUM_SHARED_AVL_TREE_H