New Topic/Question
Reply
Posted 23 June 2012 - 01:09 PM
#Priority Queue
__author__ = "Adam Traub"
__date__ = "6/23/2012"
from Queue import Queue
import inspect
class PriorityQueue:
def __init__(self):
self.master = {}
self.length = 0
def enqueue(self, value, priority=1):
if self.master.get(priority) != None:
self.master.get(priority).enqueue(value)
else:
self.master[priority] = Queue()
self.master[priority].enqueue(value)
self.length += 1
def dequeue(self):
highestKey = self.__getFrontQueue()
retVal = self.master.get(highestKey).dequeue()
if self.master.get(highestKey).isEmpty():
self.master.pop(highestKey)
self.length -= 1
return retVal
def clear(self):
self.master = {}
self.length = 0
def isEmpty(self):
return self.length == 0
def hasMore(self):
return self.length >= 0
def peek(self):
return self.master.get(self.__getFrontQueue()).front()
def __len__(self):
return self.length
def __getFrontQueue(self):
if self.length <= 0:
raise IndexError((inspect.stack()[1][3]).title() +" can't be used on an empty PriortiyQueue")
return sorted(self.master.keys())[-1]
Admittedly, this one wasn't as involved as I thought it would be. I only spent about 45 minutes on this, but I don't think it's too bad. I'm sure it's riddled with errors, but I am a little proud of my utilization of the inspect class for smarter error reporting on the __getFrontQueue method (This makes it so that the name of the function that called getFrontQueue gets reported when the error is raised, pretty nifty, yeah?).
I really do enjoy building data structures though. They're easy to make, but take time and skill to optimize. Now that I've basically gotten generators out of my system, I think I'll start working on more data structures. So, here's my question to the community, are there any data structures that are near and dear to your hearts? Sure, most of us are fond of arrays/lists/arraylists and dictionaries/hashtables, but what about the more complex ones? What data structures have you built? What have you struggled with? What are some of your prouder "structured" achievements?
This post has been edited by atraub: 23 June 2012 - 01:41 PM
MultiQuote
That's a while ago now, I might have the code somewhere I can dig up. Or maybe worth rewriting it (I assume it can be improved) for a tutorial! 
| 