Thread: Binary Search Tree - Peer Review (Part 1)

  1. #1
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654

    Binary Search Tree - Peer Review (Part 1)

    So, I've made a minimalistic binary search tree data structure, not for practical reasons, but for experience and ... for a better grade, shall we say?
    Anyway, this being a forum of experts and all, I wanted to hear your opinions on the code, if any. Criticism is sincerely welcome.

    I know the interface isn't truly consistent, and that's bad, but eh... I figure it doesn't matter so much for a minimalistic implementation. This is just to get a working search tree.

    The code is about 156 lines long, so sit down, grab some beer or coffee and have fun looking at it!

    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 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;
    
    		XTree(): m_TreeSize(0) {}
    
    		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);
    		}
    
    		NodePtr_t Find(const Key_t & Key) const { return Find(Key, m_Root).first; }
    
    		bool Delete(const Key_t & Key)
    		{
    			try
    			{
    				NodePtr_t tmp;
    				Delete( Key, Find(Key, m_Root, tmp) );
    				return true;
    			}
    			catch (const Exceptions::XKeyNotFound&) { return false; }
    		}
    
    		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
    			{
    				if (parent)
    				{
    					if ( Key < parent->GetKey() ) DeleteHelper(to_delete, parent->GetModifiableLeft());
    					else if ( Key > parent->GetKey() ) DeleteHelper(to_delete, parent->GetModifiableRight());
    				}
    				else
    				{
    					// Special case: deleting root
    					DeleteHelper(to_delete, m_Root);
    				}
    			}
    		}
    
    		void DeleteHelper(NodePtr_t & ToDelete, NodePtr_t & NodeToModify)
    		{
    			if (!ToDelete->m_Left && !ToDelete->m_Right)
    				NodeToModify = nullptr;
    			else if (ToDelete->m_Left && !ToDelete->m_Right)
    				NodeToModify = ToDelete->m_Left;
    			else if (!ToDelete->m_Left && ToDelete->m_Right)
    				NodeToModify = ToDelete->m_Right;
    		}
    
    		// Returns true if item was inserted
    		bool Insert(NodePtr_t & InsertAt, const Key_t & Key, Value_t & Value)
    		{
    			if ( Key == InsertAt->m_Key ) throw Exceptions::XKeyNotUnique();
    			if ( InsertHelper(InsertAt->m_Left, Key, InsertAt->m_Key, Value, std::less<Key_t>()) ) return true;
    			if ( InsertHelper(InsertAt->m_Right, Key, InsertAt->m_Key, Value, std::greater<Key_t>()) ) return true;
    			return false;
    		}
    
    		// Returns true if item was inserted
    		template<typename Comparison_t>
    		bool InsertHelper(NodePtr_t & InsertAt, const Key_t & Key, const Value_t & NodeKey, Value_t & Value, Comparison_t Comparator)
    		{
    			if (Comparator(Key, NodeKey))
    			{
    				if (InsertAt)
    					return Insert(InsertAt, Key, Value);
    				InsertAt = std::make_shared<Node_t>(Key, Value);
    				return true;
    			}
    			return false;
    		}
    
    		std::pair<NodePtr_t, NodePtr_t> Find(const Key_t & Key, NodePtr_t & NodeToSearch, NodePtr_t & PrevNode)
    		{
    			if (!NodeToSearch) throw Exceptions::XKeyNotFound();
    			if (Key == NodeToSearch->m_Key)
    				return std::make_pair(NodeToSearch, PrevNode);
    			else if (Key < NodeToSearch->m_Key)
    				return Find(Key, NodeToSearch->m_Left, NodeToSearch);
    			else if (Key > NodeToSearch->m_Key)
    				return Find(Key, NodeToSearch->m_Right, NodeToSearch);
    			assert(false);
    			throw std::runtime_error("Unknown internal error"); // Silence compiler warnings
    		}
    
    		NodePtr_t m_Root;
    	};
    }
    
    #endif
    Last edited by Elysia; 09-24-2011 at 02:47 AM.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    Criticism is sincerely welcome.
    Have you written test cases to make sure that it works?
    My best code is written with the delete key.

  3. #3
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    I did, but seemingly there were bugs in the testing code. Thank goodness for peer reviews, or I would likely have been burned when I tried to use it.
    Updated first post with new code that fixes the delete regression.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    I tend to do this:
    Code:
    		void DeleteHelper(NodePtr_t & ToDelete, NodePtr_t & NodeToModify)
    		{
    			if (!ToDelete->m_Left)
    			{
    				if (!ToDelete->m_Right)
    					NodeToModify = nullptr;
    				else
    					NodeToModify = ToDelete->m_Right;
    			}
    			else if (!ToDelete->m_Right)
    			{
    				NodeToModify = ToDelete->m_Left;
    			}
    		}
    I also reduce the number of operator overloads that would be required to use the code by swapping a greater-than around to be a less-than.

    I'm not sure I'd have that InsertHelper function myself. The logic of it is a bit strange.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by iMalc View Post
    I tend to do this:
    Factoring out common cases, huh? I like that kind of thinking!

    I also reduce the number of operator overloads that would be required to use the code by swapping a greater-than around to be a less-than.
    Definitely a must have. Great advice, something I tend to neglect.

    I'm not sure I'd have that InsertHelper function myself. The logic of it is a bit strange.
    Well, I was factoring out common code there. But thinking about it some more, I was able to eliminate it without much trouble.

    I updated the code:
    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 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;
    
    		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);
    		}
    
    		NodePtr_t Find(const Key_t & Key) const { return Find(Key, m_Root).first; }
    
    		bool Delete(const Key_t & Key)
    		{
    			try
    			{
    				NodePtr_t tmp;
    				Delete( Key, Find(Key, m_Root, tmp) );
    				return true;
    			}
    			catch (const Exceptions::XKeyNotFound&) { return false; }
    		}
    
    		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
    			{
    				if (parent)
    				{
    					if ( Key < parent->GetKey() ) DeleteHelper(to_delete, parent->GetModifiableLeft());
    					else if ( Key > parent->GetKey() ) DeleteHelper(to_delete, parent->GetModifiableRight());
    				}
    				else
    				{
    					// Special case: deleting root
    					DeleteHelper(to_delete, m_Root);
    				}
    			}
    		}
    
    		void DeleteHelper(NodePtr_t & ToDelete, NodePtr_t & NodeToModify)
    		{
    			if (!ToDelete->m_Left)
    			{
    				if (/*!ToDelete->m_Left && */!ToDelete->m_Right)
    					NodeToModify = nullptr;
    				else if (/*!ToDelete->m_Left && */ToDelete->m_Right)
    					NodeToModify = ToDelete->m_Right;
    			}
    			else if (/*ToDelete->m_Left && */!ToDelete->m_Right)
    				NodeToModify = ToDelete->m_Left;
    		}
    
    		void Insert(NodePtr_t & InsertAt, const Key_t & Key, Value_t & Value)
    		{
    			static std::less<Key_t> Comparator;
    			NodePtr_t * InsertAt_ = nullptr;
    
    			if ( Comparator(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);
    		}
    
    		std::pair<NodePtr_t, NodePtr_t> Find(const Key_t & Key, NodePtr_t & NodeToSearch, NodePtr_t & PrevNode)
    		{
    			if (!NodeToSearch) throw Exceptions::XKeyNotFound();
    			if (Key == NodeToSearch->m_Key)
    				return std::make_pair(NodeToSearch, PrevNode);
    			else if (Key < NodeToSearch->m_Key)
    				return Find(Key, NodeToSearch->m_Left, NodeToSearch);
    			else //if (Key > NodeToSearch->m_Key)
    				return Find(Key, NodeToSearch->m_Right, NodeToSearch);
    			assert(false);
    			throw std::runtime_error("Unknown internal error");
    		}
    
    		NodePtr_t m_Root;
    	};
    }
    
    #endif
    Interesting note: The comparator line is now the biggest bottleneck in the insert function--and also one line that cannot be removed or optimized (actually, it's the jnz branching instruction that is the bottleneck, so good luck optimization that).
    That leaves us with a code of 163 lines.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  6. #6
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    [Edit]
    Ah, the newer source is better.
    [/Edit]

    Code:
    std::shared_ptr<XNode> m_Left, m_Right;
    // ...
    NodePtr_t m_Root;
    Even though a BST isn't circular, this still bothers me.

    And yea, I know what you are shooting for.

    Code:
    		bool Insert(NodePtr_t & InsertAt, const Key_t & Key, Value_t & Value)
    		{
    			if ( Key == InsertAt->m_Key ) throw Exceptions::XKeyNotUnique();
    			if ( InsertHelper(InsertAt->m_Left, Key, InsertAt->m_Key, Value, std::less<Key_t>()) ) return true;
    			if ( InsertHelper(InsertAt->m_Right, Key, InsertAt->m_Key, Value, std::greater<Key_t>()) ) return true;
    			return false;
    		}
    
    		// Returns true if item was inserted
    		template<typename Comparison_t>
    		bool InsertHelper(NodePtr_t & InsertAt, const Key_t & Key, const Value_t & NodeKey, Value_t & Value, Comparison_t Comparator)
    		{
    			if (Comparator(Key, NodeKey))
    			{
    				if (InsertAt)
    					return Insert(InsertAt, Key, Value);
    				InsertAt = std::make_shared<Node_t>(Key, Value);
    				return true;
    			}
    			return false;
    		}
    I have to echo iMalc about this; the mutual recursion is a little weird.

    Also, with a modification to the way your search routine works, you could just use that to figure out where to stick a new node and reduce the stack requirements for any given depth.

    Code:
    		std::pair<NodePtr_t, NodePtr_t> Find(const Key_t & Key, NodePtr_t & NodeToSearch, NodePtr_t & PrevNode)
    		{
    			if (!NodeToSearch) throw Exceptions::XKeyNotFound();
    			if (Key == NodeToSearch->m_Key)
    				return std::make_pair(NodeToSearch, PrevNode);
    			else if (Key < NodeToSearch->m_Key)
    				return Find(Key, NodeToSearch->m_Left, NodeToSearch);
    			else if (Key > NodeToSearch->m_Key)
    				return Find(Key, NodeToSearch->m_Right, NodeToSearch);
    			assert(false);
    			throw std::runtime_error("Unknown internal error"); // Silence compiler warnings
    		}
    O_o

    Call me silly, but your logic is bugging the crap out of me.

    If you've built your tree using strictly, using "less than" operations, you don't need the kind of checks you have in your searching function.

    Consider, you have a tree that is strictly "less than" arranged. (If a node is greater than the "left branch" value, the value is either along the right path or doesn't exist.) Such a strict tree doesn't need a branching operation for "greater than" because a single additional function call will find the target case or stop recursion naturally. Finally, branching left or right when those directions do not exist is technically a violation of the expected contract. (It doesn't matter here, but it would get you into trouble with some big contracts.)

    This function should be a wrapper; this class needs a search routine that doesn't "throw" by default. With that small change, you have a cleaner interface and still provide a way for "succeed or roll back" style operations. As a consequence, internal operations that depend on this function do not need to trash the exception mechanism.

    Oddly, it is possible to construct a tree intentionally to break this function. (You'd have to use a class specifically designed to do this as the key type.) If you get to the end of a branch without finding a tree, an exception is raised; if you get along a branch with a median value, the program crashes. ([Edit]I'm assuming a given behavior for `terminate'; some good ones exist so it may at least crash gracefully.[/Edit]) This isn't just inconsistent; it is simply wrong.

    Soma
    Last edited by phantomotap; 09-24-2011 at 04:15 PM.

  7. #7
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by phantomotap View Post
    I have to echo iMalc about this; the mutual recursion is a little weird.

    Also, with a modification to the way your search routine works, you could just use that to figure out where to stick a new node and reduce the stack requirements for any given depth.
    Well, to be honest, I was gunning for the compiler to inline in, seeing as it didn't recursively call itself. I tried adding "__forceinline" in the beginning to see if the compiler would inline it, and it did so without complaints. I didn't actually check the assembly when I removed that keyword, though.
    No matter though, since it's gone now.

    O_o

    Call me silly, but your logic is bugging the crap out of me.

    If you've built your tree using strictly, using "less than" operations, you don't need the kind of checks you have in your searching function.

    Consider, you have a tree that is strictly "less than" arranged. (If a node is greater than the "left branch" value, the value is either along the right path or doesn't exist.) Such a strict tree doesn't need a branching operation for "greater than" because a single additional function call will find the target case or stop recursion naturally. Finally, branching left or right when those directions do not exist is technically a violation of the expected contract. (It doesn't matter here, but it would get you into trouble with some big contracts.)
    I assume the source (below) is better in this regard? If we haven't found a match and it isn't along the left branch, we must search the right branch.
    This may be a twist of logic, but I do check to see that the node we're examining isn't null. So if the left branch is null, when we recursively call ourself, the if (!node) check will succeed and the function will fail.

    Oddly, it is possible to construct a tree intentionally to break this function. (You'd have to use a class specifically designed to do this as the key type.) If you get to the end of a branch without finding a tree, an exception is raised; if you get along a branch with a median value, the program crashes. ([Edit]I'm assuming a given behavior for `terminate'; some good ones exist so it may at least crash gracefully.[/Edit]) This isn't just inconsistent; it is simply wrong.
    I assume you have some specific case in mind that will crash it?

    New code:
    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 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;
    
    		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);
    		}
    
    		NodePtr_t Find(const Key_t & Key) const
    		{
    			std::pair<NodePtr_t, NodePtr_t> Result;
    			if (!Find(Key, m_Root, Result))
    				throw Exceptions::XKeyNotFound();
    			return Result.first;
    		}
    
    		bool Delete(const Key_t & Key)
    		{
    			NodePtr_t tmp;
    			std::pair<NodePtr_t, NodePtr_t> Result;
    			if (!Find(Key, m_Root, tmp, 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)
    				{
    					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, NodePtr_t & NodeToSearch, NodePtr_t & PrevNode, std::pair<NodePtr_t, NodePtr_t> & Result)
    		{
    			if (!NodeToSearch) return false;
    			if (Key == NodeToSearch->m_Key)
    			{
    				Result = std::make_pair(NodeToSearch, PrevNode);
    				return true;
    			}
    			else if (Key < NodeToSearch->m_Key)
    				return Find(Key, NodeToSearch->m_Left, NodeToSearch, Result);
    			else //if (Key > NodeToSearch->m_Key)
    				return Find(Key, NodeToSearch->m_Right, NodeToSearch, Result);
    			assert(false);
    			throw std::runtime_error("Unknown internal error");
    		}
    
    		NodePtr_t m_Root;
    	};
    }
    
    #endif
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  8. #8
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    I assume you have some specific case in mind that will crash it?
    Of course, but I'd have to set out to break it.

    It doesn't much matter though because it wouldn't work on the new version.

    That said, now that the last case is always executed, the lines that exist only to pacify compiler should be removed. (Any reasonable compiler will not complain because the "else" case always returns.)

    I assume the source (below) is better in this regard?
    Well, you do need to fix the code, working source is always a plus, and replace the non-standard C++ fixtures, the bits that are "Visual C++" specific, with proper fixtures, but the new source is better in this regard, but lets take a last look at that `Find' function.

    Code:
    		bool Find(const Key_t & Key, NodePtr_t & NodeToSearch, NodePtr_t & PrevNode, std::pair<NodePtr_t, NodePtr_t> & Result)
    		{
    			if (!NodeToSearch) return false;
    			if (Key == NodeToSearch->m_Key)
    			{
    				Result = std::make_pair(NodeToSearch, PrevNode);
    				return true;
    			}
    			else if (Key < NodeToSearch->m_Key)
    				return Find(Key, NodeToSearch->m_Left, NodeToSearch, Result);
    			else //if (Key > NodeToSearch->m_Key)
    				return Find(Key, NodeToSearch->m_Right, NodeToSearch, Result);
    			assert(false);
    			throw std::runtime_error("Unknown internal error");
    		}
    Now, that first test, the one for null, always executes, but it is only necessary because you've intentionally called the function with null multiple times.

    I was saying that it should be written so that these calls are never made.

    Soma

    Code:
    		bool Find(const Key_t & Key, NodePtr_t & NodeToSearch, NodePtr_t & PrevNode, std::pair<NodePtr_t, NodePtr_t> & Result)
    		{
    			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)
    				return Find(Key, NodeToSearch->m_Right, NodeToSearch, Result);
    			return(false);
    		}

  9. #9
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    If there are any extensions you can glance (gleem?) from the code, I would love to fix those. Using two compilers is a pain.
    I fixed the Find function as per your suggestion.

    Comeau output makes no sense. Moo!
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  10. #10
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    Using two compilers is a pain.
    I got three phrases for you: "compiler driver", "benchmark profile", and "testbed suite".

    I use five; everything I build for public or personal consumption has to get through a lot. I only ever interact directly with my IDE which in turn interacts with GNU "make" which in turn interacts with the compiler driver.

    The thing that jumped out, which caused me to assume that there were more, is the following bit of code.

    Code:
    friend XTree<Key_t, Value_t>;
    What is this? What is `XTree' during the parsing phase at that point in the file?

    Beyond this, everything else I found are really programming or logic errors that will not compile anywhere. I'll leave you to fix those.

    Soma

  11. #11
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by phantomotap View Post
    I got three phrases for you: "compiler driver", "benchmark profile", and "testbed suite".

    I use five; everything I build for public or personal consumption has to get through a lot. I only ever interact directly with my IDE which in turn interacts with GNU "make" which in turn interacts with the compiler driver.
    Obviously, this is good advice, but it's just generally too annoying to have to do that all the time, unless it could be automated. But I have no desire to either search for such an automation nor make one. Ugh.

    The thing that jumped out, which caused me to assume that there were more, is the following bit of code.

    Code:
    friend XTree<Key_t, Value_t>;
    What is this? What is `XTree' during the parsing phase at that point in the file?
    Well, I'm going to guess that it's an unknown template class (we have only the forward declaration at this point).
    Aside from that... no idea.

    Beyond this, everything else I found are really programming or logic errors that will not compile anywhere. I'll leave you to fix those.
    But the code does compile, or I would have fixed them, so finding them isn't exactly trivial.
    It's fine if you don't want to name them due to reasons of your own, but won't compile anywhere is a bit of an understatement, I think.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  12. #12
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    Well, I'm going to guess that it's an unknown template class (we have only the forward declaration at this point).
    Correct. Now look up the correct way to declare a class a friend.

    But the code does compile
    No. It doesn't. Not really.

    The code seems to compile without use because it is a template and the offenses are derived from dependent types.

    Code up a driver calling every function at least once.

    or I would have fixed them
    Yes; that's why I assumed that you didn't really know about them yet.

    so finding them isn't exactly trivial.
    It really is; if your compiler doesn't have a "compile all templates" option; a complete driver is always necessary for developing generic mechanisms.

    Soma

  13. #13
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Issue stacked upon issue, huh? I have to learn all these quirks one day. But it's probably going to take a long time.
    Meh. I'll be back when I've ironed out these issues.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  14. #14
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    I only use two compilers for code I make publicly available myself. Now five, that's impressive!
    I remember being shocked to discover how visual studio would happily ignore template code that could never compile.

    As for whether the Find function has redundant test or not, I would go the approach of std::set in Visual Studio's implementation. IN debug mode it adds extra code to try and catch a less-than operator that doesn't obey strict weak ordering. But in release mode the check is not done.
    First make sure that the additional check will help to catch that kind of bug, and then just make sure it's only done in debug build.
    Things that would break strict weak ordering would be:
    Code:
    friend operator <(const myType1 &a, const myType1 &b)
    {
        return !(a.member < b.member); // can't simply negate like this
    }
    friend operator <(const myType2 &a, const myType2 &b)
    {
        return a.foo < b.foo || a.bar < b.bar; // not how you order multiple members
    }
    friend operator <(const myType3 &a, const myType3 &b)
    {
        return (rand() & 1) != 0; // intentionally break it
    }
    friend operator <(const myType3 &a, const myType3 &b)
    {
        return false;
    }
    Most of these can make a<b and b<a both return true for certain items a and b. The last one however is not something that you can catch. It will just make all items appear equal.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  15. #15
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Long time since I last worked on this, but ah well.
    I've taken care of the issues mentioned, I believe.
    The code now compiles with a forced template instantiation. I've fixed const issues, and added a debug check for broken < operators.
    Only problem is that I couldn't find a way to merge the find functions. If anyone has an idea on how to do that, please do tell.
    New code:

    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.

    Code:
    "ComeauTest.c", line 30: error: qualified name is not allowed
      		const std::shared_ptr<XNode> & GetLeft() const { return m_Left; }
      		      ^
    I am quite unsure why it thinks qualified names are not allowed.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  2. Request for peer review
    By ruthgrin in forum C++ Programming
    Replies: 13
    Last Post: 01-26-2006, 10:03 PM
  3. A Binary Search Tree of... Binary Search Trees...
    By SlyMaelstrom in forum C++ Programming
    Replies: 5
    Last Post: 12-10-2005, 02:12 PM
  4. Search Engine - Binary Search Tree
    By Gecko2099 in forum C Programming
    Replies: 9
    Last Post: 04-17-2005, 02:56 PM
  5. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM