"""
 Various standard data structures

      >>> s = Stack()
      >>> s.push('a')
      >>> s.push('b')
      >>> len(s)
      2
      >>> s.pop()
      'b'
      >>> s.pop()
      'a'
      >>> len(s)
      0

      >>> q = Queue()
      >>> q.push('a')
      >>> q.push('b')
      >>> len(q)
      2
      >>> q.pop()
      'a'
      >>> q.pop()
      'b'
      >>> len(q)
      0

     >>> h = MinHeap()
     >>> for i in ('c', 'a', 'b', 'z', 'm'):
     ...   h.push(i)
     >>> h.pop()              # remove smallest
     'a'
     >>> h[0]                 # remaining smallest is always root (i.e. zeroth)
     'b'
     >>> del h[h.index('m')]  # find where 'm' is and delete it
     >>> h.push('x')
     >>> [h.pop() for j in range(4)]
     ['b', 'c', 'x', 'z']

 Jim Mahoney | March 11 2013 | MIT License
"""

# see http://www.rafekettler.com/magicmethods.html

from heapq import heappush, heappop, heapify

class DataCollection(object):
    """ parent class for other structures below """
    def __init__(self):
        self.data = []
    def __len__(self):
        return len(self.data)
    def __repr__(self):
        return "<%s %s at 0x%x>" % (self.__class__.__name__, 
                                    str(self.data), id(self))

class MinHeap(DataCollection):
    """ A minimum priority queue """
    # built from Python's built-in heapq methods """
    def push(self, item):
        heappush(self.data, item)
    def peek(self):
        return self.data[0]
    def pop(self):
        return heappop(self.data)
    def __delitem__(self, index):
        del self.data[index]
        heapify(self.data)
    def __getitem__(self, index):
        return self.data[index]
    def index(self, i):
        return self.data.index(i)

class Stack(DataCollection):
    """ first-in-last-out collection """
    def push(self, item):
        self.data.append(item)       # put onto right end
    def pop(self):
        return self.data.pop()       # pull from right end


class Queue(DataCollection):
    """ first-in-first-out collection """
    def push(self, item):
        self.data.append(item)       # put onto right end
    def pop(self):
        return self.data.pop(0)      # pull from left end

if __name__ == "__main__":
    import doctest
    doctest.testmod()