class Percolate::Facet::TagFacet::TagPoset
A data structure representing the partial order induced on collections of tags.
Attributes
Public Class Methods
The constructor.
@param tags [Array] the tags. @param value [Object] the associated value. @param supersets [Array] the {TagPoset}s that contain tag supersets.
# File lib/percolate/facet/tag_facet.rb, line 66 def initialize(tags = [], value = nil, supersets = []) @tags = tags @value = value @supersets = supersets end
Public Instance Methods
Inserts the given collection of tags and its associated value into the partial order.
@param tags [Array] the tags. @param value [Object] the associated value. @param visited [Set] the visited {TagPoset}s so far, memoized by their tags.
# File lib/percolate/facet/tag_facet.rb, line 77 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
Calculates the best matches for the given collection of tags.
@param tags [Array] the tags. @param visited [Set] the visited {TagPoset}s so far, memoized by their tags.
@return [Array] the values associated with best matches.
# File lib/percolate/facet/tag_facet.rb, line 165 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
Merges the given {TagPoset} with this one.
@param other [TagPoset] the other {TagPoset}.
@return [TagPoset] the merged result.
# File lib/percolate/facet/tag_facet.rb, line 191 def merge(other) TagPoset.new.merge!(self).merge!(other) end
Mutatively merges the given {TagPoset} with this one.
@param other [TagPoset] the other {TagPoset}.
@return [TagPoset] `self`.
# File lib/percolate/facet/tag_facet.rb, line 200 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
Finds transitive supersets that contain the given collection of tags.
@param remainder [Array] the remaining tags to look for. @param visited [Set] the visited {TagPoset}s so far, memoized by their tags.
@return [Array] the transitive supersets.
# File lib/percolate/facet/tag_facet.rb, line 129 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