Name

Tree::Ops - Tree operations.

Synopsis

Create a tree:

my $a = Tree::Ops::new 'a', 'A';

for(1..2)
 {$a->open  ('b', "B$_");
  $a->single('c', "C$_");
  $a->close;
 }
$a->single  ('d', 'D');
$a->single  ('e', 'E');

Print it:

is_deeply $a->print, <<END;
Key    Value
a      A
b    B1
  c  C1
b    B2
  c  C2
d    D
e    E
END

Navigate through the tree:

is_deeply $a->lastMost->prev->prev->first->key,           'c';
is_deeply $a->first->next->last->parent->first->value,    'C2';

Traverse the tree:

is_deeply [map{$_->value} $a->by], [qw(C1 B1 C2 B2 D E A)];

Select items from the tree:

is_deeply [map{$_->value} $a->select('b')],               [qw(B1 B2)];
is_deeply [map{$_->value} $a->select(qr(b|c))],           [qw(B1 C1 B2 C2)];
is_deeply [map{$_->value} $a->select(sub{$_[0] eq 'd'})], [qw(D)];

Reorganize the tree:

$a->first->next->stepEnd->stepEnd->first->next->stepBack;
is_deeply $a->print, <<END;
Key      Value
a        A
b      B1
  c    C1
b      B2
  d    D
    c  C2
  e    E
END

Description

Tree operations.

Version 20200720.

The following sections describe the methods in each functional area of this module. For an alphabetic listing of all methods by name see Index.

Build

Create a tree. There is no implicit ordering applied to the tree, the relationships between parents and children within the tree are as established by the user and can be reorganized at will using the methods in this module.

new($key, $value)

Create a new child optionally recording the specified key or value.

   Parameter  Description
1  $key       Key
2  $value     Value

Example:

  my $a = Tree::Ops::new 'a', 'A';  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  for(1..2)
   {$a->open  ('b', "B$_");
    $a->single('c', "C$_");
    ok $a->activeScope->key eq 'b';
    $a->close;
   }
  $a->single  ('d', 'D');
  $a->single  ('e', 'E');
  is_deeply $a->print, <<END;
Key    Value
a      A
  b    B1
    c  C1
  b    B2
    c  C2
  d    D
  e    E
END

  is_deeply [map{$_->value} $a->by], [qw(C1 B1 C2 B2 D E A)];

  is_deeply $a->lastMost->prev->prev->first->key,           'c';
  is_deeply $a->first->next->last->parent->first->value,    'C2';

  is_deeply [map{$_->value} $a->select('b')],               [qw(B1 B2)];
  is_deeply [map{$_->value} $a->select(qr(b|c))],           [qw(B1 C1 B2 C2)];
  is_deeply [map{$_->value} $a->select(sub{$_[0] eq 'd'})], [qw(D)];

  $a->first->next->stepEnd->stepEnd->first->next->stepBack;
  is_deeply $a->print, <<END;
Key      Value
a        A
  b      B1
    c    C1
  b      B2
    d    D
      c  C2
    e    E
END

This is a static method and so should either be imported or invoked as:

Tree::Ops::new

activeScope($tree)

Locate the active scope in a tree.

   Parameter  Description
1  $tree      Tree

Example:

  my $a = Tree::Ops::new 'a', 'A';
  for(1..2)
   {$a->open  ('b', "B$_");
    $a->single('c', "C$_");

    ok $a->activeScope->key eq 'b';  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

    $a->close;
   }
  $a->single  ('d', 'D');
  $a->single  ('e', 'E');
  is_deeply $a->print, <<END;
Key    Value
a      A
  b    B1
    c  C1
  b    B2
    c  C2
  d    D
  e    E
END

  is_deeply [map{$_->value} $a->by], [qw(C1 B1 C2 B2 D E A)];

  is_deeply $a->lastMost->prev->prev->first->key,           'c';
  is_deeply $a->first->next->last->parent->first->value,    'C2';

  is_deeply [map{$_->value} $a->select('b')],               [qw(B1 B2)];
  is_deeply [map{$_->value} $a->select(qr(b|c))],           [qw(B1 C1 B2 C2)];
  is_deeply [map{$_->value} $a->select(sub{$_[0] eq 'd'})], [qw(D)];

  $a->first->next->stepEnd->stepEnd->first->next->stepBack;
  is_deeply $a->print, <<END;
Key      Value
a        A
  b      B1
    c    C1
  b      B2
    d    D
      c  C2
    e    E
END

open($tree, $key, $value)

Add a child and make it the currently active scope into which new children will be added.

   Parameter  Description
1  $tree      Tree
2  $key       Key
3  $value     Value to be recorded in the interior child being opened

Example:

  my $a = Tree::Ops::new 'a', 'A';
  for(1..2)

   {$a->open  ('b', "B$_");  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

    $a->single('c', "C$_");
    ok $a->activeScope->key eq 'b';
    $a->close;
   }
  $a->single  ('d', 'D');
  $a->single  ('e', 'E');
  is_deeply $a->print, <<END;
Key    Value
a      A
  b    B1
    c  C1
  b    B2
    c  C2
  d    D
  e    E
END

  is_deeply [map{$_->value} $a->by], [qw(C1 B1 C2 B2 D E A)];

  is_deeply $a->lastMost->prev->prev->first->key,           'c';
  is_deeply $a->first->next->last->parent->first->value,    'C2';

  is_deeply [map{$_->value} $a->select('b')],               [qw(B1 B2)];
  is_deeply [map{$_->value} $a->select(qr(b|c))],           [qw(B1 C1 B2 C2)];
  is_deeply [map{$_->value} $a->select(sub{$_[0] eq 'd'})], [qw(D)];

  $a->first->next->stepEnd->stepEnd->first->next->stepBack;
  is_deeply $a->print, <<END;
Key      Value
a        A
  b      B1
    c    C1
  b      B2
    d    D
      c  C2
    e    E
END

close($tree)

Close the current scope returning to the previous scope.

   Parameter  Description
1  $tree      Tree

Example:

  my $a = Tree::Ops::new 'a', 'A';
  for(1..2)
   {$a->open  ('b', "B$_");
    $a->single('c', "C$_");
    ok $a->activeScope->key eq 'b';

    $a->close;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

   }
  $a->single  ('d', 'D');
  $a->single  ('e', 'E');
  is_deeply $a->print, <<END;
Key    Value
a      A
  b    B1
    c  C1
  b    B2
    c  C2
  d    D
  e    E
END

  is_deeply [map{$_->value} $a->by], [qw(C1 B1 C2 B2 D E A)];

  is_deeply $a->lastMost->prev->prev->first->key,           'c';
  is_deeply $a->first->next->last->parent->first->value,    'C2';

  is_deeply [map{$_->value} $a->select('b')],               [qw(B1 B2)];
  is_deeply [map{$_->value} $a->select(qr(b|c))],           [qw(B1 C1 B2 C2)];
  is_deeply [map{$_->value} $a->select(sub{$_[0] eq 'd'})], [qw(D)];

  $a->first->next->stepEnd->stepEnd->first->next->stepBack;
  is_deeply $a->print, <<END;
Key      Value
a        A
  b      B1
    c    C1
  b      B2
    d    D
      c  C2
    e    E
END

single($tree, $key, $value)

Add one child in the current scope.

   Parameter  Description
1  $tree      Tree
2  $key       Key
3  $value     Value to be recorded in the child being created

Example:

  my $a = Tree::Ops::new 'a', 'A';
  for(1..2)
   {$a->open  ('b', "B$_");

    $a->single('c', "C$_");  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

    ok $a->activeScope->key eq 'b';
    $a->close;
   }

  $a->single  ('d', 'D');  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  $a->single  ('e', 'E');  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply $a->print, <<END;
Key    Value
a      A
  b    B1
    c  C1
  b    B2
    c  C2
  d    D
  e    E
END

  is_deeply [map{$_->value} $a->by], [qw(C1 B1 C2 B2 D E A)];

  is_deeply $a->lastMost->prev->prev->first->key,           'c';
  is_deeply $a->first->next->last->parent->first->value,    'C2';

  is_deeply [map{$_->value} $a->select('b')],               [qw(B1 B2)];
  is_deeply [map{$_->value} $a->select(qr(b|c))],           [qw(B1 C1 B2 C2)];
  is_deeply [map{$_->value} $a->select(sub{$_[0] eq 'd'})], [qw(D)];

  $a->first->next->stepEnd->stepEnd->first->next->stepBack;
  is_deeply $a->print, <<END;
Key      Value
a        A
  b      B1
    c    C1
  b      B2
    d    D
      c  C2
    e    E
END

include($tree, $include)

Include the specified tree in the currently open scope.

   Parameter  Description
1  $tree      Tree being built
2  $include   Tree to include

Example:

  my $i = fromLetters('B(CD)');
  my $a = Tree::Ops::new 'a';
     $a->open ('b');

     $a->include($i->first);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

     $a->close;

  is_deeply $a->print, <<END;
Key      Value
a
  b
    B
      C
      D
END

fromLetters($letters)

Create a tree from a string of letters - useful for testing.

   Parameter  Description
1  $letters   String of letters and ( ).

Example:

  my $a = fromLetters(q(bc(d)e));  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  is_deeply $a->print, <<END;
Key    Value
a
  b
  c
    d
  e
END

Navigate through a tree.

first($parent)

Get the first child under the specified parent.

   Parameter  Description
1  $parent    Parent

Example:

  my %l = map{$_->key=>$_} fromLetters('b(c)d(efgh(i(j)))')->by;
  my ($a, $b, $c, $d, $e, $f, $g, $h, $i, $j) = @l{'a'..'j'};
  is_deeply $c->parent,   $b;

  is_deeply $a->first,    $b;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply $a->last,     $d;
  is_deeply $e->next,     $f;
  is_deeply $f->prev,     $e;

last($parent)

Get the last child under the specified parent.

   Parameter  Description
1  $parent    Parent

Example:

  my %l = map{$_->key=>$_} fromLetters('b(c)d(efgh(i(j)))')->by;
  my ($a, $b, $c, $d, $e, $f, $g, $h, $i, $j) = @l{'a'..'j'};
  is_deeply $c->parent,   $b;
  is_deeply $a->first,    $b;

  is_deeply $a->last,     $d;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply $e->next,     $f;
  is_deeply $f->prev,     $e;

next($child)

Get the next sibling following the specified child.

   Parameter  Description
1  $child     Child

Example:

  my %l = map{$_->key=>$_} fromLetters('b(c)d(efgh(i(j)))')->by;
  my ($a, $b, $c, $d, $e, $f, $g, $h, $i, $j) = @l{'a'..'j'};
  is_deeply $c->parent,   $b;
  is_deeply $a->first,    $b;
  is_deeply $a->last,     $d;

  is_deeply $e->next,     $f;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply $f->prev,     $e;

prev($child)

Get the previous sibling of the specified child.

   Parameter  Description
1  $child     Child

Example:

  my %l = map{$_->key=>$_} fromLetters('b(c)d(efgh(i(j)))')->by;
  my ($a, $b, $c, $d, $e, $f, $g, $h, $i, $j) = @l{'a'..'j'};
  is_deeply $c->parent,   $b;
  is_deeply $a->first,    $b;
  is_deeply $a->last,     $d;
  is_deeply $e->next,     $f;

  is_deeply $f->prev,     $e;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

