Listing 3: table.cpp — cross-reference table with deeply const members

#include <stdio.h>
#include <string.h>

#include "table.h"

struct list_node
    {
public:
    unsigned number;
    list_node *&next();
    list_node const *next() const;
private:
    list_node *_next;
    };

inline
list_node *&list_node::next()
    {
    return _next;
    }

inline
list_node const *list_node::next() const
    {
    return _next;
    }

struct cross_reference_table::tree_node
    {
public:
    char *&word();
    char const *word() const;
    list_node *&first();
    list_node const *first() const;
    list_node *&last();
    list_node const *last() const;
    tree_node *&left();
    tree_node const *left() const;
    tree_node *&right();
    tree_node const *right() const;
private:
    char *_word;
    list_node *_first, *_last;
    tree_node *_left, *_right;
    };

inline
char *&cross_reference_table::tree_node::word()
    {
    return _word;
    }

inline
char const *
cross_reference_table::tree_node::word() const
    {
    return _word;
    }

inline
list_node *&
cross_reference_table::tree_node::first()
    {
    return _first;
    }

inline
list_node const *
cross_reference_table::tree_node::first() const
    {
    return _first;
    }

inline
list_node *&
cross_reference_table::tree_node::last()
    {
    return _last;
    }

inline
list_node const *
cross_reference_table::tree_node::last() const
    {
    return _last;
    }

inline
cross_reference_table::tree_node *&
cross_reference_table::tree_node::left()
    {
    return _left;
    }

inline
cross_reference_table::tree_node const *
cross_reference_table::tree_node::left() const
    {
    return _left;
    }

inline
cross_reference_table::tree_node *&
cross_reference_table::tree_node::right()
    {
    return _right;
    }

inline
cross_reference_table::tree_node const *
cross_reference_table::tree_node::right() const
    {
    return _right;
    }

cross_reference_table::tree_node *
cross_reference_table::add_tree
    (tree_node *t, char const *w, unsigned n)
    {
    int cmp;
    if (t == NULL)
        {
        t = new tree_node;
        t->word() = new char [strlen(w) + 1];
        strcpy(t->word(), w);
        t->first() = new list_node;
        t->first()->number = n;
        t->first()->next() = NULL;
        t->last() = t->first();
        t->left() = t->right() = NULL;
        }
    else if ((cmp = strcmp(w, t->word())) < 0)
        t->left() = add_tree(t->left(), w, n);
    else if (cmp > 0)
        t->right() = add_tree(t->right(), w, n);
    else if (n != t->last()->number)
        {
        t->last()->next() = new list_node;
        t->last() = t->last()->next();
        t->last()->number = n;
        t->last()->next() = NULL;
        }
    return t;
    }

void
cross_reference_table::put_tree(tree_node const *t) const
    {
    if (t != NULL)
        {
        put_tree(t->left());
        printf("%12s:", t->word());
        list_node const *p;
        for (p = t->first(); p != NULL; p = p->next())
            printf(" %4d", p->number);
        printf("\n");
        put_tree(t->right());
        }
    }