python priority queue

[faby]

hello everyone!

I wanted to create a priority queue in which there would be different dictionaries with their priority numbers. The major problem I'm experiencing is that the queue just prints the dictionaries without regard for their priority. Please what do I have to do so that the queue prints the different dictionaries based on their assigned priority numbers?

Thanks in advance!

Below is my python code:

from Queue import PriorityQueue
#making the priority queue object
pq = PriorityQueue()

#making the different dictionaries
firstDict = {'boy':'short', 'girl':'tall'}
secondDict = {'man':'tall', 'woman':'short'}

#putting the objects in the priorityQueue with a priority number
pq.put(firstDict, 1)
pq.put(secondDict,2)

#printing the dictionary according to their priority
#lower number means higher priority

while not pq.empty():
   print pq.get()

[TrustyTony]

Corrected your finishing tag to (/code)

from Queue import PriorityQueue
#making the priority queue object
pq = PriorityQueue()

#making the different dictionaries
firstDict = {'boy':'short', 'girl':'tall'}
secondDict = {'man':'tall', 'woman':'short'}

#putting the objects in the priorityQueue with a priority number
pq.put(secondDict,2)
pq.put(firstDict, 1)

#printing the dictionary according to their priority
#lower number means higher priority

while not pq.empty():
   print pq.get()

I get result correctly first firstDict, then secondDict, irrespectively which order I put them in.

""" Output:
{'boy': 'short', 'girl': 'tall'}
{'woman': 'short', 'man': 'tall'}
"""

[tbone2sk]

Python dictionaries are unordered key-value pairs, so there is no way for them to be in the same order at all times, but recently python version 2.7 was released with a ordered dictionary feature. I have not used any of the 3.0+ versions of python so I don't know if OrderedDict is included in those builds too, but below is a solution to get the dicts in order with OrderedDict.

from Queue import PriorityQueue
from collections import OrderedDict

#making the priority queue object
pq = PriorityQueue()

#making the different dictionaries
firstDict = OrderedDict([('boy','short'),
                         ('girl','tall')])
secondDict = OrderedDict([('man','tall'),
                          ('woman','short')])

#putting the objects in the priorityQueue with a priority number
pq.put(firstDict, 1)
pq.put(secondDict,2)

#printing the dictionary according to their priority
#lower number means higher priority

while not pq.empty():
    print pq.get()

[faby]

thanks for helping me correct my code display. Meanwhile, I just tried to write a short python code that shows my problem but the previous code doesn't show it. so I'll paste a part of my original code.

NB: PriorityQueue is a standard python class not a class I built.

Thanks!

#Python 2.6.5

from Queue import PriorityQueue

class Speak:

   def __init__(self):
      """Constructor of class Speak. The constructor contains a PriorityQueue object which would be used later
      """
      #make a global queue
      self.pq = PriorityQueue()
   
   def add_to_queue(self, given_dict):
       """Add every received dictionary and use its respective priority key to get its priority value in the global queue
       """
       self.pq.put(given_dict, given_dict['priority'])
          
   def loop_queue(self):
       print "\nLooping the queue gives these dictionaries:\n"
       while not self.pq.empty():
           print self.pq.get(), "\n"
   
              
if __name__ == '__main__':
   
   speech = Speak()
   firstDict = {'command_type': 'say_string',
       'control_command': 'stop',
       'priority': 3
       }
   
   secondDict = {'command_type': 'say_string',
        'control_command': 'resume',
        'priority': 2
        }

   thirdDict = {'command_type': 'say_wav',
        'control_command': None,
        'priority': 1
        }


    #add all dictionaries to global queue and loop the queue
   speech.add_to_queue(firstDict)
   speech.add_to_queue(secondDict)
   speech.add_to_queue(thirdDict)
   speech.loop_queue()

    #Below is what I get as my result:

"""
Looping the queue gives these dictionaries:

{'priority': 2, 'command_type': 'say_string', 'control_command': 'resume'}

{'priority': 3, 'command_type': 'say_string', 'control_command': 'stop'}

{'priority': 1, 'command_type': 'say_wav', 'control_command': None}

"""

#This is what I was hoping could have been my result:
"""
Looping the queue gives these dictionaries:

{'priority': 3, 'command_type': 'say_string', 'control_command': 'stop'}

{'priority': 2, 'command_type': 'say_string', 'control_command': 'resume'}

{'priority': 1, 'command_type': 'say_wav', 'control_command': None}

"""

[TrustyTony]

PriorityQueues are for multitasking situations and I do not use multitasking programming so well.

I recoded your code to simple list with fixed amount of priorities. That enabled me also to print the list in reversed priority order as you requested:

#Python 2.6.5

from Queue import PriorityQueue

class Speak:
   lowestpriority = 5
   def __init__(self):
      """Constructor of class Speak. The constructor contains a PriorityQueue object which would be used later
      """
      #make a global queue
      self.pq = [[] for priority in range(self.lowestpriority)] # prioritylevels
##      print self.pq # debug
   
   def add_to_queue(self, given_dict):
       """Add every received dictionary and use its respective priority key to get its priority value in the global queue
       """
       self.pq[given_dict['priority']-1].append(given_dict)
##       print self.pq # debug
          
   def loop_queue(self):
       print "\nLooping the queue in reverse order of priority gives these dictionaries:\n"
       for item in reversed(filter(None,self.pq)):
           print item

   def get(self):
        for priorityevents in self.pq:
            while priorityevents:
                yield priorityevents.pop(0) ## use list as ques to keep insertion order (remove from front)
                
