Loser tree in Python

I am taking an Advanced Data Structures and Algorithms class with Dr. Sahni at UF. I used a data structure discussed in this class as an opportunity to learn Python a little better. I implemented the loser tree. The loser tree is a complete binary tree with n external nodes and n-1 internal nodes. The root of the tree has the overall winner. The loser tree is a more efficient version of a winner tree which are both types of Tournament Trees. In the winner tree the winner of each competition is inside the nodes, however it is more efficient to keep the loser of the competitions in side the nodes and bubble the winner up the tree.

The loser tree has applications in areas such as Run Generations during external sorts, Bin-Packing Problems (Truck Loading), and others.

I am not yet sure of how to transfer my c++ knowledge of pointer to Python, so I used an array representation of the binary tree to keep track of the nodes. If anybody knows how I could implement a tree with pointers, I would love to know.

In anycase, below is my code. It isnt great code, and any suggestions would be great! Thanks to Yet Another Coding Blog for the code highlighting tip.

#!/usr/bin/env python

import copy

class INode:
 ''' Internal nodes of the tree '''
 def __init__(self,value=None,ptr=None,run=0):
  self.value = value
  self.ptr = ptr
  self.run = run

 def __repr__(self):
  return repr(self.value)

 def __cmp__(self,node):
  if isinstance(node,INode):
   # return cmp(self.value, node.value)
   return self.value <= node.value
  else:
   # return cmp(self.value, node)
   return self.value <= node
 

 def __copy__(self):
  return INode(self.value,self.ptr,self.run)
  
 def copy(self):
  new = INode()
  new.value = self.value
  new.ptr = self.ptr
  new.run = self.run
  return new
 __copy__ = __deepcopy__ = copy

 def clear(self):
  ''' Clear the value of this INode '''
  self.value = None
  self.ptr = None
  self.run = None
  
class LoserTree:
 '''The size of data must be a ,perfect square (i.e. 2,4,8,16) '''
 def __init__(self,data=None):
  self.size = len(data)
  self.data = [INode() for i in xrange(len(data))]
  self.data.extend([INode(data[i],i+self.size) for i in xrange(len(data))])
  self.initialize() 

 def initialize(self):
  '''Build the tree'''
  index = self.size # Give us the index of the lowest level
  left = True
  for i in xrange(0,self.size,2):
   l,r = int(index+i), int(index+i+1)
   if(left):
    if(self.__cmp(self.data[l], self.data[r])):
     # Left Wins
     loser = r/2
     self.data[loser] = copy.copy(self.data[r])

     winner = loser/2
     self.data[winner] = copy.copy(self.data[l])
    else:
     # Right Wins
     loser = l/2
     self.data[loser] = copy.copy(self.data[l])

     winner = loser/2
     self.data[winner] = copy.copy(self.data[r])
   elif(not left):
    # We are on the right side of a tree
    # so we need to bubble the winner up
    winner = None
    win_tmp = None
    if(self.__cmp(self.data[l],self.data[r])):
     # Left Wins
     loser = l/2
     self.data[loser] = copy.copy(self.data[r])

     win_tmp = copy.copy(self.data[l])
     winner = loser/2
    else:
     # Right Wins
     loser = r/2
     self.data[loser] = copy.copy(self.data[l])

     win_tmp = copy.copy(self.data[r])
     winner = loser/2
    # Bubble up
    while True:
     if(self.data[winner].value == None):
      self.data[winner] = copy.copy(win_tmp)
      break

     elif(self.__cmp(self.data[winner], win_tmp)):
      tmp = copy.copy(self.data[winner])
      self.data[winner] = copy.copy(win_tmp)
      win_tmp = copy.copy(tmp)

      winner /=2
     else:
      winner /= 2
   left = not left

 def getWinner(self):
  return self.data[0].value  
  
 def popReplace(self, newValue):
  '''Return the winner and update the tree with the new item'''
  oldWinner = copy.copy(self.data[0])
  runner = self.data[0].ptr
  levelup = runner/2
  
  newINode = INode(newValue,runner,oldWinner.run)
  # Is new node less than the old winner 
  # if so increment the run count
  if(newValue < oldWinner.value):
   newINode.run = oldWinner.run + 1

        # Replace Winner
  self.data[runner] = copy.copy(newINode)
  self.data[0].clear()
 
  win_tmp = copy.copy(self.data[runner])
  while runner > 0:
   levelup = runner/2
   if(self.__cmp(win_tmp,self.data[levelup])):
    #win_tmp wins and is promoted
    runner /= 2
   else:
    tmp = copy.copy(self.data[levelup])
    self.data[levelup] = copy.copy(win_tmp)
    win_tmp = tmp
    runner /= 2
  self.data[0] = copy.copy(win_tmp)

  return oldWinner

 def __repr__(self):
  '''This prints the leaves of the tree'''
  return repr(self.data[0:self.size])
  
 def __cmp(self,left,right):
  '''This compare function compares the current run, then the values'''
  if(left.run == right.run):
   return cmp(left, right)
  else:
   return cmp(left.run, right.run)

if __name__ == '__main__':
 print "Data  :",
 data = [4,3,6,8,1,5,7,3,2,6,9,4,5,2,5,8]
 print data
 t = LoserTree(data)
 print "Leaves:",t
 print "Winner: ", t.getWinner()
 replace = 9
 w = t.popReplace(replace)
 print "Replaced the winner %s with %s" % (w,replace)
 print "New Winner: ", t.getWinner()
 print "Leaves:",t

© Christan Grant - 2008