Revision history for Perl extension Algorithm::SkipList. (Changes which may not be backwards compatible are marked with an asterisk '*'.) 1.02 Wed Jan 4 2005 * removed validate_key and validate_value methods from node types - removed commented-out assertions - added _search_nodes method - keys and values methods rewritten, and can retrieve keys or values between key ranges ranges - copy method rewritten - corrected typo in error message - added missing test to MANIFEST - added additional tests - added SIGNATURE to distribution 1.01 Fri Sep 3 2004 - minor correction to distribution 1.00 Fri Sep 3 2004 - renamed distribution to Algorithm-SkipList - updated version numbers - added deprecation note to List::SkipList abstract 0.73_01 Mon Aug 2 2004 - renamed module to Algorithm::SkipList from List::SkipList - Node and Header types are now in separate files - List::SkipList is included, but gives deprecation warnings - header node gives warnings when calling key or value methods - heavy test has less tests for standard dist - renamed test files - minor code changes - corrected typos in POD - removed benchmarking code from etc/ - redid version numbering of Node and Header classes, since they were ignored by PAUSE/CPAN indexers anyway - added PurePerl dummy class 0.73 Mon Jul 26 2004 - rebuilt distribution with proper META.yml 0.72 Wed Jun 30 2004 - removed List::SkipList::Null type and $NULL variable - moved Test::More from requires to build_requires parameter 0.71 Sat Jun 12 2004 - updated POD - redesigned internals of first_key, next_key and last_key * delete now resets last_key * the parameters for last_key are changed (this interface was meant for internal use only, however) - added index_by_key, key_by_index and value_by_index methods - updated documentation on p and k parameters - added support for k parameter - redid probability distribution calculations - fixed bug in benchmarks (was "existing" bogus keys) - added support for duplicate values - added find_duplicates method - corrected typos in POD for new method 0.71_01 Wed Jun 9 2004 - fixed bug in benchmarks (was deleting bogus keys) - added some warnings - improved delete method - added truncate method - _search_with_finger now builds correct update vector - append calls _adjust_level_threshold - minor optimizations of node class * renamed internal key {LASTNODE} to {LIST_END} so as not to be confused with last_key method - _first_node is not autoloading since it's now used by first_key - updated POD to reflect issue with undefined values - improved copy method (undef values handled) - copy method can accept an argument: copy from key * copy method no longer resets first_key * _first_node no longer returns a finger (it was never used) - updated documentation on values for max_level and p - corrected typos in documentation - added tests for deleted greatest bug - fixed bug with greatest method when deleting last node - added _greatest_node method to find the last node as needed - other minor code changes 0.70_01 Sun Jun 6 2004 - tests rewritten (work in progress) - fixed bug with next_key checking node when key was deleted - uses Test::More for tests - fixed "Too late to run INIT block" error with Test::More use_ok, $NULL is now set in import() method - fixed bug where level sometimes exceeded user-set max level - P and max_level can now be set dynamically - added tests for max_level and p - checks for error when setting max_level or P - fixed bug with definition of List::SkipList::Null - $NULL is now an 'our' variable and accessible from outside - level method was changed to autoload, since it was redundant - minor optimization of _search_with_finger and _search * header method in Node is read-only - it returns a pointer which can be used to change values anyway * key method in Node is read-only - it should not be changed once it is inside a list - added _adjust_level_threshold method from code that was in _new_node_level to adjust SIZE_THRESHOLD/SIZE_LEVEL - _adjust_level_threshold is called upon inserts and deletes - SIZE_LEVEL does not decrease under MIN_LEVEL * removed null() method - it was never used * max_level cannot be greater than 32 (cleaner code) - increased coverage of "heavy" test script - minor updates to all test scripts 0.65 Thu June 3 2004 - updated README 0.64 Thu June 3 2004 - updated examples in documentation of custom node - minor optimizations and code cleanup - commented-out call to prev() in _debug - removed use of Carp::Assert in tests - redesigned benchmark script and included parse-out.pl - updated Benchmark.txt - updated README 0.63 Fri May 28 2004 - The default value of P is now 0.25, which appears to yield better results in tests. * renamed _random_level to _new_node_level - SIZE_THRESHOLD/SIZE_LEVEL now decrease with deletions - additional minor optimizations and code cleanup - optimizations of Header and Null node types - updated tests - Benchmark: re-commented-out delete test for Tree::RedBlack (which was accidentally uncommented in v0.62) 0.62 Tue May 18 2004 - fixed typo in (commented-out) assertion - additional minor optimizations and code cleanup - updated tests - corrected README 0.61 Mon May 17 2004 * find no longer returns a finger in array context * header is now a special subclass of List::SkipList::Node - added special Null subclass of Header - added null() method to return global null node - a lot of minor code optimizations - added comments - maximum level of new nodes changed so that it is based on size of list - updated Benchmark.txt file 0.60 Sat Apr 24 2004 - updates to POD - cleaned up comments - added next function - redid last_key, first_key and next_key functions - last_key accepts arguments to modify LASTKEY - changed calls to die to croak - added experimental hooks to implement prev and prev_key methods - added stub prev_key method - bug fix: reset method called during copy method - added more tests to heavy test script * renamed find to find_with_finger and added find for searches which do not return updated fingers * renamed _search to _search_with_finger and added _search for searches which do not return updated fingers - modified next_key test to check for initial key of "0" - removed if (CACHE_INSERT_FINGERS) tests - additional optimizations and code cleanup - added test to search for non-existent keys in Benchmark.pl 0.51 Mon Apr 12 2004 - fixed bug with next_key method called without first_key - added tests for this bug - added "heavy" test to distribution - minor optimizations of delete method - assertions are no longer required (which leads to ~3% speedup) and removed section in POD about assertions - removed commented-out references to forward method - minor updates to source code comments 0.50 Mon Mar 29 2004 - section about Assertions added to POD - documented level() method - clear method now intitializes initial node header - added various assertions * removed the forward method from *::Node - uses enum module - added test for non-integer keys - clear method now resets LAST_INSRT cache - removed use of LEVEL for List::SkipList::Node * key_cmp method accesses KEY directly rather than uses the key method * calling convention for List::SkipList::Node is changed - various optimizations to List::SkipList and *::Node - added comparison to Tree::RedBlack in Benchmark.pl - minor changes to _search method - added Benchmark.pl script for generating benchmarks in distro - redesigned benchmarking script 0.42 Sat Mar 20 2004 - fixed bug with Build.PL not autospliting files 0.41 Fri Mar 19 2004 * List::SkipList::Node is now array-based rather than hash-based to improve speed. - updates to POD, README, Benchmark.txt - added search method as alias to find - renamed Benchmark to Benchmark.txt - optimized deletions 0.40 Wed Mar 17 2004 - added Benchmark file to distribution * key_cmp now ignores when key is undefined - _insert returns the value of $node->key_cmp($key) - broke up test cases into separate files - added finger caching to speed up sequential inserts - fixed bugs with values, keys, copy, merge, first_key and next_key methods related to use of search fingers - fixed bug with append method - fixed bug with search fingers: they were not being used - _debug now prints to STDERR * reset method is not called when a new node is added or deleted (which is in accord with documentation) - stub for next method added - List::SkipList::Node ignores invalid and extra arguments - minor optimizations in List::SkipList and List::SkipList::Node - improved speed of _random_level - disabled assertions (for 50% speed improvement!) - inserted corrected comment in README about actual performance in comparison to trees 0.33 Tue Mar 16 2004 - fixed typos in test cases that caused Makefile tests to fail - removed causes of warnings in 01-SkipList.t - replaced explicit package names with __PACKAGE__ placeholder 0.32 Mon Mar 15 2004 - renamed test.pl to t/01-SkipList.t - added Build.PL to distribution - updated README - corrected and updated POD 0.31 Fri Feb 13 2004 - removed memoized node example from POD - reformatted E-mail addresses in various files to foil spam harvesters - changes calls to keys to CORE::keys [Bug 5317] - added version to List::SkipList::Node - corrected errors in POD formatting - corrected and updated POD - added META.yml file to distribution 0.30 Tue Dec 2 2003 - ability to tie hashes - made some methods autoloading - added last_key and reset methods to allow auto-enumeration - added least, greatest, keys and values methods - added _first_node, merge, append and copy methods - insert now returns a finger - more updates to documentation 0.21 Wed Nov 26 2003 - bug fix: first_key method returns a proper finger - added documentation and tests about memoization 0.20 Wed Nov 26 2003 - if no last_key specified for next_key, it returns first_key - search fingers added - find, first_key, next_key return a list in list context as part of support for search fingers - minor changes to documentation 0.13 Wed Nov 19 2003 - added call to validate_key in key_cmp in Node 0.12 Wed Nov 19 2003 - added validate_key and validate_node methods to Node 0.11 Sun Nov 16 2003 - modified test script to better check next_key function - bug fix: next_key did not check that $last_key existed 0.10 Sat Nov 15 01:11:00 2003 - updated test script appropriately - added first_key and next_key methods - added ability to customize List::SkipList::Node - moved debug method to after __END__ block - renamed random_level to _random_level - changed type checking to use isa() method - updated documentation 0.02 Fri Nov 14 01:08:00 2003 - incorporated experimental code into module - began writing initial test script 0.01 Fri Nov 14 00:50:00 2003 - original version; created by h2xs 1.21 with options -X -n List::SkipList -v 0.01 0.00 Wed Nov 12 2003 - experimental versions, unreleased.