The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.
 / 
Tree-Bulk-20240415
River stage zero No dependents
++
/ Tree::Bulk

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 "20240415".

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

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 "SetHeights";
    my  $a = node(1,1)->setKeysPerNode(1);
    my  $b = node(2,2)->setKeysPerNode(1);
    my  $c = node(3,3)->setKeysPerNode(1);
    my  $d = node(4,4)->setKeysPerNode(1);
    my  $e = node(5,5);
    $a->right = $b; $b->up = $a;
    $b->right = $c; $c->up = $b;
    $c->right = $d; $d->up = $c;
    $d->right = $e; $e->up = $d;

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

    $e->setHeights(1);
    is_deeply $a->printKeys, <<END;
  SA0 4 1
  Rr1 3   2->1
  Lz3 1       3->4
  Rd2 2     4->2
  Rz3 1       5->4
  END
  #save $a;

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


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


    $c->balance;
    is_deeply $a->printKeys, <<END;
  SA0 4 1
  Rr1 3   2->1
  Lz3 1       3->4
  Rd2 2     4->2
  Rz3 1       5->4
  END
  #save $a;

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

simplexWithLeaf ($tree)

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

     Parameter  Description
  1  $tree      Tree

Example:

  if (1)
   {lll "Balance";
    my  $a = node(1,1)->setKeysPerNode(1); $a->height = 5;
    my  $b = node(2,2)->setKeysPerNode(1); $b->height = 4;
    my  $c = node(3,3)->setKeysPerNode(1); $c->height = 3;
    my  $d = node(4,4)->setKeysPerNode(1); $d->height = 2;
    my  $e = node(5,5);                    $e->height = 1;
    $a->right = $b; $b->up = $a;
    $b->right = $c; $c->up = $b;
    $c->right = $d; $d->up = $c;
    $d->right = $e; $e->up = $d;

    $e->balance;
    is_deeply $a->printKeys, <<END;
  SA0 5 1
  Rr1 4   2->1
  Rr2 3     3->2
  Rr3 2       4->3
  Rz4 1         5->4
  END
  #save $a;

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


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


    $d->balance;
    is_deeply $a->printKeys, <<END;
  SA0 5 1
  Rr1 4   2->1
  Rr2 3     3->2
  Rr3 2       4->3
  Rz4 1         5->4
  END
  #save $a;

    $c->balance;
    is_deeply $a->printKeys, <<END;
  SA0 5 1
  Rr1 3   2->1
  Lz3 1       3->4
  Rd2 2     4->2
  Rz3 1       5->4
  END
  #save $a;

    $b->balance;
    is_deeply $a->printKeys, <<END;
  SA0 4 1
  Lr2 2     2->4
  Rz3 1       3->2
  Rd1 3   4->1
  Rz2 1     5->4
  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;
   }

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;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

   }

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;
   }

names ($tree)

Names of all nodes in a tree in order

     Parameter  Description
  1  $tree      Tree

Example:

  if (1)
   {my sub randomLoad($$$)                                                        # Randomly load different size nodes
     {my ($N, $keys, $height) = @_;                                               # Number of elements, number of keys per node, expected height

      lll "Random load $keys";

      srand(1);                                                                   # Same randomization
      my $t = Tree::Bulk::new->setKeysPerNode($keys);
      for my $r(randomizeArray 1..$N)
       {$t->insert($r, 2 * $r);
        $t->check;
       }

      is_deeply $t->actualHeight, $height;                                        # Check height
      confess unless $t->actualHeight == $height;

      is_deeply join(' ', 1..$N), $t->names;  # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲


      my %t = map {$_=>2*$_}   1..$N;
      for my $r(randomizeArray 1..$N)                                             # Delete in random order
       {$t->delete   ($r);
            delete $t{$r};
        checkAgainstHash $t, %t;
        check($t);
       }

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

    randomLoad(222, 1, 11);                                                       # Random loads
    randomLoad(222, 8, 8);
    randomLoad(222, 4, 9);
   }

balance ($t)

Balance a node

     Parameter  Description
  1  $t         Tree

Example:

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

    my  $a = node(1,2) ->setKeysPerNode(1);
    my  $b = node(2,4) ->setKeysPerNode(1);
    my  $c = node(6,12)->setKeysPerNode(1);
    my  $d = node(5,10)->setKeysPerNode(1);
    my  $e = node(4,8) ->setKeysPerNode(1);
    my  $f = node(3,6) ->setKeysPerNode(1);
    $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 4 1
  Lr2 2     2->4
  Rz3 1       3->2
  Rd1 3   4->1
  Lz3 1       5->6
  Rl2 2     6->4
  END
  #save $a;


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

    is_deeply $a->printKeys, <<END;
  SA0 4 1
  Lr2 2     2->4
  Rz3 1       3->2
  Rd1 3   4->1
  Lz3 1       5->6
  Rl2 2     6->4
  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, 10;

    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, 10;

    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, 10;

    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, 10;

    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, 10;

    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
  Rr1 2   2->1
  Rz2 1     3->2
  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
  Rr1 2   9 11 13 15->1 3 5 7
  Rz2 1     17 19 21->9 11 13 15
  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);
   }

