binary_search_tree.hxx

Go to the documentation of this file.

/*===========================================================================================================
 *
 * HUC - Hurna Core
 *
 * Copyright (c) Michael Jeulin-Lagarrigue
 *
 *  Licensed under the MIT License, you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *         https://github.com/Hurna/Hurna-Core/blob/master/LICENSE
 *
 * Unless required by applicable law or agreed to in writing, software distributed under the License is
 * distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and limitations under the License.
 *
 * The above copyright notice and this permission notice shall be included in all copies or
 * substantial portions of the Software.
 *
 *=========================================================================================================*/
#ifndef MODULE_DATA_STRUCTURES_BST_HXX
#define MODULE_DATA_STRUCTURES_BST_HXX

#include <memory>

namespace huc
{
  template <typename IT, typename Compare, typename IsEqual>
  class BST
  {
    typedef typename std::iterator_traits<IT>::value_type Value;
    public:
      static std::unique_ptr<BST> Build(const IT& begin, const IT& end)
      {
        if (begin >= end)
          return  nullptr;

        // Create root node
        auto root = std::unique_ptr<BST>(new BST(*begin));

        // Insert all remaining elements within the tree
        for (auto it = begin + 1; it != end; ++it)
          root->Insert(*it);

        return root;
      }

      static std::unique_ptr<BST> BuildFromSorted(const IT& begin, const IT& end)
      {
        if (begin >= end)
          return nullptr;

        const auto middle = begin + (std::distance(begin,end) / 2);
        auto root = std::unique_ptr<BST>(new BST(*middle));

        // Recursively insert both children
        root->SetLeftChild(std::move(BuildFromSorted(begin, middle)));
        root->SetRightChild(std::move(BuildFromSorted(middle + 1, end)));

        return root;
      }

      const BST* Find(const Value& data)
      {
        // Key found returns node
        if (IsEqual()(this->data, data))
          return this;

        // Key is less than current node - search in left subtree
        if (Compare()(data, this->data))
          return this->leftChild ? this->leftChild->Find(data) : nullptr;

        // Search in right subtree
        return this->rightChild ? this->rightChild->Find(data) : nullptr;
      }

      void Insert(const Value& data)
      {
        // Key is lower or equal than current root - Insert on the left side
        if (Compare()(data, this->data))
        {
          if (!this->leftChild)
            this->SetLeftChild(std::move(std::unique_ptr<BST>(new BST(data))));
          else
            this->leftChild->Insert(data);
        }
        // Key is greater than current root - Insert on the right side
        else
        {
          if (!this->rightChild)
            this->SetRightChild(std::move(std::unique_ptr<BST>(new BST(data))));
          else
            this->rightChild->Insert(data);
        }
      }

      bool IsBlanced() const { return this->MaxHeight() - this->MinHeight() <= 1; }

      bool IsValid() const
      {
        auto previousNode = std::unique_ptr<const BST*>(new const BST*);
        *previousNode = nullptr;
        return this->IsValid(previousNode);
      }

      std::size_t MaxHeight() const
      {
        return 1 + std::max(((this->leftChild) ? this->leftChild->MaxHeight() : 0),
                            ((this->rightChild) ? this->rightChild->MaxHeight() : 0));
      }

      std::size_t MinHeight() const
      {
        return 1 + std::min(((this->leftChild) ? this->leftChild->MinHeight() : 0),
                            ((this->rightChild) ? this->rightChild->MinHeight() : 0));
      }

      static const BST* Remove(std::unique_ptr<BST>& bst, const Value& data)
      {
        // Break on empty unique_ptr
        if (!bst)
          return nullptr;

        // Reach node matching the value
        if (!IsEqual()(bst->data, data))
        {
          if (Compare()(data, bst->data))
            Remove(bst->leftChild, data);
          else
            Remove(bst->rightChild, data);
        }
        // Proceed removal
        else
        {
          // Recursively delete all subnodes containing the same value
          if (bst->leftChild && IsEqual()(bst->data, bst->leftChild->data))
            Remove(bst->leftChild, data);

          // No child - Simply remove node
          if (!bst->leftChild && !bst->rightChild)
            bst.reset();
          // Both children:
          // - Swap node value with its predecessor
          // - Remove predecessor node and replace it with its child
          else if (bst->leftChild && bst->rightChild)
          {
            auto& predecessor = bst->GetPredecessor();
            std::swap(bst->data, predecessor->data);
            predecessor.reset(predecessor->leftChild.release());
          }
          // Left node is unique child - remove node and replace it with its child.
          else if (bst->leftChild)
            bst.reset(bst->leftChild.release());
          // Right node is unique child - remove node and replace it with its child.
          else if (bst->rightChild)
            bst.reset(bst->rightChild.release());
        }

        // Return pointer handled by bst.
        return bst.get();
      }

      std::size_t Size() const
      {
        return 1 + ((this->leftChild) ? this->leftChild->Size() : 0)
                 + ((this->rightChild) ? this->rightChild->Size() : 0);
      }

      Value GetData() const { return this->data; }
      const BST* GetLeftChild() const { return this->leftChild.get(); }
      const BST* GetRightChild() const { return this->rightChild.get(); }

    private:
      BST(const Value& data) : data(data) {}
      BST(BST&) {}           // Not Implemented
      BST operator=(BST&) {} // Not Implemented

      bool IsValid(std::unique_ptr<const BST*>& previousNode) const
      {
        // Recurse on left child without breaking if not failing
        if (this->leftChild &&!this->leftChild->IsValid(previousNode))
          return false;

        // First node retrieve - assign
        if (!*previousNode)
          *previousNode = this;
        // Previous data does not compare well to the current one - BST not valid
        else if (!Compare()((*previousNode)->data, this->data))
          return false;

        // Set current node
        *previousNode = this;

        // Recurse on right child
        if (this->rightChild && !this->rightChild->IsValid(previousNode))
          return false;

        return true;
      }

      std::unique_ptr<BST>& GetPredecessor()
      {
        // Cannot get predecessor if no left child exists
        assert(("GetPredecessor should not be called if no left child exists.", this->leftChild));

        // Left child is the predecessor
        if (!this->leftChild->rightChild)
          return this->leftChild;

        // Return Right Most Child
        return this->leftChild->GetRightMostChild();
      }

      std::unique_ptr<BST>& GetRightMostChild()
      {
        // Cannot get predecessor if no left child exists
        assert(("GetRightMostChild should not be called if no right child exists.", this->rightChild));

        if (this->rightChild && !this->rightChild->rightChild)
          return this->rightChild;

        return this->rightChild->GetRightMostChild();
      }

      void SetLeftChild(std::unique_ptr<BST> bst) { this->leftChild = std::move(bst); }
      void SetRightChild(std::unique_ptr<BST> bst) { this->rightChild = std::move(bst); }

      typename std::iterator_traits<IT>::value_type data;
      std::unique_ptr<BST> leftChild;
      std::unique_ptr<BST> rightChild;
  };
}

#endif // MODULE_DATA_STRUCTURES_BST_HXX