#!/bin/sh
# This is a shar archive.
# The rest of this file is a shell script which will extract:
#
# 5_2.c 5_2.cmp 5_2a.h 5_2a1.c 5_2a2.c 5_2b.h 5_2b1.c 5_2b2.c 5_2b3.c 5_2b4.c makefile tnode.h tree.h
#
# 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:01 EDT 1990
#
echo x - 5_2.c
sed 's/^X//' > 5_2.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 "5_2a.h"	// class tnode
//#include "5_2a1.c"	// tnode::tnode()
//#include "5_2a2.c"	// tnode::~tnode()
#include "5_2b.h"	// class tree
//#include "5_2b1.c"	// tree::addnode()
//#include "5_2b2.c"	// tree::findnode()
//#include "5_2b3.c"	// tree::delnode() 
//#include "5_2b4.c"	// tree::orderwalk()

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

static void prnode(tnode *tn, int depth)
{
    cout << form("%*s", depth*4, " ") << tn->tword << "\n";
}

main()
{
    tree t;

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

    cout << "forward\n";
    cout << "preorderwalk:\n";
    t.preorderwalk(prnode);
    cout << "inorderwalk:\n";
    t.inorderwalk(prnode);
    cout << "postorderwalk:\n";
    t.postorderwalk(prnode);
    cout << "doubleorderwalk:\n";
    t.doubleorderwalk(prnode);
    cout << "tripleorderwalk:\n";
    t.tripleorderwalk(prnode);

    cout << "reverse\n";
    cout << "preorderwalk:\n";
    t.preorderwalk(prnode, 1);
    cout << "inorderwalk:\n";
    t.inorderwalk(prnode, 1);
    cout << "postorderwalk:\n";
    t.postorderwalk(prnode, 1);
    cout << "doubleorderwalk:\n";
    t.doubleorderwalk(prnode, 1);
    cout << "tripleorderwalk:\n";
    t.tripleorderwalk(prnode, 1);
    return 0;
}
!EOF!
ls -l 5_2.c
echo x - 5_2.cmp
sed 's/^X//' > 5_2.cmp << '!EOF!'
forward
preorderwalk:
 hello
    a
        brown
            black
            fox
                dog
    there
        is
            test
                of
                    lists
                        jumped
                            lazy
                    quick
                        over
                the
        this
inorderwalk:
    a
            black
        brown
                dog
            fox
 hello
        is
                        jumped
                            lazy
                    lists
                of
                        over
                    quick
            test
                the
    there
        this
postorderwalk:
            black
                dog
            fox
        brown
    a
                            lazy
                        jumped
                    lists
                        over
                    quick
                of
                the
            test
        is
        this
    there
 hello
doubleorderwalk:
 hello
    a
    a
        brown
            black
            black
        brown
            fox
                dog
                dog
            fox
 hello
    there
        is
        is
            test
                of
                    lists
                        jumped
                        jumped
                            lazy
                            lazy
                    lists
                of
                    quick
                        over
                        over
                    quick
            test
                the
                the
    there
        this
        this
tripleorderwalk:
 hello
    a
    a
        brown
            black
            black
            black
        brown
            fox
                dog
                dog
                dog
            fox
            fox
        brown
    a
 hello
    there
        is
        is
            test
                of
                    lists
                        jumped
                        jumped
                            lazy
                            lazy
                            lazy
                        jumped
                    lists
                    lists
                of
                    quick
                        over
                        over
                        over
                    quick
                    quick
                of
            test
                the
                the
                the
            test
        is
    there
        this
        this
        this
    there
 hello
reverse
preorderwalk:
 hello
    there
        this
        is
            test
                the
                of
                    quick
                        over
                    lists
                        jumped
                            lazy
    a
        brown
            fox
                dog
            black
inorderwalk:
        this
    there
                the
            test
                    quick
                        over
                of
                    lists
                            lazy
                        jumped
        is
 hello
            fox
                dog
        brown
            black
    a
postorderwalk:
        this
                the
                        over
                    quick
                            lazy
                        jumped
                    lists
                of
            test
        is
    there
                dog
            fox
            black
        brown
    a
 hello
doubleorderwalk:
 hello
    there
        this
        this
    there
        is
            test
                the
                the
            test
                of
                    quick
                    quick
                        over
                        over
                of
                    lists
                    lists
                        jumped
                            lazy
                            lazy
                        jumped
        is
 hello
    a
        brown
            fox
            fox
                dog
                dog
        brown
            black
            black
    a
