/ 
Tree-RB-XS-0.00_02
River stage zero No dependents
/ Tree::RB::XS

NAME

Tree::RB::XS - Similar API to Tree::RB implemented in C

VERSION

version 0.00_02

SYNOPSIS

my $tree= Tree::RB::XS->new;
$tree->put(a => 1);
say $tree->get('a');
$tree->delete('a');

# optimize for integer comparisons
$tree= Tree::RB::XS->new(key_type => KEY_TYPE_INT);
$tree->put(1 => "x");

# optimize for floating-point comparisons
$tree= Tree::RB::XS->new(key_type => KEY_TYPE_FLOAT);
$tree->put(0.125 => "x");

# optimize for byte strings
$tree= Tree::RB::XS->new(key_type => KEY_TYPE_BSTR);
$tree->put("test" => "x");

# inspect the node objects
say $tree->min->key;
say $tree->nth(0)->key;
my $node= $tree->min;
my $next= $node->next;
$node->prune;

DESCRIPTION

This module is similar to Tree::RB but implemented in C for speed.

CONSTRUCTOR

new

my $tree= Tree::RB::XS->new( %OPTIONS );
                   ...->new( \&compare_fn );

Options:

key_type

This chooses how keys will be stored in this tree: KEY_TYPE_ANY (the default), KEY_TYPE_INT, KEY_TYPE_FLOAT, KEY_TYPE_BSTR, or KEY_TYPE_USTR. Integers are of course the most efficient, followed by floats, followed by byte-strings and unicode-strings, followed by 'ANY' (which stores a whole perl scalar). BSTR and USTR both save an internal copy of your key, so might be a bad idea if your keys are extremely large and nodes are frequently added to the tree. The difference between BSTR and USTR is in how the bytes are initially copied out of the key during /insert, the former as raw bytes and the latter as UTF8 bytes.

If the compare_fn is a Perl coderef, this is forced to KEY_TYPE_ANY. (it is best for performance to store a whole perl scalar if they are going to be passed to your comparison function over and over and over).

compare_fn

A coderef that compares its parameters in the same manner as cmp.

If specified as a perl coderef, this forces key_type => KEY_TYPE_ANY, since calling your callback over and over is most efficient if the scalars are stored as scalars. Beware that using a custom coderef throws away most of the speed gains from using this XS variant over plain Tree::RB.

If not provided, the default comparison for ANY uses perl's own cmp operator, the default for BSTR and USTR are C's memcmp function, and INT and FLOAT are the obvious numeric comparisons. memcmp does not give correct unicode sorting, of course, but it's fast.

TODO: It would be neat to have a collection of enumerated XS comparison functions available to choose from, to get custom behavior without the performance hit of a coderef callback.

ATTRIBUTES

key_type

compare_fn

The optional coderef that will be called each time keys need compared.

allow_duplicates

Boolean, read/write. Controls whether "insert" will allow additional nodes with keys that already exist in the tree. This does not change the behavior of "put", only "insert". If you set this to false, it does not remove duplicates that already existed. The initial value is false.

size

Returns the number of elements in the tree.

METHODS

get

my $val= $tree->get($key);

Fetch a value form the tree, by its key. Unlike "get" in Tree::RB, this always returns a single value, regardless of list context, and does not accept options for how to find nearby keys.

get_node

Same as "get", but returns the node instead of the value.

put

my $old_val= $tree->put($key, $new_val);

Associate the key with a new value. If the key previously existed, this returns the old value, and updates the tree to reference the new value. If the tree allows duplicate keys, this will replace all nodes having this key.

delete

my $count= $tree->delete($key);

Delete any node with a key identical to $key, and return the number of nodes removed. (This will only return 0 or 1, unless you enable duplicate keys.)

insert

Insert a new node into the tree, and return the index at which it was inserted. If the node already existed, this returns -1 and does not change the tree.

min_node

Get the tree node with minimum key. Returns undef if the tree is empty.

Alias: min

max_node

Get the tree node with maximum key. Returns undef if the tree is empty.

Alias: max

nth_node

Get the Nth node in the sequence from min to max. N is a zero-based index. You may use negative numbers to count down form max.

Alias: nth

NODE OBJECTS

The nodes returned by the methods above have the following attributes:

key

The sort key. Read-only, but if you supplied a reference and you modify what it points to, you will break the sorting of the tree.

value

The data associated with the node. Read/Write.

prev

The previous node in the sequence of keys.

next

The next node in the sequence of keys.

left

The left sub-tree.

The right sub-tree.

parent

The parent node, if any.

color

0 = black, 1 = red.

count

The number of items in the tree rooted at this node (inclusive)

And the following methods:

prune

Remove this single node from the tree. The node will still have its key and value, but all attributes linking to other nodes will become undef.

EXPORTS

KEY_TYPE_ANY
KEY_TYPE_INT
KEY_TYPE_FLOAT
KEY_TYPE_BSTR
KEY_TYPE_USTR

AUTHOR

Michael Conrad <mike@nrdvana.net>

COPYRIGHT AND LICENSE

This software is copyright (c) 2021 by Michael Conrad.

This is free software; you can redistribute it and/or modify it under the same terms as the Perl 5 programming language system itself.