Name

Tree::Bulk - Bulk Tree operations

Synopsis

Bulk trees store several (key,data) pairs in each node of a balanced tree to reduce the number of tree pointers: up, left, right, etc. used to maintain the tree. This has no useful effect in Perl code, but in C code, especially C code that uses SIMD instructions, the savings in space can be considerable which allows the processor caches to be used more effectively. This module demonstrates insert, find, delete operations on bulk trees as a basis for coding these algorithms more efficiently in assembler code.

is_deeply $t->printKeys, <<END;
SA0 4 1 2 3 4
Lz2 1     5 6 7 8->9 10 11 12
Rd1 3   9 10 11 12->1 2 3 4
Lz3 1       13 14 15 16->17 18 19 20
Rd2 2     17 18 19 20->9 10 11 12
Rz3 1       21 22->17 18 19 20
END

for my $n($t->inorder)
 {$n->setKeysPerNode(2);
 }

is_deeply $t->printKeys, <<END;
SA0 5 1 2
Lz3 1       3 4->5 6
Ld2 2     5 6->9 10
Rz3 1       7 8->5 6
Rd1 4   9 10->1 2
Lz4 1         11 12->13 14
Ld3 2       13 14->17 18
Rz4 1         15 16->13 14
Rd2 3     17 18->9 10
Rr3 2       19 20->17 18
Rz4 1         21 22->19 20
END

Description

Bulk Tree operations

Version "20210226".

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

Bulk Tree

isRoot($tree)

Return the tree if it is the root

   Parameter  Description
1  $tree      Tree

Example:

if (1)
 {lll "Attributes";
  my  $t = Tree::Bulk::new->setKeysPerNode(1);
  my  $b = $t->insert(2,4);
  my  $a = $t->insert(1,2);
  my  $c = $t->insert(3,6);
  ok  $a->isLeftChild;
  ok  $c->isRightChild;
  ok !$a->isRightChild;
  ok !$c->isLeftChild;

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


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


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

  ok  $a->leaf;
  ok  $c->leaf;
  ok  $b->duplex;
  ok  $c->root == $b;
  ok  $c->root != $a;
 }

root($tree)

Return the root node of a tree

   Parameter  Description
1  $tree      Tree

Example:

if (1)
 {lll "Attributes";
  my  $t = Tree::Bulk::new->setKeysPerNode(1);
  my  $b = $t->insert(2,4);
  my  $a = $t->insert(1,2);
  my  $c = $t->insert(3,6);
  ok  $a->isLeftChild;
  ok  $c->isRightChild;
  ok !$a->isRightChild;
  ok !$c->isLeftChild;
  ok  $b->isRoot;
  ok !$a->isRoot;
  ok !$c->isRoot;
  ok  $a->leaf;
  ok  $c->leaf;
  ok  $b->duplex;

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


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

 }

leaf($tree)

Return the tree if it is a leaf

   Parameter  Description
1  $tree      Tree

Example:

if (1)
 {lll "Attributes";
  my  $t = Tree::Bulk::new->setKeysPerNode(1);
  my  $b = $t->insert(2,4);
  my  $a = $t->insert(1,2);
  my  $c = $t->insert(3,6);
  ok  $a->isLeftChild;
  ok  $c->isRightChild;
  ok !$a->isRightChild;
  ok !$c->isLeftChild;
  ok  $b->isRoot;
  ok !$a->isRoot;
  ok !$c->isRoot;

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


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

  ok  $b->duplex;
  ok  $c->root == $b;
  ok  $c->root != $a;
 }

duplex($tree)

Return the tree if it has left and right children

   Parameter  Description
1  $tree      Tree

Example:

if (1)
 {lll "Attributes";
  my  $t = Tree::Bulk::new->setKeysPerNode(1);
  my  $b = $t->insert(2,4);
  my  $a = $t->insert(1,2);
  my  $c = $t->insert(3,6);
  ok  $a->isLeftChild;
  ok  $c->isRightChild;
  ok !$a->isRightChild;
  ok !$c->isLeftChild;
  ok  $b->isRoot;
  ok !$a->isRoot;
  ok !$c->isRoot;
  ok  $a->leaf;
  ok  $c->leaf;

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

  ok  $c->root == $b;
  ok  $c->root != $a;
 }

simplex($tree)

Return the tree if it has either a left child or a right child but not both.

   Parameter  Description
1  $tree      Tree

Example:

if (1)
 {lll "Rotate";
  my  $t = Tree::Bulk::new->setKeysPerNode(1);
  my  $a = node(1,2);
  my  $b = node(2,4);
  my  $c = node(3,6);
  my  $d = node(4,8);
  $a->right = $b; $b->up = $a;
  $b->right = $c; $c->up = $b;
  $c->right = $d; $d->up = $c;
  $d->setHeights(1);


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


  is_deeply $a->printKeys, <<END;
SA0 4 1
Rr1 3   2->1
Rr2 2     3->2
Rz3 1       4->3
END
#save $a;
  $b->rotateLeft;
  is_deeply $a->printKeys, <<END;
SA0 3 1
Lz2 1     2->3
Rd1 2   3->1
Rz2 1     4->3
END
#save $a;

  $c->rotateLeft; $c->setHeights(2);
  is_deeply $a->printKeys, <<END;
SA0 4 1
Lz3 1       2->3
Ll2 2     3->4
Rl1 3   4->1
END
#save $a;

  $d->rotateRight; $d->setHeights(1);
  is_deeply $a->printKeys, <<END;
SA0 3 1
Lz2 1     2->3
Rd1 2   3->1
Rz2 1     4->3
END
#save $a;

  $c->rotateRight; $c->setHeights(2);
  is_deeply $a->printKeys, <<END;
SA0 4 1
Rr1 3   2->1
Rr2 2     3->2
Rz3 1       4->3
END
#save $a;
 }

