Class: Critbit

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/critbit.rb

Defined Under Namespace

Classes: Cursor, DeleteCursor, EachCursor, EachKeyCursor, EachValueCursor, ListCursor

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(default = nil, &block) ⇒ Object

new → new_critbit

new(obj) → new_critbit

new {|critbit, key| block } → new_critbit

Returns a new, empty critbit. If this critbit is subsequently accessed by a key that doesn’t correspond to a critbit entry, the value returned depends on the style of new used to create the critbit. In the first form, the access returns nil. If obj is specified, this single object will be used for all default values. If a block is specified, it will be called with the critbit object and the key, and should return the default value. It is the block’s responsibility to store the value in the critbit if required.

Parameters:

  • default (Default) (defaults to: nil) —

    the default return value if the key is not found

  • block (Block) —

    the default block to be executed if key is not found



122
123
124
125
126
127
 
# File 'lib/critbit.rb', line 122

def initialize(default = nil, &block)
  @default = default
  @default_proc = block
  @prefix = nil
  @java_critbit =  MCritBitTree.new(StringKeyAnalyzer.new)
end

Instance Attribute Details

#default ⇒ Object

Returns the value of attribute default.



36
37
38
 
# File 'lib/critbit.rb', line 36

def default
  @default
end

#default_proc ⇒ Object

Returns the value of attribute default_proc.



37
38
39
 
# File 'lib/critbit.rb', line 37

def default_proc
  @default_proc
end

#java_critbit ⇒ Object (readonly)

Returns the value of attribute java_critbit.



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

def java_critbit
  @java_critbit
end

#prefix ⇒ Object

Returns the value of attribute prefix.



38
39
40
 
# File 'lib/critbit.rb', line 38

def prefix
  @prefix
end

Class Method Details

.[](*args) ⇒ Object

Critbit[ key, value, … ] → new_hash

Critbit[ [ [key, value], … ] ] → new_hash

Critbit[ object ] → new_hash

Creates a new critbit populated with the given objects.

Similar to the literal hash { key => value, … }. In the first form, keys and values occur in pairs, so there must be an even number of arguments.

The second and third form take a single argument which is either an array of key-value pairs or an object convertible to a hash.

Parameters:

  • args (Args) —

    list of arguments in any of the above formats

Returns:

  • a new Critbit



57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
 
# File 'lib/critbit.rb', line 57

def self.[](*args)

  crit = Critbit.new
  
  if args.size == 1
    
    if ((args[0].is_a? Hash) || (args[0].is_a? Critbit))
      args[0].each do |k, v|
        crit[k] = v
      end
    elsif (args[0].is_a? Array)
      args[0].each do |key_pair|
        if ((key_pair.is_a? Array) && (key_pair.size == 2))
          crit[key_pair[0]] = key_pair[1]
        else
          raise "Illegal argument for Critbit #{key_pair}"
        end
      end
    else
      raise "illegal argument for Critbit"
    end
    
    return crit
    
  end
  
  if (args.size % 2 != 0)
    raise "odd number of arguments for Critbit"
  else
    i = 0
    begin
      crit[args[i]] = args[i+1]
      i += 2
    end while i < args.size
  end

  return crit
  
end

.try_convert(arg) ⇒ Object 



101
102
103
 
# File 'lib/critbit.rb', line 101

def self.try_convert(arg)
  
end

Instance Method Details

#[](key) ⇒ Object

Element Reference—Retrieves the value object corresponding to the key object. If not found, returns the default value (see Hash::new for details). the default_proc

Parameters:

  • key (key) —

    the key to be retrieved

Returns:

  • the value reference by this key or the default value or result of executing



135
136
137
138
139
140
141
142
143
144
 
# File 'lib/critbit.rb', line 135

def[](key)
  
  val = retrieve(key)
  if (val == nil)
    val = @default
    val = @default_proc.call(self, key, val) if @default_proc
  end
  val
  
end

#[]=(key, val) ⇒ Object Also known as: store

Associates the value given by value with the key given by key.

Parameters:

  • key (Key) —

    the key element

  • val (Value) —

    the value associated with the key

Returns:

  • the value associated with the key



151
152
153
154
 
# File 'lib/critbit.rb', line 151

def[]=(key, val)
  key = key.to_s if key.is_a? Symbol
  @java_critbit.put(key, val)
end

#assoc(key) ⇒ Object

Searches through the critbit comparing obj with the key using ==. Returns the key-value pair (two elements array) or nil if no match is found. See Array#assoc.

Parameters:

  • key (Key) —

    the key to search for

Returns:

  • Array with two elements [key, value]



164
165
166
 
# File 'lib/critbit.rb', line 164

def assoc(key)
  [key, retrieve(key)]
end

#clear ⇒ Object

Removes all key-value pairs from critbit



170
171
172
 
# File 'lib/critbit.rb', line 170

def clear
  @java_critbit.clear
end

