electedOrderedList.rb

class ElectedOrderedListItem
    # subitem:  the item itself, the payload
    # lowerItems: A list of items that were seen before this item
    # seen: How often it was seen before
    # rating: rating to store if there is no other way
    attr_accessor :payload, :rating, :seen, :lowerItems

    def initialize(payload, rating)
        self.payload = payload
        self.seen = 1
        self.lowerItems = []
        self.rating = rating
    end

    def find_index(payload)
        self.lowerItems.find_index {|lowerItem| lowerItem.payload == payload }
    end
    
    def include?(payload)
        self.lowerItems.any? {|lowerItem| lowerItem.payload == payload }
    end

    def saw(payload)
        idx = self.find_index(payload)
        if idx
            return self.lowerItems[idx].seen
        end
        return 0
    end

    # if already present: increment send
    # otherwise append
    def merge(otherLowerItems)
        otherLowerItems.each do |otherLowerItem|
            idx = self.find_index(otherLowerItem.payload)
            if idx
                self.lowerItems[idx].seen += 1
            else
                self.lowerItems.push(otherLowerItem)
            end
        end
    end
end

class ElectedOrderedList
    # the list of items
    attr_accessor :list

    def initialize
        self.list = []
    end

    def add(payload, rating)
        lowerItems = self.list.map {|x| ElectedOrderedListItem.new(x.payload, x.rating) }
        eolItem = ElectedOrderedListItem.new(payload, rating)
        eolItem.lowerItems = lowerItems
        self.list.push(eolItem)
    end
    

    def +(other_list)
        # for each item in other_list: for all item that came before, add them to the lowerItems of the item in list, or raise their weight
        other_list.list.each_with_index do |otherItem, idx|
            pos = self.index(otherItem.payload)
            if pos.nil?
                # append item with own lowerItems list, if not existing already
                self.list.push(otherItem)
            else
                self.list[pos].merge(otherItem.lowerItems)
            end
        end
        
        # balance the list according to the lowerItems list in each entry, taking each entry as vote
        self.balance
        return self
    end


    def balance
        list_ = []
        self.list.each do |item|
            break if item.nil?
            if list_.empty?
                list_.push(item)
            else
                electedInsert(item, list_)
            end
        end
        self.list = list_
    end

    def voteLower(idx)
        item = list[idx]
        votes = list.take(idx).map {|x| x.saw(item.payload) }.inject(:+) || 0
        return votes
    end

    def voteHigher(idx)
        item = list[idx]
        votes = list[idx..-1].map {|x| item.saw(x.payload) }.inject(:+) || 0
        return votes
    end

    # insert item to list at the elected best position, where:
    #   1. The highest known position which an other item before in the list that is known to be lower...
    #   2. ...that did not by itself saw the item to insert as being lower more often
    def electedInsert(item, list)
        highest = list.select{|x| item.include?(x.payload) }.last
        if highest
            if highest.saw(item.payload).to_i < item.saw(highest.payload).to_i
                pos = list.index(highest) + 1
                list.insert(pos, item)
            else
                pos = list.index(highest)
                pos.downto(0) do |i|
                    if list[i].saw(item.payload).to_i < item.saw(list[i].payload).to_i
                        list.insert(i, item)
                        break
                    end
                end
            end
        else
            # item knows of no other item. See if one of the others know item. Else insert according to rating
            lowest = list.select{|x| x.include?(item.payload) }.first
            if (lowest)
                list.insert(list.index(lowest), item)
            else
                higher = list.detect {|x| x.rating > item.rating }
                if higher
                    list.insert(list.index(higher), item)
                else
                    list.push(item)
                end
            end
        end
    end
   
    def each(&blk)
        self.list.each(&blk)
    end

     # return index of list item that has the same subitem
    def index(payload)
        list.each_with_index do |item, i|
            return i if payload == item.payload
        end
        return nil
    end

end