Rank: 130189 based on 0 downloads (last 30 days) and 0 file submitted
photo

Ahmed Gad

E-mail
Company/University
UAB

Personal Profile:

 

Watch this Author's files

 

Comments and Ratings by Ahmed Gad View all
Updated File Comments Rating
24 Jun 2010 Queue (A simple implementation) Author: Dimitri Shvorob

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 Queue (A simple implementation) Author: Dimitri Shvorob

Simple yet powerful. Thanks so much.

Contact us