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



124
125
126
127
128
129
 
# File 'lib/critbit.rb', line 124

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.



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

def default
  @default
end

#default_proc ⇒ Object

Returns the value of attribute default_proc.



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

def default_proc
  @default_proc
end

#java_critbit ⇒ Object (readonly)

Returns the value of attribute java_critbit.



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

def java_critbit
  @java_critbit
end

#prefix ⇒ Object

Returns the value of attribute prefix.



40
41
42
 
# File 'lib/critbit.rb', line 40

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



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
96
97
 
# File 'lib/critbit.rb', line 59

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 



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

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



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

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



153
154
155
156
 
# File 'lib/critbit.rb', line 153

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]



166
167
168
 
# File 'lib/critbit.rb', line 166

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

#clear ⇒ Object

Removes all key-value pairs from critbit



172
173
174
 
# File 'lib/critbit.rb', line 172

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



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

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.



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

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.



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

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.



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

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.



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

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) 


279
280
281
 
# File 'lib/critbit.rb', line 279

def empty?
  @size == 0
end

#eql?(other) ⇒ Boolean

Returns:

  • (Boolean) 


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
315
316
 
# File 'lib/critbit.rb', line 284

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.



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

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



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

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) 


364
365
366
 
# File 'lib/critbit.rb', line 364

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) 


376
377
378
 
# File 'lib/critbit.rb', line 376

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.



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

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.



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

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.



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

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.



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

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



439
440
441
442
 
# File 'lib/critbit.rb', line 439

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

#max ⇒ Object 



546
547
548
 
# File 'lib/critbit.rb', line 546

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.



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

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.



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

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 



538
539
540
 
# File 'lib/critbit.rb', line 538

def min
  @java_critbit.min
end

#put_all(other_critbit) ⇒ Object

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



554
555
556
 
# File 'lib/critbit.rb', line 554

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.



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

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.



562
563
564
 
# File 'lib/critbit.rb', line 562

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

#size ⇒ Object Also known as: length 



513
514
515
 
# File 'lib/critbit.rb', line 513

def size
  @java_critbit.size()
end

#values(prefix = nil) ⇒ Object 



523
524
525
526
 
# File 'lib/critbit.rb', line 523

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