Code:
#ifndef BSEARCHTREE_20110923_2257
#define BSEARCHTREE_20110923_2257
#include <utility>
#include <memory>
#include <functional>
#include <stdexcept>
#include <cassert>
namespace NBSearchTree
{
namespace Exceptions
{
class XKeyNotUnique: public std::runtime_error { public: XKeyNotUnique(): std::runtime_error("Key not unique") {} };
class XKeyNotFound: public std::runtime_error { public: XKeyNotFound(): std::runtime_error("Key not found") {} };
}
template<typename Key_t, typename Value_t> class XTree;
template<typename Key_t, typename Value_t>
class XNode
{
public:
friend class XTree<Key_t, Value_t>;
XNode(Key_t Key, Value_t & Value): m_Key(Key), m_Value(Value) {}
void SetValue(const Value_t & Value) { m_Value = Value; }
const Value_t & GetValue() const { return m_Value; }
const Key_t & GetKey() const { return m_Key; }
const std::shared_ptr<XNode> & GetLeft() const { return m_Left; }
const std::shared_ptr<XNode> & GetRight() const { return m_Right; }
protected:
void SetKey(const Key_t & Key) { m_Key = Key; }
std::shared_ptr<XNode> & GetModifiableLeft() { return m_Left; }
std::shared_ptr<XNode> & GetModifiableRight() { return m_Right; }
Key_t m_Key;
Value_t m_Value;
std::shared_ptr<XNode> m_Left, m_Right;
};
template<typename Key_t, typename Value_t>
class XTree
{
public:
typedef XNode<Key_t, Value_t> Node_t;
typedef std::shared_ptr<Node_t> NodePtr_t;
typedef std::shared_ptr<const Node_t> ConstNodePtr_t;
void Insert(const Key_t & Key, Value_t Value)
{
if (!m_Root)
{
m_Root = std::make_shared<Node_t>(Key, Value);
return;
}
Insert(m_Root, Key, Value);
}
ConstNodePtr_t Find(const Key_t & Key) const
{
std::pair<ConstNodePtr_t, ConstNodePtr_t> Result;
if (!Find(Key, m_Root, Result))
throw Exceptions::XKeyNotFound();
return Result.first;
}
bool Delete(const Key_t & Key)
{
std::pair<NodePtr_t, NodePtr_t> Result;
if (!Find(Key, m_Root, Result))
return false;
Delete(Key, Result);
return true;
}
NodePtr_t GetRoot() const { return m_Root; }
protected:
void Delete(const Key_t & Key, const std::pair<NodePtr_t, NodePtr_t> KeyPair)
{
auto pair = KeyPair;
auto parent = pair.second;
auto to_delete = pair.first;
if (to_delete->m_Left && to_delete->m_Right)
{
auto successor = to_delete->m_Right;
auto successor_parent = to_delete;
while (successor->m_Left)
{
successor_parent = successor;
successor = successor->m_Left;
}
auto successor_key = successor->GetKey();
Delete(successor->m_Key, std::make_pair(successor, successor_parent));
to_delete->SetKey(successor_key);
}
else
{
NodePtr_t * NodeToModify;
if (parent)
{
assert( ((Key < parent->GetKey()) && !(parent->GetKey() < Key)) ||
((parent->GetKey() < Key) && !(Key < parent->GetKey())) );
if ( Key < parent->GetKey() ) NodeToModify = &parent->GetModifiableLeft();
else NodeToModify = &parent->GetModifiableRight();
}
else
NodeToModify = &m_Root; // Special case: deleting root
if (!to_delete->m_Left)
{
if (/*!ToDelete->m_Left && */!to_delete->m_Right)
*NodeToModify = nullptr;
else if (/*!ToDelete->m_Left && */to_delete->m_Right)
*NodeToModify = to_delete->m_Right;
}
else if (/*ToDelete->m_Left && */!to_delete->m_Right)
*NodeToModify = to_delete->m_Left;
}
}
void Insert(NodePtr_t & InsertAt, const Key_t & Key, Value_t & Value)
{
NodePtr_t * InsertAt_ = nullptr;
if (Key < InsertAt->m_Key)
InsertAt_ = &InsertAt->m_Left;
else
{
if ( Key == InsertAt->m_Key ) throw Exceptions::XKeyNotUnique();
InsertAt_ = &InsertAt->m_Right;
}
if (*InsertAt_)
{
Insert(*InsertAt_, Key, Value);
return;
}
*InsertAt_ = std::make_shared<Node_t>(Key, Value);
}
bool Find(const Key_t & Key, const NodePtr_t & NodeToSearch, std::pair<ConstNodePtr_t, ConstNodePtr_t> & Result) const
{
NodePtr_t tmp;
return Find(Key, NodeToSearch, tmp, Result);
}
bool Find(const Key_t & Key, NodePtr_t & NodeToSearch, std::pair<NodePtr_t, NodePtr_t> & Result)
{
NodePtr_t tmp;
return Find(Key, NodeToSearch, tmp, Result);
}
bool Find(const Key_t & Key, const NodePtr_t & NodeToSearch, const NodePtr_t & PrevNode, std::pair<ConstNodePtr_t, ConstNodePtr_t> & Result) const
{
if (Key == NodeToSearch->m_Key)
{
Result = std::make_pair(NodeToSearch, PrevNode);
return true;
}
else if (NodeToSearch->m_Left && Key < NodeToSearch->m_Key)
return Find(Key, NodeToSearch->m_Left, NodeToSearch, Result);
else if (NodeToSearch->m_Right/* && Key > NodeToSearch->m_Key*/)
return Find(Key, NodeToSearch->m_Right, NodeToSearch, Result);
return false;
}
bool Find(const Key_t & Key, NodePtr_t & NodeToSearch, NodePtr_t & PrevNode, std::pair<NodePtr_t, NodePtr_t> & Result) const
{
if (Key == NodeToSearch->m_Key)
{
Result = std::make_pair(NodeToSearch, PrevNode);
return true;
}
else if (NodeToSearch->m_Left && Key < NodeToSearch->m_Key)
return Find(Key, NodeToSearch->m_Left, NodeToSearch, Result);
else if (NodeToSearch->m_Right/* && Key > NodeToSearch->m_Key*/)
return Find(Key, NodeToSearch->m_Right, NodeToSearch, Result);
return false;
}
NodePtr_t m_Root;
};
}
#endif
Cameau still makes no sense whatsoever, however.