Python论坛的帖子：

星期二十一月 6 18:50:44 HKT 2007

Hello,

Recently I'm working on a new data structure written in python: Tree,
by operator overloading. I want it can act as a builtin type, such as
list and dict, but do something like a tree, to make those things need
trees can be more convenient.

For example,
1. to create a Tree, there are several ways:
(1) A empty Tree:
>>> root = Tree(None)
>>> print root
  ** Tree **
    () : None,

(2) A tree like this:
    root('zero')
      \--trunk('a')
      \--branch(1)
>>> root = Tree('zero', trunk='a', branch=1)
>>> print root
  ** Tree **
    ('trunk',) : 'a',
    () : 'zero',
    ('branch',) : 1,

(3) With items:
>>> root = Tree('zero', trunk='a', branch=1, _node_items={'try' : 'x'})
>>> print root
  ** Tree **
    ('trunk',) : 'a',
    () : 'zero',
    (('try',),) : 'x',
    ('branch',) : 1,
or like this:
>>> root = Tree('value', {'x' : 'v1', 'y' : 2}, trunk='v3', branch=4)
>>> print root
  ** Tree **
    ('trunk',) : 'v3',
    () : 'value',
    (('y',),) : 2,
    ('branch',) : 4,
    (('x',),) : 'v1',

The items can be considered as attributes of a Tree node, something like
XML attr? '')

(4) A more complicated one:
>>> root = Tree('value', {'x' : 'v1', 'y' : Tree(2, {'z' : 'v3'}, br=4)},
trunk='v5', branch=Tree(6, {'a' : 'v7'}, br=8))
>>> print root
  ** Tree **
    ('branch', ('a',)) : 'v7',
    (('y',),) : 2,
    ('branch',) : 6,
    ('branch', 'br') : 8,
    ('trunk',) : 'v5',
    (('x',),) : 'v1',
    (('y', 'z'),) : 'v3',
    () : 'value',
    (('y',), 'br') : 4,

2. Or create a Tree with setattr syntax :
>>> root = Tree(None)
>>> root = Tree('value')
>>> root['x'] = 'v1'
>>> root['y'] = 2
>>> root.trunk = 'v5'
>>> root.branch = 6
>>> root['x']['z'] = 'v3'
>>> root['x'].br = 4
>>> root.branch['a'] = 'v7'
>>> root.branch.br = 8
>>> print root
  ** Tree **
    ('branch', ('a',)) : 'v7',
    () : 'value',
    (('y',),) : 2,
    ('branch',) : 6,
    ('branch', 'br') : 8,
    ('trunk',) : 'v5',
    (('x', 'z'),) : 'v3',
    (('x',),) : 'v1',
    (('x',), 'br') : 4,

3. It's very simple to retrive the value of any given Tree node:
>>> print root
  ** Tree **
    (('x', 'y'),) : 'xy',
    (('y',),) : 3,
    ('branch',) : 7,
    ('trunk', ('a',)) : 5,
    ('trunk',) : 4,
    (('x',),) : 1,
    ('trunk', ('a', 'b'), 'data') : ['trunk', 'ab', 6],
    () : 0,
    (('x',), 'data') : ['x', 2],
    ('trunk', ('a', 'b')) : 'trunk ab',
    ('trunk', ('a',), 'data') : 'a data',
    ('branch', 'data') : 8,
>>> root()
0
>>> root.trunk()
4
>>> root.branch()
7
>>> root['x']

>>> root['x']()
1
>>> root['x'].data()
['x', 2]

4. As you have seen, the "print" operation of course have traversed the
Tree. Traverse return a path sequences to nodes map(dict) --
Tree<http://crablfs.sourceforge.net/tree.html#Tree>
 dict, every
item represents a single Tree<http://crablfs.sourceforge.net/tree.html#Tree>
 node. It't better to be called by
