#!/bin/sh
# This is a shar archive.
# The rest of this file is a shell script which will extract:
#
# 5_4.cmp 5_4.h 5_4a.c 5_4b.c 5_4c.c 5_4d.c 5_4tst.c makefile
#
# To extract the files from this shell archive file simply
# create a directory for this file, move the archive file
# to it and enter the command
#
#	sh filename
# 
# The files will be extracted automatically.
# Note: Do not use csh.
#
# Archive created: Mon Jul 30 23:03:23 EDT 1990
#
echo x - 5_4.cmp
sed 's/^X//' > 5_4.cmp << '!EOF!'
member(of) = 0
member(of) = 1
i = 0, 'a'
i = 1, 'black'
i = 2, 'brown'
i = 3, 'dog'
i = 4, 'fox'
i = 5, 'hello'
i = 6, 'is'
i = 7, 'jumped'
i = 8, 'lazy'
i = 9, 'lists'
i = 10, 'of'
i = 11, 'over'
i = 12, 'quick'
i = 13, 'test'
i = 14, 'the'
i = 15, 'the'
i = 16, 'there'
i = 17, 'this'
!EOF!
ls -l 5_4.cmp
echo x - 5_4.h
sed 's/^X//' > 5_4.h << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// node set <nodeset.h>
// Exercise 5.4
#ifndef NODESET_H
#define NODESET_H

struct tnode
{
    char *tword;
    int count;
    tnode *left, *right;
    tnode(char*);
    ~tnode();
};

typedef int (*i_f_ptn_ptn)(tnode*, tnode*);

class nodeset
{
    int cursize, maxsize;
    tnode **x;
    i_f_ptn_ptn cmp;

public:
    nodeset(int m, i_f_ptn_ptn cmp); // at most m nodes
    ~nodeset();

    int member(tnode* t);	// is "t" a member?
    void insert(tnode* t);	// add "t" to set

    void iterate(int& i)	{ i = 0; }
    int ok(int& i)		{ return i < cursize; }
    tnode* next(int& i)		{ return x[i++]; }
};
#endif /* NODESET_H */
!EOF!
ls -l 5_4.h
echo x - 5_4a.c
sed 's/^X//' > 5_4a.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// create a node set
nodeset::nodeset(int m, i_f_ptn_ptn cfn)
{
    if (m < 1)	error("illegal nodeset size");
    cursize = 0;
    maxsize = m;
    cmp = cfn;
    x = new tnode*[maxsize];
}
!EOF!
ls -l 5_4a.c
echo x - 5_4b.c
sed 's/^X//' > 5_4b.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// delete a node set
nodeset::~nodeset()
{
    for (int i = 0; i < cursize; i++)
	delete x[i];
    delete x;
}
!EOF!
ls -l 5_4b.c
echo x - 5_4c.c
sed 's/^X//' > 5_4c.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// insert a node into the node set
void nodeset::insert(tnode* t)
{
    if (++cursize > maxsize)
        error("too many elements");
    int i = cursize - 1;
    x[i] = new tnode(t->tword);
    
    while (i > 0 && (*cmp)(x[i-1], x[i]) > 0) {
        tnode* t = x[i];	// swap x[i] & x[i-1]
	x[i] = x[i-1];
	x[i-1] = t;
	i--;
    }
}
!EOF!
ls -l 5_4c.c
echo x - 5_4d.c
sed 's/^X//' > 5_4d.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// is `s' a member of the node set?
int nodeset::member(tnode* t)	// binary search
{
    int l = 0;
    int u = cursize - 1;
    
    while (l <= u) {
        int m = (l + u) / 2;
	int cmpval = (*cmp)(t, x[m]);
	if (cmpval < 0)
	    u = m - 1;
	else if (cmpval > 0)
	    l = m + 1;
	else
	    return 1;	// found
    }
    return 0;		// not found
}
!EOF!
ls -l 5_4d.c
echo x - 5_4tst.c
sed 's/^X//' > 5_4tst.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
#include <stream.h>
#include <string.h>
#include <error.h>
#include "5_4.h"		// class tnode, class nodeset
#include "5_4a.c"		// nodeset::nodeset
#include "5_4b.c"		// nodeset::~nodeset
#include "5_4c.c"		// nodeset::insert
#include "5_4d.c"		// nodeset::member

char *x[] =
{
    "hello", "there", "this", "is", "a", "test", "of", "lists",
    "the", "quick", "brown", "fox", "jumped", "over", "the", "lazy", "black", "dog", 0
};

int nodecmp(tnode *t1, tnode *t2)
{
    return strcmp(t1->tword, t2->tword);
}

// constructor for a tnode

tnode:: tnode(char *s)
{
    count = 1;
    tword = new char[strlen(s)+1];
    strcpy(tword, s);
    left = right = 0;
}

// destructor for a tnode

tnode:: ~tnode()
{
    delete tword;

    if (left)
	delete left;

    if (right)
	delete right;
}

main()
{
    nodeset s(30, nodecmp);

    tnode *of = new tnode("of");
    cout << "member(of) = " << s.member(of) << "\n";

    for (char **xp = x; *xp; xp++)
	s.insert(new tnode(*xp));

    cout << "member(of) = " << s.member(of) << "\n";

    int i;
    for (s.iterate(i); s.ok(i); )
	{
	cout << "i = " << i << ", '";
	tnode *t = s.next(i);
	cout << t->tword << "'\n";
	}
    return 0;
}

!EOF!
ls -l 5_4tst.c
echo x - makefile
sed 's/^X//' > makefile << '!EOF!'
CC= CC -I. -I../../CC
ERROR=  ../../error.o
CFLAGS= -I.

all: 5_4tst

5_4tst: 5_4.h 5_4a.c 5_4b.c 5_4c.c 5_4d.c 5_4tst.c
	$(CC) $(CFLAGS) 5_4tst.c -o 5_4tst $(ERROR)

CMP= 5_4.cmp
OUT= 5_4.out

5_4.out: 5_4tst ;	5_4tst > 5_4.out

test: all $(OUT) $(CMP)
	cmp 5_4.out 5_4.cmp
	echo tests done
!EOF!
ls -l makefile
# The following exit is to ensure that extra garbage 
# after the end of the shar file will be ignored.
exit 0