kanwei/algorithms

This system is a Ruby gem providing high-performance data structures and algorithms, implemented primarily as C extensions for speed with Ruby fallbacks for compatibility. It offers a modular library of containers such as deques, heaps, red-black trees, splay trees, tries, and KD-trees, alongside algorithmic modules for sorting, searching, and string manipulation like Levenshtein distance. The codebase includes comprehensive benchmarks and tests to validate the performance and correctness of these native implementations.

Introduces a new Binary Search Tree container implemented as a Ruby C extension (CBst). This addition provides a keyed collection that supports insertion, deletion, search, and iteration, with optimized comparison logic for Fixnum and String keys to improve performance over generic object comparison.

ext/containers/bst · high confidence

A new C extension named CDeque has been added to provide a deque (double-ended queue) data structure. This implementation exposes methods for adding and removing elements from both the front and back of the queue, as well as querying the size, checking if the queue is empty, clearing the contents, and iterating through elements in both forward and backward directions. The extension is built using Ruby's C API and includes garbage collection support to properly manage memory for the stored objects.

ext/containers/deque · high confidence

This change introduces two new native C extensions for Ruby: \CSplayTreeMap\ and \CRBTreeMap\. The \ext/containers/splaytree\_map\ directory now contains the implementation for a splay tree map, providing optimized insertion, retrieval, and deletion operations that splay accessed nodes to the root. Similarly, the \ext/containers/rbtree\_map\ directory adds a red-black tree map implementation, ensuring balanced tree structures for consistent performance. These extensions offer high-performance, memory-efficient alternatives to pure Ruby hash implementations for ordered key-value storage.

_ext/containers/splaytree\map · high confidence

A new C extension for string algorithms has been added, introducing the \Algorithms::String.levenshtein\_dist\ method. This feature calculates the Levenshtein distance (edit distance) between two strings, implemented in C for performance and integrated into the existing \Algorithms\ module structure.

ext/algorithms · high confidence

The containers library now includes several new data structures. A Deque (double-ended queue) is available, implemented in C with a Ruby fallback, allowing O(1) additions and removals from both ends. A KDTree supports nearest-neighbor searches in multi-dimensional space. A SuffixArray enables fast substring searches via binary search on sorted suffixes. A Trie (specifically a Ternary Search Tree) provides O(m) key lookups and supports wildcard matching and longest-prefix queries. These new containers are added alongside existing ones like Heap, PriorityQueue, Queue, Stack, RBTreeMap, and SplayTreeMap.

lib/containers · high confidence

The library now includes three new algorithm modules: \Algorithms::Search\ provides binary search and the Knuth-Morris-Pratt (KMP) substring search; \Algorithms::Sort\ implements multiple sorting algorithms including bubble, comb, selection, heap, insertion, shell, and quicksort; and \Algorithms::String\ provides string algorithm support via an optional C extension.

lib/algorithms · high confidence

The executable script located at bin/algorithms has been removed from the project. This change eliminates the specific algorithmic tool or entry point that was previously available in this location.

bin · high confidence

The legacy implementations for Stack, Heap, Hash, Priority Queue, and Queue have been removed from the library. This cleanup eliminates stubbed or incomplete classes (such as the placeholder Heap class and the basic Stack wrapper) that were previously part of the data structures module, likely to make way for more robust or distinct implementations introduced in other parts of the codebase.

lib/datastructures · high confidence

The library has been reorganized from a single monolithic class into modular namespaces (Algorithms and Containers), providing users with a broader range of data structures and algorithms. Users can now access heaps, stacks, queues, deques, priority queues, red-black trees, splay trees, tries, suffix arrays, and KD-trees via the Containers module, alongside search, sorting (including dual-pivot quicksort), and string algorithms (like Levenshtein distance) via the Algorithms module. The main entry point now requires these specific sub-modules, enabling more granular usage and better organization of the available functionality.

lib · high confidence

The project's build system has been updated to replace the Echoe gem with Bundler and Rake's native ExtensionTask. This change modifies the Rakefile to explicitly define C extension tasks (such as CString, CDeque, CBst, CRBTreeMap, and CSplayTreeMap) and integrates RSpec for testing, ensuring that C extensions are compiled by default on non-JRuby platforms before running specs. Additionally, legacy text-based documentation files (History.txt, Manifest.txt, README.txt) have been removed in favor of Markdown equivalents (CHANGELOG.markdown, ALGORITHM\_INFO.md, README.markdown), and a .gitignore file has been added to exclude build artifacts and IDE files.

(repo-wide) · high confidence

Add benchmarks for deque, heap, sort, and treemap operations; Added comprehensive test coverage for data structures and algorithms.

This change introduces the initial packaging of the 'algorithms' Ruby gem, version 1.1.0, which provides data structures (such as heaps, priority queues, deques, stacks, queues, red-black trees, splay trees, and tries) and sorting algorithms. The package includes optional C extensions for performance on standard Ruby, while supporting JRuby via Java platform specifications. Development dependencies for testing and compilation (rspec, rake-compiler) are established via a new Gemfile and Gemfile.lock.

(dependencies) · high confidence

Written by watchdog.canine.dev from the codebase's own history, inside the signed delivery this page is composed from.

• First survey — no prior run to compare against. CAI 63.

• Code Health 96
• Architecture 100
• Maturity 45
• Readiness 61
• Security 96

• 246 commits — 215 feature/other, 31 fixes

• lib/containers — 76 commits
• (root) — 72 commits
• ext/containers — 39 commits
• (repo) — 11 commits
• lib/algorithms.rb — 7 commits
• lib/datastructures — 7 commits
• lib/algorithms — 6 commits
• spec/deque_spec.rb — 5 commits
• ext/datastructures — 3 commits
• spec/bst_gc_mark_spec.rb — 3 commits
• spec/heap_spec.rb — 3 commits
• spec/rb_tree_map_spec.rb — 3 commits
• ext/algorithms — 2 commits
• .github/workflows — 1 commit
• benchmarks/heap.rb — 1 commit
• benchmarks/sorts.rb — 1 commit
• benchmarks/treemaps.rb — 1 commit
• spec/deque_gc_mark_spec.rb — 1 commit
• spec/kd_tree_spec.rb — 1 commit
• spec/priority_queue_spec.rb — 1 commit

• fix: Added benchmark file, fixed case/when for 1.9 compatibility
• fix: Deque doc fixes
• fix: FINALLY fixed rbtree.c #delete bug. We were deleting the wrong nodes.
• fix: Fix Heap comparison not working on some Objects (#60)
• fix: Fix RBTreeMap#delete crash on missing keys
• fix: Fix SuffixArray initialization doc (#50)
• fix: Fix push to be O(1).
• fix: Fix raise_error warnings.
• fix: Fix release date
• fix: Fix specs to be compatible with new shared_examples format
• fix: Fix splaytree gc marking issue, and it can now handle over 260K entries. Now mark iteratively for splaytree and rbtree.
• fix: Fix tests for RSpec 3
• fix: Fixed README
• fix: Fixed Splay#get to not break tree
• fix: Fixed bug in CRBTree's empty? method
• fix: Fixed delete bug in CTreeMap
• fix: Fixed memory leak in CRBTree
• fix: Fixed nasty #delete bug for RBTree -- Thank you Robert Sedgewick!
• fix: Fixed some issues with Deque and added specs
• fix: JRuby fixes
• …and 226 more

Written by watchdog.canine.dev from the codebase's own history, inside the signed delivery this page is composed from.

kanwei/algorithms was measured the same way every project in this corpus was: the same rubric, at a pinned commit, with the result published in full. Point a surveyor at a repository you know and see whether you agree with it.