Class: Hipe::SimpleBTree

Inherits:
Hash
  • Object
show all
Defined in:
lib/hipe-simplebtree.rb

Overview

Experimental simple b-tree – the only purpose of this for now is to implement a method for “find the lowest key that is greater than the provided key” (or find the greatest key that is lower than a provided key) It won’t be efficient or useful for adding/removes lots of nodes, only for providing the above service. It is presumed that it will be slower than RBTrees (Red-Black tree), but faster than scanning all the elements of a sorted array to find this index.

Defined Under Namespace

Classes: Tree

Constant Summary collapse

VERSION = 
'0.0.1'

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(*args, &block) ⇒ SimpleBTree

Returns a new instance of SimpleBTree.

See Also:

  • Hash#new


15
16
17
18
19
20
21
22
23
 
# File 'lib/hipe-simplebtree.rb', line 15

def initialize(*args,&block)
  @locked_stack = 0
  @insepcting = false
  @autosort = true
  super
  @cmp_proc = nil
  @sorted_keys = [] # with a new hash it is always empty, right? (we don't have [] literal construtors)
  @tree = nil
end

Instance Attribute Details

#cmp_proc ⇒ Object

Returns the value of attribute cmp_proc.



30
31
32
 
# File 'lib/hipe-simplebtree.rb', line 30

def cmp_proc
  @cmp_proc
end

Class Method Details

.[](*args) ⇒ Object

See Also:

  • Hash::[]


26
27
28
 
# File 'lib/hipe-simplebtree.rb', line 26

def self.[](*args)
  self.new.send(:init_with_brackets, args)
end

Instance Method Details

#==(other) ⇒ Object 



103
104
105
 
# File 'lib/hipe-simplebtree.rb', line 103

def == (other)
  super && @sorted_keys == other.send(:sorted_keys) && @cmp_proc == other.cmp_proc
end

#[]=(k, value) ⇒ Object

Raises:

  • (TypeError) 


194
195
196
197
198
199
200
201
202
203
204
205
 
# File 'lib/hipe-simplebtree.rb', line 194

def []= k, value
  raise TypeError.new("can't modify simplebtree in iteration") if @locked_stack > 0
  use_key = k
  if (!has_key?(k))
    my_keys = @sorted_keys.dup # the unit test requires this
    my_keys << use_key
    my_keys.sort!(&@cmp_proc) # we want this to throw type comparison error
    @sorted_keys = my_keys
    @tree = nil # we loose a lot of sorted data when we add just one element.  # note 6.
  end
  super use_key, value
end

#_first_or_last(which) ⇒ Object 



81
82
83
84
85
86
87
88
 
# File 'lib/hipe-simplebtree.rb', line 81

def _first_or_last(which)
  if @sorted_keys.size > 0
    k = @sorted_keys.send(which)
    [get_cloned_key(k), self[k]]
  else
    default_proc ? default_proc.call(self) : default
  end
end

#bound(key1, key2 = key1) ⇒ Object

and upper_bound. If a block is given it calls the block once for each pair.

Returns:

  • an array containing key-value pairs between the result of lower_bound



265
266
267
268
269
270
271
272
273
274
275
 
# File 'lib/hipe-simplebtree.rb', line 265

def bound key1, key2=key1
 #require 'ruby-debug'
 #debugger
  return [] unless i1 = tree.lower_bound_index(key1) and i2 = tree.upper_bound_index(key2)  
  if block_given?  #note 9      
    @locked_stack += 1
    (i1..i2).each{ |i| yield @sorted_keys[i], self[@sorted_keys[i]] } 
    @locked_stack -= 1        
  end
  (i1..i2).map{ |i| [@sorted_keys[i], self[@sorted_keys[i]]] }              
end

#clear ⇒ Object 



230
 
# File 'lib/hipe-simplebtree.rb', line 230

def clear;      super; @sorted_keys.clear; @tree = nil;  end

#clone ⇒ Object 



47
48
49
50
51
52
53
 
# File 'lib/hipe-simplebtree.rb', line 47

def clone
  clone = self.class.new( &default_proc )
  clone.cmp_proc = self.cmp_proc
  clone.default = self.default unless clone.default_proc # very important! 1 hr. bug
  clone.update_with_hash self
  clone
end

#default(*args) ⇒ Object 



55
56
57
58
59
60
61
62
63
64
 
# File 'lib/hipe-simplebtree.rb', line 55

def default *args
  ret  =
  if 0==args.size then super
  elsif 2<=args.size then raise ArgumentError.new("expecting 0 or 1 had #{args.size}")
  elsif default_proc.nil? then super
  else
    self.default_proc.call self, args[0]
  end
  ret
end

#default_cmp_proc ⇒ Object 



77
78
79
 
# File 'lib/hipe-simplebtree.rb', line 77

