containerimpl.cpp

representation of a binary search tree

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

ContainerImpl::~ContainerImpl( ) {
  delete_( root );
}

void ContainerImpl::delete_( Node*& node ) {
  if (node) {
    delete_( node->left );
    delete_( node->right );
    delete node;
    node = 0;
  }
}

void ContainerImpl::add_( Node*& node, const Key& key ) {
  if (!node) {
    node = new Node( key );
  } else {
    if (node->key > key) {
      add_( node->left, key );
    } else if (key > node->key) {
      add_( node->right, key );
    }
  }
}

void ContainerImpl::add( const Key keys[], size_t size ) {

  for (size_t i = 0; i < size; ++i) {
    add_( root, keys[i] );
  }
}

void ContainerImpl::remove_( Node*& node, const Key& key ) {
  if (!node) {
    return;
  }
  if (node->key > key) {
    remove_( node->left, key );
  } else if (key > node->key) {
    remove_( node->right, key );
  } else {
    Node * oldNode = node;
    if (!node->left) {
      node = node->right;
    } else if (!node->right) {
      node = node->left;
    } else {
      node = removeMin_( node->right );
      node->left = oldNode->left;
      node->right = oldNode->right;
    }
    delete oldNode;
  }
}

void ContainerImpl::remove( const Key keys[], size_t size ) {
  for (size_t i = 0; i < size; ++i) {
    remove_( root, keys[i] );
  }
}

ContainerImpl::Node* ContainerImpl::removeMin_( Node*& node ) {
  if (!node) {
    throw Exception( "ContainerImpl::removeMin_: internal error 4711" );
  }
  if (node->left) {
    return removeMin_( node->left );
  } else {
    Node* minNode = node;
    node = node->right;
    return minNode;
  }
}

bool ContainerImpl::isMember( const Key& key ) const { return isMember_( root, key ); }

bool ContainerImpl::isMember_( Node* node, const Key& key ) const {
  if (!node) {
    return false;
  } else if (key == node->key) {
    return true;
  } else if (node->key > key) {
    return isMember_( node->left, key );
  } else {
    return isMember_( node->right, key );
  }
}

size_t ContainerImpl::size( ) const { return size_( root ); }

size_t ContainerImpl::size_( Node* node ) const {
  return node ? 1 + size_( node->left ) + size_( node->right ) : 0;
}

Key ContainerImpl::minKey( ) const {
  if (!root) {
    throw Exception( "ContainerImpl::minKey: Baum ist leer" );
  }
  Node* current = root;
  for ( ; current->left; current = current->left) {}
  return current->key;
}

Key ContainerImpl::maxKey( ) const {
  if (!root) {
    throw Exception( "ContainerImpl::maxKey: Baum ist leer" );
  }
  Node* current = root;
  for ( ; current->right; current = current->right) {}
  return current->key;
}

std::ostream& ( std::ostream &o ) const { return put_( root, o ); }

std::ostream& ContainerImpl::put_( Node* node, std::ostream &o ) const {
  if (node) {
    o << " (";
    o << node->key;
    put_( node->left, o );
    put_( node->right, o );
    o << ')';
  } else {
    o << " .";
  }
  return o;
}

void ContainerImpl::foreach( const Functor& f, Order order ) const { foreach_( root, f, order ); }

bool ContainerImpl::foreach_( Node* node, const Functor& f, Order order ) const {
  if (order == descending) {
    return !node || foreach_( node->right, f, order ) && f( node->key ) && foreach_( node->left, f, order );
  } else {
    return !node || foreach_( node->left, f, order ) && f( node->key ) && foreach_( node->right, f, order );
  }
}