Class: Multimap

Inherits:
Object
  • Object
show all
Extended by:
Forwardable
Includes:
Enumerable
Defined in:
lib/multimap.rb

Overview

Multimap is a generalization of a map or associative array abstract data type in which more than one value may be associated with and returned for a given key.

Example

require 'multimap'
map = Multimap.new
map["a"] = 100
map["b"] = 200
map["a"] = 300
map["a"]                              # -> [100, 300]
map["b"]                              # -> [200]
map.keys                              # -> #<Multiset: {a, a, b}>

Direct Known Subclasses

NestedMultimap

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(default = []) ⇒ Multimap

call-seq:

Multimap.new           => multimap
Multimap.new(default)  => multimap

Returns a new, empty multimap.

map = Multimap.new(Set.new)
h["a"] = 100
h["b"] = 200
h["a"]           #=> [100].to_set
h["c"]           #=> [].to_set



75
76
77
 
# File 'lib/multimap.rb', line 75

def initialize(default = [])
  @hash = Hash.new(default)
end

Class Method Details

.[](*args) ⇒ Object

call-seq:

Multimap[ [key =>|, value]* ]   => multimap

Creates a new multimap populated with the given objects.

Multimap["a", 100, "b", 200]       #=> {"a"=>[100], "b"=>[200]}
Multimap["a" => 100, "b" => 200]   #=> {"a"=>[100], "b"=>[200]}



30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
# File 'lib/multimap.rb', line 30

def self.[](*args)
  default = []

  if args.size == 2 && args.last.is_a?(Hash)
    default = args.shift
  elsif !args.first.is_a?(Hash) && args.size % 2 == 1
    default = args.shift
  end

  if args.size == 1 && args.first.is_a?(Hash)
    args[0] = args.first.inject({}) { |hash, (key, value)|
      unless value.is_a?(default.class)
        value = (default.dup << value)
      end
      hash[key] = value
      hash
    }
  else
    index = 0
    args.map! { |value|
      unless index % 2 == 0 || value.is_a?(default.class)
        value = (default.dup << value)
      end
      index += 1
      value
    }
  end

  map = new
  map.instance_variable_set(:@hash, Hash[*args])
  map.default = default
  map
end

Instance Method Details

#==(other) ⇒ Object

:nodoc:



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

def ==(other) #:nodoc:
  case other
  when Multimap
    @hash == other._internal_hash
  else
    @hash == other
  end
end

#[](key) ⇒ Object

Retrieves the value object corresponding to the *keys object.



91
92
93
 
# File 'lib/multimap.rb', line 91

def [](key)
  @hash[key]
end

#containers ⇒ Object

call-seq:

map.containers    => array

Returns a new array populated with the containers from map. See also Multimap#keys and Multimap#values.

map = Multimap["a" => 100, "b" => [200, 300]]
map.containers   #=> [[100], [200, 300]]



507
508
509
510
511
 
# File 'lib/multimap.rb', line 507

def containers
  containers = []
  each_container { |container| containers << container }
  containers
end

#delete(key, value = nil) ⇒ Object

call-seq:

map.delete(key, value)  => value
map.delete(key)         => value

Deletes and returns a key-value pair from map. If only key is given, all the values matching that key will be deleted.

map = Multimap["a" => 100, "b" => [200, 300]]
map.delete("b", 300) #=> 300
map.delete("a")      #=> [100]



126
127
128
129
130
131
132
 
# File 'lib/multimap.rb', line 126

def delete(key, value = nil)
  if value
    @hash[key].delete(value)
  else
    @hash.delete(key)
  end
end

#delete_if ⇒ Object

call-seq:

map.delete_if {| key, value | block }  -> map

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

map = Multimap["a" => 100, "b" => [200, 300]]
map.delete_if {|key, value| value >= 300 }
  #=> Multimap["a" => 100, "b" => 200]



315
316
317
318
319
320
321
322
 
# File 'lib/multimap.rb', line 315

def delete_if
  each_association do |key, container|
    container.delete_if do |value|
      yield [key, value]
    end
  end
  self