firstMost($parent)

Return the first most descendant child in the tree starting at this parent or else return undef if this parent has no children.

   Parameter  Description
1  $parent    Child

Example:

  my $a = fromLetters('b(c)y(x)d(efgh(i(j)))');
  is_deeply $a->print, <<END;
Key        Value
a
  b
    c
  y
    x
  d
    e
    f
    g
    h
      i
        j
END

  is_deeply $a->xml,
   '<a><b><c/></b><y><x/></y><d><e/><f/><g/><h><i><j/></i></h></d></a>';

  my ($c, $b, $x, $y, $e, $f, $g, $j, $i, $h, $d) = $a->by;

  is_deeply [$c, $x, $e, $f, $g, $j], [$a->leaves];
  is_deeply [$a, $b, $y, $d, $h, $i], [$a->parentsPreOrder];
  is_deeply [$b, $y, $i, $h, $d, $a], [$a->parentsPostOrder];
  is_deeply [$a->parents],            [$a->parentsPostOrder];

  is_deeply [$a, $d, $h, $i, $y, $b], [$a->parentsReversePreOrder];
  is_deeply [$i, $h, $d, $y, $b, $a], [$a->parentsReversePostOrder];

  ok !$j->parents;

  ok  $a->lastMost  == $j;
  ok !$a->prevMost;
  ok  $j->prevMost  == $g;
  ok  $i->prevMost  == $g;
  ok  $h->prevMost  == $g;
  ok  $g->prevMost  == $f;
  ok  $f->prevMost  == $e;
  ok  $e->prevMost  == $x;
  ok  $d->prevMost  == $x;
  ok  $x->prevMost  == $c;
  ok  $y->prevMost  == $c;
  ok !$c->prevMost;
  ok !$b->prevMost;
  ok !$a->prevMost;


  ok  $a->firstMost == $c;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  ok  $a->nextMost  == $c;
  ok  $b->nextMost  == $c;
  ok  $c->nextMost  == $x;
  ok  $y->nextMost  == $x;
  ok  $x->nextMost  == $e;
  ok  $d->nextMost  == $e;
  ok  $e->nextMost  == $f;
  ok  $f->nextMost  == $g;
  ok  $g->nextMost  == $j;
  ok  $h->nextMost  == $j;
  ok  $i->nextMost  == $j;
  ok !$j->nextMost;

nextMost($child)

Return the next child with no children, i.e. the next leaf of the tree, else return undef if there is no such child.

   Parameter  Description
1  $child     Current leaf

Example:

  my $a = fromLetters('b(c)y(x)d(efgh(i(j)))');
  is_deeply $a->print, <<END;
Key        Value
a
  b
    c
  y
    x
  d
    e
    f
    g
    h
      i
        j
END

  is_deeply $a->xml,
   '<a><b><c/></b><y><x/></y><d><e/><f/><g/><h><i><j/></i></h></d></a>';

  my ($c, $b, $x, $y, $e, $f, $g, $j, $i, $h, $d) = $a->by;

  is_deeply [$c, $x, $e, $f, $g, $j], [$a->leaves];
  is_deeply [$a, $b, $y, $d, $h, $i], [$a->parentsPreOrder];
  is_deeply [$b, $y, $i, $h, $d, $a], [$a->parentsPostOrder];
  is_deeply [$a->parents],            [$a->parentsPostOrder];

  is_deeply [$a, $d, $h, $i, $y, $b], [$a->parentsReversePreOrder];
  is_deeply [$i, $h, $d, $y, $b, $a], [$a->parentsReversePostOrder];

  ok !$j->parents;

  ok  $a->lastMost  == $j;
  ok !$a->prevMost;
  ok  $j->prevMost  == $g;
  ok  $i->prevMost  == $g;
  ok  $h->prevMost  == $g;
  ok  $g->prevMost  == $f;
  ok  $f->prevMost  == $e;
  ok  $e->prevMost  == $x;
  ok  $d->prevMost  == $x;
  ok  $x->prevMost  == $c;
  ok  $y->prevMost  == $c;
  ok !$c->prevMost;
  ok !$b->prevMost;
  ok !$a->prevMost;

  ok  $a->firstMost == $c;

  ok  $a->nextMost  == $c;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok  $b->nextMost  == $c;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok  $c->nextMost  == $x;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok  $y->nextMost  == $x;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok  $x->nextMost  == $e;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok  $d->nextMost  == $e;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok  $e->nextMost  == $f;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok  $f->nextMost  == $g;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok  $g->nextMost  == $j;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok  $h->nextMost  == $j;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok  $i->nextMost  == $j;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok !$j->nextMost;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

prevMost($child)

Return the previous child with no children, i.e. the previous leaf of the tree, else return undef if there is no such child.

   Parameter  Description
1  $child     Current leaf

Example:

  my $a = fromLetters('b(c)y(x)d(efgh(i(j)))');
  is_deeply $a->print, <<END;
Key        Value
a
  b
    c
  y
    x
  d
    e
    f
    g
    h
      i
        j
END

  is_deeply $a->xml,
   '<a><b><c/></b><y><x/></y><d><e/><f/><g/><h><i><j/></i></h></d></a>';

  my ($c, $b, $x, $y, $e, $f, $g, $j, $i, $h, $d) = $a->by;

  is_deeply [$c, $x, $e, $f, $g, $j], [$a->leaves];
  is_deeply [$a, $b, $y, $d, $h, $i], [$a->parentsPreOrder];
  is_deeply [$b, $y, $i, $h, $d, $a], [$a->parentsPostOrder];
  is_deeply [$a->parents],            [$a->parentsPostOrder];

  is_deeply [$a, $d, $h, $i, $y, $b], [$a->parentsReversePreOrder];
  is_deeply [$i, $h, $d, $y, $b, $a], [$a->parentsReversePostOrder];

  ok !$j->parents;

  ok  $a->lastMost  == $j;

  ok !$a->prevMost;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok  $j->prevMost  == $g;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok  $i->prevMost  == $g;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok  $h->prevMost  == $g;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok  $g->prevMost  == $f;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok  $f->prevMost  == $e;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok  $e->prevMost  == $x;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok  $d->prevMost  == $x;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok  $x->prevMost  == $c;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok  $y->prevMost  == $c;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok !$c->prevMost;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok !$b->prevMost;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok !$a->prevMost;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok  $a->firstMost == $c;
  ok  $a->nextMost  == $c;
  ok  $b->nextMost  == $c;
  ok  $c->nextMost  == $x;
  ok  $y->nextMost  == $x;
  ok  $x->nextMost  == $e;
  ok  $d->nextMost  == $e;
  ok  $e->nextMost  == $f;
  ok  $f->nextMost  == $g;
  ok  $g->nextMost  == $j;
  ok  $h->nextMost  == $j;
  ok  $i->nextMost  == $j;
  ok !$j->nextMost;

lastMost($parent)

Return the last most descendant child in the tree starting at this parent or else return undef if this parent has no children.

   Parameter  Description
1  $parent    Child

Example:

  my $a = fromLetters('b(c)y(x)d(efgh(i(j)))');
  is_deeply $a->print, <<END;
Key        Value
a
  b
    c
  y
    x
  d
    e
    f
    g
    h
      i
        j
END

  is_deeply $a->xml,
   '<a><b><c/></b><y><x/></y><d><e/><f/><g/><h><i><j/></i></h></d></a>';

  my ($c, $b, $x, $y, $e, $f, $g, $j, $i, $h, $d) = $a->by;

  is_deeply [$c, $x, $e, $f, $g, $j], [$a->leaves];
  is_deeply [$a, $b, $y, $d, $h, $i], [$a->parentsPreOrder];
  is_deeply [$b, $y, $i, $h, $d, $a], [$a->parentsPostOrder];
  is_deeply [$a->parents],            [$a->parentsPostOrder];

  is_deeply [$a, $d, $h, $i, $y, $b], [$a->parentsReversePreOrder];
  is_deeply [$i, $h, $d, $y, $b, $a], [$a->parentsReversePostOrder];

  ok !$j->parents;


  ok  $a->lastMost  == $j;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  ok !$a->prevMost;
  ok  $j->prevMost  == $g;
  ok  $i->prevMost  == $g;
  ok  $h->prevMost  == $g;
  ok  $g->prevMost  == $f;
  ok  $f->prevMost  == $e;
  ok  $e->prevMost  == $x;
  ok  $d->prevMost  == $x;
  ok  $x->prevMost  == $c;
  ok  $y->prevMost  == $c;
  ok !$c->prevMost;
  ok !$b->prevMost;
  ok !$a->prevMost;

  ok  $a->firstMost == $c;
  ok  $a->nextMost  == $c;
  ok  $b->nextMost  == $c;
  ok  $c->nextMost  == $x;
  ok  $y->nextMost  == $x;
  ok  $x->nextMost  == $e;
  ok  $d->nextMost  == $e;
  ok  $e->nextMost  == $f;
  ok  $f->nextMost  == $g;
  ok  $g->nextMost  == $j;
  ok  $h->nextMost  == $j;
  ok  $i->nextMost  == $j;
  ok !$j->nextMost;

mostRecentCommonAncestor($first, $second)

Find the most recent common ancestor of the specified children.

   Parameter  Description
1  $first     First child
2  $second    Second child

Example:

  my %l = map{$_->key=>$_} fromLetters('b(c(d(e))f(g(h)i)j)k')->by;
  my ($a, $b, $e, $h, $k) = @l{qw(a b e h k)};

  is_deeply $a->print, <<END;
Key        Value
a
  b
    c
      d
        e
    f
      g
        h
      i
    j
  k
END


  ok $e->mostRecentCommonAncestor($h) == $b;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok $e->mostRecentCommonAncestor($k) == $a;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

Location

Verify the current location.

context($child)

Get the context of the current child.

   Parameter  Description
1  $child     Child

Example:

  my %l = map{$_->key=>$_} fromLetters('b(c)y(x)z(st)d(efgh(i(j))))')->by;
  my ($a, $x, $y, $z) = @l{qw(a x y z)};


  is_deeply [map {$_->key} $x->context], [qw(x y a)];  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  is_deeply join(' ', $a->by(sub{$_[0]->key})), "c b x y s t z e f g j i h d a";
  is_deeply join(' ', map{$_->key} $a->by),     "c b x y s t z e f g j i h d a";

  $z->cut;
  is_deeply $a->brackets, 'a(b(c)y(x)d(efgh(i(j))))';

  $y->unwrap;
  is_deeply $a->brackets, 'a(b(c)xd(efgh(i(j))))';

  $y = $x->wrap('y');
  is_deeply $y->brackets, 'y(x)';
  is_deeply $a->brackets, 'a(b(c)y(x)d(efgh(i(j))))';

  $y->putNext($y->dup);
  is_deeply $a->brackets, 'a(b(c)y(x)y(x)d(efgh(i(j))))';

isFirst($child)

Return the specified child if that child is first under its parent, else return undef.

   Parameter  Description
