binSearchTree.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_BIN_SEARCH_TREE_H
#define GUM_BIN_SEARCH_TREE_H
 
#include <agrum/agrum.h>
 
#include <agrum/base/core/binTreeNode.h>
 
namespace gum {
 
#ifndef DOXYGEN_SHOULD_SKIP_THIS
  // classes provided/used by this header
  template < typename Val, class Cmp, class Node >
  class BinSearchTree;
 
  template < typename Val, class Cmp, class Node >
  class BinSearchTreeIterator;
#endif   // DOXYGEN_SHOULD_SKIP_THIS
 
  // ===========================================================================
  // ===                      GENERIC BINARY SEARCH TREE                     ===
  // ===========================================================================

  template < typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val > >
  class BinSearchTree {
    public:
    using iterator       = BinSearchTreeIterator< Val, Cmp, Node >;
    using const_iterator = BinSearchTreeIterator< Val, Cmp, Node >;
 
    // ============================================================================
    // ============================================================================

    explicit BinSearchTree(bool uniqueness_policy = false);

    BinSearchTree(const BinSearchTree< Val, Cmp, Node >& from);

    virtual ~BinSearchTree();

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

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

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

    iterator       begin();
    const_iterator begin() const;

    iterator       rbegin();
    const_iterator rbegin() const;

    const iterator&       end();
    const const_iterator& end() const;

    const iterator&       rend();
    const const_iterator& rend() const;

    iterator       root();
    const_iterator root() const;

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

    const Val& rootValue() const;

    const Val& minValue() const;

    const Val& maxValue() const;

    const Val& insert(const Val& val);

    void erase(const Val& val);

    void erase(const iterator& iter);

    bool contains(const Val& val) const;

    void clear();

    Size size() const;

    bool empty() const;

    virtual std::string toString() const;

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

    bool uniquenessPolicy() const;

    void setUniquenessPolicy(const bool new_policy);

 
    protected:
    Node* root_;

    Cmp cmp_;

    mutable iterator* iterator_list_;

    mutable bool uniqueness_policy_;

    Size nb_elements_;

    iterator iter_end_;

    friend class BinSearchTreeIterator< Val, Cmp, Node >;

    Node* copy_(Node* root_from, Node* parent = 0, BinTreeDir dir = BinTreeDir::LEFT_CHILD);

    Node* minNode_(Node* node) const;

    Node* maxNode_(Node* node) const;

    Node* succNode_(Node* node) const;

    Node* prevNode_(Node* node) const;

    Node* getNode_(const Val& val) const;


    void deleteSubTree_(Node* node);

    virtual void erase_(Node* node);
 
    private:
    void _eraseWithTwoChildren_(Node* node);
 
    protected:
    virtual Node* insert_(const Val& val);
 
    private:
    void _updateEraseIterators_(Node* node);
  };
 
  // ===========================================================================
  // ===                 GENERIC BINARY SEARCH TREE ITERATORS                ===
  // ===========================================================================

  template < typename Val, class Cmp, class Node >
  class BinSearchTreeIterator {
    public:
    // ============================================================================
    // ============================================================================

    BinSearchTreeIterator();

    BinSearchTreeIterator(const BinSearchTreeIterator< Val, Cmp, Node >& from);

    ~BinSearchTreeIterator();

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

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

    const Val& operator*() const;

    BinSearchTreeIterator< Val, Cmp, Node >& operator++();

    BinSearchTreeIterator< Val, Cmp, Node >& operator--();

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

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

    // ############################################################################
    // ############################################################################

    BinSearchTreeIterator< Val, Cmp, Node >& up();

    BinSearchTreeIterator< Val, Cmp, Node >& downLeft();

    BinSearchTreeIterator< Val, Cmp, Node >& downRight();

    void clear();

 
    protected:
    Node* node_;

    Node* next_node_;

    Node* prev_node_;

    Node* parent_;

    Node* left_child_;

    Node* right_child_;

    BinSearchTree< Val, Cmp, Node >* tree_;

    BinSearchTreeIterator< Val, Cmp, Node >* next_iter_;
 
    private:
    friend class BinSearchTree< Val, Cmp, Node >;

    void initialize_(const BinSearchTree< Val, Cmp, Node >* tree,
                     const Node*                            current_node,
                     bool                                   add_to_iterator_list);

    void detachFromTree_();
  };
 
} /* namespace gum */
 
 
#ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
extern template class gum::BinSearchTree< int >;
#endif
 
 
// always include the template implementations
#include <agrum/base/core/binSearchTree_tpl.h>
 
#endif   // GUM_BIN_SEARCH_TREE_H