#!/bin/sh
# This is a shar archive.
# The rest of this file is a shell script which will extract:
#
# 4_7.c 4_7A.cmp 4_7A.h 4_7B.cmp 4_7B.h 4_7a.c 4_7b.c 4_7c.c 4_7d.c 4_7e.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:02:10 EDT 1990
#
echo x - 4_7.c
sed 's/^X//' > 4_7.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
#ifdef TESTA
# include "4_7A.h"			/* class tnode */
# include "4_7b.c"			/* void addnode(tree, char*) */
#endif

#ifdef TESTB
# include "4_7B.h"			/* class tnode */
# include "4_7e.c"			/* void addnode(tree, char*) */
#endif

#include "4_7a.c"			/* tree newtree() */
#include "4_7c.c"			/* void printtree(tree) */
#include "4_7d.c"			/* void aprinttree(tree) */

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

main()
{
    tree t = newtree();

    for (char **xp = x; *xp; xp++)
	addnode(t, *xp);

    cout << "tree:\n";
    printtree(t);
    cout << "alphabetic tree:\n";
    aprinttree(t);
    return 0;
}
!EOF!
ls -l 4_7.c
echo x - 4_7A.cmp
sed 's/^X//' > 4_7A.cmp << '!EOF!'
tree:
hello 1
 a 1
  brown 1
   black 1
   fox 1
    dog 1
 there 1
  is 1
   test 1
    of 1
     lists 1
      jumped 1
       lazy 1
     quick 1
      over 1
    the 2
  this 1
alphabetic tree:
a
black
brown
dog
fox
hello
is
jumped
lazy
lists
of
over
quick
test
the
there
this
!EOF!
ls -l 4_7A.cmp
echo x - 4_7A.h
sed 's/^X//' > 4_7A.h << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// tnode.h: definitions for a binary tree
// version 1
#ifndef TNODE_H
# define TNODE_H
struct tnode		// tree node
{
    char tword[20];
    int count;		// reference count
    tnode *left;
    tnode *right;
};

typedef tnode **tree;

extern tree newtree();
extern void addnode(tree, char *);
extern void printtree(tree);
extern void aprinttree(tree);
#endif /* TNODE_H */
!EOF!
ls -l 4_7A.h
echo x - 4_7B.cmp
sed 's/^X//' > 4_7B.cmp << '!EOF!'
tree:
hello 1
 a 1
  brown 1
   black 1
   fox 1
    dog 1
 there 1
  is 1
   test 1
    of 1
     lists 1
      jumped 1
       lazy 1
     quick 1
      over 1
    the 2
  this 1
alphabetic tree:
a
black
brown
dog
fox
hello
is
jumped
lazy
lists
of
over
quick
test
the
there
this
!EOF!
ls -l 4_7B.cmp
echo x - 4_7B.h
sed 's/^X//' > 4_7B.h << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// tnode.h: definitions for a binary tree
// version 2
#ifndef TNODE_H
# define TNODE_H
struct tnode		// tree node
{
    char *tword;
    int count;		// reference count
    tnode *left;
    tnode *right;
};

typedef tnode **tree;

extern tree newtree();
extern void addnode(tree, char *);
extern void printtree(tree);
extern void aprinttree(tree);
#endif /* TNODE_H */
!EOF!
ls -l 4_7B.h
echo x - 4_7a.c
sed 's/^X//' > 4_7a.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
#include <tnode.h>
// create a new tree
tree newtree()
{
    tree head = new tnode*;
    *head = 0;
    return head;
}
!EOF!
ls -l 4_7a.c
echo x - 4_7b.c
sed 's/^X//' > 4_7b.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
#include <tnode.h>
#include <string.h>
#include <error.h>

