aethyr/Aethyr
2
0
Fork 0
Code Issues 281 Pull requests Projects Releases Packages Wiki Activity Actions

Implement TrieNode data structure with insertion and longest-prefix lookup #99

New issue
Open
opened 2026-03-15 04:13:12 +00:00 by freemo · 1 comment
freemo commented 2026-03-15 04:13:12 +00:00
Owner
Copy link

Metadata

  • Commit Message: feat(dispatch): implement TrieNode with insertion and lookup
  • Branch: feature/m1-command-router

Background and Context

The trie is the core data structure for O(k) command dispatch. Each node represents
a character. Terminal nodes store a RouteEntry. The trie supports exact match and
longest-prefix match for ambiguity detection.

Expected Behavior

  • TrieNode stores children as a Hash keyed by character
  • insert(key, route_entry) adds a command registration
  • lookup(key) returns exact match or longest-prefix match
  • Ambiguous prefixes (where multiple commands share a prefix) are detected

Acceptance Criteria

  • TrieNode class in lib/aethyr/core/commands/trie_node.rb
  • insert and lookup methods
  • Ambiguity detection for shared prefixes
  • O(k) time complexity for lookup
  • BDD scenarios covering exact, prefix, ambiguous, and not-found cases

Subtasks

  • Implement TrieNode with children hash and terminal flag
  • Implement insert method
  • Implement lookup with exact and prefix matching
  • Add ambiguity detection
  • Write Cucumber feature file

Definition of Done

This issue is complete when:

  • All subtasks above are completed and checked off.
  • A Git commit is created where the first line of the commit message matches the
    Commit Message in Metadata exactly.
  • The commit is pushed to the remote on the branch matching the Branch in Metadata.
  • The commit is submitted as a pull request to master, reviewed, and merged.
## Metadata - **Commit Message**: `feat(dispatch): implement TrieNode with insertion and lookup` - **Branch**: `feature/m1-command-router` ## Background and Context The trie is the core data structure for O(k) command dispatch. Each node represents a character. Terminal nodes store a `RouteEntry`. The trie supports exact match and longest-prefix match for ambiguity detection. ## Expected Behavior - `TrieNode` stores children as a Hash keyed by character - `insert(key, route_entry)` adds a command registration - `lookup(key)` returns exact match or longest-prefix match - Ambiguous prefixes (where multiple commands share a prefix) are detected ## Acceptance Criteria - `TrieNode` class in `lib/aethyr/core/commands/trie_node.rb` - `insert` and `lookup` methods - Ambiguity detection for shared prefixes - O(k) time complexity for lookup - BDD scenarios covering exact, prefix, ambiguous, and not-found cases ## Subtasks - [x] Implement TrieNode with children hash and terminal flag - [x] Implement insert method - [x] Implement lookup with exact and prefix matching - [x] Add ambiguity detection - [x] Write Cucumber feature file ## Definition of Done This issue is complete when: - All subtasks above are completed and checked off. - A Git commit is created where the **first line** of the commit message matches the Commit Message in Metadata exactly. - The commit is pushed to the remote on the branch matching the **Branch** in Metadata. - The commit is submitted as a **pull request** to `master`, reviewed, and **merged**.
freemo added this to the (deleted) milestone 2026-03-15 04:13:12 +00:00
freemo self-assigned this 2026-03-15 04:25:23 +00:00
freemo modified the milestone from (deleted) to v1.0.0 2026-03-16 00:28:02 +00:00
freemo commented 2026-03-16 03:04:11 +00:00
Author
Owner
Copy link

Implementation Notes

Design Decisions

  • Extracted TrieOperations module from TrieNode class to satisfy Rubocop ClassLength limit while keeping a clean public API
  • Priority-based conflict resolution: higher priority wins primary slot, losers go to conflict_entries
  • All keys lowercased before insertion for case-insensitive matching
  • remove() promotes highest-priority conflict entry when primary is removed

Code Locations

  • Aethyr::Core::Commands::TrieNode - main trie data structure
  • Aethyr::Core::Commands::TrieOperations - extracted private helpers
  • Both in lib/aethyr/core/commands/trie_node.rb