1  $child     Child

Example:

  my %l = map{$_->key=>$_} fromLetters('b(c)d(efgh(i(j)))')->by;
  my ($a, $b, $c, $d, $e, $f, $g, $h, $i, $j) = @l{'a'..'j'};

  is_deeply $a->brackets, 'a(b(c)d(efgh(i(j))))';
  is_deeply $b->singleChildOfParent, $c;

  is_deeply $e->isFirst, $e;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok !$f->isFirst;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  ok !$g->isLast;
  is_deeply $h->isLast, $h;
  ok  $j->empty;
  ok !$i->empty;

isLast($child)

Return the specified child if that child is last under its parent, else return undef.

   Parameter  Description
1  $child     Child

Example:

  my %l = map{$_->key=>$_} fromLetters('b(c)d(efgh(i(j)))')->by;
  my ($a, $b, $c, $d, $e, $f, $g, $h, $i, $j) = @l{'a'..'j'};

  is_deeply $a->brackets, 'a(b(c)d(efgh(i(j))))';
  is_deeply $b->singleChildOfParent, $c;
  is_deeply $e->isFirst, $e;
  ok !$f->isFirst;

  ok !$g->isLast;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  is_deeply $h->isLast, $h;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  ok  $j->empty;
  ok !$i->empty;

singleChildOfParent($parent)

Return the only child of this parent if the parent has an only child, else undef

   Parameter  Description
1  $parent    Parent

Example:

  my %l = map{$_->key=>$_} fromLetters('b(c)d(efgh(i(j)))')->by;
  my ($a, $b, $c, $d, $e, $f, $g, $h, $i, $j) = @l{'a'..'j'};

  is_deeply $a->brackets, 'a(b(c)d(efgh(i(j))))';

  is_deeply $b->singleChildOfParent, $c;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply $e->isFirst, $e;
  ok !$f->isFirst;
  ok !$g->isLast;
  is_deeply $h->isLast, $h;
  ok  $j->empty;
  ok !$i->empty;

empty($parent)

Return the specified parent if it has no children else undef

   Parameter  Description
1  $parent    Parent

Example:

  my %l = map{$_->key=>$_} fromLetters('b(c)d(efgh(i(j)))')->by;
  my ($a, $b, $c, $d, $e, $f, $g, $h, $i, $j) = @l{'a'..'j'};

  is_deeply $a->brackets, 'a(b(c)d(efgh(i(j))))';
  is_deeply $b->singleChildOfParent, $c;
  is_deeply $e->isFirst, $e;
  ok !$f->isFirst;
  ok !$g->isLast;
  is_deeply $h->isLast, $h;

  ok  $j->empty;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok !$i->empty;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

Put

Insert children into a tree.

putFirst($parent, $child)

Place a new child first under the specified parent and return the child.

   Parameter  Description
1  $parent    Parent
2  $child     Child

Example:

  my %l = map{$_->key=>$_} fromLetters('b(c)d(e)')->by;
  my ($a, $b, $d) = @l{qw(a b d)};

  my $z = $b->putNext(new 'z');
  is_deeply $z->brackets, 'z';
  is_deeply $a->brackets, 'a(b(c)zd(e))';

  my $y = $d->putPrev(new 'y');
  is_deeply $y->brackets, 'y';
  is_deeply $a->brackets, 'a(b(c)zyd(e))';

  $z->putLast(new 't');
  is_deeply $z->brackets, 'z(t)';
  is_deeply $a->brackets, 'a(b(c)z(t)yd(e))';


  $z->putFirst(new 's');  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply $a->brackets, 'a(b(c)z(st)yd(e))';

putLast($parent, $child)

Place a new child last under the specified parent and return the child.

   Parameter  Description
1  $parent    Parent
2  $child     Child

Example:

  my %l = map{$_->key=>$_} fromLetters('b(c)d(e)')->by;
  my ($a, $b, $d) = @l{qw(a b d)};

  my $z = $b->putNext(new 'z');
  is_deeply $z->brackets, 'z';
  is_deeply $a->brackets, 'a(b(c)zd(e))';

  my $y = $d->putPrev(new 'y');
  is_deeply $y->brackets, 'y';
  is_deeply $a->brackets, 'a(b(c)zyd(e))';


  $z->putLast(new 't');  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply $z->brackets, 'z(t)';
  is_deeply $a->brackets, 'a(b(c)z(t)yd(e))';

  $z->putFirst(new 's');
  is_deeply $a->brackets, 'a(b(c)z(st)yd(e))';

putNext($child, $new)

Place a new child after the specified child.

   Parameter  Description
1  $child     Existing child
2  $new       New child

Example:

  my %l = map{$_->key=>$_} fromLetters('b(c)d(e)')->by;
  my ($a, $b, $d) = @l{qw(a b d)};


  my $z = $b->putNext(new 'z');  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply $z->brackets, 'z';
  is_deeply $a->brackets, 'a(b(c)zd(e))';

  my $y = $d->putPrev(new 'y');
  is_deeply $y->brackets, 'y';
  is_deeply $a->brackets, 'a(b(c)zyd(e))';

  $z->putLast(new 't');
  is_deeply $z->brackets, 'z(t)';
  is_deeply $a->brackets, 'a(b(c)z(t)yd(e))';

  $z->putFirst(new 's');
  is_deeply $a->brackets, 'a(b(c)z(st)yd(e))';

putPrev($child, $new)

Place a new child before the specified child.

   Parameter  Description
1  $child     Child
2  $new       New child

Example:

  my %l = map{$_->key=>$_} fromLetters('b(c)d(e)')->by;
  my ($a, $b, $d) = @l{qw(a b d)};

  my $z = $b->putNext(new 'z');
  is_deeply $z->brackets, 'z';
  is_deeply $a->brackets, 'a(b(c)zd(e))';


  my $y = $d->putPrev(new 'y');  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply $y->brackets, 'y';
  is_deeply $a->brackets, 'a(b(c)zyd(e))';

  $z->putLast(new 't');
  is_deeply $z->brackets, 'z(t)';
  is_deeply $a->brackets, 'a(b(c)z(t)yd(e))';

  $z->putFirst(new 's');
  is_deeply $a->brackets, 'a(b(c)z(st)yd(e))';

Steps

Move the start or end of a scope forwards or backwards as suggested by Alex Monroe.

step($parent)

Make the first child of the specified parent the parents previous sibling and return the parent. In effect this moves the start of the parent one step forwards.

   Parameter  Description
1  $parent    Parent

Example:

  my %l = map{$_->key=>$_} fromLetters('b(c)d(efgh(i(j)))')->by;
  my ($a, $b, $d) = @l{qw(a b d)};

  is_deeply $a->brackets, 'a(b(c)d(efgh(i(j))))';


  $d->step;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply $a->brackets, 'a(b(c)ed(fgh(i(j))))';


  $d->stepBack;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply $a->brackets, 'a(b(c)d(efgh(i(j))))';


  $b->stepEnd;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply $a->brackets, 'a(b(cd(efgh(i(j)))))';


  $b->stepEndBack;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply $a->brackets, 'a(b(c)d(efgh(i(j))))';

stepEnd($parent)

Make the next sibling of the specified parent the parents last child and return the parent. In effect this moves the end of the parent one step forwards.

   Parameter  Description
1  $parent    Parent

Example:

  my %l = map{$_->key=>$_} fromLetters('b(c)d(efgh(i(j)))')->by;
  my ($a, $b, $d) = @l{qw(a b d)};

  is_deeply $a->brackets, 'a(b(c)d(efgh(i(j))))';

  $d->step;
  is_deeply $a->brackets, 'a(b(c)ed(fgh(i(j))))';

  $d->stepBack;
  is_deeply $a->brackets, 'a(b(c)d(efgh(i(j))))';


  $b->stepEnd;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply $a->brackets, 'a(b(cd(efgh(i(j)))))';


  $b->stepEndBack;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply $a->brackets, 'a(b(c)d(efgh(i(j))))';

stepBack()

Make the previous sibling of the specified parent the parents first child and return the parent. In effect this moves the start of the parent one step backwards.

Example:

  my %l = map{$_->key=>$_} fromLetters('b(c)d(efgh(i(j)))')->by;
  my ($a, $b, $d) = @l{qw(a b d)};

  is_deeply $a->brackets, 'a(b(c)d(efgh(i(j))))';

  $d->step;
  is_deeply $a->brackets, 'a(b(c)ed(fgh(i(j))))';


  $d->stepBack;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply $a->brackets, 'a(b(c)d(efgh(i(j))))';

  $b->stepEnd;
  is_deeply $a->brackets, 'a(b(cd(efgh(i(j)))))';

  $b->stepEndBack;
  is_deeply $a->brackets, 'a(b(c)d(efgh(i(j))))';

stepEndBack()

Make the last child of the specified parent the parents next sibling and return the parent. In effect this moves the end of the parent one step backwards.

Example:

  my %l = map{$_->key=>$_} fromLetters('b(c)d(efgh(i(j)))')->by;
  my ($a, $b, $d) = @l{qw(a b d)};

  is_deeply $a->brackets, 'a(b(c)d(efgh(i(j))))';

  $d->step;
  is_deeply $a->brackets, 'a(b(c)ed(fgh(i(j))))';

  $d->stepBack;
  is_deeply $a->brackets, 'a(b(c)d(efgh(i(j))))';

  $b->stepEnd;
  is_deeply $a->brackets, 'a(b(cd(efgh(i(j)))))';


  $b->stepEndBack;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply $a->brackets, 'a(b(c)d(efgh(i(j))))';

Edit

Edit a tree in situ.

cut($child)

Cut out a child and all its content and children, return it ready for reinsertion else where.

   Parameter  Description
1  $child     Child

Example:

  my %l = map{$_->key=>$_} fromLetters('b(c)y(x)z(st)d(efgh(i(j))))')->by;
  my ($a, $x, $y, $z) = @l{qw(a x y z)};

  is_deeply [map {$_->key} $x->context], [qw(x y a)];

  is_deeply join(' ', $a->by(sub{$_[0]->key})), "c b x y s t z e f g j i h d a";
  is_deeply join(' ', map{$_->key} $a->by),     "c b x y s t z e f g j i h d a";


  $z->cut;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply $a->brackets, 'a(b(c)y(x)d(efgh(i(j))))';

  $y->unwrap;
  is_deeply $a->brackets, 'a(b(c)xd(efgh(i(j))))';

  $y = $x->wrap('y');
  is_deeply $y->brackets, 'y(x)';
  is_deeply $a->brackets, 'a(b(c)y(x)d(efgh(i(j))))';

  $y->putNext($y->dup);
  is_deeply $a->brackets, 'a(b(c)y(x)y(x)d(efgh(i(j))))';

dup($parent)

Duplicate a parent and all its descendants.

   Parameter  Description
1  $parent    Parent