end

#each ⇒ Object

call-seq:

map.each { |key, value| block } => map

Calls block for each key/value pair in map, passing the key and value to the block as a two-element array.

map = Multimap["a" => 100, "b" => [200, 300]]
map.each { |key, value| puts "#{key} is #{value}" }

produces:

a is 100
b is 200
b is 300



148
149
150
151
152
 
# File 'lib/multimap.rb', line 148

def each
  each_pair do |key, value|
    yield [key, value]
  end
end

#each_association(&block) ⇒ Object

call-seq:

map.each_association { |key, container| block } => map

Calls block once for each key/container in map, passing the key and container to the block as parameters.

map = Multimap["a" => 100, "b" => [200, 300]]
map.each_association { |key, container| puts "#{key} is #{container}" }

produces:

a is [100]
b is [200, 300]



167
168
169
 
# File 'lib/multimap.rb', line 167

def each_association(&block)
  @hash.each_pair(&block)
end

#each_container ⇒ Object

call-seq:

map.each_container { |container| block } => map

Calls block for each container in map, passing the container as a parameter.

map = Multimap["a" => 100, "b" => [200, 300]]
map.each_container { |container| puts container }

produces:

[100]
[200, 300]



184
185
186
187
188
 
# File 'lib/multimap.rb', line 184

def each_container
  each_association do |_, container|
    yield container
  end
end

#each_key ⇒ Object

call-seq:

map.each_key { |key| block } => map

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

map = Multimap["a" => 100, "b" => [200, 300]]
map.each_key { |key| puts key }

produces:

a
b
b



204
205
206
207
208
 
# File 'lib/multimap.rb', line 204

def each_key
  each_pair do |key, _|
    yield key
  end
end

#each_pair ⇒ Object

call-seq:

map.each_pair { |key_value_array| block } => map

Calls block for each key/value pair in map, passing the key and value as parameters.

map = Multimap["a" => 100, "b" => [200, 300]]
map.each_pair { |key, value| puts "#{key} is #{value}" }

produces:

a is 100
b is 200
b is 300



224
225
226
227
228
229
230
 
# File 'lib/multimap.rb', line 224

def each_pair
  each_association do |key, values|
    values.each do |value|
      yield key, value
    end
  end
end

#each_value ⇒ Object

call-seq:

map.each_value { |value| block } => map

Calls block for each key in map, passing the value as a parameter.

map = Multimap["a" => 100, "b" => [200, 300]]
map.each_value { |value| puts value }

produces:

100
200
300



246
247
248
249
250
 
# File 'lib/multimap.rb', line 246

def each_value
  each_pair do |_, value|
    yield value
  end
end

#eql?(other) ⇒ Boolean

:nodoc:

Returns:

  • (Boolean) 


261
262
263
264
265
266
267
268
 
# File 'lib/multimap.rb', line 261

def eql?(other) #:nodoc:
  case other
  when Multimap
    @hash.eql?(other._internal_hash)
  else
    @hash.eql?(other)
  end
end

#freeze ⇒ Object

:nodoc:



270
271
272
273
274
 
# File 'lib/multimap.rb', line 270

def freeze #:nodoc:
  each_container { |container| container.freeze }
  default.freeze
  super
end

#has_value?(value) ⇒ Boolean Also known as: value?

call-seq:

map.has_value?(value)    => true or false
map.value?(value)        => true or false

Returns true if the given value is present for any key in map.

map = Multimap["a" => 100, "b" => [200, 300]]
map.has_value?(300)   #=> true
map.has_value?(999)   #=> false

Returns:

  • (Boolean) 


286
287
288
 
# File 'lib/multimap.rb', line 286

def has_value?(value)
  values.include?(value)
end

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

Returns true if the given key is present in Multimap.

Returns:

  • (Boolean) 


398
399
400
 
# File 'lib/multimap.rb', line 398

def include?(key)
  keys.include?(key)
end

#index(value) ⇒ Object

call-seq:

map.index(value)    => key

Returns the key for a given value. If not found, returns nil.

