jonasn@ttds.UUCP (Jonas Nygren) (03/09/89)
There have been a few requests for software IC's written in C++. Below you
find a shar file with an implementation of Simulas simset-class in C++.
Simset is a general double-directed list facility with two classes which
you can use as base-classes for your own derived classes. I call this
set of classes for cset and they are found in the files cset.{h,c}.
Here is an example of how you could use cset to implement a list-container
class similar to the slist-class described in 'The C++ Programming Language',
para 7.3.1, although the list-handling primitives are taken from simset and
I don't use the nifty iterator class. (You find this example code in file
slist.c in the shar file below):
#include <stream.h>
#define generic entry
#include "cset.h"
typedef void *ent;
class entry : public link{
public:
ent e;
entry(ent a) { e = a; }
};
main(){
head *slist;
entry *sp;
int i = 1;
slist = new head;
new entry((ent)1)->into(slist);
(sp = new entry((ent)2))->into(slist);
new entry((ent)4)->into(slist);
new entry((ent)3)->follow(sp);
sp->pred()->follow(sp->suc());
cout << "Length of slist: " << slist->cardinal() << ".\n\n";
for(sp = slist->first(); sp; sp = sp->suc())
cout << "Entry " << i++ << " : " << (int)sp->e << ".\n";
}
A list element in slist consists of an instance of the entry-class which
is derived from the link-class. Here follows the class hierarchy together
with their member functions:
linkage
- suc
- pred
- prev
/ \
listhead link
- first - out
- last - follow
- empty - precede
- cardinal - into
! !
head entry
- <public listhead> - ?
To implement these classes I have used a special construction which I have
named 'generic'. Generic is used to allow base classes to know about the yet
undefined derived classes, in the code above generic replaces the entry-class.
The generic is implemented with preprocessor macros and that is why the
'#include cset.h' is preceeded by a '#define generic entry'. Please
study the cset implementation for a full understanding.
If my construction don't correspond with current C-coding practise or if
you find my bugs, would you please let me know. This is my first C++ program.
Answer by email if possible.
/jonas
PS Run examble by: CC cset.c slist.c ; a.out DS
------- here comes the code
: This is a shar archive. Extract with sh, not csh.
: This archive ends with exit, so do not worry about trailing junk.
echo 'Extracting cset.c'
sed 's/^X//' > cset.c << '+ END-OF-FILE cset.c'
X
X/*
X CSET - double-linked lists for C++.
X ===================================
X
X The cset implementation is based on the SIMSET description in
X a swedish Simula-bok, ISBN 91-85484-02-4, Y Sundblad och O Leringe.
X
X The cset-code is free to use for any purpose whatsoever.
X
X Jonas Nygren
X
X*/
X
X#include <stream.h>
X
X#define generic link
X
X#include "cset.h"
X
Xgeneric *link::out(){
X if(SUC && PRED){
X PRED->SUC = SUC;
X SUC->PRED = PRED;
X PRED = SUC = 0;
X --HEAD->nelem;
X HEAD = 0;
X }
X return((generic *) this);
X}
X
Xvoid link::follow(generic *gp){
X linkage *p = (linkage *)gp;
X out();
X if(p && p->SUC){
X PRED = p;
X SUC = p->SUC;
X p->SUC = SUC->PRED = (linkage *)this;
X HEAD = p->HEAD;
X ++HEAD->nelem;
X }
X}
X
Xvoid link::precede(generic *gp){
X linkage *p = (linkage *)gp;
X out();
X if(p && p->PRED){
X PRED = p->PRED;
X SUC = p;
X p->PRED = PRED->SUC = (linkage *)this;
X HEAD = p->HEAD;
X ++HEAD->nelem;
X }
X}
X
Xvoid link::into(class head *s){
X precede((generic *)s);
X}
X
Xvoid listhead::clear() {
X link *p;
X
X while(p = suc()) p->out();
X}
X
X#undef generic
X
+ END-OF-FILE cset.c
chmod 'u=rw,g=r,o=r' 'cset.c'
echo ' -rw-r--r-- 1 jonasn 1251 Mar 8 14:49 cset.c (as sent)'
echo -n ' '
/bin/ls -l cset.c
echo 'Extracting cset.h'
sed 's/^X//' > cset.h << '+ END-OF-FILE cset.h'
X
X/*
X CSET - double-linked lists for C++.
X ===================================
X
X The cset implementation is based on the SIMSET description in
X a swedish Simula-bok, ISBN 91-85484-02-4, Y Sundblad och O Leringe.
X
X The cset-code is free to use for any purpose whatsoever.
X
X Jonas Nygren
X
X*/
X
Xclass linkage{
Xpublic:
X class linkage *SUC, *PRED;
X class listhead *HEAD;
X class generic *suc() {
X return((generic *)(SUC == (linkage *)HEAD ? 0 : SUC)); }
X class generic *pred() {
X return((generic *)(PRED == (linkage *)HEAD ? 0 : PRED)); }
X class linkage *prev(){ return(PRED); }
X};
X
Xclass link : linkage {
Xpublic:
X linkage::suc;
X linkage::pred;
X generic *out();
X void follow(generic *p);
X void precede(generic *p);
X void into(class head *s);
X};
X
Xclass listhead : linkage {
Xpublic:
X int nelem;
X
X linkage::suc;
X listhead() {
X SUC = PRED = (linkage *) this;
X HEAD = this;
X nelem = 0;
X }
X
X generic *first() { return(suc()); }
X generic *last() { return(pred()); }
X
X int empty() { return(nelem); }
X int cardinal() { return(nelem); }
X
X void clear();
X};
X
Xclass head : public listhead {
X listhead::first;
X listhead::last;
X listhead::empty;
X listhead::cardinal;
X listhead::clear;
X};
+ END-OF-FILE cset.h
chmod 'u=rw,g=r,o=r' 'cset.h'
echo ' -rw-r--r-- 1 jonasn 1273 Mar 8 14:47 cset.h (as sent)'
echo -n ' '
/bin/ls -l cset.h
echo 'Extracting cset.o'
sed 's/^X//' > cset.o << '+ END-OF-FILE cset.o'
+ END-OF-FILE cset.o
chmod 'u=rw,g=r,o=r' 'cset.o'
echo ' -rw-r--r-- 1 jonasn 933 Mar 8 14:50 cset.o (as sent)'
echo -n ' '
/bin/ls -l cset.o
echo 'Extracting slist.c'
sed 's/^X//' > slist.c << '+ END-OF-FILE slist.c'
X#include <stream.h>
X
X#define generic entry
X#include "cset.h"
X
Xtypedef void *ent;
X
Xclass entry : public link{
Xpublic:
X ent e;
X
X entry(ent a) { e = a; }
X};
X
Xmain(){
X head *slist;
X entry *sp;
X int i = 1;
X
X slist = new head;
X new entry((ent)1)->into(slist);
X (sp = new entry((ent)2))->into(slist);
X new entry((ent)4)->into(slist);
X new entry((ent)3)->follow(sp);
X sp->pred()->follow(sp->suc());
X
X cout << "Length of slist: " << slist->cardinal() << ".\n\n";
X for(sp = slist->first(); sp; sp = sp->suc())
X cout << "Entry " << i++ << " : " << (int)sp->e << ".\n";
X}
X
+ END-OF-FILE slist.c
chmod 'u=rw,g=r,o=r' 'slist.c'
echo ' -rw-r--r-- 1 jonasn 564 Mar 8 13:35 slist.c (as sent)'
echo -n ' '
/bin/ls -l slist.c
exit 0