Example:

  my %l = map{$_->key=>$_} fromLetters('b(c)y(x)z(st)d(efgh(i(j))))')->by;
  my ($a, $x, $y, $z) = @l{qw(a x y z)};

  is_deeply [map {$_->key} $x->context], [qw(x y a)];

  is_deeply join(' ', $a->by(sub{$_[0]->key})), "c b x y s t z e f g j i h d a";
  is_deeply join(' ', map{$_->key} $a->by),     "c b x y s t z e f g j i h d a";

  $z->cut;
  is_deeply $a->brackets, 'a(b(c)y(x)d(efgh(i(j))))';

  $y->unwrap;
  is_deeply $a->brackets, 'a(b(c)xd(efgh(i(j))))';

  $y = $x->wrap('y');
  is_deeply $y->brackets, 'y(x)';
  is_deeply $a->brackets, 'a(b(c)y(x)d(efgh(i(j))))';


  $y->putNext($y->dup);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply $a->brackets, 'a(b(c)y(x)y(x)d(efgh(i(j))))';

unwrap($child)

Unwrap the specified child and return that child.

   Parameter  Description
1  $child     Child

Example:

  my %l = map{$_->key=>$_} fromLetters('b(c)y(x)z(st)d(efgh(i(j))))')->by;
  my ($a, $x, $y, $z) = @l{qw(a x y z)};

  is_deeply [map {$_->key} $x->context], [qw(x y a)];

  is_deeply join(' ', $a->by(sub{$_[0]->key})), "c b x y s t z e f g j i h d a";
  is_deeply join(' ', map{$_->key} $a->by),     "c b x y s t z e f g j i h d a";

  $z->cut;
  is_deeply $a->brackets, 'a(b(c)y(x)d(efgh(i(j))))';


  $y->unwrap;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply $a->brackets, 'a(b(c)xd(efgh(i(j))))';

  $y = $x->wrap('y');
  is_deeply $y->brackets, 'y(x)';
  is_deeply $a->brackets, 'a(b(c)y(x)d(efgh(i(j))))';

  $y->putNext($y->dup);
  is_deeply $a->brackets, 'a(b(c)y(x)y(x)d(efgh(i(j))))';

wrap($child, $key)

Wrap the specified child with a new parent and return the new parent.

   Parameter  Description
1  $child     Child to wrap
2  $key       User data for new wrapping parent

Example:

  my %l = map{$_->key=>$_} fromLetters('b(c)y(x)z(st)d(efgh(i(j))))')->by;
  my ($a, $x, $y, $z) = @l{qw(a x y z)};

  is_deeply [map {$_->key} $x->context], [qw(x y a)];

  is_deeply join(' ', $a->by(sub{$_[0]->key})), "c b x y s t z e f g j i h d a";
  is_deeply join(' ', map{$_->key} $a->by),     "c b x y s t z e f g j i h d a";

  $z->cut;
  is_deeply $a->brackets, 'a(b(c)y(x)d(efgh(i(j))))';


  $y->unwrap;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply $a->brackets, 'a(b(c)xd(efgh(i(j))))';


  $y = $x->wrap('y');  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply $y->brackets, 'y(x)';
  is_deeply $a->brackets, 'a(b(c)y(x)d(efgh(i(j))))';

  $y->putNext($y->dup);
  is_deeply $a->brackets, 'a(b(c)y(x)y(x)d(efgh(i(j))))';

merge($parent)

Merge the children of the specified parent with those of the surrounding parents if the L[key] data of those parents smartmatch that of the specified parent. Merged parents are unwrapped. Returns the specified parent regardless. From a proposal made by Micaela Monroe.

   Parameter  Description
1  $parent    Merging parent

Example:

  my %l = map{$_->key=>$_} fromLetters('b(c)d(efgh(i(j)))')->by;
  my ($a, $d) = @l{qw(a d)};

  $d->split;
  is_deeply $d->brackets,       'd(d(e)d(f)d(g)d(h(i(j))))';
  is_deeply $a->brackets, 'a(b(c)d(d(e)d(f)d(g)d(h(i(j)))))';


  $d->first->merge;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply $d->brackets,       'd(d(efgh(i(j))))';
  is_deeply $a->brackets, 'a(b(c)d(d(efgh(i(j)))))';

  $d->first->unwrap;
  is_deeply $d->brackets,       'd(efgh(i(j)))';
  is_deeply $a->brackets, 'a(b(c)d(efgh(i(j))))';

split($parent)

Make the specified parent a grandparent of each of its children by interposing a copy of the specified parent between the specified parent and each of its children. Return the specified parent.

   Parameter  Description
1  $parent    Parent to make into a grand parent

Example:

  my %l = map{$_->key=>$_} fromLetters('b(c)d(efgh(i(j)))')->by;
  my ($a, $d) = @l{qw(a d)};


  $d->split;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply $d->brackets,       'd(d(e)d(f)d(g)d(h(i(j))))';
  is_deeply $a->brackets, 'a(b(c)d(d(e)d(f)d(g)d(h(i(j)))))';

  $d->first->merge;
  is_deeply $d->brackets,       'd(d(efgh(i(j))))';
  is_deeply $a->brackets, 'a(b(c)d(d(efgh(i(j)))))';

  $d->first->unwrap;
  is_deeply $d->brackets,       'd(efgh(i(j)))';
  is_deeply $a->brackets, 'a(b(c)d(efgh(i(j))))';

Traverse

Traverse a tree.

by($tree, $sub)

Traverse a tree in post-order to process each child with the specified sub and return an array of the results of processing each child. If no sub sub is specified, the children are returned in tree order.

   Parameter  Description
1  $tree      Tree
2  $sub       Optional sub to process each child

Example:

  my %l = map{$_->key=>$_} fromLetters('b(c)y(x)z(st)d(efgh(i(j))))')->by;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  my ($a, $x, $y, $z) = @l{qw(a x y z)};

  is_deeply [map {$_->key} $x->context], [qw(x y a)];


  is_deeply join(' ', $a->by(sub{$_[0]->key})), "c b x y s t z e f g j i h d a";  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  is_deeply join(' ', map{$_->key} $a->by),     "c b x y s t z e f g j i h d a";  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  $z->cut;
  is_deeply $a->brackets, 'a(b(c)y(x)d(efgh(i(j))))';

  $y->unwrap;
  is_deeply $a->brackets, 'a(b(c)xd(efgh(i(j))))';

  $y = $x->wrap('y');
  is_deeply $y->brackets, 'y(x)';
  is_deeply $a->brackets, 'a(b(c)y(x)d(efgh(i(j))))';

  $y->putNext($y->dup);
  is_deeply $a->brackets, 'a(b(c)y(x)y(x)d(efgh(i(j))))';

select($tree, $select)

Select matching children in a tree in post-order. A child can be selected via named value, array of values, a hash of values, a regular expression or a sub reference.

   Parameter  Description
1  $tree      Tree
2  $select    Method to select a child

Example:

  my $a = Tree::Ops::new 'a', 'A';
  for(1..2)
   {$a->open  ('b', "B$_");
    $a->single('c', "C$_");
    ok $a->activeScope->key eq 'b';
    $a->close;
   }
  $a->single  ('d', 'D');
  $a->single  ('e', 'E');
  is_deeply $a->print, <<END;
Key    Value
a      A
  b    B1
    c  C1
  b    B2
    c  C2
  d    D
  e    E
END

  is_deeply [map{$_->value} $a->by], [qw(C1 B1 C2 B2 D E A)];

  is_deeply $a->lastMost->prev->prev->first->key,           'c';
  is_deeply $a->first->next->last->parent->first->value,    'C2';


  is_deeply [map{$_->value} $a->select('b')],               [qw(B1 B2)];  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  is_deeply [map{$_->value} $a->select(qr(b|c))],           [qw(B1 C1 B2 C2)];  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  is_deeply [map{$_->value} $a->select(sub{$_[0] eq 'd'})], [qw(D)];  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  $a->first->next->stepEnd->stepEnd->first->next->stepBack;
  is_deeply $a->print, <<END;
Key      Value
a        A
  b      B1
    c    C1
  b      B2
    d    D
      c  C2
    e    E
END

Partitions

Various partitions of the tree

leaves($tree)

The set of all children without further children, i.e. each leaf of the tree.

   Parameter  Description
1  $tree      Tree

Example:

  my $a = fromLetters('b(c)y(x)d(efgh(i(j)))');
  is_deeply $a->print, <<END;
Key        Value
a
  b
    c
  y
    x
  d
    e
    f
    g
    h
      i
        j
END

  is_deeply $a->xml,
   '<a><b><c/></b><y><x/></y><d><e/><f/><g/><h><i><j/></i></h></d></a>';

  my ($c, $b, $x, $y, $e, $f, $g, $j, $i, $h, $d) = $a->by;


  is_deeply [$c, $x, $e, $f, $g, $j], [$a->leaves];  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply [$a, $b, $y, $d, $h, $i], [$a->parentsPreOrder];
  is_deeply [$b, $y, $i, $h, $d, $a], [$a->parentsPostOrder];
  is_deeply [$a->parents],            [$a->parentsPostOrder];

  is_deeply [$a, $d, $h, $i, $y, $b], [$a->parentsReversePreOrder];
  is_deeply [$i, $h, $d, $y, $b, $a], [$a->parentsReversePostOrder];

  ok !$j->parents;

  ok  $a->lastMost  == $j;
  ok !$a->prevMost;
  ok  $j->prevMost  == $g;
  ok  $i->prevMost  == $g;
  ok  $h->prevMost  == $g;
  ok  $g->prevMost  == $f;
  ok  $f->prevMost  == $e;
  ok  $e->prevMost  == $x;
  ok  $d->prevMost  == $x;
  ok  $x->prevMost  == $c;
  ok  $y->prevMost  == $c;
  ok !$c->prevMost;
  ok !$b->prevMost;
  ok !$a->prevMost;

  ok  $a->firstMost == $c;
  ok  $a->nextMost  == $c;
  ok  $b->nextMost  == $c;
  ok  $c->nextMost  == $x;
  ok  $y->nextMost  == $x;
  ok  $x->nextMost  == $e;
  ok  $d->nextMost  == $e;
  ok  $e->nextMost  == $f;
  ok  $f->nextMost  == $g;
  ok  $g->nextMost  == $j;
  ok  $h->nextMost  == $j;
  ok  $i->nextMost  == $j;
  ok !$j->nextMost;

parentsPreOrder($tree)

The set of all parents in the tree, i.e. each non leaf of the tree, i.e the interior of the tree in normal pre-order.

   Parameter  Description
1  $tree      Tree

Example:

  my $a = fromLetters('b(c)y(x)d(efgh(i(j)))');
  is_deeply $a->print, <<END;
Key        Value
a
  b
    c
  y
    x
  d
    e
    f
    g
    h
      i
        j
