develooper Front page | perl.module-authors | Postings from February 2005

what to name this data-structure (and the module it rode in on)

Thread Next
Eric Wilhelm
February 7, 2005 15:42
what to name this data-structure (and the module it rode in on)
Message ID:
I'm not sure if there was such a thing before I wrote this module.  I
needed something that would allow me to compactly express an ordered
tree while simultaneously attaching meta-data and contents to nodes of
the tree.  So, this is like a cross between a tree and a table.
Currently, I've named it Tree::Meta.

The important thing to me was being able to compactly express the tree
structure, order, and properties in an input file.  However, while
working on that I kept remembering some of the multiple-data-structure
code that I had written before (such as using one table to hold
properties, another to hold contents, and then having a hash to
facilitate random-access lookups.)  So, I went for something like an
in-memory filesystem with metadata and ordered hashes tacked onto it.

The code is only in my subversion server at the moment:

Documentation is below.

Any suggestions, comments, references, etc. are welcome.  Mostly, I
would like to know if there is a name for such a beast, and/or whether
it's been done before.  If it's been done before, I guess I've
reinvented the wheel, but I wouldn't have been able to explain what I
was looking for (or know what to search) before having written the code
to see if it would actually work.



    Tree::Meta - A filesystem-like tree with metadata

 I don't know if such a thing exists or makes any sense, but it seems
 like a step toward solving my data-structure head-scratching in the
 general case (maybe I'm just crazy.)

 The best name that I can come up with is "an n-ary tree with
 contents and metadata". This basically means that we have an ordered
 hash tree, where each node has contents and properties. The best
 mapping onto existing concepts that I can think of is that it is
 like a filesystem (with directories and files), but with metadata
 attached to each node.  Something of a tree and a table. Feel free
 to give me suggestions on what to call it. If it's been done before,
 that's great too (what was it called?)

 Currently, we can only read input from a file, which is a variation
 on YAML (but not parse-able with the YAML parser.)

    Given the following file:

      --- #notYAML:1.0
      - foo:
        owner: me
        - file:
          status: new
          - "hello world\n"
          - "nice day, isn't it?\n"
        - directory1:
          - emptyfile1:
            - ""
          - emptyfile2:
            - ""
          - emptydir:
      - bar:
        importance: 1
        - important_file:
          - "bank password:  984"
      purpose: example
      usefulness:  nil

    And this code:

      use Tree::Meta;
      my $tree = Tree::Meta->load(\*STDIN);
      print "toplevel nodes:  ", join(",", $tree->contains()), "\n";
      my %props = $tree->about();
      print "properties:  ", join(",", keys(%props)), "\n";
      print "nodes:", join("\n  ", '', $tree->recurse()), "\n";

    We would get this output:

      toplevel nodes:  foo,bar
      properties:  usefulness,purpose

      Eric L. Wilhelm
      ewilhelm at sbcglobal dot net

    This module is copyright (C) 2005 by Eric L. Wilhelm.

 This module is distributed under the same terms as Perl. See the
 Perl source package for details.

    You may use this software under one of the following licenses:

      (1) GNU General Public License
        (found at
      (2) Artistic License
        (found at

 This software is distributed with ABSOLUTELY NO WARRANTY. The author
 and any other contributors will in no way be held liable for any
 loss or damages resulting from its use.

 The source code of this module is made freely available and
 distributable under the GPL or Artistic License. Modifications to
 and use of this software must adhere to one of these licenses.
 Changes to the code should be noted as such and this notification
 (as well as the above copyright information) must remain intact on
 all copies of the code.

 Additionally, while the author is actively developing this code,
 notification of any intended changes or extensions would be most
 helpful in avoiding repeated work for all parties involved. Please
 contact the author with any such development plans.


      0.01 First public release.

    Don't call this, see load_file() or load().

      $tree = Tree::Meta->new();

    Read from a file.

      $tree = Tree::Meta->load_file($filename);

    This file format is a perversion of YAML (since we're trying to
    represent a data-structure that doesn't exist.)

      $tree= Tree::Meta->load($filehandle);

    Read through list (calling myself if necessary.) Return values...?

    The tree is made up of values (keys), properties, and contents. Each
    value has a list of properties associated with it and a list of
    contents. The content is a list of trees.

      $tree->reader(\@list, $indent, $level);

    Fetch a given node (returns a tree object.)

      $root = $tree->fetch($node);

    Return a list of all nodes below $node.

      @list = $tree->recurse($node);

    Returns 1 if the node is a directory, 2 if it is a file.


    Returns true if the node is a directory.


    Returns true if the node is a file.


    Returns the metadata hash for the given node.

      %about = $tree->about($node);

 Returns a list of contents for the given node. If the node is a
 directory, this will contain the list of files and directories
 contained therein. If the node is a file, it will be the contents of
 that file.

      @list = $tree->contains($node);

Thread Next Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About