if __name__ == '__main__':
   
   speech = Speak()
   firstDict = {'command_type': 'say_string',
       'control_command': 'stop',
       'priority': 3
       }
   
   secondDict = {'command_type': 'say_string',
        'control_command': 'resume',
        'priority': 2
        }

   thirdDict = {'command_type': 'say_wav',
        'control_command': None,
        'priority': 1
        }


    #add all dictionaries to global queue and loop the queue
   speech.add_to_queue(firstDict)
   speech.add_to_queue(secondDict)
   speech.add_to_queue(thirdDict)
   speech.loop_queue()

   print "\nGetting items out of queue in priority order:"
   for i in speech.get():
       print i
   # empty after get
   speech.loop_queue()
 
"""Output:
Looping the queue in reverse order of priority gives these dictionaries:

[{'priority': 3, 'command_type': 'say_string', 'control_command': 'stop'}]
[{'priority': 2, 'command_type': 'say_string', 'control_command': 'resume'}]
[{'priority': 1, 'command_type': 'say_wav', 'control_command': None}]

Getting items out of queue in priority order:
{'priority': 1, 'command_type': 'say_wav', 'control_command': None}
{'priority': 2, 'command_type': 'say_string', 'control_command': 'resume'}
{'priority': 3, 'command_type': 'say_string', 'control_command': 'stop'}

Looping the queue in reverse order of priority gives these dictionaries:

"""

[faby]

thanks for the reply and the re-coding! I really don't understand some of the implementation but it works. For example lines 22 and 28. Also from your implementation, I guess the use of PriorityQueue from Queue is not necessary. I'm not sure of what you did but it looks like just building up a list of dictionaries. Do you think there's a way I could make the priority list unlimited so I can always add dictionaries anytime?

Thanks again!!

[TrustyTony]

That import is of course left over from your code. The amount of memory should be the limit now, what you mean with unlimited priority list? Can you give example?

Here is some examples of functions used in lines you mentioned:

# filter all 0, [], '', False etc False values from sequence by filter
# without filter function (filter function None)
# used in my code line 28
list_with_junk = [ {},[23],4,5,0,True,764,'asfa','']

print list_with_junk
print "Filtered: %s" % filter(None,list_with_junk)

print "Range until 5",range(5)
print "Same reversed",list(reversed(range(5)))
print "Same with slicing with step -1", range(5)[::-1]


print "Making queue with numbers 1,2,3"
a=[1]
a.append(2)
a.append(3)

print a

print "First one out from front",a.pop(0)
print "Last one out from behind (stack)",a.pop()
print "Left in list: ", a

[faby]

did i say you were awesome! Yes you are!!!
i can't believe I practically learned like 5 new things within a short time. Thanks again.

Meanwhile, what I meant by unlimited priority list is that the stack/queue grows based on the number of elements needed. That also means that the global variable 'lowestpriority = 5' would be gotten rid of in the code.

For example, if only three dictionaries are given then the size of the stack will be three. Then if a fourth one is added, the stack has a size of 5. Basically, the size of the stack will automatically change without me having to change the number 'lowestpriority' any time I add another dictionary with a lower priority than the given 'lowestpriority'.

thanks one more time!

[TrustyTony]

Number of priorities has nothing to do how many elements can be added, it only gives the amount of tiers the things are kept. In normal list things are un-classified, in this class things go in different 'levels'. Changing the level to be hash index of dictionary instead index to list is not big change, also adding priority levels is easy, I added setting those as optional init parameter.

Here little generalized version allowing to put any data to queue by giving priority as parameter. Test with 8 priority levels with retrieving values and checking that we do not get lower priority items before higher ones. Actually I learned just that probably easier and cleaner way to give the items would be to import chain from functools module, but I did not make the change.

#Python 2.6.5
from random import randint
class Speak:
   def __init__(self,prioritylevels=5):
      """Constructor of class Speak.
         The constructor builds list for priority queue which would be used later
      """
      self.prioritylevels = prioritylevels
      self.pq = [[] for priority in range(self.prioritylevels)]

   def add_to_queue(self, data, priority=None):
       """Add every received data and use its given priority or
         respective priority key to get its priority value in the global queue
       """
       if priority is None: priority = data['priority']-1
       else:            priority -= 1

       if 0 <= priority < self.prioritylevels:
             self.pq[priority].append(data)
       else: raise ValueError,"Priority level out of bounds: %s" % priority

   def get(self):
        for priorityevents in self.pq:
            while priorityevents:
                yield priorityevents.pop(0) ## use list as ques to keep insertion order (remove from front)               
   def num_items(self):
      return sum(len(q) for q in speech.pq)


if __name__ == '__main__':
   
   speech = Speak(8)
   for i in range(100000):
      item=randint(0,234234)
      if not i % 10000: print i,
      priority=(item & 0b111) +1 ## lets three lowest bits decide which priority we give
      speech.add_to_queue(('Number',item),priority=priority)

   print "\n%i items in queues" % speech.num_items()
   print "Items by priorities"
   print '\n'.join("%i: %i" % (priority+1,len(q)) for priority, q in enumerate(speech.pq))
   print "\nGetting items out of queue in priority order:"
   priority=0
   for description,i in speech.get():
       assert (i & 0b111 >= priority), '** Bug ***'
       priority = i & 0b111
   # empty after get
   print "Finished"
   print "%i items in queue" % speech.num_items()

[faby]

thanks for your help. I really appreciate it! :)

[TrustyTony]

You are welcome.

One bug though: line 26 should have self.pq not speech.pq

[TrustyTony]

Looks like you forgot to mark this thread solved.