Class: Derailleur::TrieNode

Inherits:
Object
  • Object
show all
Defined in:
lib/derailleur/core/trie.rb

Direct Known Subclasses

ArrayTrieNode, HashTrieNode

Defined Under Namespace

Classes: EmptyClass

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(name, parent = nil) ⇒ TrieNode

Creates a new node whose name and optional parent are set from the parameters. There is a check wether the parent is absorbent (which disallow childrens) The children is set to EmptyClass, which is a placeholder for subclasses

Raises:

  • (ArgumentError) 


31
32
33
34
35
36
37
 
# File 'lib/derailleur/core/trie.rb', line 31

def initialize(name, parent=nil)
  raise ArgumentError, "cannot be the child of #{parent} because it is an absorbent node" if parent and parent.absorbent?
  @parent = parent
  @children = EmptyClass
  set_normal!
  self.name = name
end

Instance Attribute Details

#children ⇒ Object (readonly)

The children of this node



8
9
10
 
# File 'lib/derailleur/core/trie.rb', line 8

def children
  @children
end

#content ⇒ Object

The children of this node



11
12
13
 
# File 'lib/derailleur/core/trie.rb', line 11

def content
  @content
end

#name ⇒ Object

The name for this node



5
6
7
 
# File 'lib/derailleur/core/trie.rb', line 5

def name
  @name
end

#parent ⇒ Object

The parent of this node, or nil if this node is a root



14
15
16
 
# File 'lib/derailleur/core/trie.rb', line 14

def parent
  @parent
end

Instance Method Details

#<=>(other) ⇒ Object

Compares a node with another, based on their name



106
107
108
 
# File 'lib/derailleur/core/trie.rb', line 106

def <=> other
  name <=> other.name
end

#absorbent? ⇒ Boolean

An absorbent node is a node which cannot be parent, its name is ‘*’.

Returns:

  • (Boolean) 


96
97
98
 
# File 'lib/derailleur/core/trie.rb', line 96

def absorbent?
  @absorbent
end

#compatible_graft?(other) ⇒ Boolean

Returns true wether the other node could be grafted over this one. It is the case if both nodes are normals or both are non-normal.

Returns:

  • (Boolean) 


151
152
153
154
 
# File 'lib/derailleur/core/trie.rb', line 151

def compatible_graft?(other)
  (normal? and other.normal?) or
  ((not normal?) and (not other.normal?))
end

#compatible_handoff?(other) ⇒ Boolean

Returns true wether this node could handoff its position to another one. It is the case if both nodes are normals or both are non-normal.

Returns:

  • (Boolean) 


128
129
130
131
 
# File 'lib/derailleur/core/trie.rb', line 128

def compatible_handoff?(other)
  (normal? and other.normal?) or
  ((not normal?) and (not other.normal?))
end

#graft!(other) ⇒ Object

Placeholder for the handoff logic, this method should be overridden by subclasses.



164
165
166
167
168
169
 
# File 'lib/derailleur/core/trie.rb', line 164

def graft!(other)
  verify_graft(other)
  other.parent = parent
  parent.children.add other
  parent.children.delete self
end

#hand_off_to!(other) ⇒ Object

Placeholder for the handoff logic, this method should be overridden by subclasses.



141
142
143
144
145
146
147
 
# File 'lib/derailleur/core/trie.rb', line 141

def hand_off_to!(other)
  verify_hand_off_to(other)
  other.children.replace children
  other.parent = parent
  @children = EmptyClass
  @parent = nil
end

#normal? ⇒ Boolean

A normal node is not absorbent and node wildcard

Returns:

  • (Boolean) 


101
102
103
 
# File 'lib/derailleur/core/trie.rb', line 101

def normal?
  (not wildcard?) and (not absorbent?)
end

#root ⇒ Object

Returns the root of the tree structure (recursive)



117
118
119
 
# File 'lib/derailleur/core/trie.rb', line 117

def root
  parent ? parent.root : self
end

#root? ⇒ Boolean

Returns wether or not this node is a root node (i.e., parent is nil)

Returns:

  • (Boolean) 


122
123
124
 
# File 'lib/derailleur/core/trie.rb', line 122

def root?
  parent.nil?
end

#useless? ⇒ Boolean

A useless node has no content and no children, basically arriving at this point, there’s no handler you can ever find.

Returns:

  • (Boolean) 


112
113
114
 
# File 'lib/derailleur/core/trie.rb', line 112

def useless?
  content.nil? and children.empty?
end

#verify_graft(other) ⇒ Object

Raise argument errors if the grafting of the other node is not licit.

Raises:

  • (ArgumentError) 


157
158
159
160
 
# File 'lib/derailleur/core/trie.rb', line 157

def verify_graft(other)
  raise ArgumentError, "incompatible grafting" unless compatible_graft?(other)
  raise ArgumentError, "cannot graft a root" if root?
end

#verify_hand_off_to(other) ⇒ Object

Raise argument errors if the handoff to other is not licit.

Raises:

  • (ArgumentError) 


134
135
136
137
 
# File 'lib/derailleur/core/trie.rb', line 134

def verify_hand_off_to(other)
  raise ArgumentError, "cannot hand off to node: #{other} because it is useful" unless other.useless?
  raise ArgumentError, "uncompatible handoff between #{self} and #{other}" unless compatible_handoff?(other)
end

#wildcard? ⇒ Boolean

A wildcard node is a node whose name was set with a trailing ‘:’

Returns:

  • (Boolean) 


91
92
93
 
# File 'lib/derailleur/core/trie.rb', line 91

def wildcard?
  @wildcard
end