bnode.py

'''\
Python Binary Tree Node class.

classes:
    bnode (object)

usage:
    Create a binary tree from a list of data:
        b_tree = bnode.create_btree(data)

    Create a new binary node instance:
        b_node = bnode(name, [value, [lt, rt]])

NOTE: This is a totally silly class! Python's native containers provide quick access
and lots of flexibility, so there's no real reason to use a binary tree (seeing as
how the main feature of a b-tree is quick access to elements and trivial sorting).
I wrote this more for fun and as a nod to my distant origins writing building block
code in far less expressive (yet mightly in their own right) languages.

Developer@Sonnack.com
April 2010
'''
####################################################################################################
from __future__ import print_function
from sys import stdout, stderr, argv
from logger import logger, info, debug, trace
####################################################################################################
Log = logger('bnode')


##~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~##
class bnode (object):
    '''\
Binary Tree Node Class.

properties:
    nid                     - Node ID
    name                    - Node Name
    value                   - Node Value
    left                    - Left Link
    right                   - Right Link

methods:
    bn()                    - returns node's value
    str(bn)                 - returns node's name
    len(bn)                 - number of nodes in tree (always at least 1)
    bn1 oper bn2            - operations: <, <=, ==, !=, >=, >
    bn[0|1]                 - indexed link access: [0] left; [1] right
    repr(bn)                - returns JSON-like string
    bool(bn)                - always true

    print_tree  (fp)        - print tree to a stream

    find_node   (name)      - returns bnode if found
    find_value  (value)     - returns bnode if found

    travel      (cbftn)     - travel tree; exit if cbftn returns non-zero
    travel_pre  (cbftn)     - travel tree; exit if cbftn returns non-zero
    travel_post (cbftn)     - travel tree; exit if cbftn returns non-zero

    insert      (bnode)     - insert new node into the tree

    insert_left_left    (bnode)
    insert_left_right   (bnode)
    insert_right_left   (bnode)
    insert_right_right  (bnode)

    delete_left_left    (bnode)
    delete_left_right   (bnode)
    delete_right_left   (bnode)
    delete_right_right  (bnode)

    remove_all_left     ()
    remove_all_right    ()
    remove_nodes        (bnode)

'''
    @classmethod
    def create_btree (cls, data):
        '''Return a new btree containing the passed data.'''
        datum = data[0]
        rest = data[1:]
        root = cls(datum[0], datum[1])
        Log.trace('root: %s' % root)
        for datum in rest:
            node = cls(datum[0], datum[1])
            root.insert(node)
            Log.trace()
        return root

    @classmethod
    def SN (cls):
        '''Serial Number global method.'''
        cls.__sn += 1
        return cls.__sn
    __sn = 1000

    def __init__ (self, name, value=None, lt=None, rt=None):
        '''New bnode instance.'''
        self.nid = bnode.SN()
        self.name = name
        self.value = value
        self.left = lt
        self.right = rt
        Log.trace('bnode::new: %s=%s' % (name,value))

    def insert (self, node):
        '''Insert a new node in the tree. (RECURSIVE!)'''
        Log.trace('bnode[%s]::insert: %s' % (self.name,node.name))
        # !!!!!Node Names must implement the __lt__() method!!!!!!
        diff = ((self.name < node.name) - (node.name < self.name))
        Log.trace('bnode[%s]::insert[%s]: diff=%+d' % (self.name,node.name,diff))
        # If name matches this node, don't insert; just return this node...
        if diff == 0:
            Log.trace('bnode[%s]::insert[%s]: EXISTS' % (self.name,node.name))
            return
        # If name is "less-than" this node, insert it down the left branch...
        if diff < 0:
            # Left branch exists, so insert new node into it...
            if self.left:
                Log.trace('bnode[%s]::insert[%s]: Left Branch...' % (self.name,node.name))
                self.left.insert(node)
                return
            # No left node, yet, so just link the new one...
            Log.trace('bnode[%s]::insert[%s]: LEFT' % (self.name,node.name))
            self.left = node
            return
        # If name is "greater-than" this node, insert it down the right branch...
        if 0 < diff:
            # Right branch exists, so insert new node into it...
            if self.right:
                Log.trace('bnode[%s]::insert[%s]: Right Branch...' % (self.name,node.name))
                self.right.insert(node)
                return
            # No right node, yet, so just link the new one...
            Log.trace('bnode[%s]::insert[%s]: RIGHT' % (self.name,node.name))
            self.right = node
            return
        # Code flow should *never* get here...
        raise RuntimeError('bnode:Insert failed in a supposedly impossible way!')

    def find_node (self, name):
        '''Find a node (by its name). Return node if found, else None.'''
        if self.name == name: return self
        if name < self.name:
            if self.left:
                return self.left.find_node(name)
        if self.name < n:
            if self.right:
                return self.right.find_node(name)
        return None

    def find_value (self, value):
        '''Find a node by its value. Return node if found, else None.'''
        # Return ourself if we match...
        if self.value == value: return self
        if self.left:
            x = self.left.find_value(value)
            if x: return x
        if self.right:
            x = self.right.find_value(value)
            if x: return x
        return None

    def travel (self, callback, level=0):
        '''Travel tree (from this node); invoke callback on each node. Exit if CB returns non-zero.'''
        if self.left:
            b = self.left.travel(callback, level=level+1)
            if b: return b
        b = callback(self, level)
        if b: return b
        if self.right:
            b = self.right.travel(callback, level=level+1)
            if b: return b
        return None

    def travel_pre (self, callback, level=0):
        '''Travel tree (pre-fix); invoke callback function on each node. Exit if CB returns non-zero.'''
        b = callback(self, level)
        if b: return b
        if self.left:
            b = self.left.travel_pre(callback, level=level+1)
            if b: return b
        if self.right:
            b = self.right.travel_pre(callback, level=level+1)
            if b: return b
        return None

    def travel_post (self, callback, level=0):
        '''Travel tree (post-fix); invoke callback function on each node. Exit if CB returns non-zero.'''
        if self.left:
            b = self.left.travel_post(callback, level=level+1)
            if b: return b
        if self.right:
            b = self.right.travel_post(callback, level=level+1)
            if b: return b
        b = callback(self, level)
        if b: return b
        return None

    def insert_left_left (self, other):
        '''SPCL: Insert new left node; move current left node to left of inserted node.'''
        temp = self.left
        self.left = other
        other.left = temp
        return self
        
    def insert_left_right (self, other):
        '''SPCL: Insert new left node; move current left node to right of inserted node.'''
        temp = self.left
        self.left = other
        other.right = temp
        return self

    def insert_right_left (self, other):
        '''SPCL: Insert new right node; move current right node to left of inserted node.'''
        temp = self.right
        self.right = other
        other.left = temp
        return self
        
    def insert_right_right (self, other):
        '''SPCL: Insert new right node; move current right node to right of inserted node.'''
        temp = self.right
        self.right = other
        other.right = temp
        return self

    def delete_left_left (self):
        '''Remove left node; link its left node in place; insert its right node in new left node.'''
        if not self.left: return
        nd = self.left
        if not nd.left:
            if not nd.right:
                # Left node had no children, so just delete it and we're done...
                self.left = None
                return
            # Left node has no left branch, so use the right one instead...
            self.left = nd.right
            return
        # Left node's left node is the new left node...
        self.left = nd.left
        # Insert the deleted node's right node into the new left node...
        if nd.right:
            self.left.insert(nd.right)

    def delete_left_right (self):
        '''Remove left node; link its right node in place; insert its left node in new left node.'''
        if not self.left: return
        nd = self.left
        if not nd.right:
            if not nd.left:
                # Left node had no children, so just delete it and we're done...
                self.left = None
                return
            # Left node has no right branch, so use the left one instead...
            self.left = nd.left
            return
        # Left node's right node is the new left node...
        self.left = nd.right
        # Insert the deleted node's left node into the new left node...
        if nd.left:
            self.left.insert(nd.left)

    def delete_right_left (self):
        '''Remove right node; link its left node in place; insert its right node in new right node.'''
        if not self.right: return
        nd = self.right
        if not nd.left:
            if not nd.right:
                # Right node had no children, so just delete it and we're done...
                self.right = None
                return
            # Right node has no left branch, so use the right one instead...
            self.right = nd.right
            return
        # Right node's left node is the new right node...
        self.right = nd.left
        # Insert the deleted node's right node into the new right node...
        if nd.right:
            self.right.insert(nd.right)

    def delete_right_right (self):
        '''Remove right node; link its right node in place; insert its left node in new right node.'''
        if not self.right: return
        nd = self.right
        if not nd.right:
            if not nd.left:
                # Right node had no children, so just delete it and we're done...
                self.right = None
                return
            # Right node has no right branch, so use the left one instead...
            self.right = nd.left
            return
        # Right node's right node is the new right node...
        self.right = nd.right
        # Insert the deleted node's left node into the new right node...
        if nd.left:
            self.right.insert(nd.left)

    def remove_all_left (self):
        '''Remove the nodes (if any, but presumably) on the left.'''
        if not self.left: return
        self.__remove_nodes(self.left)
        self.left = None

    def remove_all_right (self):
        '''Remove the nodes (if any, but presumably) on the right.'''
        if not self.right: return
        self.__remove_nodes(self.right)
        self.right = None

    def __remove_nodes (self, node):
        '''Remove all nodes below given node (RECURSIVE).'''
        Log.trace('bnode[%s]::remove-nodes: %s' % (self.name,node.name))
        if node.left:
            node.__remove_nodes(node.left)
            node.left = None
        if node.right:
            node.__remove_nodes(node.right)
            node.right = None

    def print_tree (self, fp=stdout):
        '''Print the tree from this node down.'''
        print('B-Tree Contents:', file=fp)
        print('================', file=fp)
        self.__print_tree(fp=fp)
        print(file=fp)

    def __print_tree (self, fp=stdout):
        '''Tree printer traveler. (RECURSIVE!)'''
        if self.left: self.left.__print_tree(fp=fp)
        print('%s: "%s"' % (self.name, self.value), file=fp)
        if self.right: self.right.__print_tree(fp=fp)

    def list_to_log (self):
        if self.left: self.left.list_to_log()
        Log.info('%s: %s' % (self.name, self.value))
        if self.right: self.right.list_to_log()

    def __call__ (self):
        '''Return node's value.'''
        return self.value

    def __str__ (self):
        '''Return node's name.'''
        return self.name

    def __repr__ (self):
        '''Return a JSON-like string for the node.'''
        va = hex(id(self.value)) if self.value else '0'
        lt = hex(id(self.left)) if self.left else '0'
        rt = hex(id(self.right)) if self.right else '0'
        s = '{bnode:{id:%s, n:"%s", v:%s, l:%s, r:%s}}'
        t = (hex(self.nid), self.name, va, lt, rt)
        return s % t

    def __lt__ (self, other):
        if type(self) != type(other): return False
        if self.name < other.name: return True
        return False

    def __le__ (self, other):
        if type(self) != type(other): return False
        if self.name <= other.name: return True
        return False

    def __eq__ (self, other):
        if type(self) != type(other): return False
        if self.name == other.name: return True
        return False

    def __ne__ (self, other):
        return not self.__eq__(other)

    def __gt__ (self, other):
        return not self.__le__(other)

    def __ge__ (self, other):
        return not self.__lt__(other)

    def __hash__ (self):
        return self.nid

    def __getitem__ (self, ix):
        '''For indexed link access: 1:left; 2:right (other values ignored)'''
        ii = int(ix)
        if ii == 1: return self.left
        if ii == 2: return self.right
        return None

    def __setitem__ (self, ix, link):
        '''For indexed link access: 1:left; 2:right (other values ignored)'''
        ii = int(ix)
        if ii == 1: self.left = link
        if ii == 2: self.right = link

    def __len__ (self):
        '''Number of nodes (including this) in tree. (NOT RELATED to get/set item!)'''
        n = 1
        if self.left: n += len(self.left)
        if self.right: n += len(self.right)
        return n

    def __nonzero__ (self):
        return True



####################################################################################################
'''eof'''