FetchBannedIPs/Tree.h

#ifndef __TREE_H
#define __TREE_H

#include <forward_list>

// Tree is both a linked list and a binary tree.
// A linked list is easy to loop through.
// A binary tree is fast to search through.

template <typename T>
class TreeNode
{
	public:
	T *Item;
	TreeNode<T> *Smaller;
	TreeNode<T> *Bigger;
	TreeNode()
	{
		Item = nullptr;
		Smaller = nullptr;
		Bigger = nullptr;
	}
	TreeNode(T *item)
	{
		Item = item;
		Smaller = nullptr;
		Bigger = nullptr;
	}
	~TreeNode()
	{
		if (Item != nullptr) {
			delete Item;
			Item = nullptr;
		}
		if (Smaller != nullptr) {
			delete Smaller;
			Smaller = nullptr;
		}
		if (Bigger != nullptr) {
			delete Bigger;
			Bigger = nullptr;
		}
	}
};

template <typename T>
class Tree
{
	public:	
	TreeNode<T> *SortedList; // This is a binary tree.
	std::forward_list<T*> List;	// All the items in SortedList are also in List.
	
	void Clear()
	{
		while (!List.empty()) {
			List.pop_front(); // The item is not deleted because it's also being stored in the SortedList tree.
		}
		if (SortedList != nullptr) {
			delete SortedList;
			SortedList = nullptr;
		}
	}
	
	// Find a node or the next place it goes. Returns found status in found. 
	TreeNode<T> *Find(T *item,int &found,int (*compareFunction)(T*,T*)) const
	{	
		// If the node was found then found = 0 and the node is returned.
		// If the node was not found then found !=0 and the insert point is returned.
		// If found < 0 then add to ->Bigger.
		// If found > 0 then add to ->Smaller.
		// If the list is empty then found = 0 and nullptr is returned.
		// If found = 0 and nullptr is returned then the node was not found.
		TreeNode<T> *loop;
		TreeNode<T> *next;
		int compare;
		
		compare = 0;
		loop = SortedList;
		if (SortedList != nullptr) {
			while (true) {
				compare = compareFunction(loop->Item,item);
				if (compare < 0) {
					next = loop->Bigger;
					if (next == nullptr) {
						break;
					}
					loop = next;
					continue;
				}
				if (compare > 0) {
					next = loop->Smaller;
					if (next == nullptr) {
						break;
					}
					loop = next;
					continue;
				}
				break;
			}
		}
		found = compare;
		return loop;
	}
	
	// Returns all items in this tree that aren't in the other tree.
	// Assumes that the calling function has logic in place to not search empty lists.
	void Subtract(const Tree<T> &other,std::forward_list<T*> &difference,int (*compareFunction)(T*,T*))
	{
		int found;
		TreeNode<T> *search;	
		for (auto loop = List.begin(); loop != List.end();++loop) {				
			search = other.Find(*loop,found,compareFunction);
			if ((found != 0) && (search != nullptr)) {
				difference.push_front(*loop);
			}
		}
	}

	// Adds an item to this tree. Returns true if successful.
	// Sets *item to nullptr if the item is moved to the tree.
	bool Add(T **item,int (*compareFunction)(T*,T*)) {
		int found;
		TreeNode<T> *search;
		if ((item == nullptr) || (*item == nullptr)) {
			return false;
		}
		if (SortedList == nullptr) {
			SortedList = new TreeNode<T>(*item);
			if (SortedList == nullptr) {
				throw "Out of memory in Tree.Add";
			}
			List.push_front(*item);
			*item = nullptr;
			return true;
		}
		search = Find(*item,found,compareFunction);
		if (found < 0) {
			search->Bigger = new TreeNode<T>(*item);
			if (search->Bigger == nullptr) {
				throw "Out of memory in Tree.Add";
			}
			List.push_front(*item);
			*item = nullptr;
		}
		if (found > 0) {
			search->Smaller = new TreeNode<T>(*item);
			if (search->Smaller == nullptr) {
				throw "Out of memory in Tree.Add";
			}
			List.push_front(*item);
			*item = nullptr;
		}
		return true;
	}
	Tree()
	{
		SortedList = nullptr;
	}
	~Tree()
	{
		Clear();
	}
};

#endif