briand@infmx.UUCP (brian donat) (05/26/90)
//
// 1 of 4
//
// I thought that some of you might be curious as to what kind of
// critcisms my linked list class recieved and further since the
// criticism I did recieve was somewhat instructive, and further
// still, since nobody flamed me for posting a heap of code, I've
// decided to post version 2.00, with explanations attached
// regarding improvements gleened from the critiques I recieved.
//
// First, I'd decided on-my-own, to break the original code out into
// separate '.c' and '.h' files and achieved this just before the
// first helpful advice arrived.
//
// Still further, some of that advice recommended creating STACK and
// QUEUE classes, instead of writing functions which used class list
// as a stack or a queue.
//
// So, the following files are now extant:
//
// vlist.h a virtural base class for list
// vlist.c members for class VLIST
// list.h class LIST derived from VLIST
// stack.h class STACK derived from VLIST
// stack.c members for class STACK
// queue.h class QUEUE derived from VLIST
// queue.c members for class QUEUE
// testmain.c main() for testing purposes as before.
//
// Discussion continued below.
---------------------------------Cut HERE---------------------------------
/////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
// \\
// vlist.h Version 2.00 \\
// A linked-list object: May 25, 1990, Brian L. Donat \\
// \\
/////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
//
// The following classes compose a very general doubly linked list,
// which may be added to, inserted into, deleted from, and read from.
// This size of list is maintained, allowing external algorithms to
// perform finite operations on the list data.
//
/////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
typedef int ELEMENT;
////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\
// NODE is a base class which allows for the
// creation of a doubly linked list.
class NODE {
friend class VLIST;
NODE *next, *previous;
ELEMENT data;
};
////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\
// VLIST is the actual doubly linked list class
//
// [ NOTE: original comments deleted for brevity.]
class VLIST {
int listsize;
NODE *head, *tail;
NODE *cnode; // current NODE or copy NODE.
public:
VLIST();
~VLIST();
virtual void headend();
virtual void tailend();
virtual void insert(ELEMENT E);
virtual void add(ELEMENT E) { cnode = tail; insert(E); }
virtual void remove();
virtual void step();
virtual void backstep();
virtual int find(ELEMENT E);
virtual ELEMENT getval() const;
virtual int getsize() const { return listsize; }
};
---------------------------------Cut HERE---------------------------------
// A lot more concise, eh?
// One of the things I got hit for here was my style of 'commenting'.
// /////\\\\\ <- One person believes that some compilers
// might view the last '\' as an escape which
// doom the next line to being commented out.
// I tested this and can't prove it as a concern with Cfront 2.0
// Anybody got any insight on this?
// Next, the whole class has been redefined as a virtual base class
// so that others may use it flexibly via inheritance.
// the previous definition had the following line:
//
// void add(ELEMENT E) { cnode = tail; list::insert(E); }
// The 'list::' qualifier would of course not helped people
// were they to copy this class via parameterization.
// Beyond this, there were some suggestions about 'inlines'.
// Is a line such as
// foo() { cnode = (head->next) ? head->next : nptr; }
// really too big to be an inline?
//
// What's a good rule of thumb for predicting the fulcrum
// between memory usage for a function's stack
// and that used by actual code inserted inline?
// Does a programmer have to calculate it byte by byte?
//
// And there's another question, notice the member add(), --
// it has a function call within its declaration, is
// the overhead for that call expanded inline too?
// -- at what cost?
//
// Further, isn't the use of 'inline' a matter of determined choice
// based on trade-offs in memory usage vs. run-time?
//
//
-- infmx!briand@pyramidbriand@infmx.UUCP (brian donat) (05/26/90)
//
// 2 of 4
//
// Ready for bite number 2? It deals with splitting up things
// over files.
//
// Believe me! This was fun to do the first time through. There
// was a point in time, when I really didn't think I knew at
// all what I was doing.
//
// First off, it appears that enum types can not be multiply
// declared in more than one header file that will later be
// #included in one source or linked object. You can't
// extern the blasted things either!
// So, don't get sucked into thinking that they'll do you a
// good turn if you use them in a class!
// After about an hour of fiddling around with enum types inside
// a class, I concluded emphatically that they should be
// totally banned from inclusion within class scope.
//
// Dr. Cline from Clarkston U. in NY emphasized this hazard
// and also demonstrated that code can be written more compactly
// without using 'boolean' as an enumeration type.
//
// Notice however, how I've used #define below.
//
// Dr. Cline also pointed out how my constructor could be compacted
// and be made more readable by using the initialization list
// feature.
//
// Discussion continued below.
---------------------------------Cut HERE---------------------------------
/////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
// \\
// vlist.c Version 2.00 \\
// VLIST class member functions: May 25, 1990, Brian L. Donat \\
// \\
/////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
#include <stdlib.h>
#include "vlist.h"
#define FALSE 0
#define TRUE 1
int listError = FALSE;
VLIST::VLIST() : listsize(0), head(new NODE), tail(new NODE), cnode(head) {
if(!head || !tail) abort(); // No Memory?!
head->previous = tail->next = 0;
head->next = tail; tail->previous = head;
}
VLIST::~VLIST() {
headend();
while(listsize) remove();
delete head; delete tail;
}
void VLIST::headend() { cnode = listsize ? head->next : head; }
void VLIST::tailend() { cnode = listsize ? tail->previous : tail; }
int VLIST::find(ELEMENT E) {
for(NODE *nptr = head; nptr->next && nptr->data != E; nptr = nptr->next);
cnode = (nptr->next) ? nptr : cnode;
return nptr->next != 0;
}
void VLIST::insert(ELEMENT E) { NODE *pptr = cnode->previous;
// If at the head of an empty list, fake an add().
if(!listsize && !cnode->previous) { cnode = tail; pptr = head; }
// build new NODE
NODE *newptr = new NODE;
newptr->data = E;
newptr->next = cnode;
newptr->previous = cnode->previous;
// Update Adjacent Nodes
pptr->next = newptr;
cnode->previous = newptr;
cnode = newptr;
listsize++;
}
void VLIST::remove(void) { listError = FALSE;
if(!listsize) listError = TRUE;
else if(!cnode->previous) listError = TRUE;
else if(!cnode->next) listError = TRUE;
else { NODE *pptr = cnode->previous;
NODE *nptr = cnode->next;
// let the previous and next NODEs reference each other.
pptr->next = cnode->next;
nptr->previous = cnode->previous;
// remove the current node.
delete cnode;
// If the next pointer is not tail, make it current,
// else make the previous pointer the current NODE.
cnode = (nptr->next) ? nptr : pptr;
listsize--;
}
}
void VLIST::step() {
cnode = cnode->next ? cnode->next : cnode;
cnode = cnode->next ? cnode : cnode->previous;
}
void VLIST::backstep() {
cnode = (cnode->previous) ? cnode->previous : cnode;
cnode = (cnode->previous) ? cnode : cnode->next;
}
ELEMENT VLIST::getval(void) const { listError = FALSE;
if(!cnode->previous || !cnode->next) listError = TRUE;
return cnode->data;
}
---------------------------------Cut HERE---------------------------------
// One of the only other odd things I noticed here is the following
// return nptr->next != 0;
// The above tidbit of code is a rather sneaky way of insuring an
// integer return type.
// True! nptr->next could be 0 or some lvalue.
// If it had been written return nptr->next however, the compiler
// bellyaches about an incompatible return type and a (int) cast
// would have to be used.
// Note too, that in the find() member that awful boolean enum type
// is blasted to kingdom come!
//
// One thing that raises questions in my mind at this point is
// error reporting. I originally defined some of these class
// members with built in error messages, but Yeccchhh! Of course,
// I didn't want to leave 'em in there.
//
// However, as an alternative, I stuck up a global 'listError' to
// communicate the error outside the class.
// Now it occurs to me that I could have used a static listError
// private to the class and provided members to get at it, but
// Yechhhh!!!
// Notice too, how I'm having to initialize listError at the top
// of every member that needs to use it.
// I suppose the best thing might be to have an internal escape,
// perhaps with setjmp() and longjmp() stuck in there, operating
// on either a static listError or still, the global.
// Anybody got a good idea on how to monitor member errors safely,
// without having to abort() or exit(), or without having to
// play with added overhead, etc...
//
-- infmx!briand@pyramidbriand@infmx.UUCP (brian donat) (05/26/90)
//
// 3 of 4
//
// Time for the redefined STACK and QUEUE classes.
//
// Well hell, the new LIST class was easy enough!
// Discussion follows below.
---------------------------------Cut HERE---------------------------------
/////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
// \\
// list.h \\
// LIST class derived from VLIST: May 25, 1990, Brian L. Donat \\
// \\
/////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
extern int listError;
extern class VLIST;
class LIST : public VLIST { };
---------------------------------Cut HERE---------------------------------
// Instant derived class. A complete alias of VLIST.
// Is this an idiotic thing to do or what?
//
// You should note that there is no #include "vlist.h" here.
// Don't do it! You'll be sorry.
// Use extern class VLIST instead! And make sure that there's
// nothing in either file that's going to cause multiply defined
// compiler errors. Unless that is, you like to spin your wheels
// for no good reason!
// Now, below is the new STACK class.
// Pretty simple? Notice how I had to get at listError?
// Helper functions are private and the definition of STACK
// has VLIST being private also to prevent usage of VLIST's
// members directly.
//
// What's interesting here is that I could have done this
// thisaway:
//
// class STACK {
// VLIST list;
// public:
//
// and maybe achieved the same thing.
// Would it be the same?
// Again, you won't find any of them blased enum booleans in here.
//
// More Discussion follows below.
---------------------------------Cut HERE---------------------------------
/////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
// \\
// stack.h Version 1.00 \\
// STACK class derived from VLIST: May 25, 1990, Brian L. Donat \\
// \\
/////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
#define MAXSIZE 20
#define stackError listError
extern int listError;
extern class VLIST;
class STACK : private VLIST {
int overflow();
int underflow();
public:
void push(ELEMENT);
ELEMENT pop();
};
---------------------------------Cut HERE---------------------------------
// And here below, for your perusal are STACK's members.
// I've made life a bit easier for genericity by declaring an ELEMENT
// EDUMMY which is a default return from pop(), when nothing should
// be returned.
// And hey! It's OK to use enum boolean here!!
// But man o' man, don't get caught with your shorts down by having
// it in a '.h' file with a class definition!
//
// I declared overflow() and underflow() inline. Are these good
// inline? I'd think so. They're only used once each!
//
// More Discussion follows below.
---------------------------------Cut HERE---------------------------------
/////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
// \\
// stack.c Version 1.00 \\
// STACK member functions : May 25, 1990, Brian L. Donat \\
// \\
/////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
#include "vlist.h"
#include "stack.h"
const ELEMENT EDUMMY = 0;
enum boolean { FALSE, TRUE };
// Note that this code is written so that
// the stack can never overflow or
// underflow. These tests is done during
// push() or pop() to see if it will
// overflow overflow or underflow will
// occur prior to actual execution.
inline int STACK::overflow() { return (boolean)(getsize() >= MAXSIZE); }
inline int STACK::underflow() { return (boolean)!getsize(); }
void STACK::push(ELEMENT E) { stackError = FALSE;
if(overflow()) stackError = TRUE; else add(E);
}
ELEMENT STACK::pop() { ELEMENT E = EDUMMY; stackError = FALSE;
if(underflow()) stackError = TRUE; else { E = getval(); remove(); }
return E;
}
---------------------------------Cut HERE---------------------------------
// Just the Queue stuff follows. You can punch out now if you like.
---------------------------------Cut HERE---------------------------------
/////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
// \\
// queue.h Version 1.00 \\
// STACK class derived from VLIST: May 25, 1990, Brian L. Donat \\
// \\
/////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
#define MAXSIZE 20
#define queueError listError
extern int listError;
extern class VLIST;
class QUEUE : private VLIST {
public:
int overflow();
int underflow();
void enqueue(ELEMENT);
ELEMENT dequeue();
};
---------------------------------Cut HERE---------------------------------
/////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
// \\
// queue.c Version 1.00 \\
// QUEUE member functions : May 25, 1990, Brian L. Donat \\
// \\
/////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
#include "vlist.h"
#include "queue.h"
const ELEMENT EDUMMY = 0;
enum boolean { FALSE, TRUE };
// Note that this code is written so that
// the queue can never overflow or
// underflow. These tests is done during
// enqueue() or dequeue() to see if it
// will overflow overflow or underflow
// will occur prior to actual execution.
int QUEUE::overflow() { return (boolean)(getsize() >= MAXSIZE); }
int QUEUE::underflow() { return (boolean)!getsize(); }
void QUEUE::enqueue(ELEMENT E) { queueError = FALSE;
if(overflow()) queueError = TRUE;
else { headend(); insert(E); } // In this queue, we feed the headend.
}
ELEMENT QUEUE::dequeue() { ELEMENT E = EDUMMY; queueError = FALSE;
if(underflow()) queueError = TRUE;
else {
tailend(); // In this queue, we ... (No Jokes Please!)
E = getval();
remove();
}
return E;
}
---------------------------------Cut HERE---------------------------------
-- infmx!briand@pyramidbriand@infmx.UUCP (brian donat) (05/26/90)
//
// 4 of 4
//
// Finally! End of discussion is immenent!
//
// Nothing much is changed in main(). Afterall it's only used to
// test and demonstrate.
// I've just added an idiotic error test VError(). I believe I
// stated that it seems rather awkward getting error info out of
// a class and across header file boundaries, didn't I?
// Yes, I did.
//
// So, I do have one or two observances at this point though.
//
// 1. As promised, I found that I could tinker and change
// class definitions without making significant changes to
// my main().
//
// 2. My reorganizing of STACK and QUEUE in classes was
// reflected by what seems a longer compile time overall.
// Keep those '.o's around. ar 'em -> lib.xxx.
//
// Thanks to those of you who took part in this little exercise.
---------------------------------Cut HERE---------------------------------
/////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
// \\
// testmain.c Version 2.00 \\
// tests for VLIST class : May 25, 1990, Brian L. Donat \\
// \\
// CC testmain.c stack.c queue.c vlist.c -o <progname> \\
// progname | more \\
// \\
/////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
//
// This program demonstrates and provides testing for the VLIST class
// and its derivatives, STACK and QUEUE.
//
/////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
#include <stream.h>
#include "vlist.h"
#include "list.h"
#include "stack.h"
#include "queue.h"
enum boolean { FALSE, TRUE };
enum errtype { STACKFULL, STACKEMPT, QUEUEFULL, QUEUEEMPT };
void listTest(), listScan(LIST &),
stackTest(),
queueTest();
int VError(int, int);
main() {
listTest();
stackTest(); cout << "\n\n" << flush;
queueTest(); cout << "\n\n" << flush;
}
void listTest() { LIST intList;
// Note the following does not test out
// the error return global listError, but
// this has been validated elsewhere as
// either stackError or queueError.
cout << "\nLINKED LIST TEST:\n";
intList.add(9);
intList.insert(3);
intList.step();
intList.insert(2);
intList.backstep();
intList.remove();
intList.step();
if(intList.find(2)) intList.insert(23);
else intList.tailend();
intList.insert(88);
intList.insert(55);
intList.add(22);
intList.headend();
intList.insert(100);
listScan(intList);
cout << "\n\n";
}
// Output the LIST, head -> tail.
void listScan(LIST &intList) {
intList.headend();
if(intList.getsize()) {
cout << "\n" << intList.getval(); intList.step();
for(int i = intList.getsize() - 1; i > 0; --i) {
cout << ", " << intList.getval(); intList.step();
}
}
else cout << "\nList is Empty!!\n\n";
}
// Build a stack from the LIST class
void stackTest(void) { STACK intStack; ELEMENT E;
cout << "\nSTACK TEST:\n";
intStack.push(1); if(VError(STACKFULL, stackError)) return;
intStack.push(2); if(VError(STACKFULL, stackError)) return;
E = intStack.pop(); if(VError(STACKEMPT, stackError)) return;
cout << "\n" << E;
intStack.push(3); if(VError(STACKFULL, stackError)) return;
intStack.push(4); if(VError(STACKFULL, stackError)) return;
E = intStack.pop(); if(VError(STACKEMPT, stackError)) return;
cout << "\n" << E;
E = intStack.pop(); if(VError(STACKEMPT, stackError)) return;
cout << "\n" << E;
E = intStack.pop(); if(VError(STACKEMPT, stackError)) return;
cout << "\n" << E;
intStack.push(5); if(VError(STACKFULL, stackError)) return;
E = intStack.pop(); if(VError(STACKEMPT, stackError)) return;
cout << "\n" << E;
E = intStack.pop(); if(VError(STACKEMPT, stackError)) return;
cout << "\n" << E << "\n\n";
}
// Build a queue from the LIST class
void queueTest(void) { QUEUE intQueue; ELEMENT E;
cout << "\nQUEUE TEST:\n";
intQueue.enqueue(1); if(VError(QUEUEFULL, queueError)) return;
intQueue.enqueue(2); if(VError(QUEUEFULL, queueError)) return;
E = intQueue.dequeue(); if(VError(QUEUEEMPT, queueError)) return;
cout << "\n" << E;
intQueue.enqueue(3); if(VError(QUEUEFULL, queueError)) return;
intQueue.enqueue(4); if(VError(QUEUEFULL, queueError)) return;
E = intQueue.dequeue(); if(VError(QUEUEEMPT, queueError)) return;
cout << "\n" << E;
E = intQueue.dequeue(); if(VError(QUEUEEMPT, queueError)) return;
cout << "\n" << E;
E = intQueue.dequeue(); if(VError(QUEUEEMPT, queueError)) return;
cout << "\n" << E;
intQueue.enqueue(5); if(VError(QUEUEFULL, queueError)) return;
E = intQueue.dequeue(); if(VError(QUEUEEMPT, queueError)) return;
cout << "\n" << E;
E = intQueue.dequeue(); if(VError(QUEUEEMPT, queueError)) return;
cout << "\n" << E << "\n\n";
}
// Yes, Yes, I agree! This is a horrible way of doing things.
// But for brevity, I'm keeping things simple and therefore
// somewhat awkward too!
int VError(int errtype, int err = listError) {
if(err) switch(errtype) {
case STACKFULL: cout << "\nError! Stack is Full!"; break;
case STACKEMPT: cout << "\nError! Stack is Empty!"; break;
case QUEUEFULL: cout << "\nError! Queue is Full!"; break;
case QUEUEEMPT: cout << "\nError! Queue is Empty!"; break;
default: cout << "\nError of Unkown Type!"; break;
}
return err;
}
-- infmx!briand@pyramid