#!/usr/bin/env python3 ''' Created again on 9/May/2020 @author: rand ''' import random import copy class _NodeContainer( object ): def __init__(self, key, value ): self.key = key self.value = value self.zeroLinksAndCounts() def zeroLinksAndCounts( self ): self.listUp = None self.listDown = None self.treeParent = None self.treeLeft = None self.treeCountLeft = 0 self.treeRight = None self.treeCountRight = 0 def __repr__( self ): # a convenience for dumping the structure return '{:4s} value:{:4s} (list) up:{:4s} down:{:4s} (tree) parent:{:4s} left:{:4s} right:{:4s} (count) {:4d}<->{:<4d}'.format( str(self.key), str(self.value), str(self.listUp.key if self.listUp is not None else None), str(self.listDown.key if self.listDown is not None else None), str(self.treeParent.key if self.treeParent is not None else None), str(self.treeLeft.key if self.treeLeft is not None else None), str(self.treeRight.key if self.treeRight is not None else None), self.treeCountLeft, self.treeCountRight ).strip() class FixedSizeBinaryTree( object ): def __init__(self, maxItems): self.binaryTree = None self.listHead = None self.listTail = None self.treeLevelTolerance = 1 self.maxItems = maxItems self.listLen = 0 self.debug = 0 def setDebug( self, value ): self.debug = value def dumpTree( self, node, indentation ): if node.treeRight is not None: self.dumpTree( node.treeRight, 1 +indentation ) print( '\t{}{}'.format( '. '*indentation, node )) if node.treeLeft is not None: self.dumpTree( node.treeLeft, 1 +indentation ) def dump( self ): print( '\nList ({}): (head:{} tail:{}'.format( self.listLen, self.listHead, self.listTail )) node = self.listHead while node is not None: print( '\t{}'.format( node )) node = node.listDown print( 'Tree:' ) self.dumpTree( self.binaryTree, 0 ) print() # List routines: def listAppentItem( self, item ): if 0 < self.debug: print( 'FixedSizeBinaryTree::listAppentItem item:{}'.format( item.key )) if self.listHead is None: if 1 < self.debug: print( 'FixedSizeBinaryTree::listAppentItem item:{} is the new head'.format( item.key )) self.listHead = item self.listTail = item else: if 1 < self.debug: print( 'FixedSizeBinaryTree::listAppentItem item:{} added to tail'.format( item.key )) self.listTail.listDown = item self.listTail.listDown.listUp = self.listTail self.listTail = item self.listLen += 1 def listRemoveItem( self, item ): if 0 < self.debug: print( 'FixedSizeBinaryTree::listRemoveItem item:{}'.format( item.key )) if item.listDown is None: self.listTail = item.listUp if item.listUp is None: self.listHead = item.listDown if item.listUp is not None: item.listUp.listDown = item.listDown if item.listDown is not None: item.listDown.listUp = item.listUp item.listUp = None item.listDown = None self.listLen -= 1 def listLengthCheck( self ): if 0 < self.debug: print( 'FixedSizeBinaryTree::listLengthCheck checking length max:{} currently:{}'.format( self.maxItems, self.listLen )) if self.maxItems < self.listLen: removeItem = self.listHead if 1 < self.debug: print( 'FixedSizeBinaryTree::listLengthCheck removing item:{}'.format( removeItem )) self.listRemoveItem( removeItem ) self.treeRemoveItem( removeItem ) removeItem.zeroLinksAndCounts() # Tree routines: def treeSetParentCounts( self, item ): if 0 < self.debug: print( 'FixedSizeBinaryTree::treeSetParentCounts item:{}'.format( item.key )) if item.treeParent is not None: insertCount = item.treeCountLeft +item.treeCountRight +1 if item.treeParent.treeRight == item: item.treeParent.treeCountRight = insertCount elif item.treeParent.treeLeft == item: item.treeParent.treeCountLeft = insertCount self.treeSetParentCounts( item.treeParent ) def treeSetItemCounts( self, item ): if 0 < self.debug: print( 'FixedSizeBinaryTree::treeSetItemCounts item:{}'.format( item.key )) if item.treeLeft is not None: item.treeCountLeft = item.treeLeft.treeCountLeft +item.treeLeft.treeCountRight +1 else: item.treeCountLeft = 0 if item.treeRight is not None: item.treeCountRight = item.treeRight.treeCountLeft +item.treeRight.treeCountRight +1 else: item.treeCountRight = 0 def treeInsertItem( self, node, item ): if 0 < self.debug: print( 'FixedSizeBinaryTree::treeInsertItem node:{} key:{}'.format( node.key, item.key )) if node.key == item.key: node.value = item.value # may also be done in list... only need to do this once return node else: if item.key < node.key: if node.treeLeft is None: node.treeLeft = item item.treeParent = node self.treeSetParentCounts( item ) else: return self.treeInsertItem( node.treeLeft, item ) elif node.key < item.key: if node.treeRight is None: node.treeRight = item item.treeParent = node self.treeSetParentCounts( item ) else: return self.treeInsertItem( node.treeRight, item ) return None def treeInsert( self, item ): if 0 < self.debug: print( 'FixedSizeBinaryTree::treeInsert item:{}'.format( item.key )) if self.binaryTree is not None: return self.treeInsertItem( self.binaryTree, item ) else: self.binaryTree = item return None def treeRemoveItem( self, removeItem ): if 0 < self.debug: print( 'FixedSizeBinaryTree::treeRemoveItem disconnecting:{}'.format( removeItem )) if removeItem.treeParent is None: # == self.binaryTree: # is the head if 1 < self.debug: print( 'FixedSizeBinaryTree::treeRemoveItem path 1'.format()) if removeItem.treeRight is not None: self.binaryTree = removeItem.treeRight if removeItem.treeLeft is not None: removeItem.treeLeft.treeParent = None self.treeInsertItem( self.binaryTree, removeItem.treeLeft ) self.binaryTree.treeParent = None elif removeItem.treeLeft is not None: self.binaryTree = removeItem.treeLeft self.binaryTree.treeParent = None else: self.binaryTree = None else: if removeItem.treeParent.treeRight == removeItem: # I'm connected off to the parent's right if 1 < self.debug: print( 'FixedSizeBinaryTree::treeRemoveItem path 2'.format()) removeItem.treeParent.treeRight = removeItem.treeRight if removeItem.treeRight is not None: removeItem.treeRight.treeParent = removeItem.treeParent # I don't see how this could fail! if removeItem.treeLeft is not None: removeItem.treeLeft.treeParent = None self.treeInsertItem( removeItem.treeParent, removeItem.treeLeft ) elif removeItem.treeParent.treeLeft == removeItem: # I'm connected off to the parent's left if 1 < self.debug: print( 'FixedSizeBinaryTree::treeRemoveItem path 3'.format()) removeItem.treeParent.treeLeft = removeItem.treeLeft if 1 < self.debug: print( 'FixedSizeBinaryTree::treeRemoveItem path 3 remove Left:{}'.format( removeItem )) if removeItem.treeLeft is not None: removeItem.treeLeft.treeParent = removeItem.treeParent if removeItem.treeRight is not None: removeItem.treeRight.treeParent = None self.treeInsertItem( removeItem.treeParent, removeItem.treeRight ) self.treeSetItemCounts( removeItem.treeParent ) self.treeSetParentCounts( removeItem.treeParent ) def treeLevelThisPath( self, node ): # complicated routine... be careful if 0 < self.debug: print( 'FixedSizeBinaryTree::treeLevelThisPath node:{}'.format( node )) if 0 < self.treeLevelTolerance: if node.treeParent is not None: treeParent = node.treeParent if node.treeCountLeft +self.treeLevelTolerance < node.treeCountRight: node.treeParent = None node.treeCountRight = 0 node.treeRight.treeParent = treeParent if treeParent.treeRight == node: if 2 < self.debug: print( '\tFixedSizeBinaryTree::treeLevelThisPath node:{} path 1'.format( node.key )) treeParent.treeRight = node.treeRight node.treeRight = None self.treeSetItemCounts( treeParent ) self.treeSetParentCounts( treeParent.treeRight ) elif treeParent.treeLeft == node: if 2 < self.debug: print( '\tFixedSizeBinaryTree::treeLevelThisPath node:{} path 2'.format( node.key )) treeParent.treeLeft = node.treeRight node.treeRight = None self.treeSetItemCounts( treeParent ) self.treeSetParentCounts( treeParent.treeLeft ) self.treeInsertItem( treeParent, node ) elif node.treeCountRight +self.treeLevelTolerance < node.treeCountLeft: node.treeParent = None node.treeCountLeft = 0 node.treeLeft.treeParent = treeParent if treeParent.treeLeft == node: if 2 < self.debug: print( '\tFixedSizeBinaryTree::treeLevelThisPath node:{} path 3'.format( node.key )) treeParent.treeLeft = node.treeLeft node.treeLeft = None self.treeSetItemCounts( treeParent ) self.treeSetParentCounts( treeParent.treeLeft ) elif treeParent.treeRight == node: if 2 < self.debug: print( '\tFixedSizeBinaryTree::treeLevelThisPath node:{} path 4'.format( node.key )) treeParent.treeRight = node.treeLeft node.treeLeft = None self.treeSetItemCounts( treeParent ) self.treeSetParentCounts( treeParent.treeRight ) self.treeInsertItem( treeParent, node ) else: self.treeLevelThisPath( treeParent ) else: # head might need to be leveled if 2 < self.debug: print( '\tFixedSizeBinaryTree::treeLevelThisPath checking binaryTree'.format()) if node.treeCountLeft +self.treeLevelTolerance < node.treeCountRight: node.treeRight.treeParent = None self.binaryTree = node.treeRight node.treeRight = None node.treeCountRight = 0 self.treeInsertItem( self.binaryTree, node ) elif node.treeCountRight +self.treeLevelTolerance < node.treeCountLeft: node.treeLeft.treeParent = None self.binaryTree = node.treeLeft node.treeLeft = None node.treeCountLeft = 0 self.treeInsertItem( self.binaryTree, node ) def treeLevelLargest( self ): if 0 < self.debug: print( 'FixedSizeBinaryTree::treeLevelLargest'.format()) def getValue( node ): return abs( node.treeCountLeft -node.treeCountRight ) walkingNode = self.listHead worstNode = walkingNode worstValue = getValue( worstNode ) walkingNode = walkingNode.listDown while walkingNode is not None: testValue = getValue( walkingNode ) if worstValue < testValue: worstValue = testValue worstNode = walkingNode walkingNode = walkingNode.listDown if self.treeLevelTolerance < worstValue: self.treeLevelThisPath( worstNode ) return True return False def treeGetItem( self, node, key ): if 0 < self.debug: print( 'FixedSizeBinaryTree::treeGetItem node:{} key:{}'.format( node.key if node is not None else None, key )) if node is None: return None if node.key == key: return node if key < node.key: return self.treeGetItem( node.treeLeft, key ) # elif not needed if node.key < key: return self.treeGetItem( node.treeRight, key ) # same here def addOrUpdate( self, item ): if 0 < self.debug: print( 'FixedSizeBinaryTree::addOrUpdate adding:{}'.format( item )) existingItem = self.treeInsert( item ) if existingItem is not None: if 1 < self.debug: print( 'FixedSizeBinaryTree::addOrUpdate existingItem:{}'.format( existingItem )) self.listRemoveItem( existingItem ) item = existingItem self.listAppentItem( item ) self.listLengthCheck() self.treeLevelThisPath( item ) self.treeLevelLargest() # publicly visible methods def setTreeLevelTolerance( self, newValue ): self.treeLevelTolerance = newValue def __len__( self ): return self.listLen def __setitem__( self, key, value ): item = _NodeContainer( key, value ) if 0 < self.debug: print( 'FixedSizeBinaryTree::__setitem__ item:{}'.format( item )) self.addOrUpdate( item ) if 1 < self.debug: print( ''.format()) def __getitem__( self, key ): if 0 < self.debug: print( 'FixedSizeBinaryTree::__getitem__ key:{}'.format( key )) item = self.treeGetItem( self.binaryTree, key ) if item is not None: self.listRemoveItem( item ) self.listAppentItem( item ) return item.value return None if __name__ == "__main__": print( 'starting' ) totalItems = 20 obj = FixedSizeBinaryTree( totalItems ) obj.setTreeLevelTolerance( 1 ) def addItem( key, value=None ): if value is None: obj[key] = key else: obj[key] = value if True: # test to see if the size changes print( 'Testing size stability:' ) for i in range( totalItems ): # fill the tree addItem( i ) obj.dump() for unused in range( 3 *totalItems ): # add lots more items to the tree - which should not decrease in size addItem( random.randint( 0, 2 *totalItems )) if len( obj ) < totalItems: obj.dump() print( 'ERROR length:{} somewhere'.format( len( obj ))) break if totalItems < len( obj ): obj.dump() print( 'FAULT on length:{} somewhere'.format( len( obj ))) break if True: # test to see random additions and references print( 'Testing random placement and random access:' ) for unused in range( 100 *totalItems ): addItem( random.randint( 0, 2 *totalItems )) unused = obj[ random.randint( 0, 2 *totalItems )] obj.dump() if True: # test tree leveling as it grows addItem( 50 ) obj.dump() addItem( 70 ) obj.dump() addItem( 30 ) obj.dump() addItem( 80 ) obj.dump() addItem( 20 ) obj.dump() addItem( 90 ) obj.dump() addItem( 10 ) obj.dump() if True: # test leveling a "linear" tree for i in range( totalItems ): addItem( i ) obj.dump() print( 'done' )