NetNews Usenet Archive 1992 #20/NN_1992_20.iso/spool/comp/lang/cplus/13397

Text File | 1992-09-08 | 5.5 KB | 157 lines

Newsgroups: comp.lang.c++
Path: sparky!uunet!news.claremont.edu!ucivax!ucla-cs!ucla-mic!agsm!iwelch
From: [e-mail] (Ivo Welch)
Subject: General Datastructure Design Question
Message-ID: <[e-mail]>
Nntp-Posting-Host: risc.agsm.ucla.edu
Organization: UCLA, Anderson Graduate School Of Management
Date: 8 Sep 92 11:45:16 PDT
Lines: 146


I am rather proficient in C, but a complete novice to C++--which is driving me
up the wall. I am running gcc-1.93 (68K, as ported by NeXT 3.0PR2), which does
not offer templates. I cannot upgrade to gcc 2.2, because gdb is not ported to
NeXT. I have a beginner's design problem:


I am trying to define a simple data structure,  like a binary  tree, which can
be used by any other data structures. So, I decided to  go the C++ way, rather
than passing byte sizes of structures as I would in C.

My guess was that a good  design would  define an abstract "TreeNode" class on
which  my   BinaryTree  class would  operate.    This  abstract TreeNode class
declares 2 functions, (fix, compare).   A user would   define  her own  "Node"
class, inheriting the abstract  class,  which  [a] contains the data   and [b]
defines the fix() [=copy] and compare() functions.  The instantiated user-node
object carries with   it the information  of  what compare  and  fix functions
operate on it, because it is derived from a virtual abstract class.

Beautiful. Except that I cannot get the damn thing to  work.  Run-time errors.
The old gdb debugger 3.95 is less than helpful.  Could someone  please send me
an example of an implementation  that does something like this.  I do not want
to bother people with my code, but perhaps it clarifies some of my problems.

/ivo


The following code carries around some additional printing code, as well as an
ugly mixture of malloc's and new's, as well as some other bad C habits.

/****************************************************************/
extern "C" {
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
}

#include "BinaryTree.h"

class Node : public TreeNode {
  char *key;
  int value;
 public:
  Node(char *key, int value) { this->key= strcpy(malloc(strlen(key+1)+1), key); this->value= value; }
  Node() { this->key= 0; this->value= (-1); }
  ~Node() { if (key!=0) free(key); key= 0; }

  // now override the abstract definition;
  TreeNode *fix(TreeNode *source_virtual) {
    Node *dest; Node *src = (Node *) source_virtual;
    fprintf(stderr, "[Fixing]\n");
    dest= malloc(sizeof(Node)+1);
    dest->key= strcpy(malloc(strlen(src->key)+1), src->key);
    dest->value= src->value;
    fprintf(stderr, "[Fixed]\n");
    return dest;
  }
  int compare(TreeNode *other) { return strcmp(this->key, ((Node *) other)->key); };
  void print(FILE *f =stdout) { fprintf(f, "Node [%s] = %d\n", key, value); };
} ;

/****************************************************************/
int main() {
  BinaryTree b;
  b.setdebug(1);

  { Node store1("first", 1);    b.insert(&store1);  }
  { Node store2("second", 2);    b.insert(&store2); }
  { Node store3("third", 3);    b.insert(&store3); }
  { Node store4("fourth", 4);    b.insert(&store4); }
  { Node store5("fifth", 5);    b.insert(&store5); }
  { Node store6("six", 6);    b.insert(&store6); }

  b.print();  printf("\n");  b.printinternal();
  return 0;
}


Here comes my BinaryTree class, and the abstract TreeNode class.

/****************************************************************/
// abstract class
class TreeNode {
 public:
  virtual TreeNode *fix(TreeNode *src) =0;
  virtual int compare(TreeNode *other) =0;
  virtual void print(FILE *f =stdout) =0;
} ;


// the data structure operating on objects carrying the
// fix(), compare() and print() functions with them.
class BinaryTree {
  struct BinaryTreeNode {
    BinaryTreeNode *left, *right;
    TreeNode *value;
  public:
    BinaryTreeNode(TreeNode *newnode) { left=right= 0; value= newnode->fix(newnode); }
    void print(FILE *f =stdout);
    void printinternal(FILE *f =stdout);

    ~BinaryTreeNode() { right=right=0; } // I hope that value here gets deallocated;
  };
  BinaryTreeNode *root;
  int debug;

 public:
  BinaryTree() { root = 0; debug = 0; } ;
  ~BinaryTree() { };
  void print(FILE *f =stdout) { root->print(f); }
  void printinternal(FILE *f =stdout) { root->printinternal(f); }
  void setdebug(int i) { debug= i; }

  // each node has its own size;
  TreeNode *insert(TreeNode *newvalue) {
    BinaryTreeNode **cur= &root;
    if (debug) fprintf(stderr, "Entering Insert\n");
    while (*cur) {
      if (debug) { fprintf(stderr, "Comparing old value :"); (*cur)->value->print(); }
      if (debug) { fprintf(stderr, "To new value :"); newvalue->print(); }

      int result= (-1)*newvalue->compare((*cur)->value);
      if (result==0) { return (*cur)->value; } // found; already exists!;
      else if (result<0) cur= &((*cur)->left);
      else cur= &((*cur)->right);
    }
    if (debug) fprintf(stderr, "Malloc\n");
    (*cur) = new BinaryTreeNode(newvalue); // allocate space and call constructor;
    if (debug) fprintf(stderr, "Exiting Insert\n");
    return newvalue;
  }
} ;

// recursive functions;
void BinaryTreeNode::print(FILE *f =stdout) {
  if (right!=0) right->print();
  value->print(f);
  if (left!=0) left->print();
}

void BinaryTreeNode::printinternal(FILE *f =stdout) {
  static int level= 0;
  int c; for (c=0; c<level; ++c) putc(' ',f); value->print(f);
  if (left!=0) { level+=4;  putc('L', f); left->printinternal(); level-=4; }
  if (right!=0) { level+=4; putc('R', f); right->printinternal(); level-=4; }
}