program LinkedDeque;

type
  itemtype = integer; {Contents of deque}

  nodePtr = ^dequenode;

  dequenode = record    {deque Node Structure}
    itemData: itemtype;
    next: nodePtr;
  end;

  deque = record  {deque Structure}
    leftPtr : nodePtr;
    num : integer;
    rightPtr : nodePtr;
  end;


{*****************************************
Procedure to Initialise a deque
Pre: deque not initialised
Post:deque initialised to empty.
******************************************}
procedure init(var d:deque);
  begin
    d.leftPtr:= nil;
    d.rightPtr := nil;
    d.num:=0;
  end;


{*****************************************
Function to return True/False if deque is full
Pre: deque initialised
Post:deque unchanged
******************************************}
function isFull(d:deque): boolean;
begin
isFull:=false;
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.leftPtr=nil;
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.rightPtr=nil;
end;

{*****************************************
Function to return number of items in deque
Pre: deque initialised
Post:deque unchanged
******************************************}
function itemNo(d:deque): integer;
begin
itemNo:=d.num;
end;


{*****************************************
Procedure to add an item to the left of deque
Pre: deque initialised and not full
Post:deque has item inserted at the left
******************************************}
procedure insertL(var d:deque;i:itemtype);
  var
     tempPtr : nodePtr;

  begin
    new(tempPtr);
    tempPtr^.itemData:=i;
    tempPtr^.next:=d.leftPtr;
    d.leftPtr:=tempPtr;
    d.num:=d.num+1;
  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
    tempPtr:nodePtr;

  begin
    if (isEmptyL(d))
     then writeln('Sorry - deque is Empty')
     else
       begin
         i:=d.leftPtr^.itemData;
         tempPtr:=d.leftPtr;
         d.leftPtr:=tempPtr^.next;
         Dispose(tempPtr);
         d.num:=d.num-1;
       end;
  end;


{*****************************************
Procedure to add an item to the right of deque
Pre: deque initialised and not full
Post:deque has item inserted at the right
******************************************}
procedure insertR(var d:deque;i:itemtype);
  var
     tempPtr : nodePtr;

  begin
    new(tempPtr);
    tempPtr^.itemData:=i;
    tempPtr^.next:=d.rightPtr;
    d.rightPtr:=tempPtr;
    d.num:=d.num+1;
  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
    tempPtr:nodePtr;

  begin
    if (isEmptyR(d))
     then writeln('Sorry - deque is Empty')
     else
       begin
         i:=d.rightPtr^.itemData;
         tempPtr:=d.rightPtr;
         d.rightPtr:=tempPtr^.next;
         Dispose(tempPtr);
         d.num:=d.num-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.