Personal Knowledge Management
Python 3 tree implementation
Toggle Advanced Options
Tags
Source:
# Python 3 Tree Implementation
#
# Copyright (C) 2011, Brett Alistair Kromkamp - brettkromkamp@gmail.com
# All rights reserved.
#
# Redistribution and use in source and binary forms, with or without modification,
# are permitted provided that the following conditions are met:
#
# Redistributions of source code must retain the above copyright notice, this list
# of conditions and the following disclaimer.
#
# Redistributions in binary form must reproduce the above copyright notice, this
# list of conditions and the following disclaimer in the documentation and/or
# other materials provided with the distribution.
#
# Neither the name of the copyright holder nor the names of the contributors
# may be used to endorse or promote products derived from this software without
# specific prior written permission.
#
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR
# ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
# (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
# LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
# ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
# SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
import unittest
def sanitize_id(id):
return id.strip().replace(" ", "")
#--------------------------------------------------------------------------------
# Test suite
class TestUtilities(unittest.TestCase):
def setUp(self):
self.identifier1 = "i denti fier 1 "
def test_sanitize_id(self):
self.assertEqual(sanitize_id(self.identifier1), "identifier1")
def tearDown(self):
pass
#--------------------------------------------------------------------------------
# Module testing
if __name__ == "__main__":
unittest.main()
#================================================================================
import unittest
import uuid
from utilities import sanitize_id
# Module constants
(_ADD, _DELETE, _INSERT) = range(3)
class Node:
"""Class for basic node functionality."""
def __init__(self, name, identifier=None, expanded=True):
self.__identifier = (str(uuid.uuid1()) if identifier is None else
sanitize_id(str(identifier)))
self.name = name
self.expanded = expanded
self.__bpointer = None
self.__fpointer = []
@property
def identifier(self):
return self.__identifier
@property
def bpointer(self):
return self.__bpointer
@bpointer.setter
def bpointer(self, value):
if value is not None:
self.__bpointer = sanitize_id(value)
@property
def fpointer(self):
return self.__fpointer
def update_fpointer(self, identifier, mode=_ADD):
if mode is _ADD:
self.__fpointer.append(sanitize_id(identifier))
elif mode is _DELETE:
self.__fpointer.remove(sanitize_id(identifier))
elif mode is _INSERT:
self.__fpointer = [sanitize_id(identifier)]
#--------------------------------------------------------------------------------
# Test suite
class TestNode(unittest.TestCase):
def setUp(self):
self.node1 = Node("Test One", "ide ntifier 1 ")
def test_initialization(self):
self.assertEqual(self.node1.name, "Test One")
self.assertEqual(self.node1.identifier, "identifier1")
self.assertEqual(self.node1.expanded, True)
def test_set_fpointer(self):
self.node1.update_fpointer(" identi fier 2")
self.assertEqual(self.node1.fpointer, ['identifier2'])
def test_set_bpointer(self):
self.node1.bpointer = " identi fier 1"
self.assertEqual(self.node1.bpointer, 'identifier1')
def tearDown(self):
pass
#--------------------------------------------------------------------------------
# Module testing
if __name__ == "__main__":
unittest.main()
#================================================================================
import unittest
from node import Node
# Module constants
(_ADD, _DELETE, _INSERT) = range(3)
(_ROOT, _DEPTH, _WIDTH) = range(3)
class Tree:
def __init__(self):
self.nodes = []
def get_index(self, position):
for index, node in enumerate(self.nodes):
if node.identifier == position:
break
return index
def create_node(self, name, identifier=None, parent=None):
"""Create a child node for the node indicated by the 'parent' parameter"""
node = Node(name, identifier)
self.nodes.append(node)
self.__update_fpointer(parent, node.identifier, _ADD)
node.bpointer = parent
return node
def move_node(self, source, destination):
"""
Move a node indicated by the 'source' parameter to the parent node
indicated by the 'dest' parameter
"""
pass
def remove_node(self, identifier):
pass
def show(self, position, level=_ROOT):
queue = self[position].fpointer
if level == _ROOT:
print("{0} [{1}]".format(self[position].name,
self[position].identifier))
else:
print("t"*level, "{0} [{1}]".format(self[position].name,
self[position].identifier))
if self[position].expanded:
level += 1
for element in queue:
self.show(element, level) # recursive call
def expand_tree(self, position, mode=_DEPTH):
# Python generator. Loosly based on an algorithm from 'Essential LISP' by
# John R. Anderson, Albert T. Corbett, and Brian J. Reiser, page 239-241
yield position
queue = self[position].fpointer
while queue:
yield queue[0]
expansion = self[queue[0]].fpointer
if mode is _DEPTH:
queue = expansion + queue[1:] # depth-first
elif mode is _WIDTH:
queue = queue[1:] + expansion # width-first
def is_branch(self, position):
return self[position].fpointer
def __update_fpointer(self, position, identifier, mode):
if position is None:
return
else:
self[position].update_fpointer(identifier, mode)
def __update_bpointer(self, position, identifier):
self[position].bpointer = identifier
def __getitem__(self, key):
return self.nodes[self.get_index(key)]
def __setitem__(self, key, item):
self.nodes[self.get_index(key)] = item
def __len__(self):
return len(self.nodes)
def __contains__(self, identifier):
return [node.identifier for node in self.nodes
if node.identifier is identifier]
#--------------------------------------------------------------------------------
# Test suite
class TestTree(unittest.TestCase):
def setUp(self):
pass
def test_initialization(self):
pass
def tearDown(self):
pass
#--------------------------------------------------------------------------------
# Module testing
if __name__ == "__main__":
# Example usage
tree = Tree()
tree.create_node("Harry", "harry") # root node
tree.create_node("Jane", "jane", parent = "harry")
tree.create_node("Bill", "bill", parent = "harry")
tree.create_node("Joe", "joe", parent = "jane")
tree.create_node("Diane", "diane", parent = "jane")
tree.create_node("George", "george", parent = "diane")
tree.create_node("Mary", "mary", parent = "diane")
tree.create_node("Jill", "jill", parent = "george")
tree.create_node("Carol", "carol", parent = "jill")
tree.create_node("Grace", "grace", parent = "bill")
tree.create_node("Mark", "mark", parent = "jane")
print("="*80)
tree.show("harry")
print("="*80)
for node in tree.expand_tree("harry", mode=_WIDTH):
print(node)
print("="*80)
# Run unit tests
unittest.main()
Output from the example:
================================================================================
Harry [harry]
Jane [jane]
Joe [joe]
Diane [diane]
George [george]
Jill [jill]
Carol [carol]
Mary [mary]
Mark [mark]
Bill [bill]
Grace [grace]
================================================================================
harry
jane
bill
joe
diane
mark
grace
george
mary
jill
carol
================================================================================