Class: GeoTreeModule::GeoTree

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

Overview

See the README file for a discussion of this class.

Constant Summary collapse

ROOT_NODE_NAME_ = 
BlockFile::FIRST_BLOCK_ID
@@next_pt_id = 
500

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(block_file = nil) ⇒ GeoTree

Construct GeoTree

Parameters:

  • block_file (defaults to: nil) —

    if nil, creates in-memory tree



21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
# File 'lib/geotree/geotree.rb', line 21

def initialize(block_file = nil)

  block_file ||= BlockFile.new(KDTREE_BLOCKSIZE)
  @block_file = block_file
  @buffer = PtBuffer.new(self)

  @mod_nodes = Set.new # names of modified nodes
  @cache_dict = {}
  @c_start = NodeI.new(555,false,Bounds.new(0,0,0,0))
  @c_end = NodeI.new(666,false,Bounds.new(0,0,0,0))
  GeoTree.join_nodes(@c_start,@c_end)

  @block_file.open

  # The root node, if it exists, will be in the first block.
  if @block_file.name_max <= ROOT_NODE_NAME_
    root = NodeL.new(ROOT_NODE_NAME_,false, @@start_bounds)
    # we need to add this node to the cache since it's just been built
    cache_node(root)
    root_name = @block_file.alloc(encode_block(root))
    write_node(root)
  end
end

Class Method Details

.max_bounds ⇒ Object 



83
84
85
 
# File 'lib/geotree/geotree.rb', line 83

def self.max_bounds
  @@start_bounds
end

.open(path = nil) ⇒ Object

Open tree from file; if it doesn’t exist, creates an empty tree, one prepared to use that file to persist it

Parameters:

  • path (defaults to: nil) —

    path of file; if nil, constructs tree in memory only



91
92
93
94
95
96
97
 
# File 'lib/geotree/geotree.rb', line 91

def self.open(path = nil)
  bf = nil
  if path
    bf = DiskBlockFile.new(KDTREE_BLOCKSIZE, path)
  end
  GeoTree.new(bf);
end

.read_data_point_from(b, offset) ⇒ Object 



281
282
283
284
285
286
 
# File 'lib/geotree/geotree.rb', line 281

def self.read_data_point_from(b, offset)
  name = BlockFile.read_int(b, offset)
  weight = BlockFile.read_int(b, offset+1)
  locn = Loc.new(BlockFile.read_int(b,offset+2),BlockFile.read_int(b,offset+3))
  DataPoint.new(name,weight,locn)
end

.rnd_points(count) ⇒ Object 



260
261
262
263
 
# File 'lib/geotree/geotree.rb', line 260

def self.rnd_points(count)
  b = Bounds.new(100,100,900,900)
  rnd_points_within(count,b)
end

.rnd_points_within(count, bounds) ⇒ Object 



267
268
269
270
271
272
273
274
275
276
277
278
279
 
# File 'lib/geotree/geotree.rb', line 267

def self.rnd_points_within(count, bounds)

  a = []
  count.times do |i|
    w = Loc.new(bounds.x + rand(1 + bounds.w), bounds.y + rand(1 + bounds.h))
    next if !@@start_bounds.contains_point(w)

    wt = (rand * rand * rand * MAX_POINT_WEIGHT).to_i
    a << DataPoint.create_with_name(@@next_pt_id,wt,w)
    @@next_pt_id += 1
  end
  a
end

.write_data_point(dp, b, offset) ⇒ Object 



288
289
290
291
292
293
 
# File 'lib/geotree/geotree.rb', line 288

def self.write_data_point(dp, b, offset)
  BlockFile.write_int(b,offset, dp.name)
  BlockFile.write_int(b,offset+1, dp.weight)
  BlockFile.write_int(b,offset+2, dp.loc.x)
  BlockFile.write_int(b,offset+3, dp.loc.y)
end

Instance Method Details

#add(data_point) ⇒ Object

Add a datapoint to the tree. Does not ensure that a datapoint with this name already exists in the tree, even if it has the same location.

Raises:



103
104
105
106
 
# File 'lib/geotree/geotree.rb', line 103

def add(data_point)
  raise IllegalStateException if !open?
  @buffer.add(data_point)
end

#add_buffered_point(data_point) ⇒ Object 



62
63
64
65
66
67
68
69
70
71
72
 
# File 'lib/geotree/geotree.rb', line 62

def add_buffered_point(data_point)
  # construct path of interior nodes leading to leaf node set
  path = []
  add_data_point(data_point, ROOT_NODE_NAME_,path,@@start_bounds,false)

  # adjust populations for each internal node on path
  path.each do |n|
    n.adjust_population(1)
    write_node(n)
  end
end

#buffering=(val) ⇒ Object

Raises:



14
15
16
17
 
# File 'lib/geotree/geotree.rb', line 14

def buffering=(val)
  raise IllegalStateException if !open?
  @buffer.active = val
end

#close ⇒ Object

Raises:



49
50
51
52
53
54
55
56
57
58
59
60
 
# File 'lib/geotree/geotree.rb', line 49

