Class: Bijection

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

Overview

Bijection is a container similar to a Hash with unique values. http://en.wikipedia.org/wiki/Bijection

Bijection associates each non-nil unique x in a set X, with a non-nil unique y in a set Y.

Please send (welcome) feedback and bug reports to my github.

Examples:

b = Bijection.new
b.add 5, 7 # associates 5 in X with 7 in Y
b.size
 => 1
b.add 5, 2 # raises, 5 already in X
b.add "foo", 7 # raises, 7 already in Y
b.add "bar", 5 # OK; 5 was not yet in Y
b.size
 => 2
d = b.domain # d == [5, "bar"]
r = b.range  # r == [7, 5] # i.e., not the "same" 5 in domain
b.each_x { |x| puts x }
 => 5
 => "bar"
b.each_y { |y| puts y }
 => 7
 => 5 # i.e., not the "same" 5 that's in X
b.each_pair { |x,y| .. }
x = b.get_x 7 # x == 5
y = b.get_y 5 # y == 7
is_nil = b.get_x "returns nil if not found" # is_nil == nil
b.inverse! # X and Y are now swapped; all as above with x and y swapped

Constant Summary collapse

VERSION = 
"1.0.0"

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Bijection

Returns a new instance of Bijection.



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

def initialize
  @X = {} # @X[x] -> y
  @Y = {} # @Y[y] -> x
end

Instance Method Details

#add(x, y) ⇒ self

Note:

x must be unique in X; y must be unique in Y

add (x,y) to the bijection set (X,Y)

Parameters:

  • x —

    the non-nil object associated with y

  • y —

    the non-nil object associated with x

Returns:

  • (self) 


51
52
53
54
55
56
57
58
59
 
# File 'lib/bijection.rb', line 51

def add( x, y )
  raise "Bijection: x may not be nil" if x == nil
  raise "Bijection: y may not be nil" if y == nil
  raise "Bijection: #{x.to_s} already present in domain set X" if @X.key? x
  raise "Bijection: #{y.to_s} already present in range set Y" if @Y.key? y
  @X[x] = y
  @Y[y] = x
  self
end

#delete_by_x(x) ⇒ Object

given x, delete (x,y) and return y

Examples:

b = Bijection.new
x = 2 ; y = 3
b.add x, y
y = nil
while true do y = b.delete_by_x x ; b.add x, y end

Parameters:

  • y —

    in domain set Y

Returns:

  • the x associated with y, or nil if y not in range Y



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

def delete_by_x( x )
  y = @X[x]
  @X.delete x
  @Y.delete y
  y
end

#delete_by_y(y) ⇒ Object

given y, delete (x,y) and return x see example #delete_by_x

Parameters:

  • x —

    in domain set X

Returns:

  • the y associated with x, or nil if x not in domain X



137
138
139
140
141
142
 
# File 'lib/bijection.rb', line 137

def delete_by_y( y )
  x = @Y[y]
  @Y.delete y
  @X.delete x
  x
end

#domain ⇒ Array

get the domain set X as an Array

Returns:

  • (Array) 


63
64
65
 
# File 'lib/bijection.rb', line 63

def domain
  @X.keys
end

#each_pair {|x, y| ... } ⇒ nil

Yields:

  • (x, y) —

    each (x,y) in sets X and Y

Returns:

  • (nil) 


112
113
114
115
 
# File 'lib/bijection.rb', line 112

def each_pair
  @X.each_pair { |x,y| yield x,y } if block_given?
  nil
end

#each_x {|x| ... } ⇒ nil

Yields:

  • (x) —

    each x in domain set X

Returns:

  • (nil) 


98
99
100
101
 
# File 'lib/bijection.rb', line 98

def each_x
  @X.each_key { |x| yield x } if block_given?
  nil
end

#each_y {|y| ... } ⇒ nil

Yields:

  • (y) —

    each y in range set Y

Returns:

  • (nil) 


105
106
107
108
 
# File 'lib/bijection.rb', line 105

def each_y
  @Y.each_key { |y| yield y } if block_given?
  nil
end

#get_x(y) ⇒ Object

get the x associated with y

Parameters:

  • y —

    in domain set Y

Returns:

  • the x associated with y, or nil if y not in range Y



85
86
87
 
# File 'lib/bijection.rb', line 85

def get_x( y )
  @Y[y]
end

#get_y(x) ⇒ Object

get the y associated with x

Parameters:

  • x —

    in domain set X

Returns:

  • the y associated with x, or nil if x not in domain X



92
93
94
 
# File 'lib/bijection.rb', line 92

def get_y( x )
  @X[x]
end

#inverse! ⇒ nil

swap domain X and range Y of this

Returns:

  • (nil) 


75
76
77
78
79
80
 
# File 'lib/bijection.rb', line 75

def inverse!
  temp = @X
  @X = @Y
  @Y = temp
  nil
end

#range ⇒ Array

get the range set Y as an Array

Returns:

  • (Array) 


69
70
71
 
# File 'lib/bijection.rb', line 69

def range
  @Y.keys
end

#size ⇒ Fixnum

returns the number of pairs in the bijection

Returns:

  • (Fixnum) 


42
43
44
 
# File 'lib/bijection.rb', line 42

def size
  @X.size
end