Free tree software for linux

B::Tree is a simplified version of B::Graph for demonstration.

SYNOPSIS

perl -MO=Tree program | dot -Tps > tree.ps

This is a very cut-down version of B::Graph; it generates minimalist tree graphs of the op tree of a Perl program, merely connecting the op nodes and labelling each node with the type of op.

It was written as an example of how to write compiler modules for "Professional Perl", but Ive found it extremely useful for creating simple op tree graphs for use in presentations on Perl internals.

It requires the CPAN GraphViz module and the GraphViz package from http://www.research.att.com/sw/tools/graphviz/. It takes no options.

Image Tree is a complete and versatile photo publishing system in less than 200 lines of code.

ImgTree is based only on three files:

index php : contains all the php and html code. Must be put, unmodified in every folder of the directory tree.
data.php : contains the specific settings of every folder
style.css : the css style sheet

Every folder of the folder tree must contain the three files. Clearly index.php and style.php should be simply linked:

imgtree/
|-- data.php
|-- index.php
|-- style.css
|-- Section-A
| |-- data.php
| |-- index.php -> ../index.php
| |-- style.css -> ../style.css
| |-- 01-thumb.jpg
| |-- 01.jpg
| |-- 02-thumb.jpg
| |-- 02.jpg
| `-- ...
`-- Section-B
|-- data.php
|-- index.php -> ../index.php
|-- style.css -> ../style.css
|-- 00.jpg
|-- Subsection-B1
| |-- data.php
| |-- index.php -> ../index.php
| `-- style.css -> ../style.css
| |-- cover.jpg
`-- Subsection-B2
|-- data.php
|-- index.php -> ../index.php
|-- style.css -> ../style.css
|-- 01-thumb.jpg
|-- 01.jpg
|-- 02-thumb.jpg
|-- 02.jpg
`-- ...

Every folder act as a section and the behaviour can be choose between:

index : Contains a list of links to every subfolder of the current folder. For every section an image and a description are shown.
thumb : Thumbnails page. Shows every image file of the folder. Thumbnail must be named "xxx-thumb.jpg" for the xxx.jpg file. Ex: 01-thumb.jpg -> 01.jpg ; tramonto-thumb.jpg -> tramonto.jpg ; ecc.
cover : Cover page. Shows an image, a text and an associated link

The file data.php contin the settings specific for every section:

$gallerystart : is the gallery start to generate the back-menu. The path must be relative to the starting folder of the site
$name : name used to link the current section in the menus
$title : page title
$description: description, used as subtitle and for brief description in index pages
$indeximage : image used in index pages to link this section
$type : type of the page (cover|thumb|index)
$imgtitle : associtive array of the images descriptions. Used only by "thumb" pages
$coverimage : image used by "cover" pages
$covertext : text used by "cover" pages
$coverlink= : link used by "cover" pages
$covertitle : title used by "cover" pages

NEEDS a web server (Apache or similar) with PHP support

STX B+ Tree project is a set of C++ template classes implementing a B+ tree key/data container in main memory. The classes are designed as drop-in replacements of the STL containers set, map, multiset and multimap and follow their interfaces very closely. By packing multiple value pairs into each node of the tree the B+ tree reduces heap fragmentation and utilizes cache-line effects better than the standard red-black binary tree.
The tree algorithms are based on the implementation in Cormen, Leiserson and Rivests Introduction into Algorithms, Jan Janninks paper and other algorithm resources. The classes contain extensive assertion and verification mechanisms to ensure the implementations correctness by testing the tree invariants.
The main B+ tree implementation can be found in doxygen stx/btree.h or with plain text comments btree.h.
Special interest was put into performing a speed comparison test between the standard red-black tree and the new B+ tree implementation. The speed test results are interesting and show the B+ tree to be significantly faster.
Enhancements:
- This release introduces the demonstration program wxBTreeDemo.
- This program draws illustrations of the B+ trees constructed by the STX B+ Tree template classes.
- It allows the user to select different types of B+ tree instantiations: integer or string keys and different slot numbers.
- The user may insert and erase key/data pairs from the tree and run different search operations.
- The demo program uses the cross-platform wxWidgets toolkit and can be compiled on Linux, Windows, and Mac OS X.

Tree::BPTree is a Perl implementation of B+ trees.

SYNOPSIS

use Tree::BPTree;

# These arguments are actually the defaults
my $tree = new Tree::BPTree(
-n => 3,
-unique => 0,
-keycmp => sub { $_[0] cmp $_[1] },
-valuecmp => sub { $_[0] $_[1] },
);

# index the entries in this string:
my $string = "THERES MORE THAN ONE WAY TO DO IT"; # TMTOWTDI
my $i = 0;
$tree->insert($_, $i++) foreach (split //, $string);

# find the index of the first T
my $t = $tree->find(T);

# find the indexes of every T
my @t = $tree->find(T);

# We dont like the word WAY , so lets remove it
my $i = index $string, W;
$tree->delete($_, $i++) foreach (split //, substr($string, $i, 4));

# Reverse the sort order
$tree->reverse;

# Iterate through each key/value pair just like built-in each operator
while (my ($key, $value) = $tree->each) {
print "$key => $valuen";
}

# Reset the iterator when we quit from an "each-loop" early
$tree->reset;

# You might also be interested in using multiple each loops at once, which is
# possible through the cursor syntax. You can even delete individual pairs
# from the list during iteration.
my $cursor = $tree->new_cursor;
while (my ($key, $value) = $cursor->each) {
my $nested = $tree->new_cursor;
while (my ($nkey, $nvalue) = $nested->each) {
if ($key->shouldnt_be_in_this_tree_with($nkey)) {
$nested->delete;
}
}
}

# Iterate using an iterator subroutine
$tree->iterate(sub { print "$_[0] => $_[1]n" });

# Iterate using an iterator subroutine that returns the list of return values
# returned by the iterator
print join(, , $tree->map(sub { "$_[0] => $_[1]" })),"n";

# Grep-like operations
my @pairs = $tree->grep (sub { $_[0] =~ /S/ });
my @keys = $tree->grep_keys (sub { $_[0] =~ /S/ });
my @values = $tree->grep_values (sub { $_[0] =~ /S/ });

# Get all keys, values
my @all_keys = $tree->keys;
my @all_values = $tree->values;

# Clear it out and start over
$tree->clear;

B+ trees are balanced trees which provide an ordered map from keys to values. They are useful for indexing large bodies of data. They are similar to 2-3-4 Trees and Red-Black Trees. This implementation supports B+ trees using an arbitrary n value.

Bio::Tree::Tree is an implementation of TreeI interface.

SYNOPSIS

# like from a TreeIO
my $treeio = new Bio::TreeIO(-format => newick, -file => treefile.dnd);
my $tree = $treeio->next_tree;
my @nodes = $tree->get_nodes;
my $root = $tree->get_root_node;

This object holds handles to Nodes which make up a tree.

Tree::Visualize is a Perl module for visualizing Tree structures.

SYNOPSIS

use Tree::Visualize;
use Tree::Binary;

my $tree = Tree::Binary->new("*")
->setLeft(
Tree::Binary->new("+")
->setLeft(Tree::Binary->new("2"))
->setRight(Tree::Binary->new("2"))
)
->setRight(
Tree::Binary->new("+")
->setLeft(Tree::Binary->new("4"))
->setRight(Tree::Binary->new("5"))
);

my $visualize = Tree::Visualize->new($tree, ASCII, TopDown);
print $visualize->draw();

# +---+
# +--------| * |-------+
# | +---+ |
# +---+ +---+
# +--| + |--+ +--| + |--+
# | +---+ | | +---+ |
# +---+ +---+ +---+ +---+
# | 2 | | 2 | | 4 | | 5 |
# +---+ +---+ +---+ +---+

my $tree = Tree::Binary::Search->new();
foreach my $value (7, 3, 1, 0, 2, 5, 4, 6, 11, 9, 10, 8, 13, 12, 14) {
$tree->insert($value => $value);
}

my $visualize = Tree::Visualize->new($tree, ASCII, Diagonal);
print $visualize->draw();

# (7)-------------(11)-----(13)-(14)
# | | |
# | | (12)
# | |
# | (9)-(10)
# | |
# | (8)
# |
# (3)-----(5)-(6)
# | |
# | (4)
# |
# (1)-(2)
# |
# (0)

my $tree = Tree::Simple->new("test")
->addChildren(
Tree::Simple->new("test-1")
->addChildren(
Tree::Simple->new("test-1-1")
),
Tree::Simple->new("test-2"),
Tree::Simple->new("test-3")
);

my $visualize = Tree::Visualize->new($tree, ASCII, TopDown);
print $visualize->draw();

# |
# +------+
# | test |
# +------+
# ____________|_____________
# | | |
# +--------+ +--------+ +--------+
# | test-1 | | test-2 | | test-3 |
# +--------+ +--------+ +--------+
# |
# |
# +----------+
# | test-1-1 |
# +----------+

NOTE: This is very early release alpha software
The goal of this module is to provide a means of easily visualizing trees in a number of output formats and layouts. Currently only ASCII output and a limited number of formats are supported. There is some support for output as GraphViz dot files, but that is buggy at best right now.

As I said, this is alpha software, and so please dont expect it to do all that much. Many of the classes inside are not even implemented, and few if any are documented. I am releasing this to CPAN largely as a means of self-motivation, although I can make no promises about the speed of my progress.

DBIx::OO::Tree is a Perl module to manipulate hierarchical data using the "nested sets" model.

SYNOPSYS

CREATE TABLE Categories (
id INTEGER UNSIGNED AUTO_INCREMENT PRIMARY KEY,
label VARCHAR(255),

-- these columns are required by DBIx::OO::Tree
parent INTEGER UNSIGNED,
lft INTEGER UNSIGNED NOT NULL,
rgt INTEGER UNSIGNED NOT NULL,
mvg TINYINT DEFAULT 0,

INDEX(lft),
INDEX(rgt),
INDEX(mvg),
INDEX(parent)
);

* * *

package Category;
use base DBIx::OO;
use DBIx::OO::Tree;

__PACKAGE__->table(Categories);
__PACKAGE__->columns(P => [ id ],
E => [ label, parent ]);

# note its not necessary to declare lft, rgt, mvg or parent. We
# declare parent simply because it might be useful, but
# DBIx::OO:Tree works with low-level SQL therefore it doesnt
# require that the DBIx::OO object has these fields.

# the code below creates the structure presented in [1]

my $electronics = Category->tree_append({ label => electronics });
my $tvs = $electronics->tree_append({ label => televisions });
my $tube = $tvs->tree_append({ label => tube });
my $plasma = $tvs->tree_append({ label => plasma });
my $lcd = $plasma->tree_insert_before({ label => lcd });
my $portable = $tvs->tree_insert_after({ label => portable electronics });
my $mp3 = $portable->tree_append({ label => mp3 players });
my $flash = $mp3->tree_append({ label => flash });
my $cds = $portable->tree_append({ label => cd players });
my $radios = Category->tree_append($portable->id,
{ label => 2 way radios });

# fetch and display a subtree

my $data = $electronics->tree_get_subtree({
fields => [qw( label lft rgt parent )]
});
my $levels = Category->tree_compute_levels($data);

foreach my $i (@$data) {
print x $levels->{$i->{id}}, $i->{label}, "n";
}

## or, create DBIx::OO objects from returned data:

my $array = Category->init_from_data($data);
print join("n", (map { x $levels->{$_->id} . $_->label } @$array));

# display path info

my $data = $flash->tree_get_path;
print join("n", (map { $_->{label} } @$data));

# move nodes around

$mp3->tree_reparent($lcd->id);
$tvs->tree_reparent($portable->id);
$cds->tree_reparent(undef);

$plasma->tree_move_before($tube->id);
$portable->tree_move_before($electronics->id);

# delete nodes

$lcd->tree_delete;

This module is a complement to DBIx::OO to facilitate storing trees in database using the "nested sets model", presented in [1]. Its main ambition is to be extremely fast at retrieving data (sacrificing for this the performance of UPDATE-s, INSERT-s or DELETE-s). Currently this module requires you to have these columns in the table:

- id: primary key (integer)
- parent: integer, references the parent node (NULL for root nodes)
- lft, rgt: store the node position
- mvg: used only when moving nodes

"parent" and "mvg" are not esentially required by the nested sets model as presented in [1], but they are necessary for this module to work. In particular, "mvg" is only required by functions that move nodes, such as tree_reparent(). If you dont want to move nodes around you can omit "mvg".

Retrieval functions should be very fast (one SQL executed). To further promote speed, they dont return DBIx::OO blessed objects, but an array of hashes instead. Its easy to create DBIx::OO objects from these, if required, by calling DBIx::OO->init_from_data() (see DBIx::OO for more information).

Insert/delete/move functions, however, need to ensure the tree integrity. Heres what happens currently:

- tree_append, tree_insert_before, tree_insert_after -- these execute
one SELECT and two UPDATE-s (that potentially could affect a lot of
rows).

- tree_delete: execute one SELECT, one DELETE and two UPDATE-s.

- tree_reparent -- executes 2 SELECT-s and 7 UPDATE-s. I know, this
sounds horrible--if you have better ideas Id love to hear them.

Tree::XPathEngine is a re-usable XPath engine.

This module provides an XPath engine, that can be re-used by other module/classes that implement trees.

It is designed to be compatible with Class::XPath, ie it passes its tests if you replace Class::XPath by Tree::XPathEngine.

This code is a more or less direct copy of the XML::XPath module by Matt Sergeant. I only removed the XML processing part (that parses an XML document and load it as a tree in memory) to remove the dependency on XML::Parser, applied a couple of patches, removed a whole bunch of XML specific things (comment, processing inistructions, namespaces...), renamed a whole lot of methods to make Pod::Coverage happy, and changed the docs.

The article eXtending XML XPath, http://www.xmltwig.com/article/extending_xml_xpath/ should give authors who want to use this module enough background to do so.

WARNING: while the underlying code is rather solid, this module most likely lacks docs.
As they say, "patches welcome"... but I am also interested in any experience using this module, what were the tricky parts, and how could the code or the docs be improved.