gistfile1.rb

module Potluck
  module EventCollapser
    extend self
    
    def for_display(unsorted_events)
      latest_events = merge_sort(unsorted_events, :limit => Event::MAX_EVENTS)
      collapse(latest_events)
    end
    
    def merge_sort(unsorted_events, options)
      n = options[:limit] || 10
      columns = unsorted_events.inject([]){|m, e| m << MergeColumn.new(e) unless e.blank?; m }
      
      result = []
      while !columns.all?(&:empty?) && n > result.size
        columns.sort!
        result << columns.first.pop
      end
      
      result
    end
    
    def collapse(events)
      prev_event = events.shift
      return [] unless prev_event
      
      result = [prev_event]
      group_key_intersection = Array(prev_event["group_key"]).to_set
      
      events.each do |event|
        group_key_intersection = group_key_intersection & Array(event["group_key"])
        
        if !group_key_intersection.empty?
          prev_event["collapsed_events"] ||= []
          prev_event["collapsed_events"].push(event['_id'].to_s)
        else
          result.push(event)
          prev_event = event
          group_key_intersection = Array(event["group_key"]).to_set
        end
      end
      
      result
    end
    
    class MergeColumn
      def initialize(array)
        @array = array
        @index = 0
      end

      def value
        @array[@index]
      end

      def empty?
        @index > @array.size - 1
      end

      def pop
        @index += 1
        @array[@index - 1]
      end

      def <=>(o)
        self.value <=> o.value
      end
    end
  end
end