########################################
# The contents of this file are subject to the MLX PUBLIC LICENSE version
# 1.0 (the "License"); you may not use this file except in
# compliance with the License.
# 
# Software distributed under the License is distributed on an "AS IS"
# basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.  See
# the License for the specific language governing rights and limitations
# under the License.
# 
# The Original Source Code is "compClust", released 2003 September 03.
# 
# The Original Source Code was developed by the California Institute of
# Technology (Caltech).  Portions created by Caltech are Copyright (C)
# 2002-2003 California Institute of Technology. All Rights Reserved.
########################################
#
#       Author: Lucas J. Scharenbroich
# 
# Original Implementation:  July 10 by Lucas Scharenbroich
#
##########################################################################

"""
A specialization of the MultiWayTree

A binary tree is allowed only 2 edges incident from each node.  The
specialized case, is that each node has a total of 3 incident links.
The first two are the left and right child respectively and the third is
a link to the parent node to facillitate iterative traversals.
"""

from MultiWayTree import *

class BinaryTree(MultiWayTree):

    """
    A Node of a BinaryTree.  A node is a complete tree in itself.

    This class is a specialization on the MultiWayTreeNode restricted to
    2 children per node.
    """

    def __init__(self):
        MultiWayTree.__init__(self)

    def insert(self, node):
        """
        Inserts the node within the tree comparing on the data field.
        """

        left     = 0
        right    = 1
        
        curr = self.root()
        prev = self.root()
        
        while curr != None:
            prev = curr

            if self.find(curr).key() > node.key():
                curr = self.children(curr)[left]
                side = left
            else:
                curr = self.children(curr)[right]
                side = right

        #
        # insert the node into the structure and set its children to None
        #
        
        MultiWayTree.insert(self, node)
        self.join(node.key(), None, None)
        
        if prev != None:
            MultiWayTree.insertAt(self, prev, node.key(), side + 1)
            MultiWayTree.insertAt(self, node.key(), prev, 0)

            
    def join(self, key, left=None, right=None):
        """
        Sets the two nodes as the children of a node.
        """
        MultiWayTree.insertAt(self, key, left, 1)
        MultiWayTree.insertAt(self, key, right, 2)
        MultiWayTree.insertAt(self, left, key, 0)
        MultiWayTree.insertAt(self, right, key, 0)
        
    def iterator(self, type='LCR'):
        return BinaryTreeIterator(self, type)

class BinaryTreeIterator(MultiWayTreeIterator):
    def __init__(self, node, type='LCR'):
        MultiWayTreeIterator.__init__(self, node, type)