map = Multimap["a" => 100, "b" => [200, 300]]
map.index(100)   #=> "a"
map.index(200)   #=> "b"
map.index(999)   #=> nil



301
302
303
 
# File 'lib/multimap.rb', line 301

def index(value)
  invert[value]
end

#initialize_copy(original) ⇒ Object

:nodoc:



79
80
81
82
83
84
 
# File 'lib/multimap.rb', line 79

def initialize_copy(original) #:nodoc:
  @hash = Hash.new(original.default.dup)
  original._internal_hash.each_pair do |key, container|
    @hash[key] = container.dup
  end
end

#invert ⇒ Object

call-seq:

map.invert => multimap

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

map = Multimap["n" => 100, "m" => 100, "d" => [200, 300]]
map.invert #=> Multimap[100 => ["n", "m"], 200 => "d", 300 => "d"]



377
378
379
380
381
 
# File 'lib/multimap.rb', line 377

def invert
  h = self.class.new(default.dup)
  each_pair { |key, value| h[value] = key }
  h
end

#keys ⇒ Object

call-seq:

map.keys    => multiset

Returns a new Multiset populated with the keys from this hash. See also Multimap#values and Multimap#containers.

map = Multimap["a" => 100, "b" => [200, 300], "c" => 400]
map.keys   #=> Multiset.new(["a", "b", "b", "c"])



391
392
393
394
395
 
# File 'lib/multimap.rb', line 391

def keys
  keys = Multiset.new
  each_key { |key| keys << key }
  keys
end

#marshal_dump ⇒ Object

:nodoc:



532
533
534
 
# File 'lib/multimap.rb', line 532

def marshal_dump #:nodoc:
  @hash
end

#marshal_load(hash) ⇒ Object

:nodoc:



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

def marshal_load(hash) #:nodoc:
  @hash = hash
end

#merge(other) ⇒ Object

call-seq:

map.merge(other_map) => multimap

Returns a new multimap containing the contents of other_map and the contents of map.

map1 = Multimap["a" => 100, "b" => 200]
map2 = Multimap["a" => 254, "c" => 300]
map2.merge(map2) #=> Multimap["a" => 100, "b" => [200, 254], "c" => 300]
map1             #=> Multimap["a" => 100, "b" => 200]



428
429
430
 
# File 'lib/multimap.rb', line 428

def merge(other)
  dup.update(other)
end

#reject(&block) ⇒ Object

call-seq:

map.reject {| key, value | block }  -> map

Same as Multimap#delete_if, but works on (and returns) a copy of the map. Equivalent to map.dup.delete_if.



331
332
333
 
# File 'lib/multimap.rb', line 331

def reject(&block)
  dup.delete_if(&block)
end

#reject!(&block) ⇒ Object

call-seq:

map.reject! {| key, value | block }  -> map or nil

Equivalent to Multimap#delete_if, but returns nil if no changes were made.



341
342
343
344
345
 
# File 'lib/multimap.rb', line 341

def reject!(&block)
  old_size = size
  delete_if(&block)
  old_size == size ? nil : self
end

#replace(other) ⇒ Object

call-seq:

map.replace(other_map) => map

Replaces the contents of map with the contents of other_map.

map = Multimap["a" => 100, "b" => 200]
map.replace({ "c" => 300, "d" => 400 })
#=> Multimap["c" => 300, "d" => 400]



356
357
358
359
360
361
362
363
364
365
366
367
 
# File 'lib/multimap.rb', line 356

def replace(other)
  case other
  when Array
    @hash.replace(self.class[self.default, *other])
  when Hash
    @hash.replace(self.class[self.default, other])
  when self.class
    @hash.replace(other)
  else
    raise ArgumentError
  end
end

#select ⇒ Object

call-seq:

map.select { |key, value| block }   => multimap

Returns a new Multimap consisting of the pairs for which the block returns true.

map = Multimap["a" => 100, "b" => 200, "c" => 300]
map.select { |k,v| k > "a" }  #=> Multimap["b" => 200, "c" => 300]
map.select { |k,v| v < 200 }  #=> Multimap["a" => 100]



