AVLTree.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_AVL_TREE_H
#define GUM_AVL_TREE_H
 
#include <algorithm>
#include <string>
 
#include <agrum/agrum.h>
 
#include <agrum/base/core/hashFunc.h>
#include <agrum/base/core/staticInitializer.h>
 
#include <initializer_list>
 
namespace gum {
 
#ifndef DOXYGEN_SHOULD_SKIP_THIS
 
  template < typename Val, typename Cmp >
  class AVLTreeIterator;
  template < typename Val, typename Cmp >
  class AVLTreeIteratorSafe;
 
  template < typename Val, typename Cmp >
  class AVLTreeReverseIterator;
  template < typename Val, typename Cmp >
  class AVLTreeReverseIteratorSafe;

  template < typename Val >
  struct AVLTreeNode {
    // the neighbors in our AVL tree
    AVLTreeNode* parent{nullptr};
    AVLTreeNode* left_child{nullptr};
    AVLTreeNode* right_child{nullptr};
 
    // the height of the node in the AVL tree
    int height{1};
 
    // the element to be stored into the node
    Val value;
 
    // a class to enabling emplacing values in AVLNodes
    enum class Emplace { EMPLACE };
 
    explicit AVLTreeNode(const Val& val) : value(val) { GUM_CONSTRUCTOR(AVLTreeNode); };
 
    explicit AVLTreeNode(Val&& val) noexcept : value(std::move(val)) {
      GUM_CONSTRUCTOR(AVLTreeNode);
    };
 
    template < typename... Args >
    explicit AVLTreeNode(const Emplace& emplace, Args&&... args) :
        value(std::forward< Args >(args)...) {
      GUM_CONSTRUCTOR(AVLTreeNode);
    }
 
    AVLTreeNode(const AVLTreeNode< Val >& from) :
        parent(from.parent), left_child(from.left_child), right_child(from.right_child),
        height(from.height), value(from.value) {
      GUM_CONS_CPY(AVLTreeNode);
    }
 
    AVLTreeNode(AVLTreeNode< Val >&& from) :
        parent(from.parent), left_child(from.left_child), right_child(from.right_child),
        height(from.height), value(std::move(from.value)) {
      GUM_CONS_MOV(AVLTreeNode);
    }
 
    ~AVLTreeNode() { GUM_DESTRUCTOR(AVLTreeNode); }
 
    // two nodes are equal if and only if they contain the same value
    bool operator==(const AVLTreeNode< Val >& from) const { return value == from.value; }
  };

  template < typename Val >
  std::ostream& operator<<(std::ostream& stream, const AVLTreeNode< Val >& node) {
    return stream << '<' << node.value << '>';
  }

  template < typename Val >
  class HashFunc< AVLTreeNode< Val > >: public HashFunc< Val > {
    public:
    static Size castToSize(const AVLTreeNode< Val >& key) {
      return HashFunc< Val >::castToSize(key.value);
    }

 
    private:   // best attempt to get rid of overloaded virtual warnings
    using HashFunc< Val >::operator();
 
    public:
    INLINE Size operator()(const AVLTreeNode< Val >& key) const {
      return HashFunc< Val >::operator()(key.value);
    }
  };
 
#endif   // DOXYGEN_SHOULD_SKIP_THIS
 

  template < typename Val, typename Cmp = std::less< Val > >
  class AVLTree {
    public:
    using value_type            = Val;
    using reference             = Val&;
    using const_reference       = const Val&;
    using pointer               = Val*;
    using const_pointer         = const Val*;
    using iterator              = AVLTreeIterator< Val, Cmp >;
    using iterator_safe         = AVLTreeIteratorSafe< Val, Cmp >;
    using reverse_iterator      = AVLTreeReverseIterator< Val, Cmp >;
    using reverse_iterator_safe = AVLTreeReverseIteratorSafe< Val, Cmp >;
    using AVLNode               = AVLTreeNode< Val >;
 
    // ============================================================================
    // ============================================================================

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

    explicit AVLTree(std::initializer_list< Val > list);

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

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

    ~AVLTree();

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

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

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

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

    Size size() const noexcept;

    bool empty() const noexcept;

    bool contains(const value_type& val) const;

    bool exists(const value_type& val) const;


    const value_type& highestValue() const;


    const value_type& lowestValue() const;

    const value_type& insert(const value_type& val);

    const value_type& insert(value_type&& val);

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


    void erase(const value_type& val);


    void erase(iterator_safe& iter);


    void erase(reverse_iterator_safe& iter);

    void clear();

