No BSD License  

Highlights from
Queue

5.0

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

Queue

by

 

(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

Queueing Systems Toolbox and Mm1 Simulator inspired this file.

MATLAB release MATLAB 7.7 (R2008b)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (5)
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

23 Jun 2010 Ahmed Gad

Simple yet powerful. Thanks so much.

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.

22 May 2009 Andrea Tagliasacchi  
15 May 2009 Andrea Tagliasacchi

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

Contact us