465
466
467
468
469
470
 
# File 'lib/multimap.rb', line 465

def select
  inject(self.class.new) { |map, (key, value)|
    map[key] = value if yield([key, value])
    map
  }
end

#size ⇒ Object Also known as: length

call-seq:

map.length    =>  fixnum
map.size      =>  fixnum

Returns the number of key-value pairs in the map.

map = Multimap["a" => 100, "b" => [200, 300], "c" => 400]
map.length        #=> 4
map.delete("a")   #=> 100
map.length        #=> 3



413
414
415
 
# File 'lib/multimap.rb', line 413

def size
  values.size
end

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

call-seq:

map[key] = value        => value
map.store(key, value)   => value

Associates the value given by value with the key given by key. Unlike a regular hash, multiple can be assoicated with the same value.

map = Multimap["a" => 100, "b" => 200]
map["a"] = 9
map["c"] = 4
map   #=> {"a" => [100, 9], "b" => [200], "c" => [4]}



107
108
109
110
111
112
 
# File 'lib/multimap.rb', line 107

def store(key, value)
  update_container(key) do |container|
    container << value
    container
  end
end

#to_a ⇒ Object

call-seq:

map.to_a => array

Converts map to a nested array of [key, value] arrays.

map = Multimap["a" => 100, "b" => [200, 300], "c" => 400]
map.to_a   #=> [["a", 100], ["b", 200], ["b", 300], ["c", 400]]



480
481
482
483
484
485
486
 
# File 'lib/multimap.rb', line 480

def to_a
  ary = []
  each_pair do |key, value|
    ary << [key, value]
  end
  ary
end

#to_hash ⇒ Object

call-seq:

map.to_hash => hash

Converts map to a basic hash.

map = Multimap["a" => 100, "b" => [200, 300]]
map.to_hash   #=> { "a" => [100], "b" => [200, 300] }



495
496
497
 
# File 'lib/multimap.rb', line 495

def to_hash
  @hash.dup
end

#to_yaml(opts = {}) ⇒ Object

:nodoc:



540
541
542
543
544
545
546
547
548
549
 
# File 'lib/multimap.rb', line 540

def to_yaml(opts = {}) #:nodoc:
  YAML::quick_emit(self, opts) do |out|
    out.map(taguri, to_yaml_style) do |map|
      @hash.each do |k, v|
        map.add(k, v)
      end
      map.add('__default__', @hash.default)
    end
  end
end

#update(other) ⇒ Object Also known as: merge!

call-seq:

map.merge!(other_map)    => multimap
map.update(other_map)    => multimap

Adds each pair from other_map to map.

map1 = Multimap["a" => 100, "b" => 200]
map2 = Multimap["b" => 254, "c" => 300]

map1.merge!(map2)
#=> Multimap["a" => 100, "b" => [200, 254], "c" => 300]



443
444
445
446
447
448
449
450
451
452
453
 
# File 'lib/multimap.rb', line 443

def update(other)
  case other
  when self.class
    other.each_pair { |key, value| store(key, value) }
  when Hash
    update(self.class[self.default, other])
  else
    raise ArgumentError
  end
  self
end

#values ⇒ Object

call-seq:

map.values    => array

Returns a new array populated with the values from map. See also Multimap#keys and Multimap#containers.

map = Multimap["a" => 100, "b" => [200, 300]]
map.values   #=> [100, 200, 300]



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

def values
  values = []
  each_value { |value| values << value }
  values
end

#values_at(*keys) ⇒ Object

Return an array containing the values associated with the given keys.



528
529
530
 
# File 'lib/multimap.rb', line 528

def values_at(*keys)
  @hash.values_at(*keys)
end

#yaml_initialize(tag, val) ⇒ Object

:nodoc:



551
552
553
554
555
556
 
# File 'lib/multimap.rb', line 551

def yaml_initialize(tag, val) #:nodoc:
  default = val.delete('__default__')
  @hash = val
  @hash.default = default
  self
end