program SeqDeque;

const
  max = 10;  {Maximum size of Queue}

type
  itemtype = integer; {Contents of Queue}

  deque = record       {Queue Structure}
    left:integer;
    items: array [1..max] of itemtype;
    right: integer;
  end;


{*****************************************
Procedure to Initialise a Deque
Pre: Deque not initialised
Post:Deque initialised with left on 1 and
     right on maximum size of deque.
******************************************}
procedure init(var d:deque);
  begin
    d.left:=1;
    d.right:=max;
  end;


{*****************************************
Function to return True/False if deque is full
Pre: deque initialised
Post:deque unchanged
******************************************}
function isFull(d:deque): boolean;
begin
isFull:=d.left>d.right;
end;

{*****************************************
Function to return True/False if left Deque is empty
Pre: Deque initialised
Post:Deque unchanged
******************************************}
function isEmptyL(d:deque): boolean;
begin
isEmptyL:=d.left=1;
end;


{*****************************************
Function to return True/False if right Deque is empty
Pre: Deque initialised
Post:Deque unchanged
******************************************}
function isEmptyR(d:deque): boolean;
begin
isEmptyR:=d.right=max;
end;


{*****************************************
Function to return number of items in deque
Pre: deque initialised
Post:deque unchanged
******************************************}
function itemNo(d:deque): integer;
begin
itemNo:=(d.left-1)+(max-d.right);
end;


{*****************************************
Procedure to Insert an item at left of Deque
Pre: Deque initialised and not full
Post:Deque has item inserted at left
******************************************}
procedure insertL(var d:deque;i:itemtype);
  var c:integer;
  begin
    if (isFull(d))
     then writeln('Sorry - deque is Full')
     else
       begin
         if d.left>1
            then
                for c:=d.left downto 2 do
                    d.items[c]:=d.items[c-1];
         d.items[1]:=i;
         d.left:=d.left+1;
       end;
  end;


{*****************************************
Procedure to Remove an item from left of deque
Pre: Deque initialised and not empty
Post:Deque has item removed from left
******************************************}
procedure removeL(var d:deque;var i:itemtype);
var c:integer;
  begin
    if (isEmptyL(d))
     then writeln('Sorry - deque is Empty')
     else
       begin
         i:=d.items[1];
         if d.left>1
            then
                for c:=1 to d.left-2 do
                    d.items[c]:=d.items[c+1];
         d.left:=d.left-1;
       end;
  end;


{*****************************************
Procedure to Insert an item at right of Deque
Pre: Deque initialised and not full
Post:Deque has item inserted at right
******************************************}
procedure insertR(var d:deque;i:itemtype);
  var c:integer;
  begin
    if (isFull(d))
     then writeln('Sorry - deque is Full')
     else
       begin
         if d.right<max
            then
                for c:=d.right to max-1 do
                    d.items[c]:=d.items[c+1];
         d.items[max]:=i;
         d.right:=d.right-1;
       end;
  end;


{*****************************************
Procedure to Remove an item from right of deque
Pre: Deque initialised and not empty
Post:Deque has item removed from right
******************************************}
procedure removeR(var d:deque;var i:itemtype);
var c:integer;
  begin
    if (isEmptyR(d))
     then writeln('Sorry - deque is Empty')
     else
       begin
         i:=d.items[max];
         if d.right<max
            then
                for c:=max downto d.right+2 do
                    d.items[c]:=d.items[c-1];
         d.right:=d.right+1;
       end;
  end;


{*****************************************
               MAIN PROGRAM
******************************************}
Var
  Testdeque:deque;
  item:itemtype;

BEGIN
  init(Testdeque);
  insertL(Testdeque,21);
  insertL(Testdeque,24);
  insertR(Testdeque,28);
  writeln('Number of items in deque: ',itemNo(Testdeque));
  removeL(Testdeque,item);
  writeln('The item at the front of the deque was ',item);
  writeln('Number of items now in deque: ',itemNo(Testdeque));
  insertL(Testdeque,1);
  insertL(Testdeque,2);
  insertR(Testdeque,3);
  insertR(Testdeque,4);
  insertR(Testdeque,5);
  insertR(Testdeque,6);
  insertL(Testdeque,7);
  insertL(Testdeque,8);
  insertL(Testdeque,9);
END.
