NAME

Tree::Numbered - a thin N-ary tree structure with a unique number for each item.

SYNOPSYS

use Tree::Numbered;
my $tree = Tree::Numbered->new('John Doe');
$tree->append('John Doe Jr.');
$tree->append('Marry-Jane Doe');

while (my $branch = $tree->nextNode) {
   $branch->delete if ($branch->getValue eq 'Stuff I dont want');
}

my $itemId = what_the_DB_says;
print join ' --- ', $tree->follow($itemId); # a list of items up to itemId.

$tree->allProcess( sub {
    my $self = shift;
    $self->getValue =~ /^(\S*)/;
    $self->addField('FirstName', $1);
} );

etc. 

DESCRIPTION

Tree::Numbered is a special N-ary tree with a number for each node. This is useful on many occasions. The first use I found for that (and wrote this for) was to store information about the selected item as a number instead of storing the whole value which is space-expensive.

Every tree also has a lucky number of his own that distinguishes it from other trees created by the same module. This module is thin on purpose and is meant to be a base class for stuff that can make use of this behaveiour. For example, I wrote Tree::Numbered::DB which ties a tree to a table in a database, and Javascript::Menu which uses this tree to build menus for websites.

One more feature that the module implements for the ease of subclassing it is an API for adding and removing fields from trees and nodes.

BUILDING AND DESTROYING A TREE

Tree::Numbered->new

There is only one correct way to start an independent tree with its own lucky number from scratch: calling the class function new. Using new as a method is wrong because it will create a node for the same tree but the tree won't know of its existence. See below.

There are two forms of calling new. The first is calling it with one argument only - the value for the node. If you do that, the tree / node will be created with one field, called 'Value', and this field will receive the value you supplied as an argument.

The second form is calling new with a hash of <field name> => <field value> pairs. For each pair, a field by the name <field name> be created, and it's value will be <field value>. The Value field will not be created unless you specifically request it.

Note: Calling new with no arguments is the same as calling it in the second form.

$tree->clone

Another way to obtain a new tree object is to clone an existing one. The clone method does that. The original object remains untouched.

$tree->append

This is the correct way to add an item to a tree or a branch thereof. Internally uses $tree->new but does other stuff. The arguments for append are the same as for new.

$tree->delete

Deletes the child pointed to by the cursor (see below) and returns the deleted item. Note that it becomes risky to use this item since its parent tree knows nothing about it from the moment it is deleted and you can cause collisions so use with caution.

WORKING WITH FIELDS

As this module is designed for subclassing, I added a mechanism to easily create fields in a tree. Fields are different from normal object attributes in that they are specifically registered as fields within their object, and can be added, removed, and querried for existence. For every field a set of accessors is auto created (actually, autoloaded). In the section 'Subclassing Issues' there's more on using fields vs. regular attributes.

One more important thing to know about fields is that every node inherits all fields that his parent had at the moment of creation. The value of the field is also inherited unless the field was requested in the argument list for append, in which case it takes the value provided as an argument.

Naming your fields: If you want to make use of the automatic accessors, you might want to name your fields with a capital first letter. This is because the accessors created for a field are nothing more then the name of the field prefixed with either 'get' or 'set'. Alternatively, use underscore-lower letter if that's your style.

But what if I only need one field for storing some value?

No problem - The module knows of a default field called 'Value' which is created if you only give one argument - the value - to new or append. When you build a tree like that, you'll have the methods getValue and setValue. Furthermore, the method follow guesses that you want this field if you do not specify any other. So working with one field only is just a short-code version of working with many.

Methods for working with fields:

getFieldNames

Returns a list of all registered fields within a node.

addField(name, [value])

Adds a field only to the node on which the method was invoked. if value is not specified, the field's value will default to undef. If the field does not exist, will do nothing - won't even set its value.

If you need to add a field to all existing descendants of a node (future ones inherit the field automatically) use either deepProcess or allProcess as described above in 'Synopsys'.

Returns: True on success, undef on failure.

removeField(name)

Removes the field by that name, and deletes its value.

Returns: True on success, undef on failure.

getField(name)

Returns the value of the field given in the name argument. if the field does not exist returns undef. If you want to check if the field exists, use hasField or try to call the automatic getter for that field, an attempt that will cause a painfull death if there's no such field.

setField(name, [value])

Sets the value of the requested field. If value is not specified, undef is assumed. Returns the new value on success, undef on failure (field does not exist).

getFields

Returns a reference to a hash of Field => Value pairs, for each field the node owns.

setFields([Field => Value, Field => Value, ...])

Sets the requested fields to the requested values. Keeps quiet if a field does not exist, so watch out.

ITERATING OVER CHILD ITEMS

The cursor