def close
  raise IllegalStateException if !open?

  # Stop buffering, in case we were, to flush points to tree
  @buffer.active = false

  # Flush the block file, among other things
  done_operation

  @block_file.close
  @block_file = nil
end

#dump(root_node = nil) ⇒ Object

Dump tree in graphical form

Raises:



246
247
248
249
250
251
252
253
254
255
256
257
258
 
# File 'lib/geotree/geotree.rb', line 246

def dump(root_node = nil)
  raise IllegalStateException if !open?
  root_node ||= read_root_node

  s2 = "-"*50+"\n"

  s = "KDTree (rooted at #{root_node.name})\n"
  s << s2

  dump_aux(s,root_node,0,{})
  s << s2
  s
end

#find(rect) ⇒ Object

Find all points intersecting a rectangle.

Raises:



210
211
212
213
214
215
216
 
# File 'lib/geotree/geotree.rb', line 210

def find(rect)
  raise IllegalStateException if (!open? || @buffer.active)
  a = []
  find_aux(rect,a,ROOT_NODE_NAME_,@@start_bounds,false)
  done_operation
  a
end

#find_point(df) ⇒ Object

Determine if a particular datapoint lies in the tree

Raises:



219
220
221
222
223
224
225
226
227
228
229
230
231
 
# File 'lib/geotree/geotree.rb', line 219

def find_point(df)
  raise IllegalStateException if (!open? || @buffer.active)
  vb = Bounds.new(df.loc.x,df.loc.y,1,1)
  fa = find(vb)
  ret = false
  fa.each do |dp|
    if dp.name == df.name
      ret = true
      break;
    end
  end
  ret
end

#open? ⇒ Boolean

Returns:

  • (Boolean) 


45
46
47
 
# File 'lib/geotree/geotree.rb', line 45

def open?
  @block_file != nil
end

#remove(data_point) ⇒ Object

Remove a datapoint. Returns the datapoint if it was found and removed, otherwise nil. A datapoint will be removed iff both its name and location match the sought point; the weight is ignored.

Raises:



112
113
114
115
116
117
118
119
120
121
122
123
124
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
158
159
160
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
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
 
# File 'lib/geotree/geotree.rb', line 112

def remove(data_point)

  raise IllegalStateException if @buffer.active

  removed = nil
  block do

    # construct path of interior nodes leading to the leaf node set that contains the point
    # (if one exists)
    internal_path = []

    n = read_root_node

    while !n.leaf

      internal_path << n

      # find the child that will contain the point
      child_slot = n.slot_intersecting_line(n.vertical ? data_point.loc.y : data_point.loc.x)
      next_name = n.slot_child(child_slot)
      if next_name == 0
        n = nil
        break
      end
      n = read_node(next_name,n.slot_bounds(child_slot),!n.vertical)
    end
    break if !n

    # build list of overflow nodes
    leaf_set = build_leaf_set(n)

    # We now have path containing the path of internal nodes, and leaf_set the leaf nodes

    # find the node containing this point
    found_leaf_index  = found_slot = -1

    leaf_set.each_with_index do |leaf,i|
      found_slot = leaf.find_point(data_point)
      if found_slot >= 0
        found_leaf_index = i
        break
      end
    end
    break if found_leaf_index < 0

    # copy last datapoint to found location's, then delete last datapoint
    leaf_node = leaf_set[found_leaf_index]
    removed = leaf_node.data_point(found_slot)

    last_leaf_node = leaf_set[-1]
    lu = last_leaf_node.used

    leaf_node.set_data_point(found_slot, last_leaf_node.data_point(lu-1))
    last_leaf_node.pop_last_point

    write_node(last_leaf_node)
    write_node(leaf_node)

    # If the last leaf is now empty, remove it
    if last_leaf_node.used == 0
      leaf_set.pop
      if leaf_set.size != 0
        prev_leaf = leaf_set[-1]
        prev_leaf.overflow = 0
        write_node(prev_leaf)
        delete_node(last_leaf_node)
      else
        # It was the first leaf in the set, so we should remove it
        # from its parent (NodeI) slot (if it's not the root)
        if last_leaf_node.name != ROOT_NODE_NAME_
          parent = internal_path[-1]
          parent.remove_child_named(last_leaf_node.name)
          write_node(parent)
        end
      end
    end

    # for each internal node in the path:
    # [] adjust population by -1
    # [] if population has dropped below half the capacity of a leaf node,
    #     convert subtree to leaf node
    while internal_path.size != 0
      inode = internal_path.pop

      inode.adjust_population(-1)
      write_node(inode)

      if inode.population < SPLIT_SIZE/2
        collapse_internal_node(inode)
      end
    end
  end
  done_operation
  removed
end

#statistics ⇒ Object

Calculate some statistics about the tree

Returns:

  • dictionary of field(string) => value

Raises:



235
236
237
238
239
240
241
242
243
 
# File 'lib/geotree/geotree.rb', line 235

def statistics
  raise IllegalStateException if !open?

  st = TreeStats.new
  i = ROOT_NODE_NAME_
  aux_stats(ROOT_NODE_NAME_,@@start_bounds,false,false,0,st)

  st.summary
end