Hash Definitions

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

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

setHeights ($tree)

Set heights along path to root

     Parameter  Description
  1  $tree      Tree

Example:

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

    my  $a = node(1,2) ->setKeysPerNode(1);
    my  $b = node(2,4) ->setKeysPerNode(1);
    my  $c = node(6,12)->setKeysPerNode(1);
    my  $d = node(5,10)->setKeysPerNode(1);
    my  $e = node(4,8) ->setKeysPerNode(1);
    my  $f = node(3,6) ->setKeysPerNode(1);
    $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 4 1
  Lr2 2     2->4
  Rz3 1       3->2
  Rd1 3   4->1
  Lz3 1       5->6
  Rl2 2     6->4
  END
  #save $a;

    $b->balance;
    is_deeply $a->printKeys, <<END;
  SA0 4 1
  Lr2 2     2->4
  Rz3 1       3->2
  Rd1 3   4->1
  Lz3 1       5->6
  Rl2 2     6->4
  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
  Rr1 2   9 11 13 15->1 3 5 7
  Rz2 1     17 19 21->9 11 13 15
  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);
   }

setHeight ($tree)

Set height of a tree from its left and right trees

     Parameter  Description
  1  $tree      Tree

rotateLeft ($n)

Rotate a node left

     Parameter  Description
  1  $n         Node

Example:

  if (1)
   {lll "Rotate";
    my  $a = node(1,2)->setKeysPerNode(1);
    my  $b = node(2,4)->setKeysPerNode(1);
    my  $c = node(3,6)->setKeysPerNode(1);
    my  $d = node(4,8)->setKeysPerNode(1);
    $a->right = $b; $b->up = $a;
    $b->right = $c; $c->up = $b;
    $c->right = $d; $d->up = $c;
    $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;

    $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 3 1
  Lz2 1     2->3
  Rd1 2   3->1
  Rz2 1     4->3
  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 3 1
  Lz2 1     2->3
  Rd1 2   3->1
  Rz2 1     4->3
  END
  #save $a;
   }

rotateRight ($n)

Rotate a node right

     Parameter  Description
  1  $n         Node

Example:

  if (1)
   {lll "Rotate";
    my  $a = node(1,2)->setKeysPerNode(1);
    my  $b = node(2,4)->setKeysPerNode(1);
    my  $c = node(3,6)->setKeysPerNode(1);
    my  $d = node(4,8)->setKeysPerNode(1);
    $a->right = $b; $b->up = $a;
    $b->right = $c; $c->up = $b;
    $c->right = $d; $d->up = $c;
    $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;
    $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 3 1
  Lz2 1     2->3
  Rd1 2   3->1
  Rz2 1     4->3
  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 3 1
  Lz2 1     2->3
  Rd1 2   3->1
  Rz2 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

unchain ($t)

Remove a tree from the middle of a chain. A leaf is considered to be in the middle of a chain and so can be removed with this method

     Parameter  Description
  1  $t         Tree

refillFromRight ($target)

Push a key to the target node from the next node

     Parameter  Description
  1  $target    Target tree

refillFromLeft ($target)

Push a key to the target node from the previous node

     Parameter  Description
  1  $target    Target tree

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

checkLRU($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 checkLRU - 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 name - Name of a tree

20 names - Names of all nodes in a tree in order

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 refillFromLeft - Push a key to the target node from the previous node

29 refillFromRight - Push a key to the target node from the next node

30 root - Return the root node of a tree

31 rotateLeft - Rotate a node left

32 rotateRight - Rotate a node right

33 setHeight - Set height of a tree from its left and right trees

34 setHeights - Set heights along path to root

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

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

37 simplexWithLeaf - Return the tree if it has either a left child or a right child but not both and the child it has a leaf.

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

39 unchain - Remove a tree from the middle of a chain.

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://prb.appaapps.com

Copyright

Copyright (c) 2016-2023 Philip R Brenan.

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