Python3树结构实现

Python3treeimplementationSource:#Python3TreeImplementation##Copyright(C)2011,[e-mail]#Allrightsreserved.##Redistributionanduseinsourceandbinaryforms,withorwithoutmodification,#arepermittedprovidedthatthefollowingconditionsaremet:##Redistributionsofsourcecodemustretaintheabovecopyrightnotice,thislist#ofconditionsandthefollowingdisclaimer.##Redistributionsinbinaryformmustreproducetheabovecopyrightnotice,this#listofconditionsandthefollowingdisclaimerinthedocumentationand/or#othermaterialsprovidedwiththedistribution.##Neitherthenameofthecopyrightholdernorthenamesofthecontributors#maybeusedtoendorseorpromoteproductsderivedfromthissoftwarewithout#specificpriorwrittenpermission.##THISSOFTWAREISPROVIDEDBYTHECOPYRIGHTHOLDERSANDCONTRIBUTORSASISAND#ANYEXPRESSORIMPLIEDWARRANTIES,INCLUDING,BUTNOTLIMITEDTO,THEIMPLIED#WARRANTIESOFMERCHANTABILITYANDFITNESSFORAPARTICULARPURPOSEARE#DISCLAIMED.INNOEVENTSHALLTHECOPYRIGHTHOLDERORCONTRIBUTORSBELIABLEFOR#ANYDIRECT,INDIRECT,INCIDENTAL,SPECIAL,EXEMPLARY,ORCONSEQUENTIALDAMAGES#(INCLUDING,BUTNOTLIMITEDTO,PROCUREMENTOFSUBSTITUTEGOODSORSERVICES;#LOSSOFUSE,DATA,ORPROFITS;ORBUSINESSINTERRUPTION)HOWEVERCAUSEDANDON#ANYTHEORYOFLIABILITY,WHETHERINCONTRACT,STRICTLIABILITY,ORTORT#(INCLUDINGNEGLIGENCEOROTHERWISE)ARISINGINANYWAYOUTOFTHEUSEOFTHIS#SOFTWARE,EVENIFADVISEDOFTHEPOSSIBILITYOFSUCHDAMAGE.importunittestdefsanitize_id(id):returnid.strip().replace(,)#--------------------------------------------------------------------------------#TestsuiteclassTestUtilities(unittest.TestCase):defsetUp(self):self.identifier1=identifier1deftest_sanitize_id(self):self.assertEqual(sanitize_id(self.identifier1),identifier1)deftearDown(self):pass#--------------------------------------------------------------------------------#Moduletestingif__name__==__main__:unittest.main()#================================================================================importunittestimportuuidfromutilitiesimportsanitize_id#Moduleconstants(_ADD,_DELETE,_INSERT)=range(3)classNode:Classforbasicnodefunctionality.def__init__(self,name,identifier=None,expanded=True):self.__identifier=(str(uuid.uuid1())ifidentifierisNoneelsesanitize_id(str(identifier)))self.name=nameself.expanded=expandedself.__bpointer=Noneself.__fpointer=[]@propertydefidentifier(self):returnself.__identifier@propertydefbpointer(self):[e-mail](self,value):ifvalueisnotNone:self.__bpointer=sanitize_id(value)@propertydeffpointer(self):returnself.__fpointerdefupdate_fpointer(self,identifier,mode=_ADD):ifmodeis_ADD:self.__fpointer.append(sanitize_id(identifier))elifmodeis_DELETE:self.__fpointer.remove(sanitize_id(identifier))elifmodeis_INSERT:self.__fpointer=[sanitize_id(identifier)]#--------------------------------------------------------------------------------#TestsuiteclassTestNode(unittest.TestCase):defsetUp(self):self.node1=Node(TestOne,identifier1)deftest_initialization(self):self.assertEqual(self.node1.name,TestOne)self.assertEqual(self.node1.identifier,identifier1)self.assertEqual(self.node1.expanded,True)deftest_set_fpointer(self):self.node1.update_fpointer(identifier2)self.assertEqual(self.node1.fpointer,['identifier2'])deftest_set_bpointer(self):self.node1.bpointer=identifier1self.assertEqual(self.node1.bpointer,'identifier1')deftearDown(self):pass#--------------------------------------------------------------------------------#Moduletestingif__name__==__main__:unittest.main()#================================================================================importunittestfromnodeimportNode#Moduleconstants(_ADD,_DELETE,_INSERT)=range(3)(_ROOT,_DEPTH,_WIDTH)=range(3)classTree:def__init__(self):self.nodes=[]defget_index(self,position):forindex,nodeinenumerate(self.nodes):ifnode.identifier==position:breakreturnindexdefcreate_node(self,name,identifier=None,parent=None):Createachildnodeforthenodeindicatedbythe'parent'parameternode=Node(name,identifier)self.nodes.append(node)self.__update_fpointer(parent,node.identifier,_ADD)node.bpointer=parentreturnnodedefmove_node(self,source,destination):Moveanodeindicatedbythe'source'parametertotheparentnodeindicatedbythe'dest'parameterpassdefremove_node(self,identifier):passdefshow(self,position,level=_ROOT):queue=self[position].fpointeriflevel==_ROOT:print({0}[{1}].format(self[position].name,self[position].identifier))else:print(t*level,{0}[{1}].format(self[position].name,self[position].identifier))ifself[position].expanded:level+=1forelementinqueue:self.show(element,level)#recursivecalldefexpand_tree(self,position,mode=_DEPTH):#Pythongenerator.Looslybasedonanalgorithmfrom'EssentialLISP'by#JohnR.Anderson,AlbertT.Corbett,andBrianJ.Reiser,page239-241yieldpositionqueue=self[position].fpointerwhilequeue:yieldqueue[0]expansion=self[queue[0]].fpointerifmodeis_DEPTH:queue=expansion+queue[1:]#depth-firstelifmodeis_WIDTH:queue=queue[1:]+expansion#width-firstdefis_branch(self,position):returnself[position].fpointerdef__update_fpointer(self,position,identifier,mode