containerimpl.h

representation of a binary search tree

#ifndef CONTAINERIMPL_H
#define CONTAINERIMPL_H

#include <iostream>
#include "Container.h"

class ContainerImpl : public Container {

  class Node {
  public:
    Key key;
    Node * left;
    Node * right;
    Node( const Key& key, Node * left = 0, Node * right = 0 ) : key( key ), left( left ), right( right ) {}
  };

  Node * root;

  void add_( Node*& node, const Key& key );
  void remove_( Node*& node, const Key& key );
  Node* removeMin_( Node*& node );
  bool isMember_( Node* node, const Key& key ) const;
  size_t size_( Node* node ) const;
  std::ostream& put_( Node* node, std::ostream &o ) const;
  bool foreach_( Node* node, const Functor& f, Order order ) const;
  void delete_( Node*& node );

  virtual std::ostream& put( std::ostream &o ) const;
public:
  ContainerImpl() : root( 0 ) { }
  virtual ~ContainerImpl( );

  using Container::add;
  virtual void add( const Key keys[], size_t size );

  using Container::remove;
  virtual void remove( const Key keys[], size_t size );

  virtual bool isMember( const Key& key ) const;
  virtual size_t size( ) const;
  virtual bool isEmpty( ) const { return !root; }

  virtual void foreach( const Functor& f, Order order = dontcare ) const;

  virtual Key minKey( ) const;
  virtual Key maxKey( ) const;

  virtual int teamNr( ) const { return 0; }
  virtual int themeNr( ) const { return 0; }
};

#endif //CONTAINERIMPL_H