5.0

5.0 | 3 ratings Rate this file 22 Downloads (last 30 days) File Size: 3.35 KB File ID: #23354
image thumbnail

Queue

by Dimitri Shvorob

 

18 Mar 2009

(A simple implementation)

| Watch this File

File Information
Description

Submission implements strongly-typed polymorphic Queue and Priority Queue collections.
 
Please see ‘help queue’ and ‘help pqueue’ for examples.

Acknowledgements

The author wishes to acknowledge the following in the creation of this submission:
Queueing Systems Toolbox, mm1_simulator

MATLAB release MATLAB 7.7 (R2008b)
Tags for This File  
Everyone's Tags
Tags I've Applied
Add New Tags Please login to tag files.
Comments and Ratings (5)
15 May 2009 Andrea Tagliasacchi

I wish you implemented a fast queue for matlab, not an object oriented one...

22 May 2009 Andrea Tagliasacchi  
22 May 2009 Andrea Tagliasacchi

Good choice for object oriented. However, if you want a generic priority queue which don't assume elements to be Matlab objects refer to my submission.

23 Jun 2010 Ahmed Gad

Simple yet powerful. Thanks so much.

24 Jun 2010 Ahmed Gad

Hi,

1- It needed some improvements for pre-allocation before insertion.
2- Priority queue implementation using heaps is much more efficient than the current one.

I changed the implementation a bit to consider those two points. I'll post the code to you to change yours instead.

Hope it helps.

PQueue.m

classdef PQueue < Queue
   
   % PQueue - strongly-typed Priority Queue collection
   %
   % Properties:
   %
   % Type (string)
   % Comparator (function handle, @gt by default)
   %
   % Methods:
   %
   % PQueue(type)
   % PQueue(type,comparator)
   % display
   % size
   % isempty
   % clear
   % contains(obj)
   % offer(obj)
   % remove(obj)
   % peek - returns [] if queue is empty
   % poll - returns [] if queue is empty
   % values - returns contents in a cell array
   %
   % Notes:
   %
   % Compatible classes must overload eq() for object-to-object comparisons
   %
   % Comparator must be defined in the class, or a base class: RedWidget and
   % BlueWidget objects can be combined if a Widget comparator is defined
   %
   % Derived from Queue
   %
   % Example:
   %
   % q = PQueue('Widget',@gt)
   %
   % q.offer(RedWidget(1))
   % q.offer(RedWidget(3))
   % q.offer(RedWidget(2))
   % q.offer(BlueWidget(2))
   % q.offer(BlueWidget(2))
   %
   % q.size
   % q.remove(RedWidget(2));
   % q.size
   % q.remove(BlueWidget(2));
   % q.size
   %
   % q.peek
   % q.poll
   % q.size
   %
   % Author: dimitri.shvorob@gmail.com, 3/15/09
   % Modified for heap implementation and pre-allocation by:
   % a[DOT]mounir86@gmailDOTcom, 24/06/2010
   
   properties (SetAccess = protected)
       Comparator % function handle
   end
         
   methods
       
       function[obj] = PQueue(type,varargin)
           obj = obj@Queue(type);
           if nargin > 1
               obj.Comparator = varargin{1};
           else
               obj.Comparator = @gt;
           end
       end
      
       function[obj] = offer(obj,e)
           
           if length(e) > 1
              throw(MException('PQueue:offerMultiple','??? Cannot offer multiple elements at once.'))
           end
           if ~isa(e,obj.Type)
              throw(MException('PQueue:offerInvalidType','??? Invalid type.'))
           end
           
           obj.Elements{obj.lastInd+1} = e;
           obj.lastInd = obj.lastInd + 1;
           if(length(obj.Elements) == obj.lastInd)
               obj.Elements = [obj.Elements obj.Elements];
           end
           
           currInd = obj.lastInd;
           parentInd = floor(currInd / 2);
           while(parentInd ~= 0)
               if(obj.Comparator(obj.Elements{currInd},obj.Elements{parentInd}))
                   tempElement = obj.Elements{currInd};
                   obj.Elements{currInd} = obj.Elements{parentInd};
                   obj.Elements{parentInd} = tempElement;
                   
                   currInd = parentInd;
                   parentInd = floor(currInd / 2);
               else
                   break;
               end
           end
       end
       
       function[out] = poll(obj)
           
           if obj.isempty
               out = [];
               return;
           end
           
           out = obj.Elements{1};

           if(obj.size == 1)
               obj.lastInd = obj.lastInd - 1;
               return;
           end
           
           obj.Elements{1} = obj.Elements{obj.lastInd};
           obj.lastInd = obj.lastInd - 1;
           
           currInd = 1;
           childInd = currInd * 2;
           
           while(childInd <= obj.lastInd)
               
               if(childInd + 1 > obj.lastInd)

                   if(~obj.Comparator(obj.Elements{currInd},obj.Elements{childInd}))
                   
                    tempElement = obj.Elements{currInd};
                    obj.Elements{currInd} = obj.Elements{childInd};
                    obj.Elements{childInd} = tempElement;

                    currInd = childInd;
                    childInd = currInd * 2;
                   else
                    break;
                   end

               elseif(obj.Comparator(obj.Elements{childInd + 1},obj.Elements{childInd}))
                   
                   if(~obj.Comparator(obj.Elements{currInd},obj.Elements{childInd + 1}))
                   
                    tempElement = obj.Elements{currInd};
                    obj.Elements{currInd} = obj.Elements{childInd + 1};
                    obj.Elements{childInd + 1} = tempElement;

                    currInd = childInd + 1;
                    childInd = currInd * 2;
                   else
                    break;
                   end
                   
               elseif(~obj.Comparator(obj.Elements{currInd},obj.Elements{childInd}))
                   
                   tempElement = obj.Elements{currInd};
                   obj.Elements{currInd} = obj.Elements{childInd};
                   obj.Elements{childInd} = tempElement;
                   
                   currInd = childInd;
                   childInd = currInd * 2;
                   
               else
                   break;
               end
           end
       end
                  
   end
    
