/ 
Tree-Serial-0.2
River stage zero No dependents
/ Tree::Serial

NAME

Tree::Serial - Perl module for deserializing lists of strings into tree-like structures

SYNOPSIS

The following piece of code appears as script/tree-serial-general-examples.pl in the present distribution.

#!/usr/bin/env perl
use warnings;
use v5.12;

use Data::Dumper;
$Data::Dumper::Indent = 0;

use Tree::Serial;

say Dumper(Tree::Serial->new());
# $VAR1 = bless( {'separator' => '.','traversal' => 0,'degree' => 2}, 'Tree::Serial' );

say Dumper(Tree::Serial->new({separator => "#", degree => 5, traversal => 4}));
# $VAR1 = bless( {'degree' => 5,'separator' => '#','traversal' => 4}, 'Tree::Serial' );

say Dumper(Tree::Serial->new()->strs2hash([qw(p q . . r . .)]));
# $VAR1 = {'1' => {'name' => 'r'},'name' => 'p','0' => {'name' => 'q'}};

say Dumper(Tree::Serial->new({traversal => 2})->strs2lol([qw(a b . c . . .)]));
# $VAR1 = [[['c'],'b'],'a'];

say Dumper(Tree::Serial->new({traversal => 2,showMissing => undef})->strs2lol([qw(a b . c . . .)]));
# $VAR1 = [[[],[[],[],'c'],'b'],[],'a'];

say Dumper(Tree::Serial->new({traversal => 2,showMissing => "X"})->strs2hash([qw(a b . c . . .)]));
# $VAR1 = {'name' => 'a','0' => {'0' => {'name' => 'X'},'name' => 'b','1' => {'1' => {'name' => 'X'},'name' => 'c','0' => {'name' => 'X'}}},'1' => {'name' => 'X'}};

The list-of-lists format produced in post-order is meant to inter-operate with the already-existing (and excellent) Tree::DAG_Node (specifically, its lol_to_tree method).

The following code, appearing as script/tree-serial-2dag.pl in this distribution, illustrates.

#!/usr/bin/env perl
use warnings;
use v5.12;

use Data::Dumper;
$Data::Dumper::Indent = 0;

use Tree::Serial;
use Tree::DAG_Node;

my $lol = Tree::Serial->new({traversal => 2})->strs2lol([qw(1 2 4 . 7 . . . 3 5 . . 6 . .)]);

say Dumper($lol);
# $VAR1 = [[[['7'],'4'],'2'],[['5'],['6'],'3'],'1'];

my $tree = Tree::DAG_Node->lol_to_tree($lol);
my $diagram = $tree->draw_ascii_tree;
say map "$_\n", @$diagram; 

#         |
#        <1>
#     /-----\
#     |     |
#    <2>   <3>
#     |   /---\
#    <4>  |   |
#     |  <5> <6>
#    <7>
#

DESCRIPTION

The purpose of the module is to turn lists of strings (typically passed on the command line) into tree-like structures: hashes and lists of lists (of lists, etc.; i.e. nested).

The idea is that you would instantiate the deserializer class that this package provides, passing it a number of parameters:

  • the separator meaning the dummy piece of string that indicates an empty node;

  • the degree, meaning the maximal degree the deserializer assumes all tree nodes have. Whatever missing nodes there are, you will then have to indicate by instances of the above-mentioned separator;

  • the traversal: a non-negative integer between 0 and degree that tells the deserializer where to place the root when producing a list of lists.

You always specify the tree nodes in pre-order traversal; the traversal attribute specifies what sort of output to produce. An example: assuming the separator is '.' and the degree is 2 (the default), the list

1 2 4 . 7 . . . 3 5 . . 6 . .

would represent the binary tree

           `
    1
   / \
  2   3
 /   / \
4   5   6
 \
  7

The initial inspiration was provided by this discussion, which applies to binary trees only. The present module handles k-ary trees for arbitrary k ≥ 2.

INSTALLATION

Using cpanm: clone this repo, cd into it, and then:

$ cpanm .

Manual install:

$ perl Makefile.PL
$ make
$ make install

ATTRIBUTES

separator

The string that will indicate a missing node to the deserializer, if you specify a k-ary tree that is not full. It defauls to '.'.

degree

The common maximal degree assumed of the tree nodes. It defaults to 2 (i.e. to handling binary trees):

my $ts = Tree::Serial->new({degree => 2});

is the same as

my $ts = Tree::Serial->new();

but you can specify any other positive integer.

traversal

my $ts = Tree::Serial->new({traversal => 1});

A non-negative integer, indicating where the root is placed as you deserialize the tree into a list of lists. It defaults to 0, meaning the root comes first, before the subtrees: what is usually called pre-order traversal.

If you've specified a k-ary tree, then setting the traversal attribute to k means you are doing a post-order traversal instead:

my $ts = Tree::Serial->new({degree => 3, traversal => 3});

showMissing

It tells the deserializer object what to do with missing nodes (which you enter as separator). There are a number of options:

  • Let it default to non-existent, in the sense that exists returns false on $deserializer{showMissing}. Empty nodes will then not be rendered at all:

    say Dumper(Tree::Serial->new({traversal => 2})->strs2lol([qw(1 2 . 3 . . .)]));
# $VAR1 = [[['3'],'2'],'1'];

  • Set it to undef, in which case you will get empty hashes/arrays for the missing nodes:

    say Dumper(Tree::Serial->new({traversal => 2,showMissing => undef})->strs2lol([qw(1 2 . 3 . . .)]));
# $VAR1 = [[[],[[],[],'3'],'2'],[],'1'];

  • Finally, make sure it exists and is defined, and the missing nodes will be rendered carrying that label (the value of $deserializer{showMissing}):

    say Dumper(Tree::Serial->new({traversal => 2,showMissing => "X"})->strs2hash([qw(a b . c . . .)]));
# $VAR1 = {'name' => 'a','0' => {'0' => {'name' => 'X'},'name' => 'b','1' => {'1' => {'name' => 'X'},'name' => 'c','0' => {'name' => 'X'}}},'1' => {'name' => 'X'}};

METHODS

strs2hash

This will turn your list of strings into a nested hashref:

say Dumper(Tree::Serial->new()->strs2hash([qw(p q . . r . .)]));
# $VAR1 = {'1' => {'name' => 'r'},'name' => 'p','0' => {'name' => 'q'}};

strs2lol

This method produces a nested arrayref structure (list of lists, or 'lol'):

say Dumper(Tree::Serial->new({traversal => 2})->strs2lol([qw(a b . c . . .)]));
# $VAR1 = [[['c'],'b'],'a'];