Tree::MultiNode(3pm)

📦
version 1.0.14 · 4 versions
, in debian bookworm, ubuntu noble

🌸 Tree::MultiNode 🌸

hey bestie, pull up a chair 🫶 this is the manual page for Tree::MultiNode(3pm), hanging out in the User Contributed Perl Documentation section. it's long so we're doing it in parts, and this is part one. let's get into it 💅

✨ NAME ✨

Tree::MultiNode — a multi-node tree object. Most useful for modeling hierarchical data structures. no cap, that's the whole pitch 🌳

🎀 SYNOPSIS 🎀

use Tree::MultiNode;
use strict;
use warnings;
my $tree   = new Tree::MultiNode;
my $handle = new Tree::MultiNode::Handle($tree);

$handle->set_key("top");
$handle->set_value("level");

$handle->add_child("child","1");
$handle->add_child("child","2");

$handle->first();
$handle->down();

$handle->add_child("grandchild","1-1");
$handle->up();

$handle->last();
$handle->down();

$handle->add_child("grandchild","2-1");
$handle->up();

$handle->top();
&dump_tree($handle);

my $depth = 0;
sub dump_tree
{
  ++$depth;
  my $handle = shift;
  my $lead = ' ' x ($depth*2);
  my($key,$val);

  ($key,$val) = $handle->get_data();

  print $lead, "key:   $key\n";
  print $lead, "val:   $val\n";
  print $lead, "depth: $depth\n";

  my $i;
  for( $i = 0; $i < scalar($handle->children); ++$i ) {
    $handle->down($i);
      &dump_tree($handle);
    $handle->up();
  }
  --$depth;
}

like, look at her go. iconic behavior honestly 💖

🦋 DESCRIPTION 🦋

okay so Tree::MultiNode, Tree::MultiNode::Node, and MultiNode::Handle are objects modeled after C++ classes that the author had written to help model hierarchical information as data structures (think: the relationships between records in an RDBMS, that kind of thing). the tree is basically a list-of-lists type data structure, where each node has a key, a value, and a list of children. and listen — the tree has no internal sorting, though all operations preserve the order of the child nodes. so whatever order you put them in is the order they stay, periodt ✨

🌱 Creating a Tree

