Source Code for Module coinor.blimpy.Queues

  1  ''' 
  2  This module implements a Queue class, a simple list-based queue data structure 
  3  and a PriorityQueue class, which is a heap-based priority queue data structure. 
  4  ''' 
  5   
  6  __version__    = '1.1.0' 
  7  __author__     = 'Aykut Bulut, Ted Ralphs (ayb211@lehigh.edu,ted@lehigh.edu)' 
  8  __license__    = 'BSD' 
  9  __maintainer__ = 'Aykut Bulut' 
 10  __email__      = 'ayb211@lehigh.edu' 
 11  __url__        = None 
 12  __title__      = 'Queue data structure' 
 13   
 14  from LinkedList import LinkedList 
 15   
 16 -class Queue(object): 
 17      ''' 
 18      A queue data structure built on top of a linked list 
 19      attributes: 
 20          items:    A list that holds objects in the queue 
 21                    type: LinkedList 
 22      methods: 
 23          __init__(self):        constructor of the class 
 24          isEmpty(self):         returns True if the queue instance is empty 
 25          push(self,item):       inserts item to the queue 
 26          pop(self,item):        removes first item in the queue if no item is 
 27                                 specified removes the given item if item is 
 28                                 specified 
 29          size(self):            returns the size of the queue 
 30      ''' 
 31 -    def __init__(self): 
 32          self.items = LinkedList() 
 33   
 34 -    def isEmpty(self): 
 35          return len(self.items) == 0 
 36   
 37 -    def enqueue(self, item): 
 38          self.items.insert(0,item) 
 39   
 40 -    def push(self, item): 
 41          self.enqueue(item) 
 42   
 43 -    def dequeue(self, item = None): 
 44          if item == None: 
 45              return self.items.pop() 
 46          else: 
 47              self.items.remove(item) 
 48              return item 
 49   
 50 -    def remove(self, item = None): 
 51          self.dequeue(item) 
 52   
 53 -    def pop(self, item = None): 
 54          return self.dequeue(item) 
 55   
 56 -    def peek(self, item = None): 
 57          if item == None: 
 58              return self.items[len(self.items)-1] 
 59          else: 
 60              for i in self.items: 
 61                  if i == item: 
 62                      return i 
 63          return None 
 64   
 65 -    def size(self): 
 66          return len(self.items) 
 67   
 68  import itertools, heapq 
 69   
 70 -class PriorityQueue(object): 
 71      ''' 
 72      A priority queue based on a heap. 
 73      attributes: 
 74          heap:                  A heap-ordered list that holds objects in the 
 75                                 queue 
 76                                 type: list 
 77          entry_finder:          A (map) dictionary for finding items in the heap 
 78          counter:               A unique sequence generator 
 79          size:                  Number of items in the queue 
 80      methods: 
 81          __init__(self):        constructor of the class 
 82          isEmpty(self):         returns True if the queue is empty, False 
 83                                 otherwise 
 84          push(self,key,item,priority): inserts item with given key and  
 85                                 priority into the queue 
 86          pop(self,index):       removes item with index from the queue 
 87                                 if no item is specified or removes the given 
 88                                 item if item is specified 
 89          size(self):            returns the size of the queue 
 90      ''' 
 91 -    def __init__(self, aList = None): 
 92          if aList == None: 
 93              self.heap = [] 
 94          else: 
 95              self.heap = aList 
 96          self.entry_finder = {}               # mapping of tasks to entries 
 97          self.REMOVED = '<removed-task>'      # placeholder for a removed task 
 98          self.counter = itertools.count()     # unique sequence count 
 99          self.size = len(self.heap) 
100   
101 -    def isEmpty(self): 
102          return self.size == 0 
103   
104 -    def heapify(self): 
105          heapq.heapify(self.heap) 
106   
107 -    def pop(self, key = None): 
108          ''' 
109          Remove and return the lowest priority task. Raise KeyError if empty. 
110          ''' 
111          if key == None: 
112              while self.size: 
113                  entry = heapq.heappop(self.heap) 
114                  if entry[-1] is not self.REMOVED: 
115                      del self.entry_finder[entry[-1]] 
116                      self.size -= 1 
117                      return entry[-2] 
118              raise KeyError('pop from an empty priority queue') 
119          else: 
120              self.remove(key) 
121   
122 -    def peek(self, key = None): 
123          if key == None: 
124              while self.size: 
125                  if self.heap[0][-1] is not self.REMOVED: 
126                      return self.heap[0][-2] 
127                  else: 
128                      heapq.heappop(self.heap) 
129              raise KeyError('peek at an empty priority queue') 
130          try: 
131              return self.entry_finder[key][-2] 
132          except KeyError: 
133              return None 
134   
135 -    def get_priority(self, key): 
136          try: 
137              return self.entry_finder[key][0] 
138          except KeyError: 
139              return None 
140   
141 -    def push(self, key, priority = None, item = None): 
142          ''' 
143          Add to the heap or update the priority of an existing task. 
144          ''' 
145          if priority == None: 
146              priority = key 
147          if key in self.entry_finder: 
148              self.remove(key) 
149          if item is None: 
150              item = key 
151          count = next(self.counter) 
152          entry = [priority, count, item, key] 
153          self.entry_finder[key] = entry 
154          self.size += 1 
155          heapq.heappush(self.heap, entry) 
156   
157 -    def remove(self, key): 
158          ''' 
159          Mark an existing task as REMOVED.  Raise KeyError if not found. 
160          ''' 
161          entry = self.entry_finder.pop(key) 
162          entry[-1] = self.REMOVED 
163          self.size -= 1 
164