#delete(key) ⇒ Object

Deletes the key-value pair and returns the value from critbit whose key is equal to key. If the key is not found, returns the default value. If the optional code block is given and the key is not found, pass in the key and return the result of block. to key

Parameters:

  • key (Key)

Returns:

  • the value, the default value, or the result of applying the default block



196
197
198
199
200
201
202
203
204
205
206
207
208
 
# File 'lib/critbit.rb', line 196

def delete(key)

  val = @java_critbit.remove(key)
  # key not found
  if (val == nil)
    if block_given?
      yield key
    end
    @default
  end
  val
  
end

#delete_if(prefix = nil, &block) ⇒ Object Also known as: reject!

Deletes every key-value pair from hsh for which block evaluates to true.

If no block is given, an enumerator is returned instead.



214
215
216
217
218
219
220
221
222
223
 
# File 'lib/critbit.rb', line 214

def delete_if(prefix = nil, &block)
  
  if block_given?
    cursor = Critbit::DeleteCursor.new(self, true, &block)
    _get(cursor, prefix)
  else
    to_enum(:each, prefix)
  end
  
end

#each(prefix = nil, &block) ⇒ Object Also known as: each_pair

Calls block once for each key in critbit, passing the key-value pair as parameters.

If no block is given, an enumerator is returned instead.



231
232
233
234
235
236
237
238
239
240
 
# File 'lib/critbit.rb', line 231

def each(prefix = nil, &block)

  if block_given?
    cursor = Critbit::EachCursor.new(&block)
    _get(cursor, prefix)
  else
    to_enum(:each, prefix)
  end
  
end

#each_key(prefix = nil, &block) ⇒ Object

Calls block once for each key in critbit, passing the key as a parameter.

If no block is given, an enumerator is returned instead.



249
250
251
252
253
254
255
256
257
258
 
# File 'lib/critbit.rb', line 249

def each_key(prefix = nil, &block)
  
  if block_given?
    cursor = Critbit::EachKeyCursor.new(&block)
    _get(cursor, prefix)
  else
    to_enum(:each, prefix)
  end

end

#each_value(prefix = nil, &block) ⇒ Object

Calls block once for each value in critbit, passing the value as a parameter.

If no block is given, an enumerator is returned instead.



264
265
266
267
268
269
270
271
272
273
 
# File 'lib/critbit.rb', line 264

def each_value(prefix = nil, &block)
  
  if block_given?
    cursor = Critbit::EachValueCursor.new(&block)
    _get(cursor, prefix)
  else
    to_enum(:each, prefix)
  end

end

#empty? ⇒ Boolean

Returns true if critbit contains no key-value pairs.

Returns:

  • (Boolean) 


277
278
279
 
# File 'lib/critbit.rb', line 277

def empty?
  @size == 0
end

#eql?(other) ⇒ Boolean

Returns:

  • (Boolean) 


282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
 
# File 'lib/critbit.rb', line 282

def eql?(other)

  cr1 = each
  cr2 = other.each
  
  begin
    p1 = cr1.next
    p2 = cr2.next
    if ((p1[0] != p2[0]) || (p1[1] != p2[1]))
      return false
    end
  rescue StopIteration
    break
  end while true

  i = 0
  begin
    cr1.next
  rescue StopIteration
    i += 1
  end

  begin
    cr2.next
  rescue StopIteration
    i += 1
  end

  return false if i != 2
  
  return true
  
end

#fetch(key, default = nil, &block) ⇒ Object

Returns a value from the critbit for the given key. If the key can’t be found, there are several options: With no other arguments, it will raise an KeyError exception; if default is given, then that will be returned; if the optional code block is specified, then that will be run and its result returned.



321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
 
# File 'lib/critbit.rb', line 321

def fetch(key, default = nil, &block)
  
  key = key.to_s if key.is_a? Symbol
  res = @java_critbit.get(key)

  if (res == nil)
    if (default != nil)
      return default
    elsif (block_given?)
      block.call(key)
    else
      raise KeyError, "key '#{key}' not found"
    end
  end
  res
  
end

#flatten(level = nil) ⇒ Object

Returns a new array that is a one-dimensional flattening of this critbit. That is, for every key or value that is an array, extract its elements into the new array. The optional level argument determines the level of recursion to flatten if the value is a hash. If value is an Array it will call array.flatten



344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
 
# File 'lib/critbit.rb', line 344

def flatten(level = nil)

  res = Array.new
  each do |key, value|
    res << key
    case value
    when (Array || Hash || Critbit)
      (level)? res.concat(value.flatten(level)) : res.concat(value.flatten)
    else
      (value.respond_to?(:flatten))? res << value.flatten : res << value
    end
  end
  res
  
end

#has_key?(key) ⇒ Boolean Also known as: include?, member?, key?

Returns true if the given key is present in critbit

Returns:

  • (Boolean) 


362
363
364
 
# File 'lib/critbit.rb', line 362