    std::string toString() const;

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

    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;

 
    protected:
    AVLNode* root_node_{nullptr};

    AVLNode* lowest_node_{nullptr};

    AVLNode* highest_node_{nullptr};

    Size nb_elements_{Size(0)};

    bool owns_nodes_{true};

    Cmp cmp_;

    std::vector< iterator_safe* > safe_iterators_;
 

    AVLNode* lowestNode_() const noexcept;

    AVLNode* highestNode_() const noexcept;

    AVLNode* rightRotation_(AVLNode* node_q);

    AVLNode* leftRotation_(AVLNode* node_p);

    void rebalanceTree_(AVLNode* node);


    AVLNode* removeNodeFromTree_(AVLNode* node);

    void erase_(AVLNode* node);

    const value_type& insert_(AVLNode* node);

    void insertIntoSafeList_(iterator_safe* iter);

    void removeFromSafeList_(iterator_safe* iter);


    static AVLNode* copySubtree_(const AVLNode* from_node, AVLNode* new_parent);

    static void deleteSubtree_(AVLNode* subtree_root_node);

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

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

    explicit AVLTreeIterator(const AVLTree< 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 AVLTreeIterator(StaticInitializer init) noexcept {}
#endif   // DOXYGEN_SHOULD_SKIP_THIS

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

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

    ~AVLTreeIterator() noexcept;

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

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

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

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

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


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


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


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


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

    const_reference operator*() const;

 
 
    protected:
    using AVLNode = AVLTreeNode< Val >;

    AVLTree< Val, Cmp >* tree_{nullptr};

    AVLNode* node_{nullptr};

    AVLNode* next_node_{nullptr};

    AVLNode* preceding_node_{nullptr};
 

    AVLNode* nextNode_(AVLNode* node) const noexcept;

    AVLNode* precedingNode_(AVLNode* node) const noexcept;

    void unregisterTree_() noexcept;

    void pointToEndRend_() noexcept;
 

    friend AVLTree< Val, Cmp >;
  };

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

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

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

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

    ~AVLTreeIteratorSafe() noexcept;

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

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

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

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

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


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


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


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


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

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

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

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

    explicit AVLTreeReverseIterator(const AVLTree< 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 AVLTreeReverseIterator(StaticInitializer init) noexcept :
        AVLTreeIterator< Val, Cmp >(init) {}
#endif   // DOXYGEN_SHOULD_SKIP_THIS

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

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

    ~AVLTreeReverseIterator() noexcept;

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

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

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

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

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


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


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


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


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

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

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

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

    explicit AVLTreeReverseIteratorSafe(AVLTree< 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 AVLTreeReverseIteratorSafe(StaticInitializer init) noexcept :
        AVLTreeIteratorSafe< Val, Cmp >(init) {}
#endif   // DOXYGEN_SHOULD_SKIP_THIS

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

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

    ~AVLTreeReverseIteratorSafe() noexcept;

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

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

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

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

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


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


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


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


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

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

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

  template < typename Val, typename Cmp >
  std::ostream& operator<<(std::ostream& stream, const AVLTree< Val, Cmp >& tree) {
    return stream << tree.toString();
  }
 
 
#ifndef DOXYGEN_SHOULD_SKIP_THIS
  // _static_AVLTree_end_ is a 'constant' iterator initialized at compile time
  // that represents the end iterators for all AVL trees (whatever their
  // type). This global variable avoids creating the same iterators within every
  // 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 _AVLTree_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 AVLTreeIterator< int, std::less< int > >            _static_AVLTree_end_;
  extern const AVLTreeReverseIterator< int, std::less< int > >     _static_AVLTree_rend_;
  extern const AVLTreeIteratorSafe< int, std::less< int > >        _static_AVLTree_end_safe_;
  extern const AVLTreeReverseIteratorSafe< int, std::less< int > > _static_AVLTree_rend_safe_;
 
  inline constexpr void* const _AVLTree_end_       = (void* const)&_static_AVLTree_end_;
  inline constexpr void* const _AVLTree_rend_      = (void* const)&_static_AVLTree_rend_;
  inline constexpr void* const _AVLTree_end_safe_  = (void* const)&_static_AVLTree_end_safe_;
  inline constexpr void* const _AVLTree_rend_safe_ = (void* const)&_static_AVLTree_rend_safe_;
#endif   // DOXYGEN_SHOULD_SKIP_THIS
 
 
}   // namespace gum
 
// always include the implementation of the templates
#include <agrum/base/core/AVLTree_tpl.h>
 
#endif   // GUM_AVL_TREE_H