maybeOrderedList.rb

# mol: A maybe ordered list, by preserving some order on merge
#
# Concept:
#       We have an ordered list with values. If another list shall be merged in,
#       merge each new item below an item known in both lists that has a higher
#       value (=big brother), or above one that has a smaller value. If there
#       exists no such item, use the item value to find a higher item, and
#       insert below. When adding an item that exists already, average its value
#       and reposition as if it were a new item.
#       
#       Makes the assumption that values are on the same scale
#
#       

#   Alternative:
#       Count which items were before other items how often,
#       and to build a new order based on that. A voting algorithm


class MaybeOrderedListItem
    # subitem:  the item itself, the pazload
    # value: the numerical value defining its initial position in the list
    attr_accessor :subitem, :weight

    def initialize(subitem, weight)
        self.subitem = subitem
        self.weight = weight
    end

end

class MaybeOrderedList
    # the list of items
    attr_accessor :list

    def initialize
        self.list = []
    end

    # set item to the position in list weight defines, or adjust existing weight if existing
    def add(subitem, weight)
        weight = weight.to_f
        existingIdx = self.index(subitem)
        unless existingIdx.nil?
            self.adjustItem(existingIdx, weight)
            return 
        end
        # Item does not exist yet. Now we see whether we can just insert below an existing value
        list.each_with_index do |existing_item, index|
            if existing_item.weight > weight
                self.insertAtIndex(index, MaybeOrderedListItem.new(subitem, weight))
                return
            end
        end
        # If we are here, no item with a higher value could be found. Thus
        # this item belongs to the end of the array
        list.push(MaybeOrderedListItem.new(subitem, weight))
    end
    
    # merge other list with our list
    # This is the core of this object, as this is not a simple insert depending on weight
    # Instead, this searches for existing orderings and preserves them
    def +(other_list)
        tempMol = MaybeOrderedList.new
        tempMol.list = self.list.clone()
        
        other_list.each do |item_|
            item = item_.clone()
            item.weight = item.weight.to_f
            existingIdx = tempMol.index(item.subitem)
            unless existingIdx.nil?
                tempMol.adjustItem(existingIdx, item.weight)                
                next
            end
            # find the first brother in list that is already in other_list, and insert below 
            idx = nil
            bigBrothers = other_list.list.select{|x| x.weight > item.weight}
            

            bigBrothers.each do |bigBrother|
                idx = tempMol.index(bigBrother.subitem)
                break unless idx.nil?
            end

            # or insert above if it is a small brother
            smallBrothers = other_list.list.reverse.select{|x| x.weight < item.weight}
            if idx.nil?
                smallBrothers.each do |smallBrother|
                    idx = tempMol.index(smallBrother.subitem)
                    unless idx.nil?
                        idx = idx + 1
                        break
                    end
                end
            end
                        
            unless idx.nil?
                tempMol.insertAtIndex(idx, item)
            else
                # if there is none, use value to find first higher item
                tempMol.add(item.subitem, item.weight)
            end
        end
        return tempMol
    end

    # Without regard for other items, just move the existing item weight further
    # into the new weight direction. Idea is that this helps correct filing
    # mistakes by averaging them out
    def adjustItem(idx, newWeight)
        if (self.list[idx].weight != newWeight)
            self.list[idx].weight = self.list[idx].weight - ((self.list[idx].weight - newWeight) / 2)
            self.repositionElement(idx)
        end
    end

    # The item at idx might just have its weight changed. Move it to a new position in list,
    # according to its current weight.
    def repositionElement(idx)
        item = self.list.delete_at(idx)
        self.add(item.subitem, item.weight)
    end

    # Make sure all lower items have lower weight, and all higher items higher weight
    # Currently unused
    def rebalanceWeights(start)
        start.downto(1).each do |idx|
            if self.list[idx - 1].weight > self.list[idx].weight
                leftWeight, rightWeight = self.weightsAround(idx - 1, self.list[idx - 1])
                newWeight = rightWeight - ((rightWeight - leftWeight) / 2)
                self.list[idx - 1].weight = [newWeight, leftWeight].min
                self.list[idx].weight = [newWeight, leftWeight].max
            else
                break if self.list[idx - 1].weight < self.list[idx].weight
            end
        end
        (start.upto(self.list.size - 2)).each do |idx|
            if self.list[idx + 1].weight < self.list[idx].weight
                leftWeight, rightWeight = self.weightsAround(idx + 1, self.list[idx - 2])
                newWeight = leftWeight - ((leftWeight - rightWeight) / 2)
                self.list[idx + 1].weight =[newWeight, rightWeight].max
                self.list[idx].weight = [newWeight, rightWeight].min
            else
                break if self.list[idx + 1].weight < self.list[idx].weight
            end
        end
    end

    # Here we know the position. But you still need to compute the correct weight.
    # It has to be smaller than the following object but bigger than the prior,
    # potentially centered
    def insertAtIndex(idx, item)
        if (idx == 0 || idx == (self.list.size - 1))
            self.list.insert(idx, item)
        else
            smallerWeight, biggerWeight = self.weightsAround(idx, item)
            item.weight = smallerWeight + ((biggerWeight - smallerWeight) / 2 )
            self.list.insert(idx, item)
        end
    end

    def weightsAround(idx, item)
        if idx < self.list.length
            biggerWeight = self.list[idx].weight
        else
            biggerWeight = item.weight
        end
        if idx > 0
            smallerWeight = self.list[idx - 1].weight
        else
            smallerWeight = 0
        end
        return smallerWeight, biggerWeight
    end

    def each(&blk)
        self.list.each(&blk)
    end

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

    def items
        self.list.map{|item| item.subitem}
    end
    
end