How to store the reference of a dictionary element ?
Bengt Richter
bokr at oz.net
Thu Dec 19 08:58:22 EST 2002
On 19 Dec 2002 12:29:49 +0800, "Alfredo P. Ricafort" <alpot at mylinuxsite.com> wrote:
>On Wed, 2002-12-18 at 06:36, Bengt Richter wrote:
>
>> I tried to understand "what you are *really* trying do do"(tm) but
>couldn't ;-)
>> If you would define your requirements independently of preconceived
>implementation
>> ideas, I suspect people would be able to help better.
>>
>
>I'm not exactly sure if you are really replying to this thread. But just
>in case you are, and if you curious on what I am trying to do, then here
>it is:
>
>I am writing a wxPython program and I am trying to create a class that
>is somewhat similar to the menu_item_factory of GTK+. The structure of
>the INPUT data to the class is like this:
>
>inputData=( (path,attribute1,attribute2,....),....)
>
>for example:
> inputData=(
> ('/&File', 'text','text'....),
> ('/File/&New', 'text','text'....),
> ('/File/New/&Folder', 'text','text'..),
> ('/File/New/&Directory', 'text','text'..),
> ('/&Edit', 'text','text'..)
> )
>
>When this input is pass on to the class, it will be broken down to a new
>structure that the program can easily manipulate. The OUTPUT structure
>will be somewhat like this:
>
> outputData={'menuKey':[attribute1,attribute2,{submenu}],..}
>
>In our example above, the outcome will be like this:
>
> outputData={'File':['text','text',
> {'New':['text','text',
> {'Folder':['text','text',None],
> 'Directory:['text','text',None]
> ]
> ],
> 'Edit':['text','text',None]
> }
>
Bravo ;-) All this I can understand. So far it seems reasonable to me
(other than minimal concern that a lot of dicts take up more space than
other ways, or a single dict).
>But I realized that for this type of structure, where the submenus could
>be n level deep, I will have difficulty searching for a particular
>element in the dictionary. Instead, I am thinking of changing the
ISTM it could be difficult or easy depending on how you were searching.
Apparently your data represents a typical menu tree. How do you need to
navigate the tree besides top down? I.e., given a legal path as a sequence
of keys, e.g.,
m, sm1, sm2 = ('File','New','Directory')
it's certainly not hard to write the code (using your data from above)
outputData[m][sm1][sm2]
or walking an unspecified-length path name sequence, e.g.,
pathTuple = ('File','New','Directory')
element = outputData
for p in pathTuple: element = element[p]
or wrap that in a function
def getElement(pathSeq):
element = outputData
for p in pathSeq: element = element[p]
return element
then
element = getElement(pathTuple)
or
element = getElement(['Edit'])
to get at the last node. Of course you would want to use try:/except:
to catch key errors if you have the possibility of illegal paths.
You could define your own node class and just build a tree yourself from a root node.
E.g., minimally from what you have mentioned, and duplication the structure of
your output nested directory starting with your input data:
====< menutree.py >==============================================================
#!/usr/bin/python
# menutree.py for "Alfredo P. Ricafort" <alpot at mylinuxsite.com>
inputData=(
('/&File', 'textF0','textF1','F2'),
('/File/&New', 'textFN0','textFN1'),
('/File/New/&Folder', 'textFNF0','textFNF1'),
('/File/New/&Directory', 'textFND0','textFND1','textFND2'),
('/&Edit', 'textE0','textE1')
)
class Node:
def __init__(self, name, parent=None, attrTup=()):
__slots__ = ['name','disp','parent', 'children','attrTup'] # optional, saves space
self.name = name.replace('&','') # without shortcut &
self.disp = name # menu display text
self.parent = parent
self.children = []
self.attrTup = attrTup
def addChild(self, child):
if not isinstance(child, Node):
raise ValueError, 'Children must be Node instances, not %s' % type(child)
child.parent = self # the parent link you wanted ;-)
self.children.append(child)
def getChild(self, name):
for child in self.children:
if child.name == name:
return child
raise ValueError, 'Node "%s" has no child named "%s"' % (self.name, name)
def show(self, recurse=0, level=0):
print '%s %-30s"%s" %s' %(level*4*' ', self.name+':', self.disp, self.attrTup)
if recurse:
for child in self.children: child.show(recurse,level+1)
def __repr__(self): return '<Node %s at 0x%08x>' %( `self.name`, id(self))
def makeDict(tree):
treed = {}
def addNodeNameKey(node):
if treed.get(node.name): raise ValueError, 'Non-Unique Node name: %s' % node.name
treed[node.name]=node
for child in node.children: addNodeNameKey(child)
addNodeNameKey(tree)
return treed
makeDict = staticmethod(makeDict)
def makeTree(name, inputData):
tree = Node(name)
for tup in inputData:
path = tup[0].split('/')[1:] # assumes path starts with '/' and no insignificant spaces
currNode = tree
for name in path:
try:
currNode = currNode.getChild(name.replace('&',''))
except ValueError:
child = Node(name, currNode, tup[1:]) # currNode is parent
currNode.addChild(child)
currNode = child
return tree
makeTree = staticmethod(makeTree) # so it can be called without a node instance
def test(inData):
menuTree = Node.makeTree('Menu Bar',inData) # give root node a name
menuTree.show(1,0)
menuTree.treeDict = Node.makeDict(menuTree) # attach optional directory for test
return menuTree # so we can print dir showing access via root node
inputData2=( # test out of order and reorderd input
('/File/New/&Directory', 'textFND0','textFND1','textFND2'),
('/File/New/&Folder', 'textFNF0','textFNF1'),
('/&File', 'textF0','textF1','F2'),
('/File/&New', 'textFN0','textFN1'),
('/&Edit', 'textE0','textE1'),
('/File/E&xit', 'TTFN ;-)')
)
if __name__ == '__main__':
def boxit(s):
print ' +-%s-+' % ('-'*len(s))
print ' | %s |' % s
print ' +-%s-+' % ('-'*len(s))
boxit('From ordered data')
root = test(inputData)
boxit('Directory of all nodenames (must be unique) to look up named nodes')
print '{\n%s}' % (''.join([('%s:%s,\n' % (`k`,`v`)) for k,v in root.treeDict.items()]))
boxit('Parent links of nodes in dict')
for k,v in root.treeDict.items(): print '%15s is parent of %s' % (
v.parent and v.parent.name or '(No parent)', k)
boxit('From out of order & reordered input with added item')
test(inputData2)
=================================================================================
This gives the output
+-------------------+
| From ordered data |
+-------------------+
Menu Bar: "Menu Bar" ()
File: "&File" ('textF0', 'textF1', 'F2')
New: "&New" ('textFN0', 'textFN1')
Folder: "&Folder" ('textFNF0', 'textFNF1')
Directory: "&Directory" ('textFND0', 'textFND1', 'textFND2')
Edit: "&Edit" ('textE0', 'textE1')
+--------------------------------------------------------------------+
| Directory of all nodenames (must be unique) to look up named nodes |
+--------------------------------------------------------------------+
{
'Edit':<Node 'Edit' at 0x007f9220>,
'Menu Bar':<Node 'Menu Bar' at 0x007f8d10>,
'File':<Node 'File' at 0x007f95b0>,
'Directory':<Node 'Directory' at 0x007f9490>,
'New':<Node 'New' at 0x007f8b90>,
'Folder':<Node 'Folder' at 0x007f94f0>,
}
+-------------------------------+
| Parent links of nodes in dict |
+-------------------------------+
Menu Bar is parent of Edit
(No parent) is parent of Menu Bar
Menu Bar is parent of File
New is parent of Directory
File is parent of New
New is parent of Folder
+-----------------------------------------------------+
| From out of order & reordered input with added item |
+-----------------------------------------------------+
Menu Bar: "Menu Bar" ()
File: "File" ('textFND0', 'textFND1', 'textFND2')
New: "New" ('textFND0', 'textFND1', 'textFND2')
Directory: "&Directory" ('textFND0', 'textFND1', 'textFND2')
Folder: "&Folder" ('textFNF0', 'textFNF1')
Exit: "E&xit" ('TTFN ;-)',)
Edit: "&Edit" ('textE0', 'textE1')
--
You can play with the above interactively, e.g.,
>>> import menutree
>>> mt = menutree.Node.makeTree('Interactive',menutree.inputData)
>>> mt
<Node 'Interactive' at 0x007f9050>
>>> mt.show()
Interactive: "Interactive" ()
>>> md = menutree.Node.makeDict(mt) # make a separate dict
>>> md['New']
<Node 'New' at 0x007fa870>
>>> md['New'].children
[<Node 'Folder' at 0x007fac00>, <Node 'Directory' at 0x007f9730>]
>>> md['New'].parent
<Node 'File' at 0x007f8d60>
>>> md['File']
<Node 'File' at 0x007f8d60>
>>> mt.children[0].children[0]
<Node 'New' at 0x007fa870>
>>> mt.children[0].children[0].getChild('Folder')
<Node 'Folder' at 0x007fac00>
>>> md.get('Folder')
<Node 'Folder' at 0x007fac00>
>>> md['Folder']
<Node 'Folder' at 0x007fac00>
>>> md['New'].show(1)
New: "&New" ('textFN0', 'textFN1')
Folder: "&Folder" ('textFNF0', 'textFNF1')
Directory: "&Directory" ('textFND0', 'textFND1', 'textFND2')
>>> md['New'].getChild('Exit')
Traceback (most recent call last):
File "<stdin>", line 1, in ?
File "menutree.py", line 31, in getChild
raise ValueError, 'Node "%s" has no child named "%s"' % (self.name, name)
ValueError: Node "New" has no child named "Exit"
Well, that demos the exception anyway. Exit was in the other input:
>>> mt2 = menutree.Node.makeTree('Test',menutree.inputData2)
>>> mt2.treeDict = menutree.Node.makeDict(mt2) # attach dict to root
>>> mt2
<Node 'Test' at 0x007fa060>
>>> mt2.treeDict.keys()
['Directory', 'Exit', 'File', 'Test', 'New', 'Folder', 'Edit']
>>> mt2.treeDict['Exit']
<Node 'Exit' at 0x007f8940>
>>> mt2.treeDict['Exit'].parent
<Node 'File' at 0x007fbeb0>
>>> mt2.treeDict['Exit'].parent.parent
<Node 'Test' at 0x007fa060>
>>> mt2.treeDict['Exit'].parent.parent.parent
>>> `mt2.treeDict['Exit'].parent.parent.parent`
'None'
>>> mt2.treeDict['Exit'].attrTup
('TTFN ;-)',)
>>> mt2.treeDict['Exit'].attrTup[0]
'TTFN ;-)'
>structure to just 1 level like this:
>
Seems like a pinched shoe for your concepts ;-)
>In Python:
>----------
>(1)
>
>inputData={'parentKey':[attribute1,attribute2,ptrToChild1,ptrToChild2...], 'child1Key':[attribute1,attribute2,ptrToGrandChild1....]
> 'child2Key':[attribute1,attribute2,None]
> 'grandchild1Key':[attribute1,attribute2,None]
> ..}
>
> OR
>
>(2) inputData= {'parentKey':[attribute1,attribute2,None],
> 'child1Key':[attribute1,attribute2,ptrToParent]
> 'child2Key':[attribute1,attribute2,ptrToParent]
> 'grandchildKey':[attribute1,attribute2,ptrToChild1]
> ..}
>
>(2) In C
>--------
> struct inputData {
> struct inputData *parent;
> char * path;
> char * attribute1;
> char * attribute2;
> }
>
>
>What I was hoping for is to store the reference(not the value) of the
>parent or the child. So if I where to use (2) as my structure and say:
>
> parent=inputData['child1Key'][2]
>
>then I would end up with the reference to the 'parentKey' element. At
>the same time I can use
>
> inputData.has_key(key)
>
>to search for a particular key.
>
I'm still not sure what walks you want to take through the tree, but for
single user interactive, any brute force search should be ok. And now
you can go up and down and sideways ;-)
Note that the extra flat directory is *not* constructed by Node.makeTree,
but instead is done by passing the root node to Node.makeDict. See
interactive log above for examples. These latter methods are static
class methods, so you call them just like plain functions.
I put in the __repr__ method so things would be clearer interactively.
ISTM Python is much nicer than you're letting be to you ;-)
Regards,
Bengt Richter
More information about the Python-list
mailing list