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
From:
Eric Wilhelm
Date:
February 7, 2005 15:42
Subject:
what to name this data-structure (and the module it rode in on)
Message ID:
200502071747.15218.ewilhelm@sbcglobal.net
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:
  http://ericwilhelm.homeip.net/Tree-Meta/trunk/code/perl/lib/Tree/Meta.pm

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.

Thanks,
Eric

--

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

ABOUT
 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?)

SYNOPSIS
 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
      nodes:
        /foo
        /foo/file
        /foo/directory1
        /foo/directory1/emptyfile1
        /foo/directory1/emptyfile2
        /foo/directory1/emptydir
        /bar
        /bar/important_file

AUTHOR
      Eric L. Wilhelm
      ewilhelm at sbcglobal dot net
      http://pages.sbcglobal.net/mycroft/

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

LICENSE
 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 http://www.gnu.org/copyleft/gpl.html)
      (2) Artistic License
        (found at http://www.perl.com/pub/language/misc/Artistic.html)

NO WARRANTY
 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.

Modifications
 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.

SEE ALSO
      Tree::Simple
      Tie::Hash::Indexed
      Tie::IxHash

CHANGES
      0.01 First public release.

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

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

  load_file
    Read from a file.

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

  load
    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);

  reader
    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);

Methods
  fetch
    Fetch a given node (returns a tree object.)

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

  recurse
    Return a list of all nodes below $node.

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

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

      $tree->type($node);

  is_dir
    Returns true if the node is a directory.

      $tree->is_dir($node);

  is_file
    Returns true if the node is a file.

      $tree->is_file($node);

  about
    Returns the metadata hash for the given node.

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

  contains
 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


nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About