Class: FDS::UnorderedSet

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

Instance Method Summary collapse

Constructor Details

#initialize ⇒ UnorderedSet

Returns a new instance of UnorderedSet.



2
3
4
5
6
7
8
 
# File 'lib/fds/unordered_set.rb', line 2

def initialize
  @index = 0
  @data = Hash.new do |h, e|
    h[e] = @index
    @index += 1
  end
end

Instance Method Details

#&(other) ⇒ Object Also known as: intersection 



64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
 
# File 'lib/fds/unordered_set.rb', line 64

def &(other)
  if self.size < other.size
    result = self.dup
    bigger_set = other
  else
    result = other.dup
    bigger_set = self
  end

  result.keep_if do |e|
    bigger_set.include?(e)
  end

  result
end

#add(e) ⇒ Object Also known as: << 



10
11
12
13
 
# File 'lib/fds/unordered_set.rb', line 10

def add(e)
  @data[e]
  self
end

#delete(e) ⇒ Object 



21
22
23
24
 
# File 'lib/fds/unordered_set.rb', line 21

def delete(e)
  @data.delete(e)
  self
end

#delete_if ⇒ Object 



38
39
40
41
 
# File 'lib/fds/unordered_set.rb', line 38

def delete_if
  @data.delete_if { |k, _| yield k }
  self
end

#each ⇒ Object 



30
31
32
 
# File 'lib/fds/unordered_set.rb', line 30

def each
  @data.each_key(&proc)
end

#find_index(e) ⇒ Object 



15
16
17
18
19
 
# File 'lib/fds/unordered_set.rb', line 15

def find_index(e)
  # @data.has_key? is needed otherwise @data will create a new element,
  # see @data definition in #initialize.
  @data[e] if @data.has_key?(e)
end

#first ⇒ Object 



80
81
82
83
 
# File 'lib/fds/unordered_set.rb', line 80

def first
  @data.each_key { |k| return k }
  nil
end

#include?(e) ⇒ Boolean

Returns:

  • (Boolean) 


34
35
36
 
# File 'lib/fds/unordered_set.rb', line 34

def include?(e)
  find_index(e) != nil
end

#keep_if ⇒ Object 



43
44
45
46
 
# File 'lib/fds/unordered_set.rb', line 43

def keep_if
  @data.keep_if { |k, _| yield k }
  self
end

#last ⇒ Object 



85
86
87
88
89
90
91
 
# File 'lib/fds/unordered_set.rb', line 85

def last
  # All keys are read through, but no intermediate array is created as
  # whereas "keys.last" accumulates all keys for nothing.
  # We can't use @data.each_key.last, because there's no Enumerable#last. :/
  @data.reverse_each { |k, _| return k }
  nil
end

#size ⇒ Object 



26
27
28
 
# File 'lib/fds/unordered_set.rb', line 26

def size
  @data.size
end

#to_a ⇒ Object 



93
94
95
 
# File 'lib/fds/unordered_set.rb', line 93

def to_a
  @data.keys
end

#to_s ⇒ Object 



97
98
99
 
# File 'lib/fds/unordered_set.rb', line 97

def to_s
  to_a.to_s
end

#|(other) ⇒ Object Also known as: union 



48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
# File 'lib/fds/unordered_set.rb', line 48

def |(other)
  if self.size > other.size
    result = self.dup
    smaller_set = other
  else
    result = other.dup
    smaller_set = self
  end

  smaller_set.each do |e|
    result << e
  end

  result
end