tripleorderwalk:
 hello
    there
        this
        this
        this
    there
        is
            test
                the
                the
                the
            test
                of
                    quick
                    quick
                        over
                        over
                        over
                    quick
                of
                    lists
                    lists
                        jumped
                            lazy
                            lazy
                            lazy
                        jumped
                        jumped
                    lists
                of
            test
        is
        is
    there
 hello
    a
        brown
            fox
            fox
                dog
                dog
                dog
            fox
        brown
            black
            black
            black
        brown
    a
    a
 hello
!EOF!
ls -l 5_2.cmp
echo x - 5_2a.h
sed 's/^X//' > 5_2a.h << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// tnode.h
// Exercise 5.2
#ifndef TNODE_H
# define TNODE_H

struct tnode		// tree node
{
    char *tword;	// string
    int count;		// reference count
    tnode *left,
	  *right;

    tnode(char*);
    ~tnode();
};
#endif /* TNODE_H */
!EOF!
ls -l 5_2a.h
echo x - 5_2a1.c
sed 's/^X//' > 5_2a1.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// constructor for a tnode
#include <tnode.h>
#include <string.h>

tnode:: tnode(char *s)
{
    count = 1;
    tword = new char[strlen(s)+1];
    strcpy(tword, s);
    left = right = 0;
}
!EOF!
ls -l 5_2a1.c
echo x - 5_2a2.c
sed 's/^X//' > 5_2a2.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// destructor for a tnode
#include <tnode.h>

tnode:: ~tnode()
{
    delete tword;

    if (left)
	delete left;

    if (right)
	delete right;
}
!EOF!
ls -l 5_2a2.c
echo x - 5_2b.h
sed 's/^X//' > 5_2b.h << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// tree.h
// Exercise 5.2
#ifndef TREE_H
# define TREE_H

#include <tnode.h>

typedef void (*walkfn)(tnode*, int);

class tree
{
    tnode *head;

public:
    tree() { head = 0; }
    ~tree() { if (head) delete head; }

    void addnode(char *s);
    tnode *findnode(char *s);
    int delnode(char *s);

    void preorderwalk(walkfn, int = 0);
    void inorderwalk(walkfn, int = 0);
    void postorderwalk(walkfn, int = 0);
    void doubleorderwalk(walkfn, int = 0);
    void tripleorderwalk(walkfn, int = 0);
};
#endif /* TREE_H */
!EOF!
ls -l 5_2b.h
echo x - 5_2b1.c
sed 's/^X//' > 5_2b1.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// insert a new node to the left, right
// or at the node pointed to by "head"
#include <tree.h>
#include <string.h>

static void insnode(tnode **parent, char *str)
{
    // a leaf found, enter the node here
    if (!*parent)
	{
	*parent = new tnode(str);
	return;
	}

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

    // enter in the left subtree
    if (cmp < 0)
	insnode(&(*parent)->left, str);

    // enter in the right subtree
    else if (cmp > 0)
	insnode(&(*parent)->right, str);

    // equal, increment the reference count
    else /* if (cmp == 0) */
	(*parent)->count++;
}

// add a new word to the tree
void tree:: addnode(char *str)
{
    insnode(&head, str);
}
!EOF!
ls -l 5_2b1.c
echo x - 5_2b2.c
sed 's/^X//' > 5_2b2.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// find a word within the tree
#include <tree.h>
#include <string.h>

tnode *tree:: findnode(char *s)
{
    tnode *cur = head;

    for (;;)
	{
	if (!cur)
	    return 0;

	int cmp = strcmp(s, cur->tword);

	// check the left subtree
	if (cmp < 0)
	    cur = cur->left;

	// check the right subtree
	else if (cmp > 0)
	    cur = cur->right;

	// equal, found it
	else /* if (cmp == 0) */
	    return cur;
	}
}
!EOF!
ls -l 5_2b2.c
echo x - 5_2b3.c
sed 's/^X//' > 5_2b3.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// delete a word from the tree
#include <tree.h>
#include <string.h>

