#!/usr/bin/env python2.2
########################################
# 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.
########################################

"""
Test suite for the BinaryTree class

Builds a bunch of random trees, and then traverses them with a recursive and
iterative traversal.  The two walks are then compared for equality.
"""

import unittest
import os
import random
import string

from compClust.mlx.BinaryTree import *
from compClust.mlx.Node import *

class BinaryTreeTestCases(unittest.TestCase):
    def setUp(self):
        """ create a random binary tree with 100 nodes """
        
        numNodes = 500
        tree     = BinaryTree()

        index    = (numNodes/4)*2 + 1
        node     = Node(index, str(index))

        tree.insert(node)
        
        r = range(0, (numNodes-1)*2, 2)

        while len(r) > 0:
            i = random.choice(r)
            r.remove(i)
            node = Node(i, str(i))
            tree.insert(node)
                        
        self.tree = tree

    def tearDown(self):
        pass

    def lcr(self, root):
        l = []
        if root != None:
            l += self.lcr(self.tree.children(root)[0])
            l += self.tree.find(root).value()
            l += self.lcr(self.tree.children(root)[1])
        return l

    def rcl(self, root):
        l = []
        if root != None:
            l += self.rcl(self.tree.children(root)[1])
            l += self.tree.find(root).value()
            l += self.rcl(self.tree.children(root)[0])
        return l

            
    def clr(self, root):
        l = []
        if root != None:
            l += self.tree.find(root).value()
            l += self.clr(self.tree.children(root)[0])
            l += self.clr(self.tree.children(root)[1])
        return l
    
    def crl(self, root):
        l = []
        if root != None:
            l += self.tree.find(root).value()
            l += self.crl(self.tree.children(root)[1])
            l += self.crl(self.tree.children(root)[0])
        return l
    
    def lrc(self, root):
        l = []
        if root != None:
            l += self.lrc(self.tree.children(root)[0])
            l += self.lrc(self.tree.children(root)[1])
            l += self.tree.find(root).value()
        return l

    def rlc(self, root):
        l = []
        if root != None:
            l += self.rlc(self.tree.children(root)[1])
            l += self.rlc(self.tree.children(root)[0])
            l += self.tree.find(root).value()
        return l

    def iterate(self, tree, mode):
        l  = []
        iter  = tree.iterator(mode)
        tmp   = iter.next()
        while tmp != None:
            l   += tmp.value()
            tmp  = iter.next()
        return l


    def testCRL(self):
        recursive = string.join(self.crl(self.tree.root()), '')    
        iterative = string.join(self.iterate(self.tree, 'CRL'),'')

        if iterative != recursive:
            self.fail("CRL iterator did not give correct results.")

    def testCLR(self):
        recursive = string.join(self.clr(self.tree.root()), '')    
        iterative = string.join(self.iterate(self.tree, 'CLR'),'')

        if iterative != recursive:
            self.fail("CLR iterator did not give correct results.")

    def testRLC(self):
        recursive = string.join(self.rlc(self.tree.root()), '')    
        iterative = string.join(self.iterate(self.tree, 'RLC'),'')

        if iterative != recursive:
            self.fail("RLC iterator did not give correct results.")

    def testLRC(self):
        recursive = string.join(self.lrc(self.tree.root()), '')    
        iterative = string.join(self.iterate(self.tree, 'LRC'),'')

        if iterative != recursive:
            self.fail("LRC iterator did not give correct results.")

    def testRCL(self):
        recursive = string.join(self.rcl(self.tree.root()), '')    
        iterative = string.join(self.iterate(self.tree, 'RCL'),'')
        
        if iterative != recursive:
            self.fail("RCL iterator did not give correct results.")

    def testLCR(self):
        recursive = string.join(self.lcr(self.tree.root()), '')    
        iterative = string.join(self.iterate(self.tree, 'LCR'),'')

        if iterative != recursive:
            self.fail("LCR iterator did not give correct results.")

def suite(**kw):

    suite = unittest.TestSuite()

    suite.addTest(BinaryTreeTestCases("testCRL"))
    suite.addTest(BinaryTreeTestCases("testCLR"))
    suite.addTest(BinaryTreeTestCases("testRLC"))
    suite.addTest(BinaryTreeTestCases("testLRC"))
    suite.addTest(BinaryTreeTestCases("testRCL"))
    suite.addTest(BinaryTreeTestCases("testLCR"))

    return suite

if __name__ == "__main__":
  unittest.main(defaultTest="suite")