end

Queue.m

classdef Queue < handle
   
   % Queue - strongly-typed Queue collection
   %
   % Properties:
   %
   % Type (string)
   %
   % Methods:
   %
   % Queue(type)
   % display
   % size
   % isempty
   % clear
   % contains(obj)
   % offer(obj)
   % remove(obj)
   % peek - returns [] if queue is empty
   % poll - returns [] if queue is empty
   % values - returns contents in a cell array
   %
   % Notes:
   %
   % Compatible classes must overload eq() for object-to-object comparisons.
   %
   % Example:
   %
   % q = Queue('Widget')
   %
   % q.offer(RedWidget(1))
   % q.offer(RedWidget(3))
   % q.offer(RedWidget(2))
   % q.offer(BlueWidget(2))
   % q.offer(BlueWidget(2))
   %
   % q.size
   % q.remove(RedWidget(2));
   % q.size
   % q.remove(BlueWidget(2));
   % q.size
   %
   % q.peek
   % q.poll
   % q.size
   %
   % Author: dimitri.shvorob@gmail.com, 3/15/09
   % Modified for heap implementation and pre-allocation by:
   % a[DOT]mounir86@gmailDOTcom, 24/06/2010
   
   properties (GetAccess = protected, SetAccess = protected, Hidden = true)
       Elements
       lastInd
   end
   
   properties (SetAccess = protected)
       Type
   end
         
   methods
       
       function[obj] = Queue(type)
           if ~ischar(type)
              throw(MException('Queue:constructorInvalidType','??? ''type'' must be a valid class name.'))
           end
           obj.Elements = cell(1, 100);
           obj.lastInd = 0;
           obj.Type = type;
       end
       
       function disp(obj)
           disp([class(obj) '<' obj.Type '> (head on top)'])
           if ~obj.isempty
              for i = 1:obj.lastInd
                  disp(obj.Elements{i})
              end
           else
              disp([])
           end
       end
              
       function[out] = size(obj)
           out = obj.lastInd;
       end
       
       function[out] = values(obj)
           out = obj.Elements{1:obj.lastInd};
       end
              
       function[out] = isempty(obj)
           out = obj.size == 0;
       end
       
       function[obj] = clear(obj)
           obj.Elements = {};
           obj.lastInd = 0;
       end
       
       function[out] = contains(obj,e)
           out = false;
           for i = 1:obj.size
               if e == obj.Elements{i}
                  out = true;
                  break
               end
           end
       end
       
       function[obj] = offer(obj,e)
           if length(e) > 1
              throw(MException('Queue:offerMultiple','??? Cannot offer multiple elements at once.'))
           end
           if ~isa(e,obj.Type)
              throw(MException('Queue:offerInvalidType','??? Invalid type.'))
           end
           if isempty(obj.Elements)
              obj.Elements = {e};
           else
              obj.Elements{obj.lastInd+1} = e;
              obj.lastInd = obj.lastInd + 1;
              if(length(obj.Elements) == obj.lastInd)
                  obj.Elements = [obj.Elements obj.Elements];
              end
              
           end
       end
       
       function[obj] = remove(obj,e)
           if length(e) > 1
              throw(MException('Queue:removeMultiple','??? Cannot remove multiple elements at once.'))
           end
           if ~isa(e,obj.Type)
              throw(MException('Queue:removeInvalidType','??? Invalid type.'))
           end
           if ~isempty(obj.Elements)
              k = [];
              for i = 1:obj.size
                  if e == obj.Elements{i}
                    k = [k i]; %#ok
                  end
              end
              if ~isempty(k)
                  obj.Elements(k) = [];
                  obj.lastInd = obj.lastInd - length(k);
              end
           end
       end
       
       function[out] = peek(obj)
           if ~obj.isempty
               out = obj.Elements{1};
           else
               out = [];
           end
       end
       
       function[out] = poll(obj)
           if ~obj.isempty
               out = obj.Elements{1};
               obj.Elements(1) = [];
               obj.lastInd = obj.lastInd - 1;
           else
               out = [];
           end
       end
           
   end
    
end

Please login to add a comment or rating.
Tag Activity for this File
Tag Applied By Date/Time
queue priority collection container Dimitri Shvorob 19 Mar 2009 13:40:28
queue priority collection container feddo feddo 23 Mar 2010 09:03:37
queue priority collection container Mehdi 21 Nov 2010 16:17:42
queue priority collection container Abhishek 27 Jun 2011 16:28:26

Contact us at files@mathworks.com