def has_key?(key)
  @java_critbit.containsKey(key)
end

#has_value?(val) ⇒ Boolean

Returns true if the given value is present for some key in critbit.

Returns:

  • (Boolean) 


374
375
376
 
# File 'lib/critbit.rb', line 374

def has_value?(val)
  @java_critbit.containsValue(val)
end

#inspect ⇒ Object Also known as: to_s

Return the contents of this critbit as a string.



380
381
382
383
384
385
386
387
388
389
 
# File 'lib/critbit.rb', line 380

def inspect
  
  res = "{"
  each do |key, value|
    res << "\"#{key}\"=>#{value},"
  end
  res[-1] = "}"
  return res
  
end

#invert ⇒ Object

Returns a new critbit created by using critbit’s values as keys, and the keys as values.



398
399
400
401
402
403
404
405
406
 
# File 'lib/critbit.rb', line 398

def invert
  
  crit = Critbit.new
  each do |key, value|
    crit[value.to_s] = key
  end
  crit
  
end

#keep_if(prefix = nil, &block) ⇒ Object Also known as: select!

Deletes every key-value pair from critbit for which block evaluates to false.



410
411
412
413
414
415
416
417
418
419
 
# File 'lib/critbit.rb', line 410

def keep_if(prefix = nil, &block)

  if block_given?
    cursor = Critbit::DeleteCursor.new(self, false, &block)
    _get(cursor, prefix)
  else
    to_enum(:each, prefix)
  end
  
end

#key(val) ⇒ Object

Returns the key of an occurrence of a given value. If the value is not found, returns nil.



426
427
428
429
430
431
432
433
 
# File 'lib/critbit.rb', line 426

def key(val)
  
  each do |key, value|
    return key if (value == val)
  end
  return nil
  
end

#keys(prefix = nil) ⇒ Object

Returns a new array populated with the keys from this critbit



437
438
439
440
 
# File 'lib/critbit.rb', line 437

def keys(prefix = nil)
  cursor = Critbit::ListCursor.new(:key)
  _get(cursor, prefix).list
end

#max ⇒ Object 



544
545
546
 
# File 'lib/critbit.rb', line 544

def max
  @java_critbit.max
end

#merge(other_critbit, &block) ⇒ Object Also known as: update

Returns a new critbit containing the contents of other_critbit and the contents of critbit. If no block is specified, the value for entries with duplicate keys will be that of other_critbit. Otherwise the value for each duplicate key is determined by calling the block with the key, its value in critbit and its value in other_critbit.



447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
 
# File 'lib/critbit.rb', line 447

def merge(other_critbit, &block)

  crit = Critbit[self]
  if (block_given?)
    other_critbit.each do |key, value|
      value = block.call(key, self[key], value) if has_key?(key)
      crit[key] = value
    end
  else
    other_critbit.each do |key, value|
      crit[key] = value
    end
  end
  crit
    
end

#merge!(other_critbit, &block) ⇒ Object

Returns a new critbit containing the contents of other_critbit and the contents of critbit. If no block is specified, the value for entries with duplicate keys will be that of other_critbit. Otherwise the value for each duplicate key is determined by calling the block with the key, its value in critbit and its value in other_critbit.



471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
 
# File 'lib/critbit.rb', line 471

def merge!(other_critbit, &block)

  if (block_given?)
    other_critbit.each do |key, value|
      value = block.call(key, self[key], value) if has_key?(key)
      self[key] = value
    end
  else
    other_critbit.each do |key, value|
      self[key] = value
    end
  end
  self
    
end

#min ⇒ Object 



536
537
538
 
# File 'lib/critbit.rb', line 536

def min
  @java_critbit.min
end

#put_all(other_critbit) ⇒ Object

Merges the two critbits. Should be significantly faster than method merge.



552
553
554
 
# File 'lib/critbit.rb', line 552

def put_all(other_critbit)
  @java_critbit.putAll(other_critbit.java_critbit)
end

#rassoc(obj) ⇒ Object

Searches through the critbit comparing obj with the value using ==. Returns the first key-value pair (two-element array) that matches. See also Array#rassoc.



498
499
500
501
502
503
504
505
 
# File 'lib/critbit.rb', line 498

def rassoc(obj)

  each do |key, value|
    return [key, value] if obj == value
  end
  nil
  
end

#remove(key) ⇒ Object

Removes the key value pair from the critbit. If no key is found, nil is returned.



560
561
562
 
# File 'lib/critbit.rb', line 560

def remove(key)
  @java_critbit.remove(key)
end

#size ⇒ Object Also known as: length 



511
512
513
 
# File 'lib/critbit.rb', line 511

def size
  @java_critbit.size()
end

#values(prefix = nil) ⇒ Object 



521
522
523
524
 
# File 'lib/critbit.rb', line 521

def values(prefix = nil)
  cursor = Critbit::ListCursor.new(:value)
  _get(cursor, prefix).list
end