int tree:: delnode(char *s)
{
    tnode **parent = &head;
    tnode *cur = head;

    for (;;)
	{
	if (!cur)
	    return 0;

	int cmp = strcmp(s, cur->tword);

	// check the left subtree
	if (cmp < 0)
	    {
	    parent = &cur->left;
	    cur = cur->left;
	    }

	// check the right subtree
	else if (cmp > 0)
	    {
	    parent = &cur->right;
	    cur = cur->right;
	    }

	// equal, found it
	else /* if (cmp == 0) */
	    {
	    // if more than one reference,
	    // just decrement the reference count
	    if (cur->count > 1)
		cur->count--;

	    // if there are no children,
	    // delete this node and
	    // the reference to it
	    else if (!cur->left && !cur->right)
		{
		delete cur;
		*parent = 0;
		}

	    // if there are children, try doing
	    // a splice into the right node
	    else if (!cur->right->left)
		{
		*parent = cur->right;
		cur->right->left = cur->left;
		delete cur;
		}

	    // find a node on the left where
	    // we can splice in the right node
	    else
		{
		tnode *svright = cur->right;
		*parent = cur->left;
		delete cur;

		for (cur = *parent;
		     cur->right;
		     cur = cur->right)
		    ;
		cur->right = svright;
		}

	    return 1;
	    }
	}
}
!EOF!
ls -l 5_2b3.c
echo x - 5_2b4.c
sed 's/^X//' > 5_2b4.c << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// walk down the tree, invoking the named function for
// each node in the ordered fashion designated
#include <tree.h>

static void doorderedwalk(tnode *head, walkfn fn,
    int rev, int depth,
    int beginning, int middle, int end)
{
    if (!head)
	return;

    // normally go left to right
    tnode *node1 = head->left;
    tnode *node2 = head->right;

    if (rev)
	{ // go right to left
	node1 = head->right;
	node2 = head->left;
	}

    if (beginning)
        (*fn)(head, depth);

    doorderedwalk(node1, fn, rev, depth+1,
        beginning, middle, end);

    if (middle)
	(*fn)(head, depth);

    doorderedwalk(node2, fn, rev, depth+1,
        beginning, middle, end);

    if (end)
	(*fn)(head, depth);
}

// invoke the walking function in various fashions
void tree:: preorderwalk(walkfn fn, int rev)
{
    doorderedwalk(head, fn, rev, 0, 1, 0, 0);
}

void tree:: inorderwalk(walkfn fn, int rev)
{
    doorderedwalk(head, fn, rev, 0, 0, 1, 0);
}

void tree:: postorderwalk(walkfn fn, int rev)
{
    doorderedwalk(head, fn, rev, 0, 0, 0, 1);
}

void tree:: doubleorderwalk(walkfn fn, int rev)
{
    doorderedwalk(head, fn, rev, 0, 1, 1, 0);
}

void tree:: tripleorderwalk(walkfn fn, int rev)
{
    doorderedwalk(head, fn, rev, 0, 1, 1, 1);
}
!EOF!
ls -l 5_2b4.c
echo x - makefile
sed 's/^X//' > makefile << '!EOF!'
CC= CC -I. -I../../CC
CFLAGS= -I. +i -g
OBJ= 5_2.o 5_2a1.o 5_2a2.o 5_2b1.o 5_2b2.o 5_2b3.o 5_2b4.o

all: 5_2

$(OBJ): tree.h tnode.h

5_2: $(OBJ)
	$(CC) $(OBJ) -o 5_2

OUT= 5_2.out
CMP= 5_2.cmp

5_2.out: 5_2 ;	5_2 > 5_2.out

test: all $(OUT) $(CMP)
	cmp 5_2.out 5_2.cmp
	echo tests done
!EOF!
ls -l makefile
echo x - tnode.h
sed 's/^X//' > tnode.h << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// tnode.h
// Exercise 5.2
#ifndef TNODE_H
# define TNODE_H

struct tnode		// tree node
{
    char *tword;	// string
    int count;		// reference count
    tnode *left,
	  *right;

    tnode(char*);
    ~tnode();
};
#endif /* TNODE_H */
!EOF!
ls -l tnode.h
echo x - tree.h
sed 's/^X//' > tree.h << '!EOF!'
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
/* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
/* The C++ Answer Book */
/* Tony Hansen */
/* All rights reserved. */
// tree.h
// Exercise 5.2
#ifndef TREE_H
# define TREE_H

#include <tnode.h>

typedef void (*walkfn)(tnode*, int);

class tree
{
    tnode *head;

public:
    tree() { head = 0; }
    ~tree() { if (head) delete head; }

    void addnode(char *s);
    tnode *findnode(char *s);
    int delnode(char *s);

    void preorderwalk(walkfn, int = 0);
    void inorderwalk(walkfn, int = 0);
    void postorderwalk(walkfn, int = 0);
    void doubleorderwalk(walkfn, int = 0);
    void tripleorderwalk(walkfn, int = 0);
};
#endif /* TREE_H */
!EOF!
ls -l tree.h
# The following exit is to ensure that extra garbage 
# after the end of the shar file will be ignored.
exit 0