def default_cmp_proc
  return Proc.new{|x,y| x <=> y}
end

#delete(key) ⇒ Object 



218
219
220
221
222
223
224
225
226
 
# File 'lib/hipe-simplebtree.rb', line 218

def delete key
  unless has_key? key
    ret = block_given? ? yield : nil
  else
    ret = super
    sort_keys!
  end
  ret
end

#delete_if ⇒ Object Also known as: reject! 



127
128
129
130
131
132
133
134
135
136
137
138
 
# File 'lib/hipe-simplebtree.rb', line 127

def delete_if
  return each unless block_given?      
  ks = []
  _enumerate(Proc.new{|k,v| ks << k if yield(k,v) }){|k| [k,self[k]]}
  ks.each { |k| hash_delete k }
  if ks.size > 0
    sort_keys!
    self
  else
    nil
  end
end

#dump ⇒ Object 



287
288
289
290
291
 
# File 'lib/hipe-simplebtree.rb', line 287

def dump
  TypeError.new(%{cannot dump #{self.class} with default proc}) if @default_proc
  TypeError.new(%{cannot dump #{self.class} with compare proc}) if @cmp_proc    
  Marshal.dump(self)
end

#each(&proc) ⇒ Object Also known as: each_pair 



107
108
109
 
# File 'lib/hipe-simplebtree.rb', line 107

def each &proc
  return _enumerate(proc){ |k| [k, self[k]] }
end

#each_key(&proc) ⇒ Object 



117
118
119
120
 
# File 'lib/hipe-simplebtree.rb', line 117

def each_key &proc
  return _enumerate(proc){ |k| k } if block_given?
  @sorted_keys.map{|k| [k] }.each
end

#each_value(&proc) ⇒ Object 



122
123
124
125
 
# File 'lib/hipe-simplebtree.rb', line 122

def each_value &proc
  return _enumerate(proc){|k| self[k]} if block_given?
  @sorted_keys.map{|k| [self[k]] }.each
end

#first ⇒ Object 



90
 
# File 'lib/hipe-simplebtree.rb', line 90

def first; _first_or_last(:first); end

#flatten ⇒ Object 



228
 
# File 'lib/hipe-simplebtree.rb', line 228

def flatten;    each.flatten;                 end

#get_cloned_key(key) ⇒ Object 



94
95
96
97
98
99
100
101
 
# File 'lib/hipe-simplebtree.rb', line 94

def get_cloned_key key
  @clones ||= {}
  unless @clones.has_key? key
    # not sure what the test is trying to accomplish here
    @clones[key] = key.instance_of?(String) ? key.clone.freeze : key
  end
  @clones[key]
end

#hash_delete ⇒ Object 



40
 
# File 'lib/hipe-simplebtree.rb', line 40

alias_method :hash_delete, :delete

#hash_inspect ⇒ Object 



43
 
# File 'lib/hipe-simplebtree.rb', line 43

alias_method :hash_inspect, :inspect

#hash_keys ⇒ Object 



41
 
# File 'lib/hipe-simplebtree.rb', line 41

alias_method :hash_keys, :keys

#hash_replace ⇒ Object 



42
 
# File 'lib/hipe-simplebtree.rb', line 42

alias_method :hash_replace, :replace

#hash_set ⇒ Object 



39
 
# File 'lib/hipe-simplebtree.rb', line 39

alias_method :hash_set, %s{[]=}

#inspect ⇒ Object 



182
183
184
185
186
187
188
189
190
191
192
 
# File 'lib/hipe-simplebtree.rb', line 182

def inspect
  if @inspecting
    %{#<#{self.class.name}: ...>}
  else
    @inspecting = true
    # /#<Hipe::SimpleBTree: (\{.*\}), default=(.*), cmp_proc=(.*)>/      
    ret = %[#<#{self.class.name}: #{hash_inspect}, default=#{default.inspect}, cmp_proc=#{cmp_proc.inspect}>]
    @inspecting = false
    ret
  end
end

#invert ⇒ Object 



234
 
# File 'lib/hipe-simplebtree.rb', line 234

def invert;     self.class[super];            end

#keys ⇒ Object 



236
 
# File 'lib/hipe-simplebtree.rb', line 236

def keys;       @sorted_keys.dup;             end

#last ⇒ Object 



92
 
# File 'lib/hipe-simplebtree.rb', line 92

def last; _first_or_last(:last); end

#lower_bound(key) ⇒ Object 



259
 
# File 'lib/hipe-simplebtree.rb', line 259

def lower_bound key;   _bound(:lower_bound_index,key)  end

#merge(x) ⇒ Object

not sure why super way wouldn’t work



244
245
246
247
248
249
250
251
 
# File 'lib/hipe-simplebtree.rb', line 244

def merge x; #not sure why super way wouldn't work
  clone = self.class[self]
  x.each do |x,y|
    clone.hash_set(x,y)
  end
  clone.sort_keys!
  clone
end

#pop ⇒ Object 



207
208
209
210
211
212
213
214
215
216
 
# File 'lib/hipe-simplebtree.rb', line 207

def pop
  if @sorted_keys.size == 0
    ret = default_proc ? default_proc.call(self, nil) : default
  else
    key = @sorted_keys.pop
    @tree = nil
    ret = [key, delete(key)]
  end
  return ret
end

#pretty_print(q) ⇒ Object 



158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
 
# File 'lib/hipe-simplebtree.rb', line 158

def pretty_print(q)
  mybuff = ''
  if @inspecting
    mybuff << %["#<#{self.class}: ...>"]
  else
    mybuff << %[#<#{self.class}: ]
    @inspecting = true;
    els = @sorted_keys.map do |k|  # @todo learn more about PP to clean this up
      PP.pp(k, s='');s.chop!; s << '=>'; PP.pp(self[k],x=''); s<<x.strip!;
      s
    end
    str = els.join(', ');     br  = " ";      
    if str.length > 79      
      str = els.join(",\n  ");  br  = "\n ";
    end
    br = "\n " if str.include? self.class.to_s # total hack to get it to pass the tests
    PP.pp(default,def_s='')
    PP.pp(cmp_proc,cmp_s='')
    mybuff << %({#{str}},#{br}default=#{def_s.chop},#{br}cmp_proc=#{cmp_s.chop}>)
    @inspecting = false
  end
  q.text(mybuff)
end

#readjust(*args, &proc2) ⇒ Object

Raises:

  • (ArgumentError) 


66
67
68
69
70
71
72
73
74
75
 
# File 'lib/hipe-simplebtree.rb', line 66

def readjust *args, &proc2
  size = args.size + (proc2 ? 1 : 0)
  raise ArgumentError.new("wrong number of arguments - #{size} for 1") if size > 1
  new_proc = (args.size > 0 && args[0].nil?) ? default_cmp_proc : (proc2 || args[0])
  my_keys = hash_keys
  # try the sort before doing any permanant change because it might throw type comparison error      
  my_keys.sort!(&new_proc) 
  @sorted_keys = my_keys
  @cmp_proc = new_proc
end

#reject(&proc) ⇒ Object 



152
153
154
155
156
 
# File 'lib/hipe-simplebtree.rb', line 152

def reject &proc
  return each unless block_given?
  guy = select{ |k,v| ! proc.call(k,v) }
  ( guy.size == self.size ) ? nil : guy
end

#replace(tree) ⇒ Object 



277
278
279
280
281
282
283
284
285
 
# File 'lib/hipe-simplebtree.rb', line 277

def replace tree
  unless tree.instance_of? self.class
    raise TypeError.new(%{wrong argument type #{tree.class} (expected #{self.class})}) 
  end
  hash_replace tree
  @cmp_proc = tree.cmp_proc
  @default  = tree.default
  sort_keys!
end

#reverse_each(&proc) ⇒ Object 



111
112
113
 
# File 'lib/hipe-simplebtree.rb', line 111

def reverse_each &proc
  return _enumerate(proc,@sorted_keys.reverse){ |k| [k, self[k]] }
end

#select(&proc) ⇒ Object 



142
143
144
145
146
147
148
149
150
 
# File 'lib/hipe-simplebtree.rb', line 142

def select &proc
  if block_given?
    eaches = []
    @sorted_keys.each { |k| eaches << [k,self[k]] if proc.call(k,self[k]) }
    Hipe::SimpleBTree[eaches]  #* we don't know what to do about default & default proc & sort # note 4
  else
    each
  end
end

#stats ⇒ Object 



257
 
# File 'lib/hipe-simplebtree.rb', line 257

def stats;             tree.stats;              end

#to_a ⇒ Object 



240
 
# File 'lib/hipe-simplebtree.rb', line 240

def to_a;       each.to_a;                    end

#to_rbtree ⇒ Object 



253
254
255
 
# File 'lib/hipe-simplebtree.rb', line 253

def to_rbtree
  self # self.class[self]
end

#to_s ⇒ Object 



242
 
# File 'lib/hipe-simplebtree.rb', line 242

def to_s;       to_a.to_s;                    end

#update(x) ⇒ Object 



232
 
# File 'lib/hipe-simplebtree.rb', line 232

def update x;   super x; sort_keys!;          end

#upper_bound(key) ⇒ Object 



261
 
# File 'lib/hipe-simplebtree.rb', line 261

def upper_bound key;   _bound(:upper_bound_index,key)  end

#values ⇒ Object 



238
 
# File 'lib/hipe-simplebtree.rb', line 238

def values;     @sorted_keys.map{|k|self[k]}; end