END

  is_deeply $a->xml,
   '<a><b><c/></b><y><x/></y><d><e/><f/><g/><h><i><j/></i></h></d></a>';

  my ($c, $b, $x, $y, $e, $f, $g, $j, $i, $h, $d) = $a->by;

  is_deeply [$c, $x, $e, $f, $g, $j], [$a->leaves];

  is_deeply [$a, $b, $y, $d, $h, $i], [$a->parentsPreOrder];  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply [$b, $y, $i, $h, $d, $a], [$a->parentsPostOrder];
  is_deeply [$a->parents],            [$a->parentsPostOrder];

  is_deeply [$a, $d, $h, $i, $y, $b], [$a->parentsReversePreOrder];
  is_deeply [$i, $h, $d, $y, $b, $a], [$a->parentsReversePostOrder];

  ok !$j->parents;

  ok  $a->lastMost  == $j;
  ok !$a->prevMost;
  ok  $j->prevMost  == $g;
  ok  $i->prevMost  == $g;
  ok  $h->prevMost  == $g;
  ok  $g->prevMost  == $f;
  ok  $f->prevMost  == $e;
  ok  $e->prevMost  == $x;
  ok  $d->prevMost  == $x;
  ok  $x->prevMost  == $c;
  ok  $y->prevMost  == $c;
  ok !$c->prevMost;
  ok !$b->prevMost;
  ok !$a->prevMost;

  ok  $a->firstMost == $c;
  ok  $a->nextMost  == $c;
  ok  $b->nextMost  == $c;
  ok  $c->nextMost  == $x;
  ok  $y->nextMost  == $x;
  ok  $x->nextMost  == $e;
  ok  $d->nextMost  == $e;
  ok  $e->nextMost  == $f;
  ok  $f->nextMost  == $g;
  ok  $g->nextMost  == $j;
  ok  $h->nextMost  == $j;
  ok  $i->nextMost  == $j;
  ok !$j->nextMost;

parentsPostOrder($tree)

The set of all parents in the tree, i.e. each non leaf of the tree, i.e the interior of the tree in normal post-order.

   Parameter  Description
1  $tree      Tree

Example:

  my $a = fromLetters('b(c)y(x)d(efgh(i(j)))');
  is_deeply $a->print, <<END;
Key        Value
a
  b
    c
  y
    x
  d
    e
    f
    g
    h
      i
        j
END

  is_deeply $a->xml,
   '<a><b><c/></b><y><x/></y><d><e/><f/><g/><h><i><j/></i></h></d></a>';

  my ($c, $b, $x, $y, $e, $f, $g, $j, $i, $h, $d) = $a->by;

  is_deeply [$c, $x, $e, $f, $g, $j], [$a->leaves];
  is_deeply [$a, $b, $y, $d, $h, $i], [$a->parentsPreOrder];

  is_deeply [$b, $y, $i, $h, $d, $a], [$a->parentsPostOrder];  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  is_deeply [$a->parents],            [$a->parentsPostOrder];  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  is_deeply [$a, $d, $h, $i, $y, $b], [$a->parentsReversePreOrder];
  is_deeply [$i, $h, $d, $y, $b, $a], [$a->parentsReversePostOrder];

  ok !$j->parents;

  ok  $a->lastMost  == $j;
  ok !$a->prevMost;
  ok  $j->prevMost  == $g;
  ok  $i->prevMost  == $g;
  ok  $h->prevMost  == $g;
  ok  $g->prevMost  == $f;
  ok  $f->prevMost  == $e;
  ok  $e->prevMost  == $x;
  ok  $d->prevMost  == $x;
  ok  $x->prevMost  == $c;
  ok  $y->prevMost  == $c;
  ok !$c->prevMost;
  ok !$b->prevMost;
  ok !$a->prevMost;

  ok  $a->firstMost == $c;
  ok  $a->nextMost  == $c;
  ok  $b->nextMost  == $c;
  ok  $c->nextMost  == $x;
  ok  $y->nextMost  == $x;
  ok  $x->nextMost  == $e;
  ok  $d->nextMost  == $e;
  ok  $e->nextMost  == $f;
  ok  $f->nextMost  == $g;
  ok  $g->nextMost  == $j;
  ok  $h->nextMost  == $j;
  ok  $i->nextMost  == $j;
  ok !$j->nextMost;

parentsReversePreOrder($tree)

The set of all parents in the tree, i.e. each non leaf of the tree, i.e the interior of the tree in reverse pre-order.

   Parameter  Description
1  $tree      Tree

Example:

  my $a = fromLetters('b(c)y(x)d(efgh(i(j)))');
  is_deeply $a->print, <<END;
Key        Value
a
  b
    c
  y
    x
  d
    e
    f
    g
    h
      i
        j
END

  is_deeply $a->xml,
   '<a><b><c/></b><y><x/></y><d><e/><f/><g/><h><i><j/></i></h></d></a>';

  my ($c, $b, $x, $y, $e, $f, $g, $j, $i, $h, $d) = $a->by;

  is_deeply [$c, $x, $e, $f, $g, $j], [$a->leaves];
  is_deeply [$a, $b, $y, $d, $h, $i], [$a->parentsPreOrder];
  is_deeply [$b, $y, $i, $h, $d, $a], [$a->parentsPostOrder];
  is_deeply [$a->parents],            [$a->parentsPostOrder];


  is_deeply [$a, $d, $h, $i, $y, $b], [$a->parentsReversePreOrder];  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply [$i, $h, $d, $y, $b, $a], [$a->parentsReversePostOrder];

  ok !$j->parents;

  ok  $a->lastMost  == $j;
  ok !$a->prevMost;
  ok  $j->prevMost  == $g;
  ok  $i->prevMost  == $g;
  ok  $h->prevMost  == $g;
  ok  $g->prevMost  == $f;
  ok  $f->prevMost  == $e;
  ok  $e->prevMost  == $x;
  ok  $d->prevMost  == $x;
  ok  $x->prevMost  == $c;
  ok  $y->prevMost  == $c;
  ok !$c->prevMost;
  ok !$b->prevMost;
  ok !$a->prevMost;

  ok  $a->firstMost == $c;
  ok  $a->nextMost  == $c;
  ok  $b->nextMost  == $c;
  ok  $c->nextMost  == $x;
  ok  $y->nextMost  == $x;
  ok  $x->nextMost  == $e;
  ok  $d->nextMost  == $e;
  ok  $e->nextMost  == $f;
  ok  $f->nextMost  == $g;
  ok  $g->nextMost  == $j;
  ok  $h->nextMost  == $j;
  ok  $i->nextMost  == $j;
  ok !$j->nextMost;

parentsReversePostOrder($tree)

The set of all parents in the tree, i.e. each non leaf of the tree, i.e the interior of the tree in reverse post-order.

   Parameter  Description
1  $tree      Tree

Example:

  my $a = fromLetters('b(c)y(x)d(efgh(i(j)))');
  is_deeply $a->print, <<END;
Key        Value
a
  b
    c
  y
    x
  d
    e
    f
    g
    h
      i
        j
END

  is_deeply $a->xml,
   '<a><b><c/></b><y><x/></y><d><e/><f/><g/><h><i><j/></i></h></d></a>';

  my ($c, $b, $x, $y, $e, $f, $g, $j, $i, $h, $d) = $a->by;

  is_deeply [$c, $x, $e, $f, $g, $j], [$a->leaves];
  is_deeply [$a, $b, $y, $d, $h, $i], [$a->parentsPreOrder];
  is_deeply [$b, $y, $i, $h, $d, $a], [$a->parentsPostOrder];
  is_deeply [$a->parents],            [$a->parentsPostOrder];

  is_deeply [$a, $d, $h, $i, $y, $b], [$a->parentsReversePreOrder];

  is_deeply [$i, $h, $d, $y, $b, $a], [$a->parentsReversePostOrder];  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok !$j->parents;

  ok  $a->lastMost  == $j;
  ok !$a->prevMost;
  ok  $j->prevMost  == $g;
  ok  $i->prevMost  == $g;
  ok  $h->prevMost  == $g;
  ok  $g->prevMost  == $f;
  ok  $f->prevMost  == $e;
  ok  $e->prevMost  == $x;
  ok  $d->prevMost  == $x;
  ok  $x->prevMost  == $c;
  ok  $y->prevMost  == $c;
  ok !$c->prevMost;
  ok !$b->prevMost;
  ok !$a->prevMost;

  ok  $a->firstMost == $c;
  ok  $a->nextMost  == $c;
  ok  $b->nextMost  == $c;
  ok  $c->nextMost  == $x;
  ok  $y->nextMost  == $x;
  ok  $x->nextMost  == $e;
  ok  $d->nextMost  == $e;
  ok  $e->nextMost  == $f;
  ok  $f->nextMost  == $g;
  ok  $g->nextMost  == $j;
  ok  $h->nextMost  == $j;
  ok  $i->nextMost  == $j;
  ok !$j->nextMost;

parents($tree)

The set of all parents in the tree, i.e. each non leaf of the tree, i.e the interior of the tree in normal post-order.

   Parameter  Description
1  $tree      Tree

Example:

  my $a = fromLetters('b(c)y(x)d(efgh(i(j)))');
  is_deeply $a->print, <<END;
Key        Value
a
  b
    c
  y
    x
  d
    e
    f
    g
    h
      i
        j
END

  is_deeply $a->xml,
   '<a><b><c/></b><y><x/></y><d><e/><f/><g/><h><i><j/></i></h></d></a>';

  my ($c, $b, $x, $y, $e, $f, $g, $j, $i, $h, $d) = $a->by;

  is_deeply [$c, $x, $e, $f, $g, $j], [$a->leaves];

  is_deeply [$a, $b, $y, $d, $h, $i], [$a->parentsPreOrder];  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  is_deeply [$b, $y, $i, $h, $d, $a], [$a->parentsPostOrder];  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  is_deeply [$a->parents],            [$a->parentsPostOrder];  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲



  is_deeply [$a, $d, $h, $i, $y, $b], [$a->parentsReversePreOrder];  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  is_deeply [$i, $h, $d, $y, $b, $a], [$a->parentsReversePostOrder];  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲



  ok !$j->parents;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok  $a->lastMost  == $j;
  ok !$a->prevMost;
  ok  $j->prevMost  == $g;
  ok  $i->prevMost  == $g;
  ok  $h->prevMost  == $g;
  ok  $g->prevMost  == $f;
  ok  $f->prevMost  == $e;
  ok  $e->prevMost  == $x;
  ok  $d->prevMost  == $x;
  ok  $x->prevMost  == $c;
  ok  $y->prevMost  == $c;
  ok !$c->prevMost;
  ok !$b->prevMost;
  ok !$a->prevMost;

  ok  $a->firstMost == $c;
  ok  $a->nextMost  == $c;
  ok  $b->nextMost  == $c;
  ok  $c->nextMost  == $x;
  ok  $y->nextMost  == $x;
  ok  $x->nextMost  == $e;
  ok  $d->nextMost  == $e;
  ok  $e->nextMost  == $f;
  ok  $f->nextMost  == $g;
  ok  $g->nextMost  == $j;
  ok  $h->nextMost  == $j;
  ok  $i->nextMost  == $j;
  ok !$j->nextMost;

Order

Check the order and relative position of children in a tree.

above($first, $second)

Return the first child if it is above the second child else return undef.

   Parameter  Description
1  $first     First child
2  $second    Second child

Example:

  my %l = map{$_->key=>$_} fromLetters('b(c(d(efgh(i(j)k)l)m)n')->by;
  my ($a, $b, $c, $d, $e, $f, $g, $h, $i, $j, $k, $l, $m, $n) = @l{'a'..'n'};

  is_deeply $a->print, <<END;
Key            Value
a
  b
    c
      d
        e
        f
        g
        h
          i
            j
          k
        l
      m
    n
