|
##
## Datastructures: GAP package providing common datastructures.
##
## Copyright (C) 2015-2017 The datastructures team.
## For list of the team members, please refer to the COPYRIGHT file.
##
## This package is licensed under the GPL 2 or later, please refer
## to the COPYRIGHT.md and LICENSE files for details.
##
# This file implements double ended queues (deques) using a circular buffer
# stored in a GAP plain list.
#
# The four positions in a deque Q have the following purpose
#
# Q[1] - head, the index in Q[4] of the first element in the deque
# Q[2] - tail, the index in Q[4] of the last element in the deque
# Q[3] - capacity, the allocated capacity in the deque
# Q[4] - factor by which storage is resized if capacity is exceeded
# Q[5] - GAP plain list with storage for capacity many entries
#
# Global constants QHEAD, QTAIL, QCAPACITY, QFACTOR, and QDATA are bound to
# reflect the above.
#
# When a push fills the deque, its capacity is resized by QFACTO R using
# PlistDequeExpand. A new empty plist is allocated and all current entries of
# the deque are copied into the new plist with the head entry at index 1.
#
# The deque is empty if and only if head = tail and the entry that head and tail
# point to in the storage list is unbound.
InstallGlobalFunction(PlistDeque,
function(arg)
local capacity, factor, result;
if Length(arg) >= 3 then
ErrorNoReturn("usage: PlistDeque( [ <capacity>, [ <factor> ] ])");
fi;
capacity := 64;
factor := 2;
if Length(arg) >= 1 then
if not IsPosInt(arg[1]) then
ErrorNoReturn("<capacity> must be a positive integer");
fi;
capacity := arg[1];
fi;
if Length(arg) >= 2 then
if not IsRat(arg[2]) or (arg[2] <= 1) then
ErrorNoReturn("<factor> must be a rational greater than 1");
fi;
factor := arg[2];
fi;
result := [1, 1, capacity, factor, EmptyPlist(capacity)];
Objectify(PlistDequeType, result);
return result;
end);
InstallGlobalFunction(PlistDequePushBack,
function(deque, item)
local head, tail, last;
if item = fail then
ErrorNoReturn("<item> must not equal 'fail'");
fi;
head := deque![QHEAD];
tail := deque![QTAIL];
last := deque![QCAPACITY];
# Special case for empty deque,
# head = tail and deque![QDATA][tail] is
# not bound
if not IsBound(deque![QDATA][tail]) then
deque![QDATA][tail] := item;
else
if tail = last then
tail := 1;
else
tail := tail + 1;
fi;
deque![QDATA][tail] := item;
deque![QTAIL] := tail;
# If deque is full expand
if ((head = 1) and (tail = last))
or (tail + 1 = head) then
PlistDequeExpand(deque);
fi;
fi;
end);
InstallGlobalFunction(PlistDequePushFront,
function(deque, item)
local head, tail, last;
if item = fail then
ErrorNoReturn("<item> must not equal 'fail'");
fi;
head := deque![QHEAD];
tail := deque![QTAIL];
last := deque![QCAPACITY];
# If the deque is empty
if not IsBound(deque![QDATA][head]) then
deque![QDATA][head] := item;
else
if head = 1 then
head := last;
else
head := head - 1;
fi;
deque![QDATA][head] := item;
deque![QHEAD] := head;
if (head = 1 and tail = last)
or (tail + 1 = head) then
PlistDequeExpand(deque);
fi;
fi;
end);
InstallGlobalFunction(PlistDequePopFront,
function(deque)
local head, tail, last, result;
if IsEmpty(deque) then
return fail;
fi;
head := deque![QHEAD];
tail := deque![QTAIL];
last := deque![QCAPACITY];
result := deque![QDATA][head];
Unbind(deque![QDATA][head]);
if head <> tail then
if head = last then
head := 1;
else
head := head + 1;
fi;
deque![QHEAD] := head;
fi;
return result;
end);
InstallGlobalFunction(PlistDequePopBack,
function(deque)
local head, tail, last, result;
if IsEmpty(deque) then
return fail;
fi;
head := deque![QHEAD];
tail := deque![QTAIL];
last := deque![QCAPACITY];
result := deque![QDATA][tail];
Unbind(deque![QDATA][tail]);
if head <> tail then
if tail = 1 then
tail := last;
else
tail := tail - 1;
fi;
deque![QTAIL] := tail;
fi;
return result;
end);
InstallGlobalFunction(PlistDequePeekFront,
function(deque)
if IsEmpty(deque) then
return fail;
fi;
return deque![QDATA][deque![QHEAD]];
end);
InstallGlobalFunction(PlistDequePeekBack,
function(deque)
if IsEmpty(deque) then
return fail;
fi;
return deque![QDATA][deque![QTAIL]];
end);
InstallGlobalFunction(PlistDequeExpand,
function(deque)
local result, p, head, tail, last, factor;
head := deque![QHEAD];
tail := deque![QTAIL];
last := deque![QCAPACITY];
factor := deque![QFACTOR];
deque![QCAPACITY] := Int(factor * last);
if deque![QCAPACITY] = last then
# TODO: Maybe display a warning here
# might require introducing an
# InfoClass
deque![QCAPACITY] := last + 5;
fi;
result := EmptyPlist(deque![QCAPACITY]);
# Copy data into new list.
p := 1;
while head <> tail do
result[p] := deque![QDATA][head];
p := p + 1;
head := head + 1;
if head > last then
head := 1;
fi;
od;
result[p] := deque![QDATA][head];
deque![QHEAD] := 1;
deque![QTAIL] := p;
deque![QDATA] := result;
end);
## method installation
InstallMethod(PushBack,
"for IsPlistDeque and an object",
[IsPlistDequeRep, IsObject],
PlistDequePushBack);
InstallMethod(PushFront,
"for IsPlistDeque and an object",
[IsPlistDequeRep, IsObject],
PlistDequePushFront);
InstallMethod(PopFront,
"for IsPlistDeque and an object",
[IsPlistDequeRep],
PlistDequePopFront);
InstallMethod(PopBack,
"for IsPlistDeque and an object",
[IsPlistDequeRep],
PlistDequePopBack);
InstallOtherMethod(IsEmpty,
"for IsPlistDeque",
[IsPlistDequeRep],
function(deque)
local head;
head := deque![QHEAD];
return not IsBound(deque![QDATA][head]);
end);
InstallOtherMethod(Size,
"for IsPlistDeque",
[IsPlistDequeRep],
function(deque)
local head, tail;
head := deque![QHEAD];
tail := deque![QTAIL];
if not IsBound(deque![QDATA][head]) then
return 0;
else
if tail >= head then
return tail - head + 1;
else
return Capacity(deque) - (head - tail) + 1;
fi;
fi;
end);
InstallMethod(Capacity,
"for IsPlistDeque",
[IsPlistDequeRep],
function(deque)
return deque![QCAPACITY];
end);
InstallMethod( ViewString,
"for a PlistDeque",
[ IsPlistDequeRep ],
function(deque)
return STRINGIFY("<deque with "
, Size(deque), "/", Capacity(deque)
, " entries>");
end);
[ Dauer der Verarbeitung: 0.10 Sekunden
(vorverarbeitet)
]
|
