#!/bin/sh
echo 'Start of collect, part 01 of 01:'
echo 'x - Makefile'
sed 's/^X//' > Makefile << '/'
XCC = gcc
XGXX = g++ 
XGFLAGS= -g
XLIBS = -lg++
X#     The following two rules add automaticity to c++ suffixes
X.SUFFIXES: .cc .C
X.cc.o:
X	$(GXX) $(GFLAGS) -c  $<
X.C.o:
X	$(GXX) $(GFLAGS) -c $<
X#######################################################################
Xstrtable: strtable.o collect.o 
X	$(GXX) $(GFLAGS) -o strtable strtable.o collect.o -lg++
X
Xcollect: collect.o ctest.o
X	$(GXX) $(GFLAGS) -o collect collect.o ctest.o -lg++ -lm
X
/
echo 'x - collect.cc'
sed 's/^X//' > collect.cc << '/'
X//
X//	C++ Container Class Implementation File
X//	Written by Tim Budd
X//		June, 1990
X//
X
X# include "collect.h"
X
X//
X//	virtual methods and non-inline methods from class Element
X//
X
Xint Element::operator == (Element& x) 
X{	return this == &x; }
X
Xint Element::operator != (Element& x) 
X{	return ! ( *this == x); }
X
Xunsigned Element::hash() 
X{	return 0; }
X
Xvoid Element::insert (Element& n)
X{
X	// insert new element, updating links
X	n.setLink(link);
X	setLink(&n);
X}
X
Xvoid Element::removeNext ()
X{
X	// remove next element, if there is one
X	if (link)
X		setLink(link->next());
X}
X
X//
X//	virtual methods and non-inline methods from class List
X//
X
Xvoid List::addLast(Element& x)
X{	Element *p;
X
X	p = this;
X	while (next(p)) p = next(p);
X	p->insert(x);
X}
X
Xint List::includes(Element& x)
X{	Element* p;
X
X	for (p = first(); p; p = next(p))
X		if (*p == x)
X			return 1;
X	return 0;
X}
X
XElement * List::last()
X{	Element *p;
X
X	p = first();
X	while (next(p))
X		p = next(p);
X	return p;
X}
X
Xvoid List::removeLast()
X{	Element* p;
X
X	if (! first()) return;
X	for (p = this; next(p)->next(); p = next(p));
X	p->removeNext();
X}
X
Xvoid List::removeEqual(Element& x)
X{	Element* p;
X
X	for (p = this; next(p); p = next(p))
X		if (*next(p) == x) {
X			p->removeNext();
X			return;
X			}
X}
X
Xint List::size()
X{	int i = 0;
X
X	for (Element *p = first(); p; p = next(p)) i++;
X	return i;
X}
X
X//
X//	virtual methods and non-inline methods from class Set
X//
X
Xvoid Set::add(Element& x)
X{	if (! includes(x)) 
X		List::addFirst(x); 
X}
X
X//
X//	virtual methods and non-inline methods from class OrderedElement
X//
X
Xint OrderedElement::operator < (OrderedElement& x) 
X{ 	return x > *this; }
X
Xint OrderedElement::operator <= (OrderedElement& x) 
X{ 	return (*this < x) || (*this == x); }
X
Xint OrderedElement::operator > (OrderedElement& x) 
X{ 	return x < *this; }
X
Xint OrderedElement::operator >= (OrderedElement& x) 
X{	return x <= *this; }
X
X//
X//	virtual methods and non-inline methods from class Ordered
X//
X
Xvoid Ordered::add(OrderedElement& x)
X{	OrderedElement *p;
X
X	p = first();
X	// base cases - empty list or first element
X	if ((!p) || (x < *p)) {
X		List::addFirst(x);
X		return;
X		}
X
X	// looping case, loop until we find right location
X	for (; next(p); p = next(p))
X		if (x < *next(p)) {
X			List::addAfter(p, x);
X			return;
X			}
X	List::addAfter(p, x);
X}
X
X//
X//-------------------------------------------- Association
X//
X
Xclass Association : public Element
X{
X	friend class Table;
X
Xpublic:
X	Association (Element& x);	// constructor - arg is key
X
X	int virtual 	operator == (Element& x) ;
X
Xprotected:
X	Element*	associationKey;	
X	Element*	associationValue;
X	Element&	key() ;
X	Element*&	value();
X};
X
Xinline Element&	Association::key() 
X{ 	return *associationKey; }
X
Xinline Element*& Association::value() 
X{ 	return associationValue; }
X
Xinline Association::Association(Element& x)
X{ 	associationKey = &x; associationValue = (Element *) 0; } 
X
X//
X//-------------------------------------------- AssociationList
X//
X
Xclass AssociationList : public List
X{
Xpublic:
X	AssociationList() : List() {;}
X
X	void 		add(Association& x);
X	Association *	first(); 
X	Association *	next(Association* x); 
X};
X
Xinline void AssociationList::add(Association& x)
X{	List::addFirst(x); }
X
Xinline Association* AssociationList::first ()
X{ 	return (Association *) List::first(); }
X
Xinline Association * AssociationList::next(Association* x)
X{	return (Association *) List::next(x); }
X
X//
X//
X//	virtual methods and non-inline methods from class Association
X//
X
Xint Association::operator == (Element& x) 
X{
X	return key() == x;
X}
X
X//
X//	virtual methods and non-inline methods from class Table
X//
X
XTable::Table (int sz)
X{ 	tablesize = sz; 
X	elements = new AssociationList[tablesize]; 
X} 
X
XElement*& Table::operator [] (Element& x)
X{ 	Association* p;
X	AssociationList& list = elements[x.hash() % tablesize];
X
X	// see if already there
X	for (p = list.first(); p; p = list.next(p))
X		if (*p == x) 
X			return p->value();
X
X	// not there, make new association
X	p = new Association(x);
X 	list.add(*p);
X	return p->value(); 
X}
X
Xint Table::size()
X{ 	int i; int sz = 0;
X  	for (i = 0; i < tablesize; i++)
X		sz += elements[i].size();
X	return sz;
X}
X
XList& Table::keys()
X{ 	List& theList = *new List;
X	Association* p;
X	int i;
X
X	for (i = 0; i < tablesize; i++) {
X		for (p = elements[i].first(); p; p = elements[i].next(p))
X			theList.addFirst(p->key());
X		}
X	return theList; 
X}
X
XList& Table::values()
X{ 	List& theList = *new List;
X	Association* p;
X	int i;
X
X	for (i = 0; i < tablesize; i++) {
X		for (p = elements[i].first(); p; p = elements[i].next(p))
X			theList.addFirst(*(p->value()));
X		}
X	return theList; 
X}
X
Xint Table::includesKey (Element& x)
X{ 	return elements[x.hash() % tablesize].includes(x); }
X
Xvoid Table::removeKey(Element& x)
X{ 	elements[x.hash() % tablesize].removeEqual(x); }
/
echo 'x - ctest.cc'
sed 's/^X//' > ctest.cc << '/'
X//
X//	routines to test the C++ container classes
X//
X# include <stdio.h>
X# include "collect.h"
X
X//
X//	IntElement - integer elements
X//		elements which maintain integer values
X//
Xclass IntElement : public OrderedElement {
X
Xprotected:
X	int value;
X
X	int relation (int);
X
Xpublic:
X	IntElement (int i) : OrderedElement() { value = i; }
X
X	unsigned virtual hash();
X
X	int virtual operator== (Element&);
X	int virtual operator< (OrderedElement&);
X
X	int &	intReference();
X	void display();
X};
X
Xunsigned IntElement::hash() 
X{ return (unsigned) value; }
X
Xint &	IntElement::intReference() 
X{ return value; }
X
Xvoid IntElement::display() 
X{ printf(" %d ", value); }
X
X// relation is used to compare two integer values
Xint IntElement::relation(int i) 
X{ 
X	if (i < value) return 1; 
X	else if (i == value) return 0; 
X	return -1;
X}
X
X// define equality and relations in terms of underlying integers
Xint IntElement::operator == (Element& x) 
X{	return (0 == ((IntElement *) &x)->relation(value)); }
X
Xint IntElement::operator < (OrderedElement& x) 
X{	return (0 < ((IntElement *) &x)->relation(value)); }
X
X
X//
X//	Now define collections which manipulate integer elements specifically
X//
Xclass IntList : public List {
Xpublic:
X	IntElement * 	first ();
X	IntElement * 	next (IntElement *);
X	IntElement * 	last ();
X	void		add (int);
X	void		addFirst (int);
X	void		addLast (int); 
X	void		remove (int); 
X	void		print();
X};
X
XIntElement * IntList::first() 
X{ return (IntElement *) List::first(); }
X
XIntElement * IntList::next(IntElement * x) 
X{ return (IntElement *) List::next(x); }
X
XIntElement * IntList::last() 
X{ return (IntElement *) List::last(); }
X
Xvoid IntList::add(int i) 
X{ List::addFirst(* new IntElement(i)); }
X
Xvoid IntList::addFirst(int i) 
X{ List::addFirst(* new IntElement(i)); }
X
Xvoid IntList::addLast(int i) 
X{ List::addLast(* new IntElement(i)); }
X
Xvoid IntList::remove(int i)  
X{ List::removeEqual(* new IntElement(i)); }
X
Xvoid IntList::print()
X{	IntElement* p;
X
X	for (p = first(); p; p = next(p))
X		p->display();
X	printf("\n");
X};
X
Xclass IntSet : public Set {
Xpublic:
X	IntElement * 	first () ;
X	IntElement * 	next (IntElement *);
X	void		print ();
X	void		add (int);
X	void		remove (int);
X	IntSet&		operator += (int);
X};
X
XIntElement * 	IntSet::first() 
X{ return (IntElement *) Set::first(); }
X
XIntElement * 	IntSet::next(IntElement * x) 
X{ return (IntElement *) Set::next(x); }
X
Xvoid		IntSet::add(int i) 
X{ Set::add(* new IntElement(i)); }
X
Xvoid		IntSet::remove(int i) 
X{ Set::remove(* new IntElement(i)); }
X
XIntSet&		IntSet::operator += (int x)
X{ add(x); return *this; }
X
Xvoid IntSet::print()
X{	IntElement* p;
X
X	for (p = first(); p; p = next(p))
X		p->display();
X	printf("\n");
X};
X
Xclass IntOrdered : public Ordered {
Xpublic:
X	IntElement * 	first ();
X	IntElement * 	next (IntElement *);
X	void	print ();
X	void	add (int); 
X	void	remove (int);
X};
X
XIntElement * 	IntOrdered::first() 
X{ return (IntElement *) Ordered::first(); }
X
XIntElement * 	IntOrdered::next(IntElement * x) 
X{ return (IntElement *) Ordered::next(x); }
X
Xvoid	IntOrdered::add(int i) 
X{ Ordered::add(* new IntElement(i)); }
X
Xvoid	IntOrdered::remove(int i) 
X{ Ordered::remove(* new IntElement(i)); }
X
Xvoid IntOrdered::print()
X{	IntElement* p;
X
X	for (p = first(); p; p = next(p))
X		p->display();
X	printf("\n");
X};
X
Xclass IntTable : public Table {
Xpublic:
X	IntList&	keys();
X	IntList&	values();
X	int		includesKey (int); 
X	void		removeKey (int);
X	int&		operator [] (int);
X};
X
XIntList& IntTable::keys()	 
X{ return (IntList&) Table::keys(); }
X
XIntList& IntTable::values() 
X{ return (IntList&) Table::values(); }
X
Xint IntTable::includesKey(int i) 
X{ return Table::includesKey(* new IntElement(i));}
X
Xvoid IntTable::removeKey(int i) 
X{ Table::removeKey(* new IntElement(i));}
X
Xint& IntTable::operator [] (int i)
X{	Element*& x = Table::operator[](* new IntElement(i));
X	// if not there, make new element
X	if (!x) x = new IntElement(0);
X	return ((IntElement *) x)->intReference();
X}
X	
X
Xmain() {
X	IntList A;
X
X	printf("List tests\n");
X	// first add a new elements 
X	A.addFirst(5);
X	A.add(23);
X	A.addFirst(4);
X	A.addLast(6);
X	A.print();
X	printf("size is %d\n", A.size());
X
X	// display the first and last elements
X	printf("first last ");
X	A.first()->display();
X	A.last()->display();
X	printf("\n");
X
X	// try removing a few
X	printf("remove element ");
X	A.remove(23);
X	A.print();
X	printf("remove first ");
X	A.removeFirst();
X	A.print();
X	printf("remove last ");
X	A.removeLast();
X	A.print();
X
X	printf("Set test\n");
X	IntSet S;
X
X	// add a few elements to the set
X	S.add(12);
X	(S += 14) += 23;
X	S.add(12);
X	S.print();
X	// remove the element that was added twice
X	S.remove(12);
X	S.print();
X	printf("size is %d\n", S.size());
X
X	printf("Ordered Test\n");
X	IntOrdered B;
X
X	// put one value into test
X	B.add(12);
X	// display it
X	B.print();
X
X	B.add(14);
X	B.print();
X	B.add(10);
X	B.print();
X	printf("size is %d\n", B.size());
X
X	IntTable T;
X	int i;
X
X	for (i = 7; i < 200; i += 7)
X		T[i] = -i;
X
X	printf("keys ");
X	IntList &k = T.keys(); 
X	k.print();
X
X	printf("values ");
X	IntList &v = T.values(); 
X	v.print();
X
X	printf("size %d\n", T.size());
X
X	printf("includes tests %d %d %d\n", T.includesKey(14), 
X		T.includesKey(-14), T.includesKey(15));
X
X	T.removeKey(14);
X
X	printf("size %d\n", T.size());
X
X	printf("includes tests %d %d %d\n", T.includesKey(14), 
X		T.includesKey(-14), T.includesKey(15));
X}
/
echo 'x - strtable.cc'
sed 's/^X//' > strtable.cc << '/'
X//
X# include <stdio.h>
X//	String Tables -
X//		Associative arrays with string keys and values
X//		Uses the Container Classes described in
X//		``An Introduction to Object Oriented Programming''
X//
X//		Written by Tim Budd, Oregon State University, July 1990
X//
X
X# include "strtable.h"
X
Xextern "C" {
Xint strlen(char *);
Xvoid strcpy(char *, char *);
X};
X
X//
X//	StrElements are the elements placed into StrTables
X//
X
XStrElement::StrElement(char * text) : Element()
X{
X	value = new char[1+strlen(text)];
X	strcpy(value, text);
X}
X
X//	the hash value is simply the first character
Xunsigned StrElement::hash()
X{	return *value; }
X
X// 	equality is simply string equality
Xint StrElement::operator == (Element& x)
X{	char *p, *q;
X	
X	p = value;
X	q = ((StrElement&) x).value;
X	while (*p)
X		if (*p++ != *q++) {
X			return 0;
X			}
X	return 1;
X}
X
Xvoid StrElement::operator = (char * text)
X{
X	value = new char[1+strlen(text)];
X	strcpy(value, text);
X}
X
X//
X// StrTable  is the actual associative array class
X//
X
Xint	StrTable::includesKey(char * text)
X{
X	StrElement x(text);
X	return Table::includesKey(x);
X}
X
Xvoid	StrTable::removeKey(char * text)
X{
X	StrElement x(text);
X	return Table::removeKey(x);
X}
X
XStrElement& StrTable::operator[](char * text)
X{
X	StrElement *x = new StrElement(text);
X	Element*& y = Table::operator[](*x);
X	if (y) 	 // was there already, can get rid of x
X		delete x;
X	else 	// wasn't there, make new element
X		y = new StrElement("init");
X	return *((StrElement *) y);
X}
X
X
Xmain() {
X	StrTable x;
X
X	x["abc"] = "def";
X	x["ghi"] = "xxx";
X
X	printf("includes %d %d\n", x.includesKey("abc"),
X	x.includesKey("yyy"));
X	printf("values %s %s %s\n", x["abc"].text(), x["ghi"].text(), 
X			x["www"].text());
X}
/
echo 'x - collect.h'
sed 's/^X//' > collect.h << '/'
X//
X//	C++ Container Class Definitions
X//	Written by Tim Budd
X//		June, 1990
X//
X
X//
X//-------------------------------------------- Element
X//	the basic elements of a linked list
X//
X
Xclass Element 
X{
X	friend class List;
X
Xpublic:
X	Element();
X
X	int virtual 	operator == (Element& x) ;
X	int virtual 	operator != (Element& x) ;
X	unsigned virtual hash() ;
X
Xprotected:
X	Element * 	link;
X	Element *	next ();
X	void 		setLink (Element* n);
X	void		insert (Element& n);
X	void		removeNext ();
X};
X
Xinline Element::Element() 
X{	link = (Element *) 0; }
X
Xinline void Element::setLink(Element* n) 
X{	link = n; }
X
Xinline Element* Element::next()
X{	return link; }
X
X//
X//-------------------------------------------- List
X//
X
Xclass List : private Element  {
Xpublic:
X	List() : Element() {;}
X
X	void 		addFirst (Element& x);
X	void 		addLast (Element& x);
X	Element *	first ();
X	int 		includes (Element& x);
X	int 		isEmpty ();
X	Element *	last ();
X	Element *	next (Element* x);
X	void 		removeEqual (Element& x);
X	void 		removeFirst ();
X	void 		removeLast ();
X	int 		size ();
X
Xprotected:
X	void		addAfter(Element* x, Element& y);
X};
X
Xinline void List::addFirst(Element& x)
X{	Element::insert(x); }
X
Xinline Element* List::first()
X{	return Element::next(); }
X
Xinline int List::isEmpty() 
X{	return first() == 0; }
X
Xinline Element* List::next(Element* x)
X{	return x->next(); }
X
Xinline void List::addAfter(Element* x, Element& y)
X{	 x->insert(y);}
X
Xinline void List::removeFirst()
X{	List::removeNext(); }
X//
X//-------------------------------------------- Set
X//
X
Xclass Set : private List {
Xpublic:
X	Set() : List() {;}
X
X	void 		add (Element& x);
X	Element *	first();
X	int 		includes (Element& x);
X	Element *	next(Element* x);
X	void 		remove (Element& x);
X	int 		size ();
X};
X
Xinline void Set::remove(Element& x)
X{	List::removeEqual(x); }
X
Xinline int Set::includes(Element& x)
X{	return List::includes(x); }
X
Xinline int Set::size() 
X{	return List::size(); }
X
Xinline Element* Set::first()
X{	return List::first(); }
X
Xinline Element* Set::next(Element* x)
X{	return List::next(x); }
X
X//
X//-------------------------------------------- OrderedElement
X//
X
Xclass OrderedElement : public Element {
Xpublic:
X
X	OrderedElement() : Element() {;}
X
X 	int virtual 		operator <  (OrderedElement& x) ;
X	int virtual 		operator <= (OrderedElement& x) ;
X	int virtual 		operator >  (OrderedElement& x) ;
X	int virtual 		operator >= (OrderedElement& x) ;
X};
X
X//
X//-------------------------------------------- Ordered
X//
X
Xclass Ordered : private List {
Xpublic:
X	Ordered() : List() {;}
X
X	void 			add (OrderedElement& x);
X	OrderedElement *	first();
X	int 			includes (OrderedElement& x);
X	OrderedElement *	max();
X	OrderedElement *	min();
X	OrderedElement *	next(OrderedElement* x);
X	void 			remove (OrderedElement& x);
X	int 			size ();
X};
X
Xinline OrderedElement* Ordered::first()
X{ 	return (OrderedElement *) List::first(); }
X
Xinline OrderedElement* Ordered::next(OrderedElement* x)
X{	return (OrderedElement *) List::next(x); }
X
Xinline void Ordered::remove(OrderedElement& x)
X{	List::removeEqual(x); }
X
Xinline int Ordered::includes(OrderedElement& x)
X{	return List::includes(x); }
X
Xinline int Ordered::size() 
X{	 return List::size(); }
X
Xinline OrderedElement *	Ordered::min()
X{	return (OrderedElement *) List::first(); }
X
Xinline OrderedElement *	Ordered::max()
X{	return (OrderedElement *) List::last(); }
X
X//
X//-------------------------------------------- Table
X//
X
Xclass AssociationList;		// forward declaration
X
Xclass Table
X{
Xpublic:
X	Table (int sz = 17);		// constructor - size of table
X
X	int 		includesKey (Element& x);
X	List& 		keys ();
X	void 		removeKey (Element& x);
X	int 		size ();
X	List& 		values ();
X	Element*& 	operator [] (Element& x);
X
Xprotected:
X	int tablesize;			// size of the table
X	AssociationList *elements;	// table values
X
X};
X
/
echo 'x - strtable.h'
sed 's/^X//' > strtable.h << '/'
X//
X//	interface file for
X//	String Tables -
X//		Associative arrays with string keys and values
X//		Uses the Container Classes described in
X//		``An Introduction to Object Oriented Programming''
X//
X//		Written by Tim Budd, Oregon State University, July 1990
X//
X
X# include "collect.h"
X
Xclass StrElement : public Element {
X
Xpublic:
X	StrElement (char *);
X
X	unsigned virtual 	hash();
X	int virtual 		operator == (Element&);
X	void 			operator = (char *);
X	char * text();
X
Xprotected:
X	char *	value;
X};
X
Xinline char * StrElement::text()
X{	return value; }
X
Xclass StrTable : public Table {
Xpublic:
X	int		includesKey(char *);
X	void		removeKey(char *);
X	StrElement&	operator[](char *);
X};
/
echo 'Part 01 of collect complete.'
exit