Class: RadixTree::Node

Inherits:
Object
  • Object
show all
Defined in:
lib/radix_tree.rb

Constant Summary collapse

UNDEFINED = 
Object.new

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(key, index, value = UNDEFINED, children = nil) ⇒ Node

Returns a new instance of Node.



23
24
25
 
# File 'lib/radix_tree.rb', line 23

def initialize(key, index, value = UNDEFINED, children = nil)
  @key, @index, @value, @children = key, index, value, children
end

Instance Attribute Details

#children ⇒ Object (readonly)

Returns the value of attribute children.



21
22
23
 
# File 'lib/radix_tree.rb', line 21

def children
  @children
end

#index ⇒ Object (readonly)

Returns the value of attribute index.



19
20
21
 
# File 'lib/radix_tree.rb', line 19

def index
  @index
end

#key ⇒ Object (readonly)

Returns the value of attribute key.



19
20
21
 
# File 'lib/radix_tree.rb', line 19

def key
  @key
end

#value ⇒ Object (readonly)

Returns the value of attribute value.



20
21
22
 
# File 'lib/radix_tree.rb', line 20

def value
  @value
end

Instance Method Details

#delete(key, head) ⇒ Object 



111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
 
# File 'lib/radix_tree.rb', line 111

def delete(key, head)
  if same_key?(key)
    value, @value = @value, UNDEFINED
    value
  elsif !@children
    nil
  else
    pos = head_match_size(key, head)
    if child = find_child(key[pos])
      value = child.delete(key, @index)
      if value and child.undefined?
        reap(child)
      end
      value
    end
  end
end

#dump_tree(io, indent = '') ⇒ Object 



129
130
131
132
133
134
135
136
137
138
139
140
141
142
 
# File 'lib/radix_tree.rb', line 129

def dump_tree(io, indent = '')
  indent += '  '
  if undefined?
    io << sprintf("#<%s:0x%010x %s>", self.class.name, __id__, label.inspect)
  else
    io << sprintf("#<%s:0x%010x %s> => %s", self.class.name, __id__, label.inspect, @value.inspect)
  end
  if @children
    @children.each do |k, v|
      io << $/ + indent
      v.dump_tree(io, indent)
    end
  end
end

#dup ⇒ Object Also known as: clone 



144
145
146
147
148
149
150
151
152
153
154
 
# File 'lib/radix_tree.rb', line 144

def dup
    if @children
      children_dup = Hash.new
      @children.each do |k,v|
        children_dup[k] = v.dup
      end
    else
      children_dup = nil
    end
    Node.new(@key, @index, @value, children_dup)
end

#each(&block) ⇒ Object 



48
49
50
51
52
53
54
55
56
57
 
# File 'lib/radix_tree.rb', line 48

def each(&block)
  if @value != UNDEFINED
    block.call [label, @value]
  end
  if @children
    @children.each_value do |child|
      child.each(&block)
    end
  end
end

#each_key ⇒ Object 



59
60
61
62
63
 
# File 'lib/radix_tree.rb', line 59

def each_key
  each do |k, v|
    yield k
  end
end

#each_value ⇒ Object 



65
66
67
68
69
 
# File 'lib/radix_tree.rb', line 65

def each_value
  each do |k, v|
    yield v
  end
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


35
36
37
 
# File 'lib/radix_tree.rb', line 35

def empty?
  !@children and undefined?
end

#find_all(prefix, head, flag) ⇒ Object 



199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
 
# File 'lib/radix_tree.rb', line 199

def find_all(prefix, head, flag)
  flag = true if !flag && same_key?(prefix)
  if flag
    strs = []
      self.each do |l,v|
        strs << l if v != UNDEFINED
      end
    return strs
  else
    if @children
      pos = head_match_size(prefix, head)
      if child = find_child(prefix[pos])
        return child.find_all(prefix, @index, flag)
      end
    end
    nil
  end
end

#find_pre(key, head, p_key) ⇒ Object 



157
158
159
160
161
162
163
164
165
166
167
168
169
 
# File 'lib/radix_tree.rb', line 157

def find_pre(key, head, p_key)
  if same_key?(key)
    (p_key == "" ? nil : p_key)
  else
    if @children
      pos = head_match_size(key, head)
      if child = find_child(key[pos])
        return child.find_pre(key, @index, self.label)
      end
    end
    nil
  end
end

#find_suc(key, head, flag) ⇒ Object 



171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
 
# File 'lib/radix_tree.rb', line 171

def find_suc(key, head, flag)
  # check before the key or after
  flag = true if !flag && same_key?(key)
  if flag
    # after tje key and omit undefined value
    if undefined? || self.label == key
      # if undefined keep going
      if @children
        # next by lexicographic order
        k = @children.keys.sort.shift
        return @children[k].find_suc(key, nil, flag)
      end
      nil
    else
      return self.label
    end
  else
    # before the key
    if @children
      pos = head_match_size(key, head)
      if child = find_child(key[pos])
        return child.find_suc(key, @index, flag)
      end
    end
    nil
  end
end

#keys ⇒ Object 



71
72
73
 
# File 'lib/radix_tree.rb', line 71

def keys
  collect { |k, v| k }
end

#label ⇒ Object 



27
28
29
 
# File 'lib/radix_tree.rb', line 27

def label
  @key[0, @index]
end

#retrieve(key, head) ⇒ Object 



97
98
99
100
101
102
103
104
105
106
107
108
109
 
# File 'lib/radix_tree.rb', line 97

def retrieve(key, head)
  if same_key?(key)
    @value
  else
    if @children
      pos = head_match_size(key, head)
      if child = find_child(key[pos])
        return child.retrieve(key, @index)
      end
    end
    UNDEFINED
  end
end

#size ⇒ Object 



39
40
41
42
43
44
45
46
 
# File 'lib/radix_tree.rb', line 39

def size
  count = @value != UNDEFINED ? 1 : 0
  if @children
    @children.inject(count) { |r, (k, v)| r + v.size }
  else
    count
  end
end

#store(key, head, value) ⇒ Object 



79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
 
# File 'lib/radix_tree.rb', line 79

def store(key, head, value)
  if same_key?(key)
    @value = value
  else
    pos = head_match_size(key, head)
    if pos == @index
      push(key, value)
    else
      split(pos)
      if same_key?(key)
        @value = value
      else
        push(key, value)
      end
    end
  end
end

#undefined? ⇒ Boolean

Returns:

  • (Boolean) 


31
32
33
 
# File 'lib/radix_tree.rb', line 31

def undefined?
  @value == UNDEFINED
end

#values ⇒ Object 



75
76
77
 
# File 'lib/radix_tree.rb', line 75

def values
  collect { |k, v| v }
end