// insert a new node to the left, right
// or at the node pointed to by the treeheadptr
void addnode(tree treeheadptr, char *nword)
{
    // a leaf found, enter the node here
    if (!*treeheadptr)
	{
	if (strlen(nword) >= 20)
	    error("word too long in addnode");

	tnode *n = new tnode;
	*treeheadptr = n;
	n->left = n->right = 0;
	n->count = 1;
	strcpy(n->tword, nword);
	return;
	}

    // check the name
    int cmp = strcmp(nword, (*treeheadptr)->tword);

    // enter in the left subtree
    if (cmp < 0)
	addnode(&(*treeheadptr)->left, nword);

    // enter in right subtree
    else if (cmp > 0)
	addnode(&(*treeheadptr)->right, nword);

    // equal, increment the reference count
    else /* if (cmp == 0) */
	(*treeheadptr)->count++;
}
!EOF!
ls -l 4_7b.c
echo x - 4_7c.c
sed 's/^X//' > 4_7c.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
#include <tnode.h>
#include <stream.h>
// print a node's value and reference count,
// indented by the depth, followed by the
// left and right subtrees
static void prnode(tnode *leaf, int level)
{
    if (leaf)
	{
	cout << str("", level) << leaf->tword << " " <<
	    leaf->count << "\n";
	prnode(leaf->left, level+1);
	prnode(leaf->right, level+1);
	}
}

// print out the tree
void printtree(tree treeheadptr)
{
    prnode(*treeheadptr, 0);
}

!EOF!
ls -l 4_7c.c
echo x - 4_7d.c
sed 's/^X//' > 4_7d.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
#include <tnode.h>
#include <stream.h>
// print a node's value sorted between
// its left and right subtrees
static void aprnode(tnode *leaf)
{
    if (leaf)
        {
	aprnode(leaf->left);
	cout << leaf->tword << "\n";
	aprnode(leaf->right);
	}
}

// print out the tree alphabetically
void aprinttree(tree treeheadptr)
{
    aprnode(*treeheadptr);
}
!EOF!
ls -l 4_7d.c
echo x - 4_7e.c
sed 's/^X//' > 4_7e.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
#include <tnode.h>
#include <string.h>
#include <error.h>

// insert a new node to the left, right
// or at the node pointed to by the treeheadptr
void addnode(tree treeheadptr, char *nword)
{
    // a leaf found, enter the node here
    if (!*treeheadptr)
	{
	tnode *n = new tnode;
	*treeheadptr = n;
	n->left = n->right = 0;
	n->count = 1;
	n->tword = new char[strlen(nword) + 1];
	strcpy(n->tword, nword);
	return;
	}

    // check the name
    int cmp = strcmp(nword, (*treeheadptr)->tword);

    // enter in the left subtree
    if (cmp < 0)
	addnode(&(*treeheadptr)->left, nword);

    // enter in right subtree
    else if (cmp > 0)
	addnode(&(*treeheadptr)->right, nword);

    // equal, increment the reference count
    else /* if (cmp == 0) */
	(*treeheadptr)->count++;
}
!EOF!
ls -l 4_7e.c
echo x - makefile
sed 's/^X//' > makefile << '!EOF!'
CC= CC -I. -I../../CC
ERROR=  ../../error.o
CFLAGS= -I. -g

all: 4_7A 4_7B

4_7A: 4_7A.h 4_7.c 4_7a.c 4_7b.c 4_7c.c 4_7d.c
	$(CC) -I. -DTESTA 4_7.c -o 4_7A $(ERROR)

4_7B: 4_7B.h 4_7.c 4_7b.c 4_7c.c 4_7d.c 4_7e.c
	$(CC) -I. -DTESTB 4_7.c -o 4_7B $(ERROR)

CMP= 4_7A.cmp 4_7B.cmp
OUT= 4_7A.out 4_7B.out

4_7A.out: 4_7A ;	4_7A > 4_7A.out
4_7B.out: 4_7B ;	4_7B > 4_7B.out

test: all $(OUT) $(CMP)
	cmp 4_7A.out 4_7A.cmp
	cmp 4_7B.out 4_7B.cmp
	echo tests done

o4.7: o4.7a.o o4.7b.o o4.7m.o
	$(CC) o4.7a.o o4.7b.o o4.7m.o ../ex/error.o -o o4.7 $(ERROR)

o4.7a.o: o4.7a.c o4.7.h
o4.7b.o: o4.7b.c o4.7.h
o4.7m.o: o4.7m.c o4.7.h
!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