treelist.h

/*
 * TreeLinkedList - simple tree structure with lists, simlar to B-tree
 * http://projects.malcom.pl/code/treelist.xhtml
 *
 * Copyright (C) 2009 Marcin 'Malcom' Malich <me@malcom.pl>
 *
 * Released under the MIT License.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 *
 * 2009-03-18 22:00:17
 */

#ifndef _TREE_LINKED_LIST_H_
#define _TREE_LINKED_LIST_H_

template<typename T>
class TreeLinkedListNode {

public:
	typedef TreeLinkedListNode<T>	node_type;
	typedef T						value_type;

	TreeLinkedListNode()
		: m_value(), m_parent(NULL), m_next(NULL), m_children(NULL) {}

	TreeLinkedListNode(const value_type& value, node_type* parent = NULL,
						node_type* next = NULL, node_type* children = NULL)
		: m_value(value), m_parent(parent), m_next(next), m_children(children) {

		if (m_parent)
			m_parent->Append(this);
	}

	virtual ~TreeLinkedListNode() {

		node_type* c = m_children;
		while (c) {
			TreeLinkedListNode* t = c->m_next;
			delete c;
			c = t;
		}

	}


	TreeLinkedListNode(const node_type& node) {
		m_next = NULL;
		m_parent = NULL;
		Copy(node);
	}

	node_type& operator=(const node_type& node) {
		delete m_children;
		Copy(node);
		return *this;
	}


	value_type& GetValue() {
		return m_value;
	}

	void SetValue(value_type& value) {
		m_value = value;
	}


	node_type* GetParent() const {
		return m_parent;
	}

	node_type* GetNext() const {
		return m_next;
	}

	node_type* GetChildren() const {
		return m_children;
	}

	void SetParent(node_type* item) {
		m_parent = item;
	}

	void SetNext(node_type* item) {
		m_next = item;
	}

	void SetChildren(node_type* item) {
		m_children = item;
	}


	bool HasChildren() const {
		return m_children != NULL;
	}


	enum InsertPosition {
		INSERT_BEFORE,
		INSERT_AFTER
	};

	bool Insert(node_type* child, node_type* node, InsertPosition position);

	bool Remove(node_type* child);

	// add a child item to the end of the children's list
	void Append(node_type* child);

	// add a child item to the begin of the children's list
	void Prepend(node_type* child);

private:

	void Copy(const node_type& node);

	node_type* m_parent;
	node_type* m_next;
	node_type* m_children;

	value_type m_value;

};


template<typename T>
class TreeLinkedList {

public:
	typedef TreeLinkedList<T>		list_type;
	typedef TreeLinkedListNode<T>	node_type;
	typedef T						value_type;


	TreeLinkedList(node_type* root = NULL)
		: m_root(root) { }

	virtual ~TreeLinkedList() {
		delete m_root;
	}


	TreeLinkedList(const list_type& list) {
		Copy(list);
	}

	list_type& operator=(const list_type& list) {
		delete m_root;
		Copy(list);
		return *this;
	}


	node_type* GetRoot() const {
		return m_root;
	}

	void SetRoot(node_type* node) {
	//	delete m_root;
		m_root = node;
	}


	bool IsOk() const {
		return m_root != NULL;
	}

private:

	void Copy(const list_type& list) {
		if (list.m_root)
			m_root = new node_type(*list.m_root);
		else
			m_root = NULL;
	}

	node_type* m_root;

};


template<typename T>
void TreeLinkedListNode<T>::Append(node_type* child) {

	if (m_children == NULL) {
		m_children = child;
	} else {
		node_type* c = m_children;
		while (c->m_next)
			c = c->m_next;
		c->m_next = child;
	}

	child->m_next = NULL;
	child->m_parent = this;
}

template<typename T>
void TreeLinkedListNode<T>::Prepend(node_type* child) {

	child->m_next = m_children;
	m_children = child;
	child->m_parent = this;

}

template<typename T>
bool TreeLinkedListNode<T>::Insert(node_type* child, node_type* node, InsertPosition position) {

	switch (position) {
		case INSERT_BEFORE:
		{
			node_type* c = m_children;
			while (c && c->m_next != node)
				c = c->m_next;

			if (!c)
				return false;

			child->m_next = node;
			c->m_next = child;
			break;
		}

		case INSERT_AFTER:
		{
			child->m_next = node->m_next;
			node->m_next = child;
			break;
		}
	}

	child->m_parent = this;
	return true;

}

template<typename T>
bool TreeLinkedListNode<T>::Remove(node_type* child) {

	if (m_children == NULL) {
		return false;

	} else if (m_children == child) {
		m_children = child->m_next;
		child->m_parent = NULL;
		child->m_next = NULL;
		return true;

	} else {
		node_type* c = m_children;
		while (c->m_next) {
			if (c->m_next == child) {
				c->m_next = child->m_next;
				child->m_parent = NULL;
				child->m_next = NULL;
				return true;
			}
			c = c->m_next;
		}
		return false;
	}
}

template<typename T>
void TreeLinkedListNode<T>::Copy(const node_type& node) {
	m_value = node.m_value;

	if (node.m_children) {
		m_children = new node_type(*node.m_children);
		m_children->m_parent = this;

		node_type* n = m_children;
		node_type* c = node.m_children->m_next;

		while (c) {
			n->m_next = new node_type(*c);
			n->m_next->m_parent = this;
			n = n->m_next;
			c = c->m_next;
		}

	} else {
		m_children = NULL;
	}
}

#endif // _TREE_LINKED_LIST_H_