class Radix::Tree(T)

Overview

A Radix tree implementation.

It allows insertion of path elements that will be organized inside the tree aiming to provide fast retrieval options.

Each inserted path will be represented by a Node or segmented and distributed within the Tree.

You can associate a payload at insertion which will be return back at retrieval time.

Defined in:

graphlb/data_structures/radix_tree.cr

Constructors

Instance Method Summary

Constructor Detail

def self.new #

[View source]

Instance Method Detail

def add(path : String, payload : T) #

Inserts given path into the Tree

  • path - An String representing the pattern to be inserted.
  • payload - Required associated element for this path.

If no previous elements existed in the Tree, this will replace the defined placeholder.

tree = Radix::Tree(Symbol).new

# /         (:root)
tree.add "/", :root

# /         (:root)
# \-abc     (:abc)
tree.add "/abc", :abc

# /         (:root)
# \-abc     (:abc)
#     \-xyz (:xyz)
tree.add "/abcxyz", :xyz

Nodes inside the tree will be adjusted to accommodate the different segments of the given path.

tree = Radix::Tree(Symbol).new

# / (:root)
tree.add "/", :root

# /                   (:root)
# \-products/:id      (:product)
tree.add "/products/:id", :product

# /                    (:root)
# \-products/
#           +-featured (:featured)
#           \-:id      (:product)
tree.add "/products/featured", :featured

Catch all (globbing) and named parameters path will be located with lower priority against other nodes.

tree = Radix::Tree(Symbol).new

# /           (:root)
tree.add "/", :root

# /           (:root)
# \-*filepath (:all)
tree.add "/*filepath", :all

# /           (:root)
# +-about     (:about)
# \-*filepath (:all)
tree.add "/about", :about

[View source]
def find(path : String) #

Returns a Result instance after walking the tree looking up for path

It will start walking the tree from the root node until a matching endpoint is found (or not).

tree = Radix::Tree(Symbol).new
tree.add "/about", :about

result = tree.find "/products"
result.found?
# => false

result = tree.find "/about"
result.found?
# => true

result.payload
# => :about

[View source]
def root : Radix::Node(T) #

Returns the root Node element of the Tree.

On a new tree instance, this will be a placeholder.


[View source]