binSearchTree.h

Go to the documentation of this file.

/***************************************************************************
 *   Copyright (C) 2005 by Christophe GONZALES and Pierre-Henri WUILLEMIN  *
 *   {prenom.nom}_at_lip6.fr                                               *
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program is distributed in the hope that it will be useful,       *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
 *   GNU General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 ***************************************************************************/

#ifndef GUM_BIN_SEARCH_TREE_H
#define GUM_BIN_SEARCH_TREE_H

#include <agrum/agrum.h>

#include <agrum/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:
    typedef BinSearchTreeIterator< Val, Cmp, Node > iterator;
    typedef BinSearchTreeIterator< Val, Cmp, Node > const_iterator;

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

    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 const 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/core/binSearchTree_tpl.h>

#endif   // GUM_BIN_SEARCH_TREE_H