#!/bin/sh
# This is a shar archive.
# The rest of this file is a shell script which will extract:
#
# 5_3.cmp 5_3.h 5_3a.c 5_3b.c 5_3c.c 5_3d.c 5_3tst.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:13 EDT 1990
#
echo x - 5_3.cmp
sed 's/^X//' > 5_3.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_3.cmp
echo x - 5_3.h
sed 's/^X//' > 5_3.h << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// string set <strset.h>
class strset
{
    int cursize, maxsize;
    char **x;

public:
    strset(int m);		// at most m strs
    ~strset();

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

    void iterate(int& i)	{ i = 0; }
    int ok(int& i)		{ return i < cursize; }
    char* next(int& i)		{ return x[i++]; }
};
!EOF!
ls -l 5_3.h
echo x - 5_3a.c
sed 's/^X//' > 5_3a.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// create a string set
strset::strset(int m)	// at most "m" strings
{
    if (m < 1)	error("illegal strset size");
    cursize = 0;
    maxsize = m;
    x = new char*[maxsize];
}
!EOF!
ls -l 5_3a.c
echo x - 5_3b.c
sed 's/^X//' > 5_3b.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// delete a string set
strset::~strset()
{
    for (int i = 0; i < cursize; i++)
	delete x[i];
    delete x;
}
!EOF!
ls -l 5_3b.c
echo x - 5_3c.c
sed 's/^X//' > 5_3c.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// insert a string into the string set
#include <string.h>
#include <swap.h>

void strset::insert(char* t)
{
    if (++cursize > maxsize)
        error("too many elements");

    int i = cursize - 1;
    x[i] = new char[strlen(t) + 1];
    strcpy(x[i], t);
    
    for ( ; (i > 0) && (strcmp(x[i-1], x[i]) > 0); i--)
	swap(x[i-1], x[i]);
}
!EOF!
ls -l 5_3c.c
echo x - 5_3d.c
sed 's/^X//' > 5_3d.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 string set?
int strset:: member(char* t)	// binary search
{
    int lower = 0;
    int upper = cursize - 1;

    while (lower <= upper)
	{
	int middle = (lower + upper) / 2;
	int cmpval = strcmp(t, x[middle]);

	if (cmpval < 0)
	    upper = middle - 1;

	else if (cmpval > 0)
	    lower = middle + 1;

	else
	    return 1;	// found
	}

    return 0;		// not found
}
!EOF!
ls -l 5_3d.c
echo x - 5_3tst.c
sed 's/^X//' > 5_3tst.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 <error.h>

#include "5_3.h"	// class strset
#include "5_3a.c"	// strset::strset
#include "5_3b.c"	// strset::~strset
#include "5_3c.c"	// strset::insert
#include "5_3d.c"	// strset::member

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

main()
{
    strset s(30);

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

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

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

    int i;
    for (s.iterate(i); s.ok(i); )
	{
	cout << "i = " << i << ", '";
	char *t = s.next(i);
	cout << t << "'\n";
	}
    return 0;
}
!EOF!
ls -l 5_3tst.c
echo x - makefile
sed 's/^X//' > makefile << '!EOF!'
CC= CC -I. -I../../CC
ERROR=  ../../error.o
CFLAGS= -I.

all: 5_3tst

5_3tst: 5_3.h 5_3a.c 5_3b.c 5_3c.c 5_3d.c 5_3tst.c
	$(CC) $(CFLAGS) 5_3tst.c -o 5_3tst $(ERROR)

OUT= 5_3.out
CMP= 5_3.cmp

5_3.out: 5_3tst ;	5_3tst > 5_3.out

test: all $(OUT) $(CMP)
	cmp 5_3.out 5_3.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