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

NAME

Ternary_XS - Perl extension implementing ternary search trees.

SYNOPSIS

  use Tree::Ternary_XS;
  $obj = new Tree::Ternary_XS;

  $obj->insert($str);

  $obj->search($str);

  $obj->nodes();
  $obj->terminals();

  $cnt = $obj->pmsearch($char, $str);
  @list = $obj->pmsearch($char, $str);

  $cnt = $obj->nearsearch($dist, $str);
  @list = $obj->nearsearch($dist, $str);

  @list = $obj->traverse();

DESCRIPTION

Tree::Ternary_XS is a Perl interface to a C implementation of ternary search trees as described by Jon Bentley and Robert Sedgewick. Ternary search trees are interesting data structures that provide a means of storing and accessing strings. They combine the time efficiency of digital tries with the space efficiency of binary search trees. Unlike a hash, they also maintain information about relative order.

This module is an adaptation from the C implementation published in Bentley and Sedgewick's article in the April 1998 issue of Dr. Dobb's Journal (see SEE ALSO). This module attempts to recreate the interface as much as possible of Mark Rogaski's Tree::Ternary, a pure Perl implementation. As Tree::Ternary_XS uses C code, it has important space and speed advantages over Tree::Ternary.

METHODS

new()

Creates a new Tree::Ternary object.

insert( STRING )

Inserts STRING into the tree. When a string is inserted, a scalar variable is created to hold whatever data you may wish to associate with the string. A reference to this scalar is returned on a successful insert. If the string is already in the tree, undef is returned.

search( STRING )

Searches for the presence of STRING in the tree. If the string is found, a reference to the associated scalar is returned, otherwise undef is returned.

nodes()

Returns the total number of nodes in the tree. This count does not include terminal nodes.

terminals()

Returns the total number of terminal nodes in the tree.

pmsearch( CHAR, STRING )

Performs a pattern match for STRING against the tree, using CHAR as a wildcard character. The wildcard will match any characters. For example, if '.' was specified as the wildcard, and STRING was the pattern ".a.a.a." would match "bananas" and "pajamas" (if they were both stored in the tree). In a scalar context, returns the count of matches found. In an array context, returns a list of the matched strings.

nearsearch( DISTANCE, STRING )

Searches for all strings in a tree that differ from STRING by DISTANCE or fewer characters. In a scalar context, returns the count of matches found. In an array context, returns a list of the matched strings.

traverse()

Simply returns a sorted list of the strings stored in the tree. This method will do more tricks in the future.

NOTES

Character Set

Tree::Ternary_XS currently only has support for strings not containing the null character.

Incompatibilities

There are a number of differences between Tree::Ternary and Tree::Ternary_XS:

The rinsert() and rsearch() methods are not supported. Use insert() and search() instead.

The insert and search methods do not return a reference to a scalar. This limits the possibilities of the module somewhat, but is expected to be rectified (with a different interface) in a later version.

Performance

Tree::Ternary_XS has been benchmarked at about 50 times faster than Tree::Ternary, with a great reduction in memory usage.

AUTHOR

Leon Brocard, leon@astray.com

CREDITS

Thanks to Mark Rogaski for the pure Perl interface. Most of the documentation and test scripts are simply copies from Tree::Ternary.

COPYRIGHT

Copyright (c) 2000 Leon Brocard. All rights reserved. This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.

SEE ALSO

Bentley, Jon and Sedgewick, Robert. "Ternary Search Trees". Dr. Dobbs Journal, April 1998. http://www.ddj.com/articles/1998/9804/9804a/9804a.htm

Bentley, Jon and Sedgewick, Robert. "Fast Algorithms for Sorting and Searching Strings". Eighth Annual ACM-SIAM Symposium on Discrete Algorithms New Orleans, January, 1997. http://www.cs.princeton.edu/~rs/strings/