END


  ok  $c->above($j)  == $c;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok !$m->above($j);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok  $i->below($b)  == $i;
  ok !$i->below($n);

  ok  $n->after($e)  == $n;
  ok !$k->after($c);

  ok  $c->before($n) == $c;
  ok !$c->before($m);

  is_deeply [map{$_->key} $j->lineage($d)], [qw(j i h d)];
  ok !$d->lineage($m);

below($first, $second)

Return the first child if it is below the second child else return undef.

   Parameter  Description
1  $first     First child
2  $second    Second child

Example:

  my %l = map{$_->key=>$_} fromLetters('b(c(d(efgh(i(j)k)l)m)n')->by;
  my ($a, $b, $c, $d, $e, $f, $g, $h, $i, $j, $k, $l, $m, $n) = @l{'a'..'n'};

  is_deeply $a->print, <<END;
Key            Value
a
  b
    c
      d
        e
        f
        g
        h
          i
            j
          k
        l
      m
    n
END

  ok  $c->above($j)  == $c;
  ok !$m->above($j);


  ok  $i->below($b)  == $i;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok !$i->below($n);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok  $n->after($e)  == $n;
  ok !$k->after($c);

  ok  $c->before($n) == $c;
  ok !$c->before($m);

  is_deeply [map{$_->key} $j->lineage($d)], [qw(j i h d)];
  ok !$d->lineage($m);

after($first, $second)

Return the first child if it occurs strictly after the second child in the tree or else undef if the first child is above, below or before the second child.

   Parameter  Description
1  $first     First child
2  $second    Second child

Example:

  my %l = map{$_->key=>$_} fromLetters('b(c(d(efgh(i(j)k)l)m)n')->by;
  my ($a, $b, $c, $d, $e, $f, $g, $h, $i, $j, $k, $l, $m, $n) = @l{'a'..'n'};

  is_deeply $a->print, <<END;
Key            Value
a
  b
    c
      d
        e
        f
        g
        h
          i
            j
          k
        l
      m
    n
END

  ok  $c->above($j)  == $c;
  ok !$m->above($j);

  ok  $i->below($b)  == $i;
  ok !$i->below($n);


  ok  $n->after($e)  == $n;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok !$k->after($c);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok  $c->before($n) == $c;
  ok !$c->before($m);

  is_deeply [map{$_->key} $j->lineage($d)], [qw(j i h d)];
  ok !$d->lineage($m);

before($first, $second)

Return the first child if it occurs strictly before the second child in the tree or else undef if the first child is above, below or after the second child.

   Parameter  Description
1  $first     First child
2  $second    Second child

Example:

  my %l = map{$_->key=>$_} fromLetters('b(c(d(efgh(i(j)k)l)m)n')->by;
  my ($a, $b, $c, $d, $e, $f, $g, $h, $i, $j, $k, $l, $m, $n) = @l{'a'..'n'};

  is_deeply $a->print, <<END;
Key            Value
a
  b
    c
      d
        e
        f
        g
        h
          i
            j
          k
        l
      m
    n
END

  ok  $c->above($j)  == $c;
  ok !$m->above($j);

  ok  $i->below($b)  == $i;
  ok !$i->below($n);

  ok  $n->after($e)  == $n;
  ok !$k->after($c);


  ok  $c->before($n) == $c;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok !$c->before($m);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  is_deeply [map{$_->key} $j->lineage($d)], [qw(j i h d)];
  ok !$d->lineage($m);

Paths

Find paths between nodes

siblingsBefore($child)

Return a list of siblings before the specified child.

   Parameter  Description
1  $child     Child

Example:

  my $a = fromLetters('b(cde(f)ghi)j');
  my ($c, $d, $f, $e, $g, $h, $i, $b, $j) = $a->by;
# ok eval qq(\$$_->key eq '$_') for 'a'..'j';
  is_deeply $a->print, <<END;
Key      Value
a
  b
    c
    d
    e
      f
    g
    h
    i
  j
END

  is_deeply [$d->siblingsStrictlyBetween($h)], [$e, $g];
  is_deeply [$d->siblingsAfter],               [$e, $g, $h, $i];

  is_deeply [$g->siblingsBefore],              [$c, $d, $e];  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  eval {$e->siblingsStrictlyBetween($f)};
  ok $@ =~ m(Must be siblings);

siblingsAfter($child)

Return a list of siblings after the specified child.

   Parameter  Description
1  $child     Child

Example:

  my $a = fromLetters('b(cde(f)ghi)j');
  my ($c, $d, $f, $e, $g, $h, $i, $b, $j) = $a->by;
# ok eval qq(\$$_->key eq '$_') for 'a'..'j';
  is_deeply $a->print, <<END;
Key      Value
a
  b
    c
    d
    e
      f
    g
    h
    i
  j
END

  is_deeply [$d->siblingsStrictlyBetween($h)], [$e, $g];

  is_deeply [$d->siblingsAfter],               [$e, $g, $h, $i];  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply [$g->siblingsBefore],              [$c, $d, $e];
  eval {$e->siblingsStrictlyBetween($f)};
  ok $@ =~ m(Must be siblings);

siblingsStrictlyBetween($start, $finish)

Return a list of the siblings strictly between two children of the same parent else return undef.

   Parameter  Description
1  $start     Start child
2  $finish    Finish child

Example:

  my $a = fromLetters('b(cde(f)ghi)j');
  my ($c, $d, $f, $e, $g, $h, $i, $b, $j) = $a->by;
# ok eval qq(\$$_->key eq '$_') for 'a'..'j';
  is_deeply $a->print, <<END;
Key      Value
a
  b
    c
    d
    e
      f
    g
    h
    i
  j
END


  is_deeply [$d->siblingsStrictlyBetween($h)], [$e, $g];  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply [$d->siblingsAfter],               [$e, $g, $h, $i];
  is_deeply [$g->siblingsBefore],              [$c, $d, $e];

  eval {$e->siblingsStrictlyBetween($f)};  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  ok $@ =~ m(Must be siblings);

lineage($child, $ancestor)

Return the path from the specified child to the specified ancestor else return undef if the child is not a descendant of the ancestor.

   Parameter  Description
1  $child     Child
2  $ancestor  Ancestor

Example:

  my %l = map{$_->key=>$_} fromLetters('b(c(d(efgh(i(j)k)l)m)n')->by;
  my ($a, $b, $c, $d, $e, $f, $g, $h, $i, $j, $k, $l, $m, $n) = @l{'a'..'n'};

  is_deeply $a->print, <<END;
Key            Value
a
  b
    c
      d
        e
        f
        g
        h
          i
            j
          k
        l
      m
    n
END

  ok  $c->above($j)  == $c;
  ok !$m->above($j);

  ok  $i->below($b)  == $i;
  ok !$i->below($n);

  ok  $n->after($e)  == $n;
  ok !$k->after($c);

  ok  $c->before($n) == $c;
  ok !$c->before($m);


  is_deeply [map{$_->key} $j->lineage($d)], [qw(j i h d)];  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok !$d->lineage($m);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

nextPreOrderPath($start)

Return a list of children visited between the specified child and the next child in pre-order.

   Parameter  Description
1  $start     The child at the start of the path

Example:

  my @p = [my $a = fromLetters('b(c(d(e(fg)hi(j(kl)m)n)op)q)r')];

  for(1..99)

   {my @n = $p[-1][-1]->nextPreOrderPath;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

    last unless @n;
    push @p, [@n];
   }

  is_deeply $a->print, <<END;
Key            Value
a
  b
    c
      d
        e
          f
          g
        h
        i
          j
            k
            l
          m
        n
      o
      p
    q
  r
END

  my @pre = map{[map{$_->key} @$_]} @p;
  is_deeply scalar(@pre), scalar(['a'..'r']->@*);
  is_deeply [@pre],
   [["a"],
    ["b"],
    ["c"],
    ["d"],
    ["e"],
    ["f"],
    ["g"],
    ["e", "h"],
    ["i"],
    ["j"],
    ["k"],
    ["l"],
    ["j", "m"],
    ["i", "n"],
    ["d", "o"],
    ["p"],
    ["c", "q"],
    ["b", "r"]];

nextPostOrderPath($start)

Return a list of children visited between the specified child and the next child in post-order.

   Parameter  Description
1  $start     The child at the start of the path

Example:

  my @n = my $a = fromLetters('b(c(d(e(fg)hi(j(kl)m)n)op)q)r');
  my @p;
  for(1..99)

   {@n = $n[-1]->nextPostOrderPath;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

    last unless @n;
    push @p, [@n];
    last if $n[-1] == $a;
   }

  is_deeply $a->print, <<END;
Key            Value
a
  b
    c
      d
        e
          f
          g
        h
        i
          j
            k
            l
          m
        n
      o
      p
    q
  r
END

  my @post = map{[map{$_->key} @$_]} @p;
  is_deeply scalar(@post), scalar(['a'..'r']->@*);
  is_deeply [@post],
 [["b" .. "f"],
  ["g"],
  ["e"],
  ["h"],
  ["i", "j", "k"],
  ["l"],
  ["j"],
  ["m"],
  ["i"],
  ["n"],
  ["d"],
  ["o"],
  ["p"],
  ["c"],
  ["q"],
  ["b"],
  ["r"],
  ["a"]];

prevPostOrderPath($start)

Return a list of children visited between the specified child and the previous child in post-order.

   Parameter  Description
1  $start     The child at the start of the path

Example:

  my @p = [my $a = fromLetters('b(c(d(e(fg)hi(j(kl)m)n)op)q)r')];

  for(1..99)

   {my @n = $p[-1][-1]->prevPostOrderPath;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

    last unless @n;
    push @p, [@n];
   }

  is_deeply $a->print, <<END;
Key            Value
a
  b
    c
      d
        e
          f
          g
        h
        i
          j
            k
            l
          m
        n
      o
      p
    q
  r
END

  my @post = map{[map{$_->key} @$_]} @p;
  is_deeply scalar(@post), scalar(['a'..'r']->@*);
  is_deeply [@post],
   [["a"],
    ["r"],
    ["b"],
    ["q"],
    ["c"],
    ["p"],
    ["o"],
    ["d"],
    ["n"],
    ["i"],
    ["m"],
    ["j"],
    ["l"],
    ["k"],
    ["j", "i", "h"],
    ["e"],
    ["g"],
    ["f"]];

prevPreOrderPath($start)

Return a list of children visited between the specified child and the previous child in pre-order.

   Parameter  Description
1  $start     The child at the start of the path

Example:

  my @n = my $a = fromLetters('b(c(d(e(fg)hi(j(kl)m)n)op)q)r');
  my @p;
  for(1..99)

   {@n = $n[-1]->prevPreOrderPath;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

    last unless @n;
    push @p, [@n];
    last if $n[-1] == $a;
   }

  is_deeply $a->print, <<END;
Key            Value
a
  b
    c
      d
        e
          f
          g
        h
        i
          j
            k
            l
          m
        n
      o
      p
    q
  r
