'''

Originally written in 2006 Josiah Carlson
Released into the public domain.


This module implements a "pairing heap" that keeps track of where values are
so that adjust_key(value, time) operations can be fast.  It has the possibly
unfortunate feature that all values must be unique.

Running times of pair heap operations:

empty()                 -> O(1)
peek()                  -> O(1)
meld(other)             -> O(min(n+m, mlog(n+m)))
adjust_key(value, time) -> O(logn)
delete(value)           -> O(logn)
extract(n=0)            -> O(logn)
extract_all()           -> O(nlogn) #uses list.sort() because it is faster
values()                -> O(n)

The sequence interface should be ignored by the user, as certain operations
(like append) make certain assumptions about later operations that may only be
preserved when using the above pair heap operations.

'''


import heapq
import math

#entries in the heap are lists of length 2

class pair(object):
    if 1:
        __slots__ = ['time', 'value']
    def __init__(self, time, value):
        self.time = time
        self.value = value
    def __cmp__(self, other):
        return cmp(self.time, other.time)
    def __repr__(self):
        return "<item time:%.2f value:%r>"%(self.time, self.value)

def heapremove(heap, posn):
    if posn != len(heap) - 1:
        heap[posn], heap[-1] = heap[-1], heap[posn]
    
    toss = heap.pop()
    heapq._siftdown(heap, 0, posn)
    heapq._siftup(heap, posn)

class pair_heap:
    if 1:
        __slots__ = ['h', 'm']
    def __init__(self):
        self.h = []   #list of pairs
        self.m = {}   # key:posn mapping
    
    def empty(self):
        return not len(self)
    
    def peek(self):
        return self.h[0].value
    
    def meld(self, other):
        ls = len(self)
        lo = len(other)
        
        if ls + lo <= lo*math.log(max(ls+lo, math.e)):
            for i in other.h:
                self.append(i)
            
            other.h, other.m = [], {}
            
            #required by the above .append() calls due to collisions
            heapq.heapify(self)
        else:
            #insert/adjust the keys one by one
            for i in other.h:
                self.adjust_key(i.value, i.time)
            other.h, other.m = [], {}
    
    def adjust_key(self, value, time):
        if value not in self.m:
            heapq.heappush(self, pair(time, value))
            return
        
        posn = self.m[value]
        self.h[posn].time = time
        heapq._siftdown(self, 0, posn)
        heapq._siftup(self, posn)
    
    def delete(self, value):
        if value not in self.m:
            return
        heapremove(self, self.m[value])
        
    def extract(self, n=0):
        if n <= 0:
            return heapq.heappop(self).value
        return [heapq.heappop(self).value for i in xrange(min(n, len(self)))]
    
    def extract_all(self):
        r, self.h, self.m = self.h, [], {}
        #faster than performing the heapq heappop repeatedly
        r.sort()
        return [i.value for i in r]
    
    def values(self):
        return [i.value for i in self.h]
    
    
    # required for heapq which assumes the sequence interface.
    def __len__(self):
        return len(self.h)
    
    def __setitem__(self, posn, p):
        oldvalue = self.h[posn]
        self.h[posn] = p
        if self.m[oldvalue.value] == posn:
            del self.m[oldvalue.value]
        self.m[p.value] = posn
    
    def __getitem__(self, posn):
        return self.h[posn]
    
    def __delitem__(self, posn):
        self.pop(posn)
    
    def __contains__(self, value):
        return value in self.m
    
    def pop(self, posn=-1):
        lsh = len(self.h)
        if posn < 0:
            posn += lsh
        if posn != lsh-1:
            raise IndexError("pair index out of range")
        
        a = self.h.pop()
        del self.m[a.value]
        return a
    
    def append(self, p):
        if p.value in self.m:
            #item already in heap, may be an error?
            #also may want to update due to meld?
            #will keep smallest and assume that heapify will occur
            po = self.m[p.value]
            if self.h[po].time > p.time:
                self.h[po].time = p.time
            return
            
        self.m[p.value] = len(self.h)
        self.h.append(p)

    def __repr__(self):
        return repr(self.h)

def test():
    import random
    
    for p in xrange(2):
        ph = pair_heap()
        
        for i,j in zip(range(10), [chr(ord('M')-i) for i in xrange(10)]):
            ph.adjust_key(j, i)
        
        random.shuffle(ph)
        heapq.heapify(ph)
        
        ph.adjust_key('Q', 2.5)
        ph.adjust_key('M', 3.5)
        ph.delete('G')
        
        if p == 0:
            while len(ph):
                print heapq.heappop(ph)
        else:
            print ph.extract_all()
    
    a = pair_heap()
    b = pair_heap()
    
    for i in xrange(10):
        a.adjust_key('%i_a'%i, i)
        b.adjust_key('%i_b'%i, i+.5)
    a.meld(b)
    print a.extract_all()
    print b.extract_all()
    
if __name__ == '__main__':
    test()