empty($tree)

Return the tree if it is empty

   Parameter  Description
1  $tree      Tree

Example:

if (1)
 {lll "Balance";
  my  $t = Tree::Bulk::new->setKeysPerNode(1);


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

  ok $t->singleton;

  my  $a = node(1,2);
  my  $b = node(2,4);
  my  $c = node(6,12);
  my  $d = node(5,10);
  my  $e = node(4,8);
  my  $f = node(3,6);
  $a->right = $b; $b->up = $a;
  $b->right = $c; $c->up = $b;
  $c->left  = $d; $d->up = $c;
  $d->left  = $e; $e->up = $d;
  $e->left  = $f; $f->up = $e;
  $f->setHeights(1);
  is_deeply $a->printKeys, <<END;
SA0 6 1
Rr1 5   2->1
Lz5 1           3->4
Ll4 2         4->5
Ll3 3       5->6
Rl2 4     6->2
END
#save $a;

  $b->balance;
  is_deeply $a->printKeys, <<END;
SA0 5 1
Lr2 3     2->5
Lz4 1         3->4
Rl3 2       4->2
Rd1 4   5->1
Rz2 1     6->5
END
#save $a;
 }

singleton($tree)

Return the tree if it contains only the root node and nothing else

   Parameter  Description
1  $tree      Tree

Example:

if (1)
 {lll "Balance";
  my  $t = Tree::Bulk::new->setKeysPerNode(1);

  ok $t->empty;

  ok $t->singleton;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  my  $a = node(1,2);
  my  $b = node(2,4);
  my  $c = node(6,12);
  my  $d = node(5,10);
  my  $e = node(4,8);
  my  $f = node(3,6);
  $a->right = $b; $b->up = $a;
  $b->right = $c; $c->up = $b;
  $c->left  = $d; $d->up = $c;
  $d->left  = $e; $e->up = $d;
  $e->left  = $f; $f->up = $e;
  $f->setHeights(1);
  is_deeply $a->printKeys, <<END;
SA0 6 1
Rr1 5   2->1
Lz5 1           3->4
Ll4 2         4->5
Ll3 3       5->6
Rl2 4     6->2
END
#save $a;

  $b->balance;
  is_deeply $a->printKeys, <<END;
SA0 5 1
Lr2 3     2->5
Lz4 1         3->4
Rl3 2       4->2
Rd1 4   5->1
Rz2 1     6->5
END
#save $a;
 }

isLeftChild($tree)

Return the tree if it is the left child

   Parameter  Description
1  $tree      Tree

Example:

if (1)
 {lll "Attributes";
  my  $t = Tree::Bulk::new->setKeysPerNode(1);
  my  $b = $t->insert(2,4);
  my  $a = $t->insert(1,2);
  my  $c = $t->insert(3,6);

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

  ok  $c->isRightChild;
  ok !$a->isRightChild;

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

  ok  $b->isRoot;
  ok !$a->isRoot;
  ok !$c->isRoot;
  ok  $a->leaf;
  ok  $c->leaf;
  ok  $b->duplex;
  ok  $c->root == $b;
  ok  $c->root != $a;
 }

isRightChild($tree)

Return the tree if it is the right child

   Parameter  Description
1  $tree      Tree

Example:

if (1)
 {lll "Attributes";
  my  $t = Tree::Bulk::new->setKeysPerNode(1);
  my  $b = $t->insert(2,4);
  my  $a = $t->insert(1,2);
  my  $c = $t->insert(3,6);
  ok  $a->isLeftChild;

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


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

  ok !$c->isLeftChild;
  ok  $b->isRoot;
  ok !$a->isRoot;
  ok !$c->isRoot;
  ok  $a->leaf;
  ok  $c->leaf;
  ok  $b->duplex;
  ok  $c->root == $b;
  ok  $c->root != $a;
 }

name($tree)

Name of a tree

   Parameter  Description
1  $tree      Tree

Example:

if (1)
 {lll "Split and Refill";
  my $N = 22;
  my $t = Tree::Bulk::new;
  for my $k(1..$N)
   {$t->insert($k, 2 * $k);
   }


  is_deeply $t->name, "1 2 3 4";  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  is_deeply $t->printKeys, <<END;
SA0 4 1 2 3 4
Lz2 1     5 6 7 8->9 10 11 12
Rd1 3   9 10 11 12->1 2 3 4
Lz3 1       13 14 15 16->17 18 19 20
Rd2 2     17 18 19 20->9 10 11 12
Rz3 1       21 22->17 18 19 20
END
#save $t;

  for my $n($t->inorder)
   {$n->setKeysPerNode(2);
   }
  is_deeply $t->printKeys, <<END;
SA0 5 1 2
Lz3 1       3 4->5 6
Ld2 2     5 6->9 10
Rz3 1       7 8->5 6
Rd1 4   9 10->1 2
Lz4 1         11 12->13 14
Ld3 2       13 14->17 18
Rz4 1         15 16->13 14
Rd2 3     17 18->9 10
Rr3 2       19 20->17 18
Rz4 1         21 22->19 20
END
#save $t;

  for my $n($t->inorder)
   {$n->setKeysPerNode(1);
   }
  is_deeply $t->printKeys, <<END;
SA0 6 1
Lz4 1         2->3
Ld3 2       3->5
Rz4 1         4->3
Ld2 3     5->9
Lz4 1         6->7
Rd3 2       7->5
Rz4 1         8->7
Rd1 5   9->1
Lz5 1           10->11
Ld4 2         11->13
Rz5 1           12->11
Ld3 3       13->17
Lz5 1           14->15
Rd4 2         15->13
Rz5 1           16->15
Rd2 4     17->9
Lz4 1         18->19
Rd3 3       19->17
Lz5 1           20->21
Rd4 2         21->19
Rz5 1           22->21
END
#save $t;

  $_->setKeysPerNode(2) for $t->inorder;
  is_deeply $t->printKeys, <<END;
SA0 5 1 2
Lz3 1       3 4->5 6
Ld2 2     5 6->9 10
Rz3 1       7 8->5 6
Rd1 4   9 10->1 2
Lz4 1         11 12->13 14
Ld3 2       13 14->17 18
Rz4 1         15 16->13 14
Rd2 3     17 18->9 10
Lz4 1         19 20->21 22
Rl3 2       21 22->17 18
END
#save $t;

  $_->setKeysPerNode(4) for $t->inorder;
  is_deeply $t->printKeys, <<END;
SA0 4 1 2 3 4
Lz2 1     5 6 7 8->9 10 11 12
Rd1 3   9 10 11 12->1 2 3 4
Lz3 1       13 14 15 16->17 18 19 20
Rd2 2     17 18 19 20->9 10 11 12
Rz3 1       21 22->17 18 19 20
END
#save $t;
 }

setHeights($tree, $from)

Set heights along path to root

   Parameter  Description
1  $tree      Tree
2  $from      Height for this node

Example:

if (1)
 {lll "Balance";
  my  $t = Tree::Bulk::new->setKeysPerNode(1);

  ok $t->empty;
  ok $t->singleton;

  my  $a = node(1,2);
  my  $b = node(2,4);
  my  $c = node(6,12);
  my  $d = node(5,10);
  my  $e = node(4,8);
  my  $f = node(3,6);
  $a->right = $b; $b->up = $a;
  $b->right = $c; $c->up = $b;
  $c->left  = $d; $d->up = $c;
  $d->left  = $e; $e->up = $d;
  $e->left  = $f; $f->up = $e;

  $f->setHeights(1);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply $a->printKeys, <<END;
SA0 6 1
Rr1 5   2->1
Lz5 1           3->4
Ll4 2         4->5
Ll3 3       5->6
Rl2 4     6->2
END
#save $a;

  $b->balance;
  is_deeply $a->printKeys, <<END;
SA0 5 1
Lr2 3     2->5
Lz4 1         3->4
Rl3 2       4->2
Rd1 4   5->1
Rz2 1     6->5
END
#save $a;
 }

actualHeight($tree)

Get the height of a node

   Parameter  Description
1  $tree      Tree

Example:

if (1)
 {my $N = 22;
  my $t = Tree::Bulk::new;
  ok $t->empty;
  ok $t->leaf;

  for(1..$N)
   {$t->insert($_, 2 * $_);
   }

  ok $t->right->duplex;

  is_deeply actualHeight($t), 4;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  is_deeply $t->printKeys, <<END;
SA0 4 1 2 3 4
Lz2 1     5 6 7 8->9 10 11 12
Rd1 3   9 10 11 12->1 2 3 4
Lz3 1       13 14 15 16->17 18 19 20
Rd2 2     17 18 19 20->9 10 11 12
Rz3 1       21 22->17 18 19 20
END
#save $t;

  is_deeply $t->printKeysAndData, <<END;
 1   2
 2   4
 3   6
 4   8
 5  10
 6  12
 7  14
 8  16
 9  18
10  20
11  22
12  24
13  26
14  28
15  30
16  32
17  34
18  36
19  38
20  40
21  42
22  44
END

  my %t = map {$_=>2*$_} 1..$N;

  for(map {2 * $_} 1..$N/2)
   {$t->delete($_);
    delete $t{$_};
    checkAgainstHash $t, %t;
   }

  is_deeply $t->printKeys, <<END;
SA0 3 1 3 5 7
Lz2 1     9 11 13->15 17 19 21
Rl1 2   15 17 19 21->1 3 5 7
END
#save($t);

  is_deeply $t->printKeysAndData, <<END;
 1   2
 3   6
 5  10
 7  14
 9  18
11  22
13  26
15  30
17  34
19  38
21  42
END

  for(map {2 * $_-1} 1..$N/2)
   {$t->delete($_);
    delete $t{$_};
    checkAgainstHash $t, %t;
   }

  is_deeply $t->printKeys, <<END;
Sz0 1
END
#save($t);
 }

