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 searchnodes 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
• searchwith_finger now builds correct update vector
• append calls adjustlevel_threshold
• minor optimizations of node class
  • renamed internal key {LASTNODE} to {LIST_END} so as not to be confused with last_key method
• firstnode 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
  • firstnode 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 greatestnode 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 searchwith_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 adjustlevel_threshold method from code that was in newnode_level to adjust SIZE_THRESHOLD/SIZE_LEVEL
• adjustlevel_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 randomlevel to newnode_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 searchwith_finger and added search for searches which do not return updated fingers
• modified nextkey 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->keycmp($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 randomlevel
• 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 firstnode, 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 randomlevel
• 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.