END

  my @pre = map{[map{$_->key} @$_]} @p;
  is_deeply scalar(@pre), scalar(['a'..'r']->@*);
  is_deeply [@pre],
   [["r"],
    ["b", "q"],
    ["c", "p"],
    ["o"],
    ["d", "n"],
    ["i", "m"],
    ["j", "l"],
    ["k"],
    ["j"],
    ["i"],
    ["h"],
    ["e", "g"],
    ["f"],
    ["e"],
    ["d"],
    ["c"],
    ["b"],
    ["a"]];

Print

Print a tree.

printPreOrder($tree, $print)

Print tree in normal pre-order.

   Parameter  Description
1  $tree      Tree
2  $print     Optional print method

Example:

  my ($c, $b, $d, $a) = fromLetters('b(c)d')->by;
  my sub test(@) {join ' ', map{join '', $_->key} @_}


  is_deeply $a->printPreOrder, <<END;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

Key    Value
a
  b
    c
  d
END

  is_deeply test($a->nextPreOrderPath), 'b';
  is_deeply test($b->nextPreOrderPath), 'c';
  is_deeply test($c->nextPreOrderPath), 'b d';
  is_deeply test($d->nextPreOrderPath), '';

  is_deeply $a->printPostOrder, <<END;
Key    Value
    c
  b
  d
a
END

  is_deeply test($a->nextPostOrderPath), 'b c';
  is_deeply test($c->nextPostOrderPath), 'b';
  is_deeply test($b->nextPostOrderPath), 'd';
  is_deeply test($d->nextPostOrderPath), 'a';

  is_deeply $a->printReversePreOrder, <<END;
Key    Value
a
  d
  b
    c
END
  is_deeply test($a->prevPreOrderPath), 'd';
  is_deeply test($d->prevPreOrderPath), 'b c';
  is_deeply test($c->prevPreOrderPath), 'b';
  is_deeply test($b->prevPreOrderPath), 'a';

  is_deeply $a->printReversePostOrder, <<END;
Key    Value
  d
    c
  b
a
END

  is_deeply test($a->prevPostOrderPath), 'd';
  is_deeply test($d->prevPostOrderPath), 'b';
  is_deeply test($b->prevPostOrderPath), 'c';
  is_deeply test($c->prevPostOrderPath), '';

printPostOrder($tree, $print)

Print tree in normal post-order.

   Parameter  Description
1  $tree      Tree
2  $print     Optional print method

Example:

  my ($c, $b, $d, $a) = fromLetters('b(c)d')->by;
  my sub test(@) {join ' ', map{join '', $_->key} @_}

  is_deeply $a->printPreOrder, <<END;
Key    Value
a
  b
    c
  d
END

  is_deeply test($a->nextPreOrderPath), 'b';
  is_deeply test($b->nextPreOrderPath), 'c';
  is_deeply test($c->nextPreOrderPath), 'b d';
  is_deeply test($d->nextPreOrderPath), '';


  is_deeply $a->printPostOrder, <<END;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

Key    Value
    c
  b
  d
a
END

  is_deeply test($a->nextPostOrderPath), 'b c';
  is_deeply test($c->nextPostOrderPath), 'b';
  is_deeply test($b->nextPostOrderPath), 'd';
  is_deeply test($d->nextPostOrderPath), 'a';

  is_deeply $a->printReversePreOrder, <<END;
Key    Value
a
  d
  b
    c
END
  is_deeply test($a->prevPreOrderPath), 'd';
  is_deeply test($d->prevPreOrderPath), 'b c';
  is_deeply test($c->prevPreOrderPath), 'b';
  is_deeply test($b->prevPreOrderPath), 'a';

  is_deeply $a->printReversePostOrder, <<END;
Key    Value
  d
    c
  b
a
END

  is_deeply test($a->prevPostOrderPath), 'd';
  is_deeply test($d->prevPostOrderPath), 'b';
  is_deeply test($b->prevPostOrderPath), 'c';
  is_deeply test($c->prevPostOrderPath), '';

printReversePreOrder($tree, $print)

Print tree in reverse pre-order

   Parameter  Description
1  $tree      Tree
2  $print     Optional print method

Example:

  my ($c, $b, $d, $a) = fromLetters('b(c)d')->by;
  my sub test(@) {join ' ', map{join '', $_->key} @_}

  is_deeply $a->printPreOrder, <<END;
Key    Value
a
  b
    c
  d
END

  is_deeply test($a->nextPreOrderPath), 'b';
  is_deeply test($b->nextPreOrderPath), 'c';
  is_deeply test($c->nextPreOrderPath), 'b d';
  is_deeply test($d->nextPreOrderPath), '';

  is_deeply $a->printPostOrder, <<END;
Key    Value
    c
  b
  d
a
END

  is_deeply test($a->nextPostOrderPath), 'b c';
  is_deeply test($c->nextPostOrderPath), 'b';
  is_deeply test($b->nextPostOrderPath), 'd';
  is_deeply test($d->nextPostOrderPath), 'a';


  is_deeply $a->printReversePreOrder, <<END;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

Key    Value
a
  d
  b
    c
END
  is_deeply test($a->prevPreOrderPath), 'd';
  is_deeply test($d->prevPreOrderPath), 'b c';
  is_deeply test($c->prevPreOrderPath), 'b';
  is_deeply test($b->prevPreOrderPath), 'a';

  is_deeply $a->printReversePostOrder, <<END;
Key    Value
  d
    c
  b
a
END

  is_deeply test($a->prevPostOrderPath), 'd';
  is_deeply test($d->prevPostOrderPath), 'b';
  is_deeply test($b->prevPostOrderPath), 'c';
  is_deeply test($c->prevPostOrderPath), '';

printReversePostOrder($tree, $print)

Print tree in reverse post-order

   Parameter  Description
1  $tree      Tree
2  $print     Optional print method

Example:

  my ($c, $b, $d, $a) = fromLetters('b(c)d')->by;
  my sub test(@) {join ' ', map{join '', $_->key} @_}

  is_deeply $a->printPreOrder, <<END;
Key    Value
a
  b
    c
  d
END

  is_deeply test($a->nextPreOrderPath), 'b';
  is_deeply test($b->nextPreOrderPath), 'c';
  is_deeply test($c->nextPreOrderPath), 'b d';
  is_deeply test($d->nextPreOrderPath), '';

  is_deeply $a->printPostOrder, <<END;
Key    Value
    c
  b
  d
a
END

  is_deeply test($a->nextPostOrderPath), 'b c';
  is_deeply test($c->nextPostOrderPath), 'b';
  is_deeply test($b->nextPostOrderPath), 'd';
  is_deeply test($d->nextPostOrderPath), 'a';

  is_deeply $a->printReversePreOrder, <<END;
Key    Value
a
  d
  b
    c
END
  is_deeply test($a->prevPreOrderPath), 'd';
  is_deeply test($d->prevPreOrderPath), 'b c';
  is_deeply test($c->prevPreOrderPath), 'b';
  is_deeply test($b->prevPreOrderPath), 'a';


  is_deeply $a->printReversePostOrder, <<END;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

Key    Value
  d
    c
  b
a
END

  is_deeply test($a->prevPostOrderPath), 'd';
  is_deeply test($d->prevPostOrderPath), 'b';
  is_deeply test($b->prevPostOrderPath), 'c';
  is_deeply test($c->prevPostOrderPath), '';

print($tree, $print)

Print tree in normal pre-order.

   Parameter  Description
1  $tree      Tree
2  $print     Optional print method

Example:

  my $a = fromLetters('b(c)y(x)d(efgh(i(j)))');

  is_deeply $a->print, <<END;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

Key        Value
a
  b
    c
  y
    x
  d
    e
    f
    g
    h
      i
        j
END

  is_deeply $a->xml,
   '<a><b><c/></b><y><x/></y><d><e/><f/><g/><h><i><j/></i></h></d></a>';

  my ($c, $b, $x, $y, $e, $f, $g, $j, $i, $h, $d) = $a->by;

  is_deeply [$c, $x, $e, $f, $g, $j], [$a->leaves];
  is_deeply [$a, $b, $y, $d, $h, $i], [$a->parentsPreOrder];
  is_deeply [$b, $y, $i, $h, $d, $a], [$a->parentsPostOrder];
  is_deeply [$a->parents],            [$a->parentsPostOrder];

  is_deeply [$a, $d, $h, $i, $y, $b], [$a->parentsReversePreOrder];
  is_deeply [$i, $h, $d, $y, $b, $a], [$a->parentsReversePostOrder];

  ok !$j->parents;

  ok  $a->lastMost  == $j;
  ok !$a->prevMost;
  ok  $j->prevMost  == $g;
  ok  $i->prevMost  == $g;
  ok  $h->prevMost  == $g;
  ok  $g->prevMost  == $f;
  ok  $f->prevMost  == $e;
  ok  $e->prevMost  == $x;
  ok  $d->prevMost  == $x;
  ok  $x->prevMost  == $c;
  ok  $y->prevMost  == $c;
  ok !$c->prevMost;
  ok !$b->prevMost;
  ok !$a->prevMost;

  ok  $a->firstMost == $c;
  ok  $a->nextMost  == $c;
  ok  $b->nextMost  == $c;
  ok  $c->nextMost  == $x;
  ok  $y->nextMost  == $x;
  ok  $x->nextMost  == $e;
  ok  $d->nextMost  == $e;
  ok  $e->nextMost  == $f;
  ok  $f->nextMost  == $g;
  ok  $g->nextMost  == $j;
  ok  $h->nextMost  == $j;
  ok  $i->nextMost  == $j;
  ok !$j->nextMost;

brackets($tree, $print, $separator)

Bracketed string representation of a tree.

   Parameter   Description
1  $tree       Tree
2  $print      Optional print method
3  $separator  Optional child separator

Example:

  my $a = fromLetters('b(c)y(x)d(efgh(i(j)))');
  is_deeply $a->print, <<END;
Key        Value
a
  b
    c
  y
    x
  d
    e
    f
    g
    h
      i
        j
END

  is_deeply $a->xml,
   '<a><b><c/></b><y><x/></y><d><e/><f/><g/><h><i><j/></i></h></d></a>';

  my ($c, $b, $x, $y, $e, $f, $g, $j, $i, $h, $d) = $a->by;

  is_deeply [$c, $x, $e, $f, $g, $j], [$a->leaves];
  is_deeply [$a, $b, $y, $d, $h, $i], [$a->parentsPreOrder];
  is_deeply [$b, $y, $i, $h, $d, $a], [$a->parentsPostOrder];
  is_deeply [$a->parents],            [$a->parentsPostOrder];

  is_deeply [$a, $d, $h, $i, $y, $b], [$a->parentsReversePreOrder];
  is_deeply [$i, $h, $d, $y, $b, $a], [$a->parentsReversePostOrder];

  ok !$j->parents;

  ok  $a->lastMost  == $j;
  ok !$a->prevMost;
  ok  $j->prevMost  == $g;
  ok  $i->prevMost  == $g;
  ok  $h->prevMost  == $g;
  ok  $g->prevMost  == $f;
  ok  $f->prevMost  == $e;
  ok  $e->prevMost  == $x;
  ok  $d->prevMost  == $x;
  ok  $x->prevMost  == $c;
  ok  $y->prevMost  == $c;
  ok !$c->prevMost;
  ok !$b->prevMost;
  ok !$a->prevMost;

  ok  $a->firstMost == $c;
  ok  $a->nextMost  == $c;
  ok  $b->nextMost  == $c;
  ok  $c->nextMost  == $x;
  ok  $y->nextMost  == $x;
  ok  $x->nextMost  == $e;
  ok  $d->nextMost  == $e;
  ok  $e->nextMost  == $f;
  ok  $f->nextMost  == $g;
  ok  $g->nextMost  == $j;
  ok  $h->nextMost  == $j;
  ok  $i->nextMost  == $j;
  ok !$j->nextMost;