maximum($a, $b)

Maximum of two numbers

   Parameter  Description
1  $a         First
2  $b         Second

Example:

if (1)

 {is_deeply maximum(1,2), 2;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  is_deeply maximum(2,1), 2;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

 }

balance($tree)

Balance a node

   Parameter  Description
1  $tree      Tree

Example:

if (1)
 {lll "Balance";
  my  $t = Tree::Bulk::new->setKeysPerNode(1);

  ok $t->empty;
  ok $t->singleton;

  my  $a = node(1,2);
  my  $b = node(2,4);
  my  $c = node(6,12);
  my  $d = node(5,10);
  my  $e = node(4,8);
  my  $f = node(3,6);
  $a->right = $b; $b->up = $a;
  $b->right = $c; $c->up = $b;
  $c->left  = $d; $d->up = $c;
  $d->left  = $e; $e->up = $d;
  $e->left  = $f; $f->up = $e;
  $f->setHeights(1);
  is_deeply $a->printKeys, <<END;
SA0 6 1
Rr1 5   2->1
Lz5 1           3->4
Ll4 2         4->5
Ll3 3       5->6
Rl2 4     6->2
END
#save $a;


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

  is_deeply $a->printKeys, <<END;
SA0 5 1
Lr2 3     2->5
Lz4 1         3->4
Rl3 2       4->2
Rd1 4   5->1
Rz2 1     6->5
END
#save $a;
 }

insert($tree, $key, $data)

Insert a key and some data into a tree

   Parameter  Description
1  $tree      Tree
2  $key       Key
3  $data      Data

Example:

if (1)
 {lll "Insert";
  my $N = 23;
  my $t = Tree::Bulk::new->setKeysPerNode(1);
  for(1..$N)

   {$t->insert($_, 2 * $_);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

   }

  is_deeply $t->printKeys, <<END;
SA0 8 1
Lz4 1         2->3
Ld3 2       3->5
Rz4 1         4->3
Ld2 3     5->9
Lz4 1         6->7
Rd3 2       7->5
Rz4 1         8->7
Rd1 7   9->1
Lz4 1         10->11
Ld3 2       11->13
Rz4 1         12->11
Rd2 6     13->9
Lz5 1           14->15
Ld4 2         15->17
Rz5 1           16->15
Rd3 5       17->13
Lz5 1           18->19
Rd4 4         19->17
Lz6 1             20->21
Rd5 3           21->19
Rr6 2             22->21
Rz7 1               23->22
END
#save $t;
  ok $t->height == 8;
 }

find($tree, $key)

Find a key in a tree and returns its data

   Parameter  Description
1  $tree      Tree
2  $key       Key

Example:

if (1)
 {my $t = Tree::Bulk::new;
     $t->insert($_, $_*$_)    for  1..20;

  ok !find($t,  0);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok !find($t, 21);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


  ok  find($t, $_) == $_ * $_ for qw(1 5 10 11 15 20);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

 }

first($n)

First node in a tree

   Parameter  Description
1  $n         Tree

Example:

if (1)
 {my $N = 220;
  my $t = Tree::Bulk::new;

  for(reverse 1..$N)
   {$t->insert($_, 2*$_);
   }

  is_deeply $t->actualHeight, 7;

  if (1)
   {my @n;

    for (my $n = $t->first; $n; $n = $n->next)  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

     {push @n, $n->keys->@*
     }
    is_deeply \@n, [1..$N];
   }

  if (1)
   {my @p;
    for my $p(reverse $t->inorder)
     {push @p, reverse $p->keys->@*;
     }
    is_deeply \@p, [reverse 1..$N];
   }

  my @p;
  for(my $p = $t->last; $p; $p = $p->prev)
   {push @p, reverse $p->keys->@*
   }
  is_deeply \@p, [reverse 1..$N];

  my %t = map {$_=>2*$_} 1..$N;
  for   my $i(0..3)
   {for my $j(map {4 * $_-$i} 1..$N/4)
     {$t->delete   ($j);
          delete $t{$j};
      checkAgainstHash $t, %t;
     }
   }

  ok $t->empty;
  is_deeply $t->actualHeight, 1;
 }

last($n)

Last node in a tree

   Parameter  Description
1  $n         Tree

Example:

