Queue

(A simple implementation)

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)

[Andrea Tagliasacchi]

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

[Andrea Tagliasacchi]

 

[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.

[Ahmed Gad]

Simple yet powerful. Thanks so much.

[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: [e-mail], 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: [e-mail], 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