Class: Percolate::Facet::TagFacet::TagPoset

Inherits:
Object
  • Object
show all
Defined in:
lib/percolate/facet/tag_facet.rb

Overview

A data structure representing the partial order induced on collections of tags.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(tags = [], value = nil, supersets = []) ⇒ TagPoset

The constructor.

Parameters:

  • tags (Array) (defaults to: []) —

    the tags.

  • value (Object) (defaults to: nil) —

    the associated value.

  • supersets (Array) (defaults to: []) —

    the Percolate::Facet::TagFacet::TagPosets that contain tag supersets.



67
68
69
70
71
 
# File 'lib/percolate/facet/tag_facet.rb', line 67

def initialize(tags = [], value = nil, supersets = [])
  @tags = tags
  @value = value
  @supersets = supersets
end

Instance Attribute Details

#supersets ⇒ Object (readonly)

Returns the value of attribute supersets.



60
61
62
 
# File 'lib/percolate/facet/tag_facet.rb', line 60

def supersets
  @supersets
end

#tags ⇒ Object (readonly)

Returns the value of attribute tags.



60
61
62
 
# File 'lib/percolate/facet/tag_facet.rb', line 60

def tags
  @tags
end

#value ⇒ Object (readonly)

Returns the value of attribute value.



60
61
62
 
# File 'lib/percolate/facet/tag_facet.rb', line 60

def value
  @value
end

Instance Method Details

#insert(tags, value, visited = Set.new) ⇒ Object

Inserts the given collection of tags and its associated value into the partial order.

Parameters:

  • tags (Array) —

    the tags.

  • value (Object) —

    the associated value.

  • visited (Set) (defaults to: Set.new) —

    the visited Percolate::Facet::TagFacet::TagPosets so far, memoized by their tags.



78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
 
# File 'lib/percolate/facet/tag_facet.rb', line 78

def insert(tags, value, visited = Set.new)
  tags = tags.sort

  # We got an exact match. Override the value and return.
  if @tags == tags
    @value = value

    return value
  end

  n_supersets = 0
  subset_indices = []

  @supersets.each_with_index do |superset, i|
    if superset.tags - tags == []
      superset.insert(tags, value, visited) if !visited.add?(superset.tags).nil?
      n_supersets = n_supersets + 1
    elsif tags - superset.tags == []
      subset_indices.push(i)
    end
  end

  # We visited a superset; there's no more work to be done in this frame.
  if n_supersets > 0
    return value
  end

  if !subset_indices.empty?
    # The tags are a subset of at least one superset; insert them in between this poset and the superset(s).
    tp = TagPoset.new(tags, value, subset_indices.map { |i| @supersets[i] })

    subset_indices.each { |i| @supersets[i] = nil }
    @supersets = @supersets.select { |item| !item.nil? }.to_a

  else
    # The tags are not a subset of any superset; insert them separately.
    tp = TagPoset.new(tags, value, transitives(tags))
  end

  # Insert the new poset with binary search for stability.
  insertion_index = (0...@supersets.size).bsearch { |i| (@supersets[i].tags <=> tags) >= 0 } || @supersets.size
  @supersets.insert(insertion_index, tp)

  value
end

#matches(tags, visited = Set.new) ⇒ Array

Calculates the best matches for the given collection of tags.

Parameters:

Returns:

  • (Array) —

    the values associated with best matches.



166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
 
# File 'lib/percolate/facet/tag_facet.rb', line 166

def matches(tags, visited = Set.new)
  tags = tags.sort

  matches = []
  n_supersets = 0

  @supersets.each do |superset|
    if superset.tags - tags == []
      matches.concat(superset.matches(tags, visited)) if !visited.add?(superset.tags).nil?
      n_supersets = n_supersets + 1
    end
  end

  # We didn't visit a superset; push on the associated value as a best match.
  if n_supersets == 0 && !@value.nil?
    matches.push(@value)
  end

  matches
end

#merge(other) ⇒ TagPoset

Merges the given Percolate::Facet::TagFacet::TagPoset with this one.

Parameters:

Returns:



192
193
194
 
# File 'lib/percolate/facet/tag_facet.rb', line 192

def merge(other)
  TagPoset.new.merge!(self).merge!(other)
end

#merge!(other, visited = Set.new) ⇒ TagPoset

Mutatively merges the given Percolate::Facet::TagFacet::TagPoset with this one.

Parameters:

Returns:



201
202
203
204
205
206
207
208
209
 
# File 'lib/percolate/facet/tag_facet.rb', line 201

def merge!(other, visited = Set.new)
  insert(other.tags, other.value)

  other.supersets.each do |superset|
    merge!(superset, visited) if !visited.add?(superset.tags).nil?
  end

  self
end

#transitives(remainder, visited = Set.new) ⇒ Array

Finds transitive supersets that contain the given collection of tags.

Parameters:

Returns:

  • (Array) —

    the transitive supersets.



130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
 
# File 'lib/percolate/facet/tag_facet.rb', line 130

def transitives(remainder, visited = Set.new)
  transitives = []

  @supersets.each do |superset|
    r_remainder = remainder - superset.tags

    if r_remainder != []
      r_transitives = superset.transitives(r_remainder, visited)

      r_transitives = r_transitives.select do |r_superset|
        transitives.select do |superset|
          superset.tags - r_superset.tags == []
        end.empty?
      end.to_a

      transitives = transitives.select do |superset|
        r_transitives.select do |r_superset|
          r_superset.tags - superset.tags == []
        end.empty?
      end.to_a

      transitives.concat(r_transitives)
    else
      transitives.push(superset)
    end if !visited.add?(superset.tags).nil?
  end

  transitives
end