何々した順にならべるデータ構造

gistfile1.txt

module Orderd
    class Ranking
        def initialize
            @first = @last = Node.new
            @item_id_of = {}
            @marker_of = {}
            @size = 0
        end

        def top item_id
            n = @item_id_of[item_id]
            if n.nil?
                n = Node.new
                n.value = item_id
                @item_id_of[item_id] = n
                @size += 1
                update_markers
            else
                return n if n.prev.nil?

                # nをLinkListから切りはなす
                np = n.prev
                n.prev = nil
                nn = n.next
                np.next = nn
                nn.prev = np
                update_markers n
            end
            n.next = @first
            @first.prev = n
            @first = n
            n
        end

        # markerの位置を調整してやる
        def update_markers node=nil
            marker_of = {}
            @marker_of.each do |k, v|
                marker_of[v] = k
            end
            start_marker = 0
            unless node.nil?
                n = node
                counter = 1
                n = node
                until n.next.nil?
                    if marker_of[n]
                        start_marker = marker_of[n]
                        break
                    end
                    n = n.next
                    counter += 1
                end
            end
            get_markers(0, @size).each do |i|
                if @marker_of[i]
                    if i < start_marker
                        # top内から呼ばれることを想定しているので、データを抜いたところより前のランキングは1ずつずらす
                        @marker_of[i] = @marker_of[i].prev
                    else
                        if node.nil?
                            # nodeがなかった場合は、件数がかわってくるので順番をズラす
                            @marker_of[i] = @marker_of[i].prev
                        end
                    end
                else
                    counter = 1
                    n = @last
                    until n.prev.nil?
                        rank = @size - counter
                        if rank == i
                            @marker_of[i] = n
                        end
                        counter += 1
                        n = n.prev
                    end
                end
            end
        end

        # 与えられた範囲内で
        # 2のn乗の配列を返す
        def get_markers start, last
            markers = []
            num = 2
            while num <= last
                if num >= start
                    markers.push num
                end
                num *= 2
            end
            return markers
        end

        def get_item item_id
            item = @item_id_of[item_id]
            i = 1
            node = item
            marker_of = {}
            @marker_of.each do |k, v|
                marker_of[v] = k
            end

            counter = 0
            until node.prev.nil?
                if marker_of[node]
                    return marker_of[node] + counter
                end
                counter += 1
                node = node.prev
            end
            return nil
        end

        def rank_list rank, num
            result = []
            node = @first
            start_rank = get_markers(rank, @size)
            if @marker_of[start_rank[0]]
                i = start_rank[0]
                node = @marker_of[i]
            else
                i = 1
                node = @last
            end
            until node.prev.nil?
                if i >= rank
                    if i > rank + num
                    else
                        result.unshift node
                    end
                else
                    return result
                end
                node = node.prev
                i -= 1
            end

            return result
        end

        def size
            @size
        end
    end

    class Node
        attr_accessor :prev, :next, :value
        
        def inspect
            prev_object_id = @prev.nil? ? "" : @prev.object_id
            next_object_id = @next.nil? ? "" : @next.object_id
            "<Node ##{self.object_id} value=#@value prev=#{prev_object_id} next=#{next_object_id}>"
        end
    end
end

orderd = Orderd::Ranking.new

NUM = 10000
orderd.top(15)
(1..NUM).each do |i|
    num = rand(NUM)
    p [i, num]
    orderd.top(num)
end
p orderd.get_item 15
p orderd.rank_list(100, 100).map { |n| n.value }