The order in which nodes were inserted into a tree might produce
failures in lookup mechanism.
tree = Radix::Tree(Symbol).new
tree.add "/one/:id", :one
tree.add "/one-longer/:id", :two
result = tree.find "/one-longer/10"
# expected `true`
result.found? # => false
In above example, reversing the order of insertion solved the issue,
but exposed the naive sorting/prioritization mechanism used.
This change improves that by properly identifying the kind of node
being evaluated and compared against others of the same kind.
It is now possible to know in advance if a node contains an special
condition (named parameter or globbing) or is a normal one:
node = Radix::Node(Nil).new("a")
node.normal? # => true
node = Radix::Node(Nil).new(":query")
node.named? # => true
node = Radix::Node(Nil).new("*filepath")
node.glob? # => true
Which helps out with prioritization of nodes:
- A normal node ranks higher than a named one
- A named node ranks higher than a glob one
- On two of same kind, ranks are based on priority
With this change in place, above example works as expected:
tree = Radix::Tree(Symbol).new
tree.add "/one/:id", :one
tree.add "/one-longer/:id", :two
result = tree.find "/one-longer/10"
result.found? # => true
Fixes#18
Given two similar keys, one short and one with named parameter, lookup
was incorrectly picking up the named parameter version instead of the
specific one:
tree = Radix::Tree(Symbol).new
tree.add "/tag-edit/:id", :edit_tag
tree.add "/tag-edit2", :alternate_edit_tag
result = tree.find("/tag-edit2")
result.found? # => false
The order of insertion (named before specific) was causing the
lookup mechanism to validate it before checking the other options.
With the changes present here, short or long keys will be affected
anymore by named or globbed keys present when sharing part of the
key.
Fixeskemalcr/kemal#293
After Crystal 0.15, compiler will require declare the types used
by instance variables on classes.
This require changes to the usage of `Radix::Tree` by introducing
the type of payload elements it will handle:
# Will only support symbols as payload
tree = Radix::Tree(Symbol).new
tree.add "/", :root
# Error: cannot add node with anything other than Symbol
tree.add "/meaning-of-life", 42
The changes ensure future compatibility with Crystal and also
enforces a more declarative usage of `Radix::Tree`.
If necessary, you can combine multiple types to ensure a tree
can contain all the wide range of payloads you need:
tree = Radix::Tree.new(Foo | Bar | Symbol).new
tree.add "/", :root
tree.add "/foo", foo_instance
This change includes:
- Tree, Node and Result has been updated to require types.
- Node is capable of have optional payload (from defined type).
- Documentation has been updated to reflect this change.
Extract Radix Tree implementation from `Beryl` project into an
standalone library to facilitate usage by other developers.
- Move `Tree`, `Node` and `Result` into `Radix` namespace
- Clenaup standalone README and describe usage
