Priority queue: Difference between revisions
Add SAS implementation
m (Improved documentation for Stata example) |
(Add SAS implementation) |
||
Line 5,627:
Clear drains</pre>
=={{header|SAS}}==
Using macros in a SAS data step:
<lang sas>
%macro HeapInit(size=1000,nchar=20);
do;
_len = 0;
_size = &size;
array _times(&size) _temporary_ ;
array _kinds(&size) $ &nchar _temporary_;
drop _size _len;
end;
%mend;
%macro HeapSwapItem(index1, index2);
do;
_tempN = _times[&index1]; _times[&index1] = _times[&index2]; _times[&index2] = _tempN;
_tempC = _kinds[&index1]; _kinds[&index1] = _kinds[&index2]; _kinds[&index2]= _tempC;
drop _tempN _tempC;
end;
%mend;
%macro HeapEmpty;
(_len=0)
%mend;
%macro HeapCompare(index1, index2);
(_times[&index1] < _times[&index2])
%mend;
%macro HeapSiftdown(index);
do;
_parent = &index;
_done = 0;
do while (_parent*2 <= _len & ^_done);
_child = _parent*2;
if (_child+1 <= _len and %HeapCompare(_child+1,_child)) then
_child = _child + 1;
if %HeapCompare(_child,_parent) then do;
%HeapSwapItem(_child,_parent);
_parent = _child;
end;
else _done = 1;
end;
drop _done _parent _child;
end;
%mend;
%macro HeapSiftup(index);
do;
_child = &index;
_done = 0;
do while(_child>1 and ^_done);
_parent = floor(_child/2);
if %HeapCompare(_parent,_child) then
_done = 1;
else do;
%HeapSwapItem(_child,_parent);
_tempN = _child;
_child = _parent;
_parent = _tempN;
end;
end;
drop _parent _child _done _tempN;
end;
%mend;
%macro HeapPush(time, kind);
do;
if _len >= _size then do;
put "ERROR: exceeded size of heap. Consider changing size argument to %HeapInit.";
stop;
end;
_len = _len + 1;
_times[_len] = &time;
_kinds[_len] = &kind;
%HeapSiftup(_len);
end;
%mend;
%macro HeapPop;
do;
_len = _len - 1;
if (_len>0) then do;
_times[1] = _times[_len+1];
_kinds[1] = _kinds[_len+1];
%HeapSiftdown(1);
end;
end;
%mend;
%macro HeapPeek;
time = _times[1];
kind = _kinds[1];
put time kind;
%mend;
data _null_;
%HeapInit;
%HeapPush(3, "Clear drains");
%HeapPush(4, "Feed cat");
%HeapPush(5, "Make tea");
%HeapPush(1, "Solve RC tasks");
%HeapPush(2, "Tax return");
do while(^%HeapEmpty);
%HeapPeek;
%HeapPop;
end;
run;
</lang>
{{output}}
<pre>1 Solve RC tasks
2 Tax return
3 Clear drains
4 Feed cat
5 Make tea</pre>
We can reduce the namespace pollution using <code>proc fcmp</code>. Adapting the above code, we drop the
<code>%HeapSwapItem</code>, <code>%HeapSiftdown</code> and <code>%HeapSiftup</code> macros and replace
the <code>%HeapPush</code> and <code>%HeapPop</code> macros. For the test code, we get the same output.
<lang sas>
proc fcmp outlib=sasuser.funcs.trial;
subroutine HeapSwapItem(index1, index2, _times[*], _kinds[*] $);
outargs _times, _kinds;
length tempC $ 20;
tempN = _times[index1]; _times[index1] = _times[index2]; _times[index2]= tempN;
tempC = _kinds[index1]; _kinds[index1] = _kinds[index2]; _kinds[index2]= tempC;
endsub;
subroutine HeapSiftdown(index, _len, _times[*],_kinds[*] $);
outargs _times, _kinds;
parent = index;
done = 0;
do while (parent*2 <= _len and ^done);
child = parent*2;
if (child+1 <= _len and %HeapCompare(child+1,child)) then
child = child + 1;
if %HeapCompare(child,parent) then do;
call HeapSwapItem(child,parent, _times, _kinds);
parent = child;
end;
else done = 1;
end;
endsub;
subroutine HeapSiftup(index, _len, _times[*], _kinds[*] $);
outargs _times, _kinds;
child = index;
done = 0;
do while(child>1 and ^done);
parent = floor(child/2);
if %HeapCompare(parent,child) then
done = 1;
else do;
call HeapSwapItem(child,parent, _times, _kinds);
tempN = child;
child = parent;
parent = tempN;
end;
end;
endsub;
run;
options cmplib=sasuser.funcs;
%macro HeapPop;
do;
_len = _len - 1;
if (_len>0) then do;
_times[1] = _times[_len+1];
_kinds[1] = _kinds[_len+1];
call HeapSiftdown(1, _len, _times, _kinds);
end;
end;
%mend;
%macro HeapPush(time, kind);
do;
_len = _len + 1;
_times[_len] = &time;
_kinds[_len] = &kind;
call HeapSiftup(_len, _len, _times, _kinds);
end;
%mend;
</lang>
=={{header|Scala}}==
Scala has a class PriorityQueue in its standard library.
| |||