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 identification in relation to the kind of key it contains, which helps with characteristics of the node like named parameters or catch all kind (globbing).

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

Included Modules

Defined in:

graphlb/data_structures/radix_tree.cr

Constructors

Instance Method Summary

Constructor Detail

def self.new(key : String, payload : T? = nil, placeholder = 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 <=>(other : self) #

Compares this node against other, returning -1, 0 or 1 depending on whether this node differentiates from other.

Comparison is done combining node's kind and #priority. Nodes of same kind are compared by priority. Nodes of different kind are ranked.

Normal nodes

node1 = Radix::Node(Nil).new("a")  # normal
node2 = Radix::Node(Nil).new("bc") # normal
node1 <=> node2                    # => 1

Normal vs named or glob nodes

node1 = Radix::Node(Nil).new("a")         # normal
node2 = Radix::Node(Nil).new(":query")    # named
node3 = Radix::Node(Nil).new("*filepath") # glob
node1 <=> node2                           # => -1
node1 <=> node3                           # => -1

Named vs glob nodes

node1 = Radix::Node(Nil).new(":query")    # named
node2 = Radix::Node(Nil).new("*filepath") # glob
node1 <=> node2                           # => -1

[View source]
def children #

[View source]
def children=(children) #

[View source]
def glob? #

Returns true if the node key contains a glob parameter in it (catch all)

node = Radix::Node(Nil).new("*filepath")
node.glob? # => true

node = Radix::Node(Nil).new("abc")
node.glob? # => false

[View source]
def key #

[View source]
def key=(key) #

Changes current key

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

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

This will also result in change of node's #priority

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

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

[View source]
def named? #

Returns true if the node key contains a named parameter in it

node = Radix::Node(Nil).new(":query")
node.named? # => true

node = Radix::Node(Nil).new("abc")
node.named? # => false

[View source]
def normal? #

Returns true if the node key does not contain an special parameter (named or glob)

node = Radix::Node(Nil).new("a")
node.normal? # => true

node = Radix::Node(Nil).new(":query")
node.normal? # => false

[View source]
def payload #

def payload=(payload : T?) #

[View source]
def payload? #

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 up until a special elements is found.

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

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

Radix::Node(Nil).new("/src/*filepath").priority
# => 5

Radix::Node(Nil).new("/search/:query").priority
# => 8

[View source]