__call__ <http://crablfs.sourceforge.net/tree.html#Tree-__call__>
('traverse'), for example:
root('traverse') will return:
treedict = {
{
        () : Tree <http://crablfs.sourceforge.net/tree.html#Tree>(0),
        (('x',),) : Tree <http://crablfs.sourceforge.net/tree.html#Tree>(1),
        (('x',), 'data') : Tree<http://crablfs.sourceforge.net/tree.html#Tree>
(['x', 2]),
        (('x', 'y'),) : Tree <http://crablfs.sourceforge.net/tree.html#Tree>
('xy'),
        (('y',),) : Tree <http://crablfs.sourceforge.net/tree.html#Tree>(3),
        ('trunk',) : Tree <http://crablfs.sourceforge.net/tree.html#Tree>
(4),
        ('trunk', ('a',)) : Tree<http://crablfs.sourceforge.net/tree.html#Tree>
(5),
        ('trunk', ('a',), 'data') :
Tree<http://crablfs.sourceforge.net/tree.html#Tree>
("a data"),
        ('trunk', ('a', 'b')) :
Tree<http://crablfs.sourceforge.net/tree.html#Tree>
("trunk ab"),
        ('trunk', ('a', 'b'), 'data') :
Tree<http://crablfs.sourceforge.net/tree.html#Tree>
(['trunk', 'ab', 6]),
        ('branch',) : Tree <http://crablfs.sourceforge.net/tree.html#Tree>
(7),
        ('branch', 'data') : Tree<http://crablfs.sourceforge.net/tree.html#Tree>
(8)
}

5. Update a Tree with another one:
>>> def build_tree1():
        root['x'] = '1x'
...     root = Tree(0)
        root.trunk['a'] = 5
...     root['x'] = '1x'
        root.branch.data.extra = ['extra', 'info']
...     root['x'].data = 1
...     root['x']['y'] = '1xy'
...     root['x']['y'].data = 2
...     root['y'] = 3
...     root.trunk = 4
...     root.trunk['a'] = 5
...     root.trunk['a'].data = '5'
...     root.trunk['x'] = '2x'
...     root.trunk ['x'].data = 6
...     root.trunk['x']['y'] = '2xy'
...     root.trunk['x']['y'].data = 7
...     root.branch = 8
...     root.branch.data = 9
...     root.branch.data.extra = ['extra', 'info']
...     return root
...
>>> def build_tree2():
        root['x'] = '1.x'
...     root = Tree('0')
        root.trunk['x'] = ' two.x'
...     root['x'] = '1.x'
        root.branch.new = 'attr.new'
        return root...     root['x'].data = '1'
...     root['new'] = '1.new'
...     root.trunk = '4'
...     root.trunk['a'] = "a test"
...     root.trunk['x'] = None
...     root.trunk['b'] = 'b'
...     root.trunk['x'] = ' two.x'
...     root.trunk['x']['y'] = '2.xy'
...     root.trunk['x']['y'].data = '7'
...     root.trunk['new'] = '2.new'
...     root.trunk['new'].data = ' 2.new.data'
...     root.branch = '8'
...     root.branch.new = 'attr.new'
...     return root
...
>>> tree1 = build_tree1()
>>> tree2 = build_tree2()

Then you can update tree1 like these to build a new Tree:
>>> tree1('update', tree2)
>>> print tree1
  ** Tree **
    ('branch', 'data', 'extra') : ['extra', 'info'],
    ('branch', 'new') : 'attr.new',
    ('trunk', ('x', 'y')) : '2.xy',
    ('trunk', ('x',), 'data') : 6,
    ('branch',) : '8',
    ('trunk', ('x', 'y'), 'data') : '7',
    (('x',), 'data') : '1',
    ('trunk',) : '4',
    ('trunk', ('new',), 'data') : ' 2.new.data',
    ('trunk', ('new',)) : '2.new',
    ('trunk', ('x',)) : 'two.x',
    (('x',),) : '1.x',
    ('trunk', ('a',)) : 'a test',
    () : '0',
    (('y',),) : 3,
    (('x', 'y'),) : '1xy',
    ('trunk', ('a',), 'data') : '5',
    ('trunk', ('b',)) : 'b',
    ('branch', 'data') : 9,
    (('new',),) : '1.new',
    (('x', 'y'), 'data') : 2,

You can also use "+=" operator to do this:
>>> tree1 = build_tree1()
>>> tree1 += tree2
>>> print tree1
  ** Tree **
    ('branch', 'data', 'extra') : ['extra', 'info'],
    ('branch', 'new') : 'attr.new ',
    ('trunk', ('x', 'y')) : '2.xy',
    ('trunk', ('x',), 'data') : 6,
    ('branch',) : '8',
    ('trunk', ('x', 'y'), 'data') : '7',
    (('x',), 'data') : '1',
    ('trunk',) : '4',
    ('trunk', ('new',), 'data') : '2.new.data',
    ('trunk', ('new',)) : ' 2.new',
    ('trunk', ('x',)) : 'two.x',
    (('x',),) : '1.x',
    ('trunk', ('a',)) : 'a test',
    () : '0',
    (('y',),) : 3,
    (('x', 'y'),) : '1xy',
    ('trunk', ('a',), 'data') : '5',
    ('trunk', ('b',)) : 'b',
    ('branch', 'data') : 9,
    (('new',),) : '1.new',
    (('x', 'y'), 'data') : 2,

Or use "+" to build a new Tree:
>>> tree3 = tree1 + tree2

6. Compare 2 Trees:
Compare the root node value first, and if equal, compare their sub nodes,
attributes or items ...

7. Some other functions that have not been implemented ...

============
So far I use this Tree as a direct configuration method. For instance,
in my another project cutils which has a tool to do realtime file system
mirroring, the configuration file is like this:
sh# cat /etc/python/fs_mirror
"""
The configuration file for fs_mirror
"""

import tree
options = tree.Tree('fs_mirror')
o = options

#o.mode = 'daemon'
# There can be other mode, such as "run_once"

#o.host = 'localhost'
#o.port = 2123
# The server runs mirrord
#o.timeout = 60

#o.daemon = None
#o.daemon.datadir = "/var/fs_mirror"
# The mirrored dirs/files will be put into this directory

#o.fssync = 'Report'
# The synchronization mechanism you choose, it can be one of:
#    FTP, NFS, SMB/CIFS, SSH, RSYNC, ...
#    REPORT only reports the actions in wmLog,
#        does not do actual dirs creating or files transport
###o.fssync.host = 'localhost'
# Must be the same as o.host?
#o.fssync.port = 0
#o.fssync.user = 'root'
#o.fssync.passwd = ''
# Since it contains passord, you'd better keep this configuration file
secret.
# You can put the id/password pair to a secret file, such as
#    ~/.fs_mirror/secret
#    $host:$password
#    and use --password-from ~/.fs_mirror/secret:$host
#        option of fs_mirror script to appoint the password
# By this way, another user can not view the passwords by run "ps"
#        when you appointed the it from the command line option.
# The reason a command line options is used is for multi-mirroring

And the script read and analyze this configuration file can be written
like this:
...
CONFIG_MODULE_PATH = "/etc/python"
...
    options = tree.Tree('fs_mirror')
    options.mode = 'daemon'
    options.host = 'localhost'
    options.port = 2123
    options.timeout = 60
    options.daemon = None
    options.daemon.datadir = "/var/fs_mirror"
    options.fssync = 'Report'
    options.fssync.port = 0
    options.fssync.user = 'root'
    options.fssync.passwd = ''

    # Update options from a configuration file:
    try:
        sys.path.insert (0, CONFIG_MODULE_PATH)
        try:
            import fs_mirror_config as config
            options('update', config.options)
        except ImportError:
            pass
        sys.path.pop(0)
    except tree.TreeExc, trexc:
        strerr = "Invalid option because of: %s" % trexc.msg
        print >> sys.stderr, strerr
        syslog.syslog(syslog.LOG_ERR, strerr)
        sys.exit (1)

    # Update options from command line parameters:
    opts, args = getopt.gnu_getopt(sys.argv[1:], 'm:h:p:t:o:v',
        ['mode=', 'host=', 'port=', 'timeout=', 'option=', 'datadir=',
'help', 'verbose', 'password-from='])
    if args:
        options.identities = args
    ov = []
    for o, v in opts:
        if o == '-m' or o == '--mode':
            options.mode = v
        elif o == '-h' or o == '--host':
            options.host = v
        elif o == '-p' or o == '--port':
            options.port = int(v)
        elif o == '-t' or o == '--timeout':
            options.timeout = int(v)
        elif o == "--datadir":
            options.daemon.datadir = v
        elif o == '-o' or o == '--option':
            ov.append(v)
        elif o == '--help':
            print usage
            sys.exit(0)
        elif o == '-v' or o == '--verbose':
            fs_mirror.debug = 1
            fs_sync.debug = 1
        elif o == '--password-from':
            try:
                fname, hostid = v.split(':')
            except ValueError:
                raise ValueError, "Invalid secret-file:id pair for
--passwd-from"
            for line in open(fname, 'r'):
                line = line.strip()
                try:
                    id, passwd = line.split(':')
                    if id == hostid:
                        options.fssync.passwd = passwd
                        break
                except ValueError:
                    raise ValueError, "Invalid id:password pair record '%s'"
% line
    options('update', oparse(ov))

You can find the document of "cutils" project at:
http://crablfs.sourceforge.net <http://crablfs.sourceforge.net/tree.html>
/#ru_data_man
and download it from:
http://sourceforge.net/projects/crablfs
 <http://crablfs.sourceforge.net/tree.html>
But I think this Tree structure can also be used in other ways. For
example, I think it's possible to implement an API to read XML into such
structure ...

============
Luckily the basic definition has been finished now, you can also download
it from:
http://sourceforge.net/projects/crablfs
the document is in the code and unittest. And I have put the HTML at:
http://crablfs.sourceforge.net/tree.html

The source code is in SVN:
https://crablfs.svn.sourceforge.net/svnroot/crablfs/caxes/trunk/>
the files are tree.py and test_tree.py.

I hope this can be useful to you. Maybe I can write a PEP? Looking
forward to your suggestions and advices...

I'm not so expericenced, and this is only a partial finished work, since
I can only squash my limited spare time to do this and there is several
projects I have started. There are many things to learn, and now I'm
learning from you '')

Thank you.

-- 
------------------------------------------------------------------------
My Projects:
http://sourceforge.net/projects/crablfs
http://crablfs.sourceforge.net/
http://crablfs.sourceforge.net/#ru_data_man
http://crablfs.sourceforge.net/tree.html
http://cralbfs.sourceforge.net/sysadm_zh_CN.html
My Blog:
http://chowroc.blogspot.com/
http://hi.baidu.com/chowroc_z/
Looking for a space and platform to exert my originalities (for my
projects)...
-------------- ä¸ä¸é¨å --------------
??HTML?????...
URL: http://python.cn/pipermail/python-chinese/attachments/20071106/5706807f/attachment-0001.html 

标题：[python-chinese] What about a Python Tree container?