xml($tree, $print)

Print a tree as as xml.

   Parameter  Description
1  $tree      Tree
2  $print     Optional print method

Example:

  my $a = fromLetters('b(c)y(x)d(efgh(i(j)))');
  is_deeply $a->print, <<END;
Key        Value
a
  b
    c
  y
    x
  d
    e
    f
    g
    h
      i
        j
END


  is_deeply $a->xml,  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

   '<a><b><c/></b><y><x/></y><d><e/><f/><g/><h><i><j/></i></h></d></a>';

  my ($c, $b, $x, $y, $e, $f, $g, $j, $i, $h, $d) = $a->by;

  is_deeply [$c, $x, $e, $f, $g, $j], [$a->leaves];
  is_deeply [$a, $b, $y, $d, $h, $i], [$a->parentsPreOrder];
  is_deeply [$b, $y, $i, $h, $d, $a], [$a->parentsPostOrder];
  is_deeply [$a->parents],            [$a->parentsPostOrder];

  is_deeply [$a, $d, $h, $i, $y, $b], [$a->parentsReversePreOrder];
  is_deeply [$i, $h, $d, $y, $b, $a], [$a->parentsReversePostOrder];

  ok !$j->parents;

  ok  $a->lastMost  == $j;
  ok !$a->prevMost;
  ok  $j->prevMost  == $g;
  ok  $i->prevMost  == $g;
  ok  $h->prevMost  == $g;
  ok  $g->prevMost  == $f;
  ok  $f->prevMost  == $e;
  ok  $e->prevMost  == $x;
  ok  $d->prevMost  == $x;
  ok  $x->prevMost  == $c;
  ok  $y->prevMost  == $c;
  ok !$c->prevMost;
  ok !$b->prevMost;
  ok !$a->prevMost;

  ok  $a->firstMost == $c;
  ok  $a->nextMost  == $c;
  ok  $b->nextMost  == $c;
  ok  $c->nextMost  == $x;
  ok  $y->nextMost  == $x;
  ok  $x->nextMost  == $e;
  ok  $d->nextMost  == $e;
  ok  $e->nextMost  == $f;
  ok  $f->nextMost  == $g;
  ok  $g->nextMost  == $j;
  ok  $h->nextMost  == $j;
  ok  $i->nextMost  == $j;
  ok !$j->nextMost;

Data Structures

Data structures use by this package.

Tree::Ops Definition

Child in the tree.

Output fields

children - Children of this child.

key - Key for this child - any thing that can be compared with the smartmatch operator.

lastChild - Last active child chain - enables us to find the currently open scope from the start if the tree.

parent - Parent for this child.

value - Value for this child.

Private Methods

setParentOfChild($child, $parent)

Set the parent of a child and return the child.

   Parameter  Description
1  $child     Child
2  $parent    Parent

indexOfChildInParent($child)

Get the index of a child within the specified parent.

   Parameter  Description
1  $child     Child

parentsOrdered($tree, $preorder, $reverse)

The set of all parents in the tree, i.e. each non leaf of the tree, i.e the interior of the tree in the specified order.

   Parameter  Description
1  $tree      Tree
2  $preorder  Pre-order if true else post-order
3  $reverse   Reversed if true

printTree($tree, $print, $preorder, $reverse)

String representation as a horizontal tree.

   Parameter  Description
1  $tree      Tree
2  $print     Optional print method
3  $preorder  Pre-order
4  $reverse   Reverse

Index

1 above - Return the first child if it is above the second child else return undef.

2 activeScope - Locate the active scope in a tree.

3 after - Return the first child if it occurs strictly after the second child in the tree or else undef if the first child is above, below or before the second child.

4 before - Return the first child if it occurs strictly before the second child in the tree or else undef if the first child is above, below or after the second child.

5 below - Return the first child if it is below the second child else return undef.

6 brackets - Bracketed string representation of a tree.

7 by - Traverse a tree in post-order to process each child with the specified sub and return an array of the results of processing each child.

8 close - Close the current scope returning to the previous scope.

9 context - Get the context of the current child.

10 cut - Cut out a child and all its content and children, return it ready for reinsertion else where.

11 dup - Duplicate a parent and all its descendants.

12 empty - Return the specified parent if it has no children else undef

13 first - Get the first child under the specified parent.

14 firstMost - Return the first most descendant child in the tree starting at this parent or else return undef if this parent has no children.

15 fromLetters - Create a tree from a string of letters - useful for testing.

16 include - Include the specified tree in the currently open scope.

17 indexOfChildInParent - Get the index of a child within the specified parent.

18 isFirst - Return the specified child if that child is first under its parent, else return undef.

19 isLast - Return the specified child if that child is last under its parent, else return undef.

20 last - Get the last child under the specified parent.

21 lastMost - Return the last most descendant child in the tree starting at this parent or else return undef if this parent has no children.

22 leaves - The set of all children without further children, i.

23 lineage - Return the path from the specified child to the specified ancestor else return undef if the child is not a descendant of the ancestor.

24 merge - Merge the children of the specified parent with those of the surrounding parents if the L[key] data of those parents smartmatch that of the specified parent.

25 mostRecentCommonAncestor - Find the most recent common ancestor of the specified children.

26 new - Create a new child optionally recording the specified key or value.

27 next - Get the next sibling following the specified child.

28 nextMost - Return the next child with no children, i.

29 nextPostOrderPath - Return a list of children visited between the specified child and the next child in post-order.

30 nextPreOrderPath - Return a list of children visited between the specified child and the next child in pre-order.

31 open - Add a child and make it the currently active scope into which new children will be added.

32 parents - The set of all parents in the tree, i.

33 parentsOrdered - The set of all parents in the tree, i.

34 parentsPostOrder - The set of all parents in the tree, i.

35 parentsPreOrder - The set of all parents in the tree, i.

36 parentsReversePostOrder - The set of all parents in the tree, i.

37 parentsReversePreOrder - The set of all parents in the tree, i.

38 prev - Get the previous sibling of the specified child.

39 prevMost - Return the previous child with no children, i.

40 prevPostOrderPath - Return a list of children visited between the specified child and the previous child in post-order.

41 prevPreOrderPath - Return a list of children visited between the specified child and the previous child in pre-order.

42 print - Print tree in normal pre-order.

43 printPostOrder - Print tree in normal post-order.

44 printPreOrder - Print tree in normal pre-order.

45 printReversePostOrder - Print tree in reverse post-order

46 printReversePreOrder - Print tree in reverse pre-order

47 printTree - String representation as a horizontal tree.

48 putFirst - Place a new child first under the specified parent and return the child.

49 putLast - Place a new child last under the specified parent and return the child.

50 putNext - Place a new child after the specified child.

51 putPrev - Place a new child before the specified child.

52 select - Select matching children in a tree in post-order.

53 setParentOfChild - Set the parent of a child and return the child.

54 siblingsAfter - Return a list of siblings after the specified child.

55 siblingsBefore - Return a list of siblings before the specified child.

56 siblingsStrictlyBetween - Return a list of the siblings strictly between two children of the same parent else return undef.

57 single - Add one child in the current scope.

58 singleChildOfParent - Return the only child of this parent if the parent has an only child, else undef

59 split - Make the specified parent a grandparent of each of its children by interposing a copy of the specified parent between the specified parent and each of its children.

60 step - Make the first child of the specified parent the parents previous sibling and return the parent.

61 stepBack - Make the previous sibling of the specified parent the parents first child and return the parent.

62 stepEnd - Make the next sibling of the specified parent the parents last child and return the parent.

63 stepEndBack - Make the last child of the specified parent the parents next sibling and return the parent.

64 unwrap - Unwrap the specified child and return that child.

65 wrap - Wrap the specified child with a new parent and return the new parent.

66 xml - Print a tree as as xml.

Installation

This module is written in 100% Pure Perl and, thus, it is easy to read, comprehend, use, modify and install via cpan:

sudo cpan install Tree::Ops

Author

philiprbrenan@gmail.com

http://www.appaapps.com

Copyright

This module is free software. It may be used, redistributed and/or modified under the same terms as Perl itself.

To install Tree::Ops, copy and paste the appropriate command in to your terminal.

cpanm

cpanm Tree::Ops

CPAN shell

perl -MCPAN -e shell
install Tree::Ops

For more information on module installation, please visit the detailed CPAN module installation guide.

	Global
`s`	Focus search bar
`?`	Bring up this help dialog

	GitHub
`g` `p`	Go to pull requests
`g` `i`	go to github issues (only if github is preferred repository)

	POD
`g` `a`	Go to author
`g` `c`	Go to changes
`g` `i`	Go to issues
`g` `d`	Go to dist
`g` `r`	Go to repository/SCM
`g` `s`	Go to source
`g` `b`	Go to file browse

	Search terms
module: (e.g. module:Plugin)
distribution: (e.g. distribution:Dancer auth)
author: (e.g. author:SONGMU Redis)
version: (e.g. version:1.00)

Name

Synopsis

Description

Build

new($key, $value)

activeScope($tree)

open($tree, $key, $value)

close($tree)

single($tree, $key, $value)

include($tree, $include)

fromLetters($letters)

Navigation

first($parent)

last($parent)

next($child)

prev($child)

firstMost($parent)

nextMost($child)

prevMost($child)

lastMost($parent)

mostRecentCommonAncestor($first, $second)

Location

context($child)

isFirst($child)

isLast($child)

singleChildOfParent($parent)

empty($parent)

Put

putFirst($parent, $child)

putLast($parent, $child)

putNext($child, $new)

putPrev($child, $new)

Steps

step($parent)

stepEnd($parent)

stepBack()

stepEndBack()

Edit

cut($child)

dup($parent)

unwrap($child)

wrap($child, $key)

merge($parent)

split($parent)

Traverse

by($tree, $sub)

select($tree, $select)

Partitions

leaves($tree)

parentsPreOrder($tree)

parentsPostOrder($tree)

parentsReversePreOrder($tree)

parentsReversePostOrder($tree)

parents($tree)

Order

above($first, $second)

below($first, $second)

after($first, $second)

before($first, $second)

Paths

siblingsBefore($child)

siblingsAfter($child)

siblingsStrictlyBetween($start, $finish)

lineage($child, $ancestor)

nextPreOrderPath($start)

nextPostOrderPath($start)

prevPostOrderPath($start)

prevPreOrderPath($start)

Print

printPreOrder($tree, $print)

printPostOrder($tree, $print)

printReversePreOrder($tree, $print)

printReversePostOrder($tree, $print)

print($tree, $print)

brackets($tree, $print, $separator)

xml($tree, $print)

Data Structures

Tree::Ops Definition

Output fields

Private Methods