orderedbinarytree.h

用于词法分析的词法分析器

/*
  $Id: OrderedBinaryTree.h,v 1.2 1997/02/02 01:31:05 matt Exp $

  Ordered binary trees.
  
  (c) Mar 1995 Matt Phillips.
  */

#ifndef _OBTREES_H
#define _OBTREES_H

#include "Container.h"
#include "Data.h"
#include "TreeAssocItem.h"
#include "LinkedStack.h"		// for iteration

template <class K, class T, class E>
class OrderedBinaryTreeImp : public Container<T>
{
public:

  typedef OrderedBinaryTreeImpIter<K, T, E> Iterator;

  OrderedBinaryTreeImp () : root (0) {}
  ~OrderedBinaryTreeImp () {clear ();}

  // class name
  virtual const char *name () const {return "OrderedBinaryTree";}

  // get value associated with <key> or null if not found.
  T *get (const K &key) const;

  // returns true if pair with <key> exists.
  int exists (const K &key) const {return get (key) != 0;}

  // returns true if pair with <key> was removed.
  int remove (const K &key);

  // add pair (key, i).  replace if item already exists.
  T &add (const K &key, T &i) {_nItems++; return doAdd (new E (key, i));}

  // remove all items from tree.
  void clear () {doClear (root); root = 0; _nItems = 0;}

  Iterator *makeIter () const {return new Iterator (*this);}

protected:

  friend class Iterator;

  void doClear (E *r);
  T &doAdd (E *i);

  E *root;
};

template <class K, class T, class E>
class OrderedBinaryTreeImpIter : public ContainerIter<T>
{
public:
   
  OrderedBinaryTreeImpIter (const OrderedBinaryTreeImp<K, T, E> &t) :
    tree (t) {reset ();}

  virtual void reset ()
  {stack.clear (); if (tree.root) stack.push (*tree.root);}

  virtual operator int () const {return !stack.isEmpty ();}

  virtual void operator ++ (int);

  virtual T value () const
  {ITER_BOUND (!stack.isEmpty ()); return stack.top ().ref ();}

  virtual T &ref () const
  {ITER_BOUND (!stack.isEmpty ()); return stack.top ().ref ();}
   
protected:

  TypeILinkedStack(E) stack;
  const OrderedBinaryTreeImp<K, T, E> &tree;
};

template <class K, class T, class E>
T *OrderedBinaryTreeImp<K, T, E>::get (const K &key) const
{
  for (E *t = root; ; )	// follow path thru tree
  {
    if (t)
    {
      if (t->refKey () == key)
	return &(t->ref ());
      else if (key < t->refKey ())
	t = t->left;
      else
	t = t->right;
    } else
      return 0;
  }

  // this should not be executed!
}

template <class K, class T, class E>
T &OrderedBinaryTreeImp<K, T, E>::doAdd (E *i)
{
  E **r = &root;
   
  for (;;)			// follow path thru tree
  {
    E *t = *r;
      
    if (t)
    {
      if (t->refKey () == i->refKey ())
      {
	i->left = t->left;	// replace on match
	i->right = t->right;
	delete t;
	*r = i;
	_nItems++;
	return i->ref ();
      } else if (i->refKey () < t->refKey ())
	r = &(t->left);
      else
	r = &(t->right);

    } else
    {
      *r = i;
      return i->ref ();
    }
  }
}

template <class K, class T, class E>
int OrderedBinaryTreeImp<K, T, E>::remove (const K &key) 
{
  E **r = &root;
   
  for (;;)			// follow path thru tree
  {
    E *t = *r;
      
    if (t)
    {
      if (key == t->refKey ())
      {
	*r = 0;			// disconnect this node
	if (t->left) doAdd (t->left);
	if (t->right) doAdd (t->right);
	delete t;
	_nItems--;

	return 1;
      } else if (key < t->refKey ())
	r = &(t->left);
      else
	r = &(t->right);

    } else
      return 0;
  }

  // this should not be executed!
}

template <class K, class T, class E>
void OrderedBinaryTreeImp<K, T, E>::doClear (E *r)
{
  if (r)
  {
    doClear (r->left);
    doClear (r->right);
    delete r;
  }
}

template <class K, class T, class E>
void OrderedBinaryTreeImpIter<K, T, E>::operator ++ (int)
{
  ITER_BOUND (!stack.isEmpty ());

  if (stack.top ().left)
    stack.push (*stack.top ().left);
  else
  {
    while (!stack.isEmpty ())
    {
      E *right = stack.top ().right;
      stack.pop ();

      if (right)
      {
	stack.push (*right);
	break;
      } 
    }
  }
}

#define TypeDOrderedBinaryTree(K, T) OrderedBinaryTreeImp<K, T, DTreeAssocItem<K, T> >
#define TypeIOrderedBinaryTree(K, T) OrderedBinaryTreeImp<K, T, ITTreeAssocItem<K, T, 0> >
#define TypeIOOrderedBinaryTree(K, T) OrderedBinaryTreeImp<K, T, ITTreeAssocItem<K, T, 1> >

#endif