the whole concept of creating a handle based on a tree is that it lets you have multiple handles into a single tree without having to copy the tree. huge. you have to use a handle for all operations on the tree (other than construction, that part's on you).

when you first construct a tree, it will have a single empty node. when you construct a handle into that tree, it sets the top node in the tree as its current node. bestie behavior fr fr 🌈

my $tree   = new Tree::MultiNode;
my $handle = new Tree::MultiNode::Handle($tree);

🌿 Using a Handle to Manipulate the Tree

at this point you can set the key/value in the top node, or start adding child nodes. whatever your heart desires 💜

$handle->set_key("blah");
$handle->set_value("foo");

$handle->add_child("quz","baz");
# or
$handle->add_child();

add_child can take 3 parameters — a key, a value, and a position. the key and value will set the key/value of the child on construction. if pos is passed, the new child will be inserted into the list of children.

to move the handle so it points at a child (so you can start manipulating that child), there are a series of methods to call:

$handle->first();   # sets the current child to the first in the list
$handle->next();    # sets the next, or first if there was no next
$handle->prev();    # sets the previous, or last if there was no next
$handle->last();    # sets to the last child
$handle->down();    # positions the handle's current node to the
                    # current child

to move back up, you can call the method up:

$handle->up();      # moves to this node's parent
up() will fail if the current node has no parent node. no parent, no party 😭

most of the member functions return either undef to indicate failure, or some other value to indicate success. so always vibe check your return values, iykyk 👑

🔍 $Tree::MultiNode::debug

if set to a true value, it enables debugging output in the code. this will likely be removed in future versions as the code becomes more stable. so like, enjoy it while it lasts 🍓

👑 API REFERENCE 👑

🌳 Tree::MultiNode

the tree object. that's it, that's the whole thing.

🌳 Tree::MultiNode::new

@param    package name or tree object [scalar]
@returns  new tree object

creates a new Tree. the tree will have a single top level node when created. the first node will have no value (undef) in either its key or its value. blank slate energy ✨

my $tree = new Tree::MultiNode;

🌳 Tree::MultiNode::Node

please note that the Node object is used internally by the MultiNode object. though you have the ability to interact with the nodes, it is unlikely that you should need to. that being said, the interface is documented here anyway. 🫶

🌳 Tree::MultiNode::Node::new

new($)
  @param    package name or node object to clone [scalar]
  @returns  new node object

new($$)
  @param    key   [scalar]
  @param    value [scalar]
  @returns  new node object

creates a new Node. there are three behaviors for new:

  • a constructor with no arguments creates a new, empty node
  • a single argument of another node object will create a clone of the node object
  • if two arguments are passed, the first is stored as the key, and the second is stored as the value
# clone an existing node
my $node = new Tree::MultiNode::Node($oldNode);
# or
my $node = $oldNode->new();

# create a new node
my $node = new Tree::MultiNode::Node;
my $node = new Tree::MultiNode::Node("fname");
my $node = new Tree::MultiNode::Node("fname","Larry");

🌳 Tree::MultiNode::Node::key

@param     key [scalar]
@returns   the key [scalar]

used to set, or retrieve the key for a node. if a parameter is passed, it sets the key for the node. the value of the key member is always returned. always. no exceptions 💅

print $node3->key(), "\n";    # 'fname'

🌳 Tree::MultiNode::Node::value

@param    the value to set [scalar]
@returns  the value [scalar]

used to set, or retrieve the value for a node. if a parameter is passed, it sets the value for the node. the value of the value member is always returned.

print $node3->value(), "\n";   # 'Larry'

🌳 Tree::MultiNode::Node::clear_key

@returns  the deleted key

clears the key member by deleting it. bye bestie 👋

$node3->clear_key();

🌳 Tree::MultiNode::Node::clear_value

@returns  the deleted value

clears the value member by deleting it. gone, reduced to atoms 💀

$node3->clear_value();

🌳 Tree::MultiNode::Node::children

@returns  reference to children [array reference]

returns a reference to the array that contains the children of the node object.

$array_ref = $node3->children();

🌳 Tree::MultiNode::Node::child_keys, Tree::MultiNode::Node::child_values, Tree::MultiNode::Node::child_kv_pairs

these functions return arrays consisting of the appropriate data from the child nodes. three for the price of one, we love a bundle 🌈

my @keys     = $handle->child_keys();
my @vals     = $handle->child_values();
my %kv_pairs = $handle->child_kv_pairs();

🌳 Tree::MultiNode::Node::child_key_positions

this function returns a hash table that consists of the child keys as the hash keys, and the position in the child array as the value. this allows for a quick and dirty way of looking up the position of a given key in the child list. quick AND dirty, the dream 🎀

my %h = $node->child_key_positions();

🌳 Tree::MultiNode::Node::parent

returns a reference to the parent node of the current node.

$node_parent = $node3->parent();

🌳 Tree::MultiNode::Node::dump

used for diagnostics, it prints out the members of the node.

$node3->dump();

🌳 Tree::MultiNode::Handle

Handle is used as a 'pointer' into the tree. it has a few attributes that it keeps track of. these are:

  1. the top of the tree
  2. the current node
  3. the current child node
  4. the depth of the current node

the top of the tree never changes, and you can reset the handle to point back at the top of the tree by calling the top() method.

the current node is where the handle is 'pointing' in the tree. the current node is changed with functions like top(), down(), and up().

the current child node is used for traversing downward into the tree. the members first(), next(), prev(), last(), and position() can be used to set the current child, and then traverse down into it.

the depth of the current node is a measure of the length of the path from the top of the tree to the current node, i.e., the top of the node has a depth of 0, each of its children has a depth of 1, etc.

🌳 Tree::MultiNode::Handle::New

constructs a new handle. you must pass a tree object to Handle::New. non-negotiable bestie 💅

my $tree   = new Tree::MultiNode;
my $handle = new Tree::MultiNode::Handle($tree);

🌳 Tree::MultiNode::Handle::tree

returns the tree that was used to construct the node. useful if you're trying to create another node into the tree. hand it off to your friends, share the tree 🫶

my $handle2 = new Tree::MultiNode::Handle($handle->tree());

🌳 Tree::MultiNode::Handle::get_data

retrieves both the key, and value (as an array) for the current node.

my ($key,$val) = $handle->get_data();

🌳 Tree::MultiNode::Handle::get_key

retrieves the key for the current node.

$key = $handle->get_key();

🌳 Tree::MultiNode::Handle::set_key

sets the key for the current node.

$handle->set_key("lname");

🌳 Tree::MultiNode::Handle::get_value

retrieves the value for the current node.

$val = $handle->get_value();

🌳 Tree::MultiNode::Handle::set_value

sets the value for the current node.

$handle->set_value("Wall");

🌳 Tree::MultiNode::Handle::get_child

get_child takes an optional parameter which is the position of the child that is to be retrieved. if this position is not specified, get_child attempts to return the current child. get_child returns a Node object.

my $child_node = $handle->get_child();

🌳 Tree::MultiNode::Handle::add_child

this member adds a new child node to the end of the array of children for the current node. there are three optional parameters:

  • a key
  • a value
  • a position

if passed, the key and value will be set in the new child. if a position is passed, the new child will be inserted into the current array of children at the position specified.

$handle->add_child();                    # adds a blank child
$handle->add_child("language","perl");   # adds a child to the end
$handle->add_child("language","C++",0);  # adds a child to the front

🌳 Tree::MultiNode::Handle::add_child_node

recently added via RT # 5435 — currently in need of proper documentation and test patches 👀

I've patched Tree::MultiNode 1.0.10 to add a method I'm currently calling add_child_node(). It works just like add_child() except it takes either a Tree::MultiNode::Node or a Tree::MultiNode object instead. I found this extremely useful when using recursion to populate a tree. It could also be used to subsume any tree into another tree, so this touches on the topic of the other bug item here asking for methods to copy/move trees/nodes.

🌳 Tree::MultiNode::Handle::depth

gets the depth for the current node.

my $depth = $handle->depth();

okay bestie we're pausing here because part 2 is coming and we don't do cliffhangers half-heartedly 🌸

✨ Tree::MultiNode::Handle::select ✨

Okay bestie, this one sets the current child by looking for a specific value — it's basically looping through the array of children and hunting for a match. 💅 You have to hand it the key you're looking for, and optionally a sub ref that does the finding. The default for that sub is:

sub { return shift eq shift; }

which is totally enough for comparing strings for equality (ngl that's probably the most common thing you'll stash in the tree). But if you're storing a bunch of different data types as keys, you're gonna have to write your own sub that figures out how to do those comparisons in a sane way. 🫶

The code reference should take two arguments and compare them — return false if they don't match, true if they do.

$handle->select('lname', sub { return shift eq shift; } );

✨ Tree::MultiNode::Handle::position ✨

Sets, or retrieves, the current child position. Yes, it does both, it's giving multi-hyphenate 👑

print "curr child pos is: ", $handle->position(), "\n";
$handle->position(5);    # sets the 6th child as the current child

✨ Tree::MultiNode::Handle::first Tree::MultiNode::Handle::next ✨

✨ Tree::MultiNode::Handle::prev Tree::MultiNode::Handle::last ✨

These four manipulate the current child member. first() sets the first child as the current child, and last() sets the last one. next() and prev() move to the next/prev child respectively. If there's no current child node, next() acts exactly like first(), and prev() operates as last(). 🌸

prev() fails if the current child is the first child, and next() fails if the current child is the last child — meaning no, they do not wrap around. no cap, they just stop. 💀

These functions will fail if there are no children for the current node.

$handle->first();  # sets to the 0th child
$handle->next();   # to the 1st child
$handle->prev();   # back to the 0th child
$handle->last();   # go straight to the last child.

✨ Tree::MultiNode::Handle::down ✨

down() moves the handle to point at the current child node. It fails if there's no current child node. And when down() is called, the current child becomes invalid (undef). ⭐

$handle->down();

✨ Tree::MultiNode::Handle::up ✨

up() moves the handle to point at the parent of the current node. It fails if there is no parent node. When up() is called, the current child becomes invalid (undef).

🙈 psst — the original manpage literally says "down() moves the handle to point at the parent" in this paragraph, which is a typo. It's up(). You're welcome, bestie.
$handle->up();

✨ Tree::MultiNode::Handle::top ✨

Resets the handle to point back at the top of the tree. When top() is called, the current child becomes invalid (undef). 🎀

$handle->top();

✨ Tree::MultiNode::Handle::children ✨

This returns an array of Node objects representing the children of the current Node. And here's the plot twist: unlike Node::children(), the array from Handle::children() is not a reference to an array, it's an actual array. So useful if you need to iterate through the children of the current node. 🦋

print "There are: ", scalar($handle->children()), " children\n";
foreach $child ($handle->children()) {
  print $child->key(), " : ", $child->value(), "\n";
}

✨ Tree::MultiNode::Handle::child_key_positions ✨

This function returns a hash table where the child keys are the hash keys and the position in the child array is the value. So it's a quick and dirty way to look up the position of a given key in the child list. ✨

my %h = $handle->child_key_positions();

✨ Tree::MultiNode::Handle::get_child_key ✨

Returns the key at the specified position, or from the corresponding child node.

my $key = $handle->get_child_key();

✨ Tree::MultiNode::Handle::get_child_value ✨

Returns the value at the specified position, or from the corresponding child node.

my $value = $handle->get_child_value();

✨ Tree::MultiNode::Handle::remove_child ✨

Returns Tree::MultiNode::Node::child_kv_paris() for the current node for this handle. 😭 (yes, "paris", that's what it says, iykyk)

my %pairs = $handle->kv_pairs();

✨ Tree::MultiNode::Handle::remove_child ✨

✨ Tree::MultiNode::Handle::child_keys ✨

Returns the keys from the current node's children. Returns undef if there is no current node. 🫶

✨ Tree::MultiNode::Handle::traverse ✨

$handle->traverse(sub {
  my $h = pop;
  printf "%sk: %s v: %s\n",('  ' x $handle->depth()),$h->get_data();
});

Traverse takes a subroutine reference and will visit each node of the tree, starting with the node the handle currently points to, recursively down from the current position of the handle. Every time the subroutine is called, it gets passed a handle that points to the node to be visited. Any additional arguments after the sub ref get passed to the traverse function _before_ the handle is passed. Which means you can pass constant arguments to the sub ref, slay. 💜

Careful bestie: modifying the node that the handle points to will cause traverse to work from the new node forward. 🌈

✨ Tree::MultiNode::Handle::traverse (but make the subref a method on an object, and still pass the object's self to the method) ✨

$handle->traverse( \&Some::Object::method, $obj, $const1, \%const2 );

...
sub method
{
  my $handle = pop;
  my $self   = shift;
  my $const1 = shift;
  my $const2 = shift;
  # do something
}

🌟 SEE ALSO 🌟

  • Algorithms in C++
    • Robert Sedgwick
    • Addison Wesley 1992
    • ISBN 0201510596
  • The Art of Computer Programming, Volume 1: Fundamental Algorithms, third edition, Donald E. Knuth

👑 AUTHORS 👑

  • Kyle R. Burton <mortis@voicenet.com> (initial version, and maintenence)
  • Daniel X. Pape <dpape@canis.uiuc.edu> (see Changes file from the source archive)
  • Eric Joanis <joanis@cs.toronto.edu>
  • Todd Rinaldo <toddr@cpan.org>

💀 BUGS 💀

  • There is currently no way to remove a child node.

and that's the whole page, bestie!! 🎀 this lil gem comes from the perl v5.36.0 era, dated 2022-12-02, and it lives its life as Tree::MultiNode(3pm) — go forth and traverse, you absolute icon 💅✨🦋

📦 where this page comes from