00001
00002
00003
00004 _file__ = 'dataUtils.py'
00005 __title__ = 'This is the data module, which contains everything which is linked to data structure and management.'
00006 __version__ = '0.1'
00007 __author__ = 'Olivier Boudeville (olivier.boudeville@online.fr)'
00008 __project__ = 'Ceylan'
00009 __creationDate__= '2004, August 6'
00010 __comments__ = ""
00011 __source__ = 'None'
00012 __doc__ = __title__ + '\n' + __comments__
00013
00014
00015
00016
00017 import sys, types, string
00018
00019
00020 import generalUtils
00021
00022
00023 class DataUtilsException( generalUtils.GeneralUtilsException ) :
00024 """Base class for generalUtils exceptions."""
00025
00026
00027
00028 class Node:
00029 """
00030 Nodes are trees : they can contain other nodes.
00031 Each node can carry a content, whose type is NodeContent.
00032 """
00033
00034
00035 def __init__( self, newContent = None ) :
00036 """Creates an empty node with no child node."""
00037 self.content = newContent
00038 self.children = []
00039
00040
00041 def __cmp__(self, other):
00042 return self.content != other.content
00043
00044
00045 def __repr__( self ):
00046 """Returns a textual representation of this node's state."""
00047 res = "Node has "
00048 if self.content:
00049 res += "content (%s)" % ( self.content, )
00050 else:
00051 res += "no content"
00052 res += " and it has "
00053 if self.children:
00054 res += "%s children." % ( len( self.children ), )
00055 else:
00056 res += "no child."
00057
00058 return res
00059
00060
00061 def toString( self, offset = 0, nextOffset = 0, isFirstChild = True ):
00062 """
00063 Returns a stringified description of the tree.
00064
00065 __ a __ b
00066 |_ c __ d __ e
00067 |_ f
00068 |_ g
00069
00070 offset is the current position where to write
00071 nexOffset is the position where children should begin
00072 """
00073
00074
00075 res= ""
00076
00077
00078
00079
00080 branchFirst = ' __ '
00081 branchOther = ' |_ '
00082 branchEnd = ''
00083
00084 node_text = string.ljust( '%s' % (self.content,), nextOffset - offset + 1 )
00085
00086 if isFirstChild:
00087 res += branchFirst + node_text
00088 else:
00089
00090 res = offset * ' ' + branchOther + node_text
00091
00092 if len( self.children ):
00093 newOffset = offset + len( branchFirst ) + len(node_text)
00094
00095
00096 extraLength = 0
00097 for child in self.children:
00098 child_size = len( child.content )
00099 if child_size > extraLength:
00100 extraLength = child_size
00101 newNextOffset = offset + len( branchFirst ) + extraLength
00102 res += self.children[0].toString( newOffset, newNextOffset, True )
00103 for c in self.children[1:]:
00104 res += '\n' + c.toString( newOffset, newNextOffset, False )
00105 res += branchEnd
00106 return res
00107
00108
00109 def addChild( self, aChild ):
00110 """Adds a child to current node."""
00111 self.children.append( aChild )
00112
00113
00114 def removeChild( self, child ):
00115 """Removes specified child, raises an exception if child not found."""
00116 self.children.remove( child )
00117
00118
00119 def removeAllChildren( self ):
00120 self.children = None
00121
00122
00123 def getChildren( self ):
00124 """Returns this node's children."""
00125 return self.children
00126
00127
00128 def setContent( self, nodeContent ):
00129 """Sets a new content to current node, which must not have already a content."""
00130 if self.content:
00131 raise ValueError, "Node::setContent : content already assigned."
00132 self.content = nodeContent
00133
00134
00135 def getContent( self ):
00136 """Returns this node's current content."""
00137 return self.content
00138
00139
00140 def dropContent( self ):
00141 """Removes this node's content."""
00142 self.content = None
00143
00144
00145 def searchChildren( self, content ):
00146 """Searches through node's children the first, if any, that has specified content."""
00147 for c in self.children:
00148 if c.content == content:
00149 return c
00150 return None
00151
00152
00153 def listDepthFirst( self ):
00154 """
00155 Walks the tree depth-first, returns the list of encountered nodes.
00156 """
00157 res = [ self ]
00158 for c in self.children:
00159 res += c.listDepthFirst()
00160 return res
00161
00162
00163
00164 def listByHeight( self, first = True ):
00165 """
00166 Walks the tree height by height, starting from root node, and returns the list of
00167 encountered nodes.
00168 """
00169 res = []
00170 if first:
00171 res = [ self ]
00172 res += self.children
00173 for c in self.children:
00174 res += c.listByHeight( False )
00175 return res
00176
00177
00178 def searchContent( self, content ):
00179 """
00180 Searches through internal content and then recursively through children for
00181 specified content.Returns the first node found having the content, if any.
00182 Otherwise, returns None.
00183 content -> list of nodes
00184 """
00185
00186 if content == self.content:
00187 return self
00188 else:
00189 for c in self.children:
00190 res = c.searchContent( content )
00191 if res:
00192 return res
00193 return None
00194
00195
00196 def searchPathToContent( self, content ):
00197 """
00198 Returns, if possible, the path from the first found node whose
00199 content matches specified content to root node.
00200 """
00201 if content == self.content:
00202
00203 return [ self ]
00204 else:
00205
00206 for child in self.children:
00207 res = child.searchPathToContent( content )
00208 if res:
00209 res.append( self )
00210
00211 return res
00212 return None
00213
00214
00215 def display( self ) :
00216 print 'content = %s' % ( self.content,)
00217 print 'children = %s' % ( self.children,)
00218
00219
00220 class NodeExample( Node ):
00221
00222 def __init__( self, name = None ):
00223 Node.__init__( self )
00224 self.content = name
00225
00226
00227 if __name__ == "__main__":
00228
00229 import startup
00230
00231 print __doc__
00232
00233 a=NodeExample( 'a' )
00234 b=NodeExample( 'b' )
00235 c=NodeExample( 'c' )
00236 d=NodeExample( 'd' )
00237 e=NodeExample( 'e' )
00238 f=NodeExample( 'f' )
00239 g=NodeExample( 'g' )
00240
00241
00242
00243
00244
00245
00246
00247
00248 a.addChild( b )
00249 a.addChild( c )
00250 c.addChild( d )
00251 d.addChild( e )
00252 d.addChild( f )
00253 a.addChild( g )
00254
00255 print a.toString()
00256
00257 u = a.searchContent( 'd' )
00258 print 'Searching for content d : %s' % ( u, )
00259 print
00260
00261 path = a.searchPathToContent( 'd' )
00262 print 'Searching path from content d to root : '
00263 generalUtils.displayList( path )
00264 print
00265
00266
00267 l = a.listDepthFirst()
00268 print 'Listing depth-first tree :'
00269 generalUtils.displayList( l )
00270 print '(size of list : %s)' % ( len(l),)
00271 print
00272
00273 m = a.listByHeight()
00274 print 'Listing height by height tree, starting from root node :'
00275 generalUtils.displayList( m )
00276 print '(size of list : %s)' % ( len(m),)
00277 print
00278