Skip to content

Instantly share code, notes, and snippets.

@malcom malcom/treelist.h
Created Sep 9, 2009

Embed
What would you like to do?
/*
* 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_
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.