class Radix::Node(T)

Overview

A Node represents one element in the structure of a Radix tree

Carries a payload and might also contain references to other nodes down in the organization inside children.

Each node also carries a priority number, which might indicate the weight of this node depending on characteristics like catch all (globbing), named parameters or simply the size of the Node's key.

Referenced nodes inside children can be sorted by priority.

Is not expected direct usage of a node but instead manipulation via methods within Tree.

node = Radix::Node.new("/", :root)
node.children << Radix::Node.new("a", :a)
node.children << Radix::Node.new("bc", :bc)
node.children << Radix::Node.new("def", :def)
node.sort!

node.priority
# => 1

node.children.map &.priority
# => [3, 2, 1]

Defined in:

radix/node.cr

Constructors

Instance Method Summary

Constructor Detail

def self.new(key : String, payload : T | Nil = nil, placeholder : Bool = false) #

Instantiate a Node

  • key - A String that represents this node.
  • payload - An optional payload for this node.

When payload is not supplied, ensure the type of the node is provided instead:

# Good, node type is inferred from payload (Symbol)
node = Radix::Node.new("/", :root)

# Good, node type is now Int32 but payload is optional
node = Radix::Node(Int32).new("/")

# Error, node type cannot be inferred (compiler error)
node = Radix::Node.new("/")

[View source]

Instance Method Detail

def children #

[View source]
def children=(children : Array(Radix::Node(T))) #

[View source]
def key #

[View source]
def key=(key : String) #

Changes current key

node = Radix::Node(Nil).new("a")
node.key
# => "a"

node.key = "b"
node.key
# => "b"

This will also result in a new priority for the node.

node = Radix::Node(Nil).new("a")
node.priority
# => 1

node.key = "abcdef"
node.priority
# => 6

[View source]
def payload : T | Nil #

def payload=(payload : T | Nil) #

[View source]
def payload? : T | Nil | Nil #

def placeholder? #

[View source]
def priority : Int32 #

Returns the priority of the Node based on it's key

This value will be directly associated to the key size or special elements of it.

  • A catch all (globbed) key will receive lowest priority (0)
  • A named parameter key will receive priority above catch all (1)
  • Any other type of key will receive priority based on its size.
Radix::Node(Nil).new("a").priority
# => 1

Radix::Node(Nil).new("abc").priority
# => 3

Radix::Node(Nil).new("*filepath").priority
# => 0

Radix::Node(Nil).new(":query").priority
# => 1

[View source]
def sort! #

Changes the order of Node's children based on each node priority.

This ensures highest priority nodes are listed before others.

root = Radix::Node(Nil).new("/")
root.children << Radix::Node(Nil).new("*filepath") # node.priority => 0
root.children << Radix::Node(Nil).new(":query")    # node.priority => 1
root.children << Radix::Node(Nil).new("a")         # node.priority => 1
root.children << Radix::Node(Nil).new("bc")        # node.priority => 2
root.sort!

root.children.map &.priority
# => [2, 1, 1, 0]

[View source]