Every node in the tree has its own cursor that points to the current item. When you start iterating, the cursor is placed just before the first child. When you are at the last item, trying to move beyond the last item will put the cursor after the last item (which will result in an undef value, signalling the end) but the next attempt will cause the cursor to start over from the first child.

Methods for iteration

nextNode

Moves the cursor one child forward and returns the pointed child.

reset

Resets the cursor to point before the first child.

savePlace

Allows you to save the cursor's place, do stuff, then go back. There is only one save, though, so don't try to nest saves.

restorePlace

Tries to set the cursor to the item at the same place as it was when its place was saved and returns true on success. If the saved place doesn't exist anymore returns undef. Note: If you deleted items from the tree you might not get to the right place.

ACCESSORS

The following accessors are always available and deal with the node's properties, not with fields:

getNumber

Gets the number of the node within its tree. There is no setter since this number is special.

getLuckyNumber

Gets the number of the main tree that the node is a member of. Again, there is no setter since this is special.

getParentRef

Returns a reference to the parent of the node (of course the root will return undef).

childCount

Gets the number of childs for this node.

Also, as described above, for each field you create, a getter and a setter automatically show up when needed. For each field *, you'll have the methods get* and set*.

THINGS YOU CAN DO WITH NODE NUMBERS

Well, I didn't include the node numbers just for fun, this is actually very needed sometimes. There are three basic service methods that use this (subclasses may add to this):

getSubTree([number])

If a node who's number is given is a member of the subtree that the method was invoked on, that node will be returned, undef otherwise. To be consistent with set theory, any tree is considered to be its own child, so giving the number of the root node will return that node.

listChildNumbers([number])

returns a list of all numbers of nodes that are decendants (any level) of the subtree whose number is given. Number is optional, the node's own number is used if no number is specifically requested.

follow(number, [field])

returns a list of all field values starting from the decendant node with the requested number, through every parent of the node and up to the node the method was invoked on. If no such node exists, returns an empty list. If no field is specified, defaults to the Value field.

OTHER METHODS

There are two methods that apply a certain subroutine to whole trees:

deepProcess (SUBREF, ARG, ARG, ...)

For each child of the node, runs the subroutine referenced by SUBREF with an argument list that starts with a reference to the child being processed and continues with the rest of the arguments passed to deepProcess. In short, your subroutine is called as a method of the child items, so you can shift $self out of the arguments list and use it.

allProcess (SUBREF, ARG, ARG, ...)

does the same as deepProcess but runs on the root node first.

SUBCLASSING ISSUES

Fields vs. normal attributes

The usual implementation of a data field is as a hash key, either in one hash per object, or one hash per property (an inside-out object). The fields mechanism allows you to maintain a list of fields, but assumes that the fields are regular data fields. My subclasses of this modules use Fields for regular data, but do not register as fields anything with 'magical' or 'internal use only' data. The reason is that not using fields gives more control over the behaveiour of these fields.

For example, if you implement a property using the fields mechanism, and you don't want the user to access it, you'll have to manually override the automatic accessors to die or do something unpleasant when they're used.

Secondly, if you register a property as a field - it is easy to remove it by accident even if you count on it to always exist. That's bad, isn't it?

And lastly, if you count on a value to be frequently used, you might not want the overhead of autoloading the accessors or you don't need it in the list of fields.

The benefits of using fields, are in the easiness of managing a set of fields acording to changing demands and the simplicity of extending the behaveiour of a class. For example, check out my Javascript::Menu which creates the URL field if the user is just trying to build a navigational menu, but doesn't bother if the user uses the more complex, action based menus that I designed the module for.

Setting attributes that have no setters

You'll notice that none of the constant properties of this class (the number, lucky number and parent ref) have a setter. This is on purpose. These properties are determined automatically and are not supposed to be messed with.

If you do want to change the behaveiour, I assume that you know what you're doing and that you have read some source. Then you'll have no problem with implementing your desired behaveiour.

Extending field behaveiour

The fields mechanism, however, is more object-oriented. Everything that has to do with fields tries to use field methods even internally. Even new calls addField to add fields. The main implication of this (that I found) is that if you want things to happen when a field is created, you must make sure that the data for this happening (if any is required) is already available at the time of adding the field. For an example of that, see how my Tree::Numbered::DB makes sure that a field mapping will always be available, before calling SUPER::new in its own constructor.

BUGS AND PROBLEMS

Works pretty well for me. If you found anything, please send a bug report: <http://rt.cpan.org/NoAuth/Bugs.html?Dist=Tree-Numbered> or send mail to <bug-Tree-Numbered#rt.cpan.org>

SEE ALSO

Tree::Numbered::DB, Javascript::Menu

AUTHOR

Yosef Meller, < mellerf@netvision.net.il >

COPYRIGHT AND LICENSE

Copyright 2003 by Yosef Meller

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.

cpanm Tree::Numbered

perl -MCPAN -e shell
install Tree::Numbered