Test Results

  • 19 BDD scenarios, all passing
  • Covers: exact match, prefix match, ambiguous prefix, not found, conflict resolution, remove, input validation
  • Rubocop: 0 offenses
## Implementation Notes ### Design Decisions - Extracted `TrieOperations` module from `TrieNode` class to satisfy Rubocop ClassLength limit while keeping a clean public API - Priority-based conflict resolution: higher priority wins primary slot, losers go to `conflict_entries` - All keys lowercased before insertion for case-insensitive matching - `remove()` promotes highest-priority conflict entry when primary is removed ### Code Locations - `Aethyr::Core::Commands::TrieNode` - main trie data structure - `Aethyr::Core::Commands::TrieOperations` - extracted private helpers - Both in `lib/aethyr/core/commands/trie_node.rb` ### Test Results - 19 BDD scenarios, all passing - Covers: exact match, prefix match, ambiguous prefix, not found, conflict resolution, remove, input validation - Rubocop: 0 offenses
Sign in to join this conversation.
No Branch/Tag specified
Branches Tags
master
feature/m2-headless-renderer
dependabot/bundler/rdoc-6.3.2
dependabot/bundler/rexml-3.2.5
dependabot/bundler/json-tw-2.3
inprogress
dependabot/bundler/rake-tw-13.0
No results found.
Labels
Clear labels   
Blocked

Cannot proceed, depends on unresolved issue

  
Duplicate

Issue is a duplicate of an existing one

  
MoSCoW/Could Have

Desirable but not necessary, included if time permits

  
MoSCoW/Must Have

Essential, project cannot ship without it

  
MoSCoW/Should Have

Important but not strictly essential

  
Points/1

Estimated effort: 1 story points

  
Points/13

Estimated effort: 13 story points

  
Points/2

Estimated effort: 2 story points

  
Points/21

Estimated effort: 21 story points

  
Points/3

Estimated effort: 3 story points

  
Points/5

Estimated effort: 5 story points

  
Points/8

Estimated effort: 8 story points

  
Priority/Backlog

Not yet prioritized

  
Priority/Critical

Must be addressed immediately

  
Priority/High

Important, should be completed soon

  
Priority/Low

Nice to have, not time-sensitive

  
Priority/Medium

Normal priority, valid and should be addressed

  
State/Completed

Issue resolved and all PRs merged

  
State/In progress

Someone is actively working on this issue

  
State/In review

Implementation complete, PR submitted for review

  
State/Paused

Work temporarily suspended, typically blocked

  
State/Unverified

Issue created but not yet reviewed by a maintainer

  
State/Verified

Maintainer confirmed valid and actionable

  
State/Wont Do

Deliberate decision not to address this issue

  
Type/Bug

A defect in existing functionality

  
Type/Epic

Large body of work broken into multiple issues

  
Type/Feature

A new capability or user story

  
Type/Legendary

Major strategic pillar composed of multiple Epics

  
Type/Task

Technical or administrative work (not bug or feature)

  
Type/Testing

Test-only work item (TDD, test infrastructure, coverage)

No labels
Blocked
Duplicate
MoSCoW/Could Have
MoSCoW/Must Have
MoSCoW/Should Have
Points/1
Points/13
Points/2
Points/21
Points/3
Points/5
Points/8
Priority/Backlog
Priority/Critical
Priority/High
Priority/Low
Priority/Medium
State/Completed
State/In progress
State/In review
State/Paused
State/Unverified
State/Verified
State/Wont Do
Type/Bug
Type/Epic
Type/Feature
Type/Legendary
Type/Task
Type/Testing
Milestone
Clear milestone
No items
No milestone
v1.0.0
Projects
Clear projects
No items
No project
Assignees
Clear assignees
No assignees
freemo
1 participant
Notifications
Due date
The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Blocks
#98 Epic: Trie-based Command Dispatch Router
aethyr/Aethyr
Reference: aethyr/Aethyr#99
No description provided.
Delete branch "%!s()"

Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?