if (1)
 {my $N = 220;
  my $t = Tree::Bulk::new;

  for(reverse 1..$N)
   {$t->insert($_, 2*$_);
   }

  is_deeply $t->actualHeight, 7;

  if (1)
   {my @n;
    for (my $n = $t->first; $n; $n = $n->next)
     {push @n, $n->keys->@*
     }
    is_deeply \@n, [1..$N];
   }

  if (1)
   {my @p;
    for my $p(reverse $t->inorder)
     {push @p, reverse $p->keys->@*;
     }
    is_deeply \@p, [reverse 1..$N];
   }

  my @p;

  for(my $p = $t->last; $p; $p = $p->prev)  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

   {push @p, reverse $p->keys->@*
   }
  is_deeply \@p, [reverse 1..$N];

  my %t = map {$_=>2*$_} 1..$N;
  for   my $i(0..3)
   {for my $j(map {4 * $_-$i} 1..$N/4)
     {$t->delete   ($j);
          delete $t{$j};
      checkAgainstHash $t, %t;
     }
   }

  ok $t->empty;
  is_deeply $t->actualHeight, 1;
 }

next($tree)

Next node in order

   Parameter  Description
1  $tree      Tree

Example:

if (1)
 {my $N = 220;
  my $t = Tree::Bulk::new;

  for(reverse 1..$N)
   {$t->insert($_, 2*$_);
   }

  is_deeply $t->actualHeight, 7;

  if (1)
   {my @n;

    for (my $n = $t->first; $n; $n = $n->next)  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

     {push @n, $n->keys->@*
     }
    is_deeply \@n, [1..$N];
   }

  if (1)
   {my @p;
    for my $p(reverse $t->inorder)
     {push @p, reverse $p->keys->@*;
     }
    is_deeply \@p, [reverse 1..$N];
   }

  my @p;
  for(my $p = $t->last; $p; $p = $p->prev)
   {push @p, reverse $p->keys->@*
   }
  is_deeply \@p, [reverse 1..$N];

  my %t = map {$_=>2*$_} 1..$N;
  for   my $i(0..3)
   {for my $j(map {4 * $_-$i} 1..$N/4)
     {$t->delete   ($j);
          delete $t{$j};
      checkAgainstHash $t, %t;
     }
   }

  ok $t->empty;
  is_deeply $t->actualHeight, 1;
 }

prev($tree)

Previous node in order

   Parameter  Description
1  $tree      Tree

Example:

if (1)
 {my $N = 220;
  my $t = Tree::Bulk::new;

  for(reverse 1..$N)
   {$t->insert($_, 2*$_);
   }

  is_deeply $t->actualHeight, 7;

  if (1)
   {my @n;
    for (my $n = $t->first; $n; $n = $n->next)
     {push @n, $n->keys->@*
     }
    is_deeply \@n, [1..$N];
   }

  if (1)
   {my @p;
    for my $p(reverse $t->inorder)
     {push @p, reverse $p->keys->@*;
     }
    is_deeply \@p, [reverse 1..$N];
   }

  my @p;

  for(my $p = $t->last; $p; $p = $p->prev)  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

   {push @p, reverse $p->keys->@*
   }
  is_deeply \@p, [reverse 1..$N];

  my %t = map {$_=>2*$_} 1..$N;
  for   my $i(0..3)
   {for my $j(map {4 * $_-$i} 1..$N/4)
     {$t->delete   ($j);
          delete $t{$j};
      checkAgainstHash $t, %t;
     }
   }

  ok $t->empty;
  is_deeply $t->actualHeight, 1;
 }

inorder($tree)

Return a list of all the nodes in a tree in order

   Parameter  Description
1  $tree      Tree

Example:

if (1)
 {my $N = 220;
  my $t = Tree::Bulk::new;

  for(reverse 1..$N)
   {$t->insert($_, 2*$_);
   }

  is_deeply $t->actualHeight, 7;

  if (1)
   {my @n;
    for (my $n = $t->first; $n; $n = $n->next)
     {push @n, $n->keys->@*
     }
    is_deeply \@n, [1..$N];
   }

  if (1)
   {my @p;

    for my $p(reverse $t->inorder)  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

     {push @p, reverse $p->keys->@*;
     }
    is_deeply \@p, [reverse 1..$N];
   }

  my @p;
  for(my $p = $t->last; $p; $p = $p->prev)
   {push @p, reverse $p->keys->@*
   }
  is_deeply \@p, [reverse 1..$N];

  my %t = map {$_=>2*$_} 1..$N;
  for   my $i(0..3)
   {for my $j(map {4 * $_-$i} 1..$N/4)
     {$t->delete   ($j);
          delete $t{$j};
      checkAgainstHash $t, %t;
     }
   }

  ok $t->empty;
  is_deeply $t->actualHeight, 1;
 }

delete($tree, $key)

Delete a key in a tree

   Parameter  Description
1  $tree      Tree
2  $key       Key

Example:

if (1)
 {lll "Delete";
  my $N = 28;
  my $t = Tree::Bulk::new->setKeysPerNode(1);
  for(1..$N)
   {$t->insert($_, 2 * $_);
   }

  is_deeply $t->printKeys, <<END;
SA0 8 1
Lz4 1         2->3
Ld3 2       3->5
Rz4 1         4->3
Ld2 3     5->9
Lz4 1         6->7
Rd3 2       7->5
Rz4 1         8->7
Rd1 7   9->1
Lz5 1           10->11
Ld4 2         11->13
Rz5 1           12->11
Ld3 3       13->17
Lz5 1           14->15
Rd4 2         15->13
Rz5 1           16->15
Rd2 6     17->9
Lz5 1           18->19
Ld4 2         19->21
Rz5 1           20->19
Rd3 5       21->17
Lz5 1           22->23
Rd4 4         23->21
Lz6 1             24->25
Rd5 3           25->23
Lz7 1               26->27
Rd6 2             27->25
Rz7 1               28->27
END
#save $t;

  for my $k(reverse 1..$N)

   {$t->delete($k);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

    is_deeply $t->printKeys, <<END if $k == 17;
SA0 5 1
Lz4 1         2->3
Ld3 2       3->5
Rz4 1         4->3
Ld2 3     5->9
Lz4 1         6->7
Rd3 2       7->5
Rz4 1         8->7
Rd1 4   9->1
Lz4 1         10->11
Ld3 2       11->13
Rz4 1         12->11
Rd2 3     13->9
Lz4 1         14->15
Rd3 2       15->13
Rz4 1         16->15
END
#save $t if $k == 17;

    is_deeply $t->printKeys, <<END if $k == 9;
SA0 4 1
Lz3 1       2->3
Ld2 2     3->5
Rz3 1       4->3
Rd1 3   5->1
Lz3 1       6->7
Rd2 2     7->5
Rz3 1       8->7
END
#save $t if $k == 9;

    is_deeply $t->printKeys, <<END if $k == 6;
SA0 4 1
Lz2 1     2->3
Rd1 3   3->1
Lz3 1       4->5
Rl2 2     5->3
END
#save $t if $k == 6;

    is_deeply $t->printKeys, <<END if $k == 4;
SA0 3 1
Lz2 1     2->3
Rl1 2   3->1
END
#save $t if $k == 4;

    is_deeply $t->printKeys, <<END if $k == 3;
SA0 2 1
Rz1 1   2->1
END
#save $t if $k == 3;

    is_deeply $t->printKeys, <<END if $k == 1;
Sz0 1
END
#save $t if $k == 1;
   }
 }

printKeys($t)

Print the keys in a tree

   Parameter  Description
1  $t         Tree

Example:

if (1)
 {lll "Insert";
  my $N = 23;
  my $t = Tree::Bulk::new->setKeysPerNode(1);
  for(1..$N)
   {$t->insert($_, 2 * $_);
   }


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

SA0 8 1
Lz4 1         2->3
Ld3 2       3->5
Rz4 1         4->3
Ld2 3     5->9
Lz4 1         6->7
Rd3 2       7->5
Rz4 1         8->7
Rd1 7   9->1
Lz4 1         10->11
Ld3 2       11->13
Rz4 1         12->11
Rd2 6     13->9
Lz5 1           14->15
Ld4 2         15->17
Rz5 1           16->15
Rd3 5       17->13
Lz5 1           18->19
Rd4 4         19->17
Lz6 1             20->21
Rd5 3           21->19
Rr6 2             22->21
Rz7 1               23->22
END
#save $t;
  ok $t->height == 8;
 }

setKeysPerNode($tree, $N)

Set the number of keys for the current node

   Parameter  Description
1  $tree      Tree
2  $N         Keys per node to be set

Example:

if (1)
 {lll "Split and Refill";
  my $N = 22;
  my $t = Tree::Bulk::new;
  for my $k(1..$N)
   {$t->insert($k, 2 * $k);
   }

  is_deeply $t->name, "1 2 3 4";

  is_deeply $t->printKeys, <<END;
SA0 4 1 2 3 4
Lz2 1     5 6 7 8->9 10 11 12
Rd1 3   9 10 11 12->1 2 3 4
Lz3 1       13 14 15 16->17 18 19 20
Rd2 2     17 18 19 20->9 10 11 12
Rz3 1       21 22->17 18 19 20
END
#save $t;

  for my $n($t->inorder)

   {$n->setKeysPerNode(2);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

   }
  is_deeply $t->printKeys, <<END;
SA0 5 1 2
Lz3 1       3 4->5 6
Ld2 2     5 6->9 10
Rz3 1       7 8->5 6
Rd1 4   9 10->1 2
Lz4 1         11 12->13 14
Ld3 2       13 14->17 18
Rz4 1         15 16->13 14
Rd2 3     17 18->9 10
Rr3 2       19 20->17 18
Rz4 1         21 22->19 20
END
#save $t;

  for my $n($t->inorder)

   {$n->setKeysPerNode(1);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

   }
  is_deeply $t->printKeys, <<END;
SA0 6 1
Lz4 1         2->3
Ld3 2       3->5
Rz4 1         4->3
Ld2 3     5->9
Lz4 1         6->7
Rd3 2       7->5
Rz4 1         8->7
Rd1 5   9->1
Lz5 1           10->11
Ld4 2         11->13
Rz5 1           12->11
Ld3 3       13->17
Lz5 1           14->15
Rd4 2         15->13
Rz5 1           16->15
Rd2 4     17->9
Lz4 1         18->19
Rd3 3       19->17
Lz5 1           20->21
Rd4 2         21->19
Rz5 1           22->21
END
#save $t;


  $_->setKeysPerNode(2) for $t->inorder;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply $t->printKeys, <<END;
SA0 5 1 2
Lz3 1       3 4->5 6
Ld2 2     5 6->9 10
Rz3 1       7 8->5 6
Rd1 4   9 10->1 2
Lz4 1         11 12->13 14
Ld3 2       13 14->17 18
Rz4 1         15 16->13 14
Rd2 3     17 18->9 10
Lz4 1         19 20->21 22
Rl3 2       21 22->17 18
END
#save $t;


  $_->setKeysPerNode(4) for $t->inorder;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply $t->printKeys, <<END;
SA0 4 1 2 3 4
Lz2 1     5 6 7 8->9 10 11 12
Rd1 3   9 10 11 12->1 2 3 4
Lz3 1       13 14 15 16->17 18 19 20
Rd2 2     17 18 19 20->9 10 11 12
Rz3 1       21 22->17 18 19 20
END
#save $t;
 }

printKeysAndData($t)

Print the mapping from keys to data in a tree

   Parameter  Description
1  $t         Tree

Example:

if (1)
 {my $N = 22;
  my $t = Tree::Bulk::new;
  ok $t->empty;
  ok $t->leaf;

  for(1..$N)
   {$t->insert($_, 2 * $_);
   }

  ok $t->right->duplex;
  is_deeply actualHeight($t), 4;

  is_deeply $t->printKeys, <<END;
SA0 4 1 2 3 4
Lz2 1     5 6 7 8->9 10 11 12
Rd1 3   9 10 11 12->1 2 3 4
Lz3 1       13 14 15 16->17 18 19 20
Rd2 2     17 18 19 20->9 10 11 12
Rz3 1       21 22->17 18 19 20
END
#save $t;


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

 1   2
 2   4
 3   6
 4   8
 5  10
 6  12
 7  14
 8  16
 9  18
10  20
11  22
12  24
13  26
14  28
15  30
16  32
17  34
18  36
19  38
20  40
21  42
22  44
END

  my %t = map {$_=>2*$_} 1..$N;

  for(map {2 * $_} 1..$N/2)
   {$t->delete($_);
    delete $t{$_};
    checkAgainstHash $t, %t;
   }

  is_deeply $t->printKeys, <<END;
SA0 3 1 3 5 7
Lz2 1     9 11 13->15 17 19 21
Rl1 2   15 17 19 21->1 3 5 7
END
#save($t);


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

 1   2
 3   6
 5  10
 7  14
 9  18
11  22
13  26
15  30
17  34
19  38
21  42
END

  for(map {2 * $_-1} 1..$N/2)
   {$t->delete($_);
    delete $t{$_};
    checkAgainstHash $t, %t;
   }

  is_deeply $t->printKeys, <<END;
Sz0 1
END
#save($t);
 }

Tree::Bulk Definition

Bulk tree node

Output fields

data

Data corresponding to each key

height

Height of node

keys

Array of data items for this node

keysPerNode

Maximum number of keys per node

left

Left node

right

Right node

up

Parent node

Attributes

The following is a list of all the attributes in this package. A method coded with the same name in your package will over ride the method of the same name in this package and thus provide your value for the attribute in place of the default value supplied for this attribute by this package.

Replaceable Attribute List

new

Create a new tree

Private Methods

node($key, $data, $up, $side)

Create a new bulk tree node

   Parameter  Description
1  $key       Key
2  $data      $data
3  $up        Parent node
4  $side      Side of parent node

updateHeights($n)

Update height of rotated node

   Parameter  Description
1  $n         Tree

rotateLeft($n)

Rotate a node left

   Parameter  Description
1  $n         Node

Example:

if (1)
 {lll "Rotate";
  my  $t = Tree::Bulk::new->setKeysPerNode(1);
  my  $a = node(1,2);
  my  $b = node(2,4);
  my  $c = node(3,6);
  my  $d = node(4,8);
  $a->right = $b; $b->up = $a;
  $b->right = $c; $c->up = $b;
  $c->right = $d; $d->up = $c;
  $d->setHeights(1);

  ok $c->simplex;

  is_deeply $a->printKeys, <<END;
SA0 4 1
Rr1 3   2->1
Rr2 2     3->2
Rz3 1       4->3
END
#save $a;

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

  is_deeply $a->printKeys, <<END;
SA0 3 1
Lz2 1     2->3
Rd1 2   3->1
Rz2 1     4->3
END
#save $a;


  $c->rotateLeft; $c->setHeights(2);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply $a->printKeys, <<END;
SA0 4 1
Lz3 1       2->3
Ll2 2     3->4
Rl1 3   4->1
END
#save $a;

  $d->rotateRight; $d->setHeights(1);
  is_deeply $a->printKeys, <<END;
SA0 3 1
Lz2 1     2->3
Rd1 2   3->1
Rz2 1     4->3
END
#save $a;

  $c->rotateRight; $c->setHeights(2);
  is_deeply $a->printKeys, <<END;
SA0 4 1
Rr1 3   2->1
Rr2 2     3->2
Rz3 1       4->3
END
#save $a;
 }

rotateRight($n)

Rotate a node right

   Parameter  Description
1  $n         Node

Example:

if (1)
 {lll "Rotate";
  my  $t = Tree::Bulk::new->setKeysPerNode(1);
  my  $a = node(1,2);
  my  $b = node(2,4);
  my  $c = node(3,6);
  my  $d = node(4,8);
  $a->right = $b; $b->up = $a;
  $b->right = $c; $c->up = $b;
  $c->right = $d; $d->up = $c;
  $d->setHeights(1);

  ok $c->simplex;

  is_deeply $a->printKeys, <<END;
SA0 4 1
Rr1 3   2->1
Rr2 2     3->2
Rz3 1       4->3
END
#save $a;
  $b->rotateLeft;
  is_deeply $a->printKeys, <<END;
SA0 3 1
Lz2 1     2->3
Rd1 2   3->1
Rz2 1     4->3
END
#save $a;

  $c->rotateLeft; $c->setHeights(2);
  is_deeply $a->printKeys, <<END;
SA0 4 1
Lz3 1       2->3
Ll2 2     3->4
Rl1 3   4->1
END
#save $a;


  $d->rotateRight; $d->setHeights(1);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply $a->printKeys, <<END;
SA0 3 1
Lz2 1     2->3
Rd1 2   3->1
Rz2 1     4->3
END
#save $a;


  $c->rotateRight; $c->setHeights(2);  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

  is_deeply $a->printKeys, <<END;
SA0 4 1
Rr1 3   2->1
Rr2 2     3->2
Rz3 1       4->3
END
#save $a;
 }

insertUnchecked($tree, $key, $data)

Insert a key and some data into a tree

   Parameter  Description
1  $tree      Tree
2  $key       Key
3  $data      Data

refill($tree)

Refill a node so it has the expected number of keys

   Parameter  Description
1  $tree      Tree

printKeys2($t, $in, $g)

print the keys for a tree

   Parameter  Description
1  $t         Tree
2  $in        Indentation
3  $g         List of keys

checkLR($tree)

Confirm pointers in tree

   Parameter  Description
1  $tree      Tree

check($tree)

Confirm that each node in a tree is ordered correctly

   Parameter  Description
1  $tree      Tree

checkAgainstHash($t, %t)

Check a tree against a hash

   Parameter  Description
1  $t         Tree
2  %t         Expected

Index

1 actualHeight - Get the height of a node

2 balance - Balance a node

3 check - Confirm that each node in a tree is ordered correctly

4 checkAgainstHash - Check a tree against a hash

5 checkLR - Confirm pointers in tree

6 delete - Delete a key in a tree

7 duplex - Return the tree if it has left and right children

8 empty - Return the tree if it is empty

9 find - Find a key in a tree and returns its data

10 first - First node in a tree

11 inorder - Return a list of all the nodes in a tree in order

12 insert - Insert a key and some data into a tree

13 insertUnchecked - Insert a key and some data into a tree

14 isLeftChild - Return the tree if it is the left child

15 isRightChild - Return the tree if it is the right child

16 isRoot - Return the tree if it is the root

17 last - Last node in a tree

18 leaf - Return the tree if it is a leaf

19 maximum - Maximum of two numbers

20 name - Name of a tree

21 next - Next node in order

22 node - Create a new bulk tree node

23 prev - Previous node in order

24 printKeys - Print the keys in a tree

25 printKeys2 - print the keys for a tree

26 printKeysAndData - Print the mapping from keys to data in a tree

27 refill - Refill a node so it has the expected number of keys

28 root - Return the root node of a tree

29 rotateLeft - Rotate a node left

30 rotateRight - Rotate a node right

31 setHeights - Set heights along path to root

32 setKeysPerNode - Set the number of keys for the current node

33 simplex - Return the tree if it has either a left child or a right child but not both.

34 singleton - Return the tree if it contains only the root node and nothing else

35 updateHeights - Update height of rotated node

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::Bulk

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.

2 POD Errors

The following errors were encountered while parsing the POD:

Around line 156:: =pod directives shouldn't be over one line long! Ignoring all 6 lines of content
Around line 205:: =pod directives shouldn't be over one line long! Ignoring all 8 lines of content

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

cpanm

cpanm Tree::Bulk

CPAN shell

perl -MCPAN -e shell
install Tree::Bulk

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

Bulk Tree

isRoot($tree)

root($tree)

leaf($tree)

duplex($tree)

simplex($tree)

empty($tree)

singleton($tree)

isLeftChild($tree)

isRightChild($tree)

name($tree)

setHeights($tree, $from)

actualHeight($tree)

maximum($a, $b)

balance($tree)

insert($tree, $key, $data)

find($tree, $key)

first($n)

last($n)

next($tree)

prev($tree)

inorder($tree)

delete($tree, $key)

printKeys($t)

setKeysPerNode($tree, $N)

printKeysAndData($t)

Tree::Bulk Definition

Output fields

data

height

keys

keysPerNode

left

right

up

Attributes

Replaceable Attribute List

new

Private Methods

node($key, $data, $up, $side)

updateHeights($n)

rotateLeft($n)

rotateRight($n)

insertUnchecked($tree, $key, $data)

refill($tree)

printKeys2($t, $in, $g)

checkLR($tree)

check($tree)

checkAgainstHash($t, %t)

Index

Installation

Author

Copyright

Module Install Instructions