ExSite::Tree

ExSite::Tree is a generic tool for managing heirarchical tree structures such as are found in ExSite. It assumes that each tree node is essentially an ExSite datahash, and each node has a single parent node.

Each tree node consists of a datahash and some tree indexing parameters. The hash should include keys/values for the id (an arbitrary value used to reference the node) and the parent (the id value of the parent node). It can contain any other keys/values as well.

Nodes retain the order in which they were inserted into the tree.

Tree Construction

Each tree node is a datahash. One of the hash keys is used as a node ID, and another is used as a parent ID (collectively, these are the index keys). The index keys can be specifed uniquely for each node, for a bulk insert of multiple nodes, or they can be defined as defaults for all nodes.

ExSite Trees are designed to be self-constructing with typical ExSite data structures. See the example at the end for more info.

Tree Contruction

Create a new tree object
my $tree = new ExSite::Tree("id_key", "parent_key", @data);

``id_key'' and ``parent_key'' are the index keys for the datahashes in @data. They are also the default index keys for all other nodes added to the tree. @data is optional.

Add nodes to a tree
$tree->addnode($data);

$tree->addnode($data,$id_key,$parent_key);

Adds one node whose data is in %$data. If the index keys are different from the default for the tree, they can be specified as extra parameters.

$tree->addnodes($data);

$tree->addnodes($data,$id_key,$parent_key);

Same as above, except $data is taken to be a reference to an array of datahashes.

$tree->replacenode($id,$data);

$tree->replacenode($id,$data,$id_key,$parent_key);

This replaces the data in the node indexed under $id, with the contents of %$data. The replaced node will be indexed under the original key as well as under a new key determined from the replacement data.

Querying the tree

Tree nodes can be fetched as nodes (including the tree indexing parameters) or as data (ie. the original datahash). Fetching as nodes is typical for internal use; fetching as data is typical for calls from other packages. If you fetch the node, the data can be accessed as $node->{data}{...}.

Fetch a node
$tree->getnode($id,$create_flag);

$tree->getnode_data($id,$create_flag);

Fetches the node indexed under $id. If $create_flag is true, a dummy version of the node will be created if it is not found.

Fetch the parent of a node
$tree->get_parent_node($id);

$tree->get_parent_data($id);

Fetches the parent of the node indexed under $id.

Fetch the children of a node
$tree->get_child_nodes($id);

$tree->get_child_data($id);

$tree->get_child($id); # synonym for get_child_data()

Fetches the children nodes under node $id. Returns an array, or array ref, depending on the list context.

Fetch the top-level of the tree
$tree->get_topnodes();

$tree->get_topnodes_data();

Fetches the nodes that have no parents. Returns an array, or array ref, depending on the list context.

Fetch the top-level ancestor of a node
$tree->get_ancestor_node($id);

$tree->get_ancestor_data($id);

Search up through the parent links for a node without a parent.

Dump the tree
print $tree->dump(); # dump IDs

print $tree->dump($id); # dump IDs, starting from $id

print $tree->dump($id,"key1","key2"); # dump data keys, $id

Returns a string that illustrates the map as a nested list of text strings. Each map entry is shown as its ID, by default, but if alternate keys are given, the values under those keys in the node's data will be listed instead.

Example

This example creates a site map as a tree.

    # fetch a (somewhat) ordered list of pages
    my @pages = $db->fetch_match("page", {section_id=>$my_section, type=>"page"}, ["rank","page_id"]);
    # index the pages as a tree, using page.page_id and page.parent_id as the index keys
    my $map = new ExSite::Tree("page_id","parent_id",@data);

This tree consists of one node for each page, with the nodes nested exactly as they do in site menus and site maps. At each level of the tree, the pages are ordered correctly according to their page rank.

To fetch the top-level pages from the site, use:

    my @toppages = $map->get_topnodes_data();

This retrieves an ordered array of datahashes, representing the top-level pages of the site. For each of these pages, you can fetch the child pages (submenus) beneath them with:

    my @subpages = $map->get_child_data($page->{page_id});

...and so on, to any depth.

To get a quick view of the site map, use:

    print $map->dump(0,"filename");