Abs/Concrete Comments for a Queue

Abstract and Concrete Comments for a Queue

Challenge:

Write the abstract and concrete comments for the following implementation of a queue. Write the representation invariant.

//Uncommented queue program

//queue.h

#include <iostream.h>

const int maxq=5;

typedef int qelt;

class queue {
int rear;
qelt elt[maxq];
void shift ();
public:
    queue();
    int empty ();
    int addq (qelt e);
    int delq (qelt &e);
};

//queue.cc

#include "queue.h"

void queue::shift () {
for (int i=0;i<rear;i++)
elt[i]=elt[i+1];
}

queue::queue () {
rear = 0;
}

int queue::empty () {
return (rear==0);
}

int queue::addq (int e) {
if (rear<maxq) {
elt[rear++]=e;
return 1;
}
return 0;
}

int queue::delq (int &e) {
if (!empty()) {
    e=elt[0];
    rear--;
    shift ();
    return 1;
}
return 0;
}

//main.cc

#include "queue.h"

void checkempty (queue q) {
if (q.empty())
    cout << "queue is empty\n";
else
    cout << "queue is not empty\n";
}

main () {
queue q;
checkempty (q);
for (int i=1;i<7;i++)
    if (!q.addq(i))
      cout << "cannot add element " << i << '\n';
checkempty (q);
qelt a;
while (q.deleteq(a))
    cout << a;
cout << endl;
}

Solution:

//queue.h

//Representation invariant: 0<=rear<=maxq

#include <iostream.h>

const int maxq=5;

typedef int qelt;

class queue {
int rear;
qelt elt[maxq];
void shift ();
//abs: q==<q1,q2,...,qn> for n the number of elements in q ->
// q==<q1,q2,...,qn>
//con: elt[i] for 0<=i<rear -> elt[i]=elt[i+1]
public:
    queue();
    //abs: q = <>
    //con: rear = 0
    int empty ();
    //abs: empty = (q==<>)
    //con: return (rear==0)
    int addq (qelt e);
    //abs: q not full -> q, addq = q'~<e>, 1 | addq = 0
    //con: rear<maxq -> elt[rear'], rear, addq = e, rear'+1, 1 | addq = 0
    int delq (qelt &e);
    //abs: q==<frontelt>~<restofq> for <frontelt> an elt ->
    // q, e, delq = <restofq>, <frontelt>, 1 | delq = 0
    //con: rear>0 -> elt[i]=elt[i+1] for 0<=i<rear', rear=rear'-1,delq=1
    // | delq=0;
};