Module: HexaPDF::Utils::SortedTreeNode

Included in:
NameTreeNode, NumberTreeNode
Defined in:
lib/hexapdf/utils/sorted_tree_node.rb

Overview

Provides the convenience methods that are used for name trees and number trees.

The provided methods require two methods defined in the including class so that they work correctly:

leaf_node_container_name

Defines the dictionary entry name that contains the leaf node entries.

For example, for name trees this would be :Names.

key_type

Defines the class that is used for the keys in the tree.

The class defined this way is used for making sure that only valid keys are used.

For example, for name trees this would be String.

Note: Like with HexaPDF::Dictionary, the keys are assumed to always be direct objects!

See: HexaPDF::NameTreeNode, HexaPDF::NumberTreeNode

Instance Method Summary collapse

Instance Method Details

#add_entry(key, data, overwrite: true) ⇒ Object

:call-seq:

tree.add_entry(key, data, overwrite: true)           -> true or false

Adds a new tree entry (key-data pair) to the sorted tree and returns true if it was successfully added.

If the option overwrite is true, an existing entry is overwritten. Otherwise an error is raised.

This method has to be invoked on the root node of the tree!



80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
 
# File 'lib/hexapdf/utils/sorted_tree_node.rb', line 80

def add_entry(key, data, overwrite: true)
  if key?(:Limits)
    raise HexaPDF::Error, "Adding a new tree entry is only allowed via the root node"
  elsif !key.kind_of?(key_type)
    raise ArgumentError, "A key must be a #{key_type} object, not a #{key.class}"
  end

  container_name = leaf_node_container_name

  if (!key?(:Kids) && !key?(container_name)) ||
      (value[:Kids] && self[:Kids].empty?)
    value.delete(:Kids)
    value[container_name] = []
  end

  if key?(container_name)
    result = insert_pair(self[container_name], key, data, overwrite: overwrite)
    split_if_needed(self, self)
  else
    stack = []
    path_to_key(self, key, stack)

    result = insert_pair(stack.last[container_name], key, data, overwrite: overwrite)
    stack.last[:Limits] = stack.last[container_name].values_at(0, -2)
    stack.reverse_each.inject do |nested_node, node|
      nested_lower = nested_node[:Limits][0]
      nested_upper = nested_node[:Limits][1]
      if node[:Limits][0] > nested_lower
        node[:Limits][0] = nested_lower
      elsif node[:Limits][1] < nested_upper
        node[:Limits][1] = nested_upper
      end
      node
    end

    split_if_needed(stack[-2] || self, stack[-1])
  end

  result
end

#delete_entry(key) ⇒ Object

Deletes the entry specified by the key from the tree and returns the data. If the tree doesn’t contain the key, nil is returned.

This method has to be invoked on the root node of the tree!



125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
 
# File 'lib/hexapdf/utils/sorted_tree_node.rb', line 125

def delete_entry(key)
  if key?(:Limits)
    raise HexaPDF::Error, "Deleting a tree entry is only allowed via the root node"
  end

  stack = [self]
  path_to_key(self, key, stack)
  container_name = leaf_node_container_name

  return unless stack.last[container_name]
  index = find_in_leaf_node(stack.last[container_name], key)
  return unless stack.last[container_name][index] == key

  stack.last[container_name].delete_at(index) # deletes key
  value = stack.last[container_name].delete_at(index)

  stack.last[:Limits] = stack.last[container_name].values_at(0, -2) if stack.last[:Limits]

  stack.reverse_each.inject do |nested_node, node|
    if (!nested_node[container_name] || nested_node[container_name].empty?) &&
        (!nested_node[:Kids] || nested_node[:Kids].empty?)
      node[:Kids].delete(nested_node)
      document.delete(nested_node)
    end
    if !node[:Kids].empty? && node[:Limits]
      node[:Limits][0] = node[:Kids][0][:Limits][0]
      node[:Limits][1] = node[:Kids][-1][:Limits][1]
    end
    node
  end

  value
end

#each_entry ⇒ Object

:call-seq:

node.each_entry {|key, data| block }   -> node
node.each_entry                        -> Enumerator

Calls the given block once for each entry (key-data pair) of the sorted tree.



192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
 
# File 'lib/hexapdf/utils/sorted_tree_node.rb', line 192

def each_entry
  return to_enum(__method__) unless block_given?

  container_name = leaf_node_container_name
  stack = [self]
  until stack.empty?
    node = document.wrap(stack.pop, type: self.class)
    if node.key?(container_name)
      data = node[container_name]
      index = 0
      while index < data.length
        yield(data[index], data[index + 1])
        index += 2
      end
    elsif node.key?(:Kids)
      stack.concat(node[:Kids].reverse_each.to_a)
    end
  end

  self
end

#find_entry(key) ⇒ Object

Finds and returns the associated entry for the key, or returns nil if no such key is found.



161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
 
# File 'lib/hexapdf/utils/sorted_tree_node.rb', line 161

def find_entry(key)
  container_name = leaf_node_container_name
  node = self
  result = nil

  while result.nil?
    if node.key?(container_name)
      index = find_in_leaf_node(node[container_name], key)
      if node[container_name][index] == key
        result = node[container_name][index + 1]
      else
        break
      end
    elsif node.key?(:Kids)
      index = find_in_intermediate_node(node[:Kids], key)
      node = node[:Kids][index]
      node = document.wrap(node, type: self.class) if node
      break unless node && key >= node[:Limits][0] && key <= node[:Limits][1]
    else
      break
    end
  end

  result
end

#must_be_indirect? ⇒ Boolean

Tree nodes must always be indirect.

Note: There is no requirement that the root node of a tree must be indirect. However, making it indirect simplifies the implementation and is not against the spec.

Returns:

  • (Boolean) 


66
67
68
 
# File 'lib/hexapdf/utils/sorted_tree_node.rb', line 66

def must_be_indirect?
  true
end