Linear Hashing with MergeSort?

[superC]

Hello!
I need a help. I've got to make a program with insert and search function and I have to use to following. To create a database in which I will implement insert and search
The part of code is given:

#ifndef CONTAINER_H
#define CONTAINER_H

#include <iostream>
#include <string>

class Streamable {
	virtual std::ostream& put( std::ostream& o ) const = 0;
	friend std::ostream& operator<<( std::ostream& o, const Streamable& s );
public:
	virtual ~Streamable( ) {};
};

inline std::ostream& operator<<( std::ostream& o, const Streamable& s ) { return s.put( o ); }

typedef unsigned long int ValueType;

class Key {
	ValueType value;
	Key( ValueType v ) : value( v ) {}
public:
	Key() {}
	~Key( ) {}
	std::ostream& put( std::ostream& o ) const { return o << value; }
	std::istream& get( std::istream& i ) { return i >> value; }
	bool operator==( const Key& k ) const { return value == k.value; }
	bool operator>( const Key& k ) const { return value > k.value; }
	unsigned long ulongValue() const { return (unsigned long) value; }
	unsigned long hashValue() const { return (unsigned long) value; }

	friend class KeyFactory;
};

inline std::ostream& operator<<( std::ostream& o, const Key& s ) { return s.put( o ); }
inline std::istream& operator>>( std::istream& i, Key& s ) { return s.get( i ); }

class KeyFactory {
public:
	static Key newKey( unsigned long v ) { return Key( v ); }
	static Key newKey( ) { return Key( std::rand( ) ); }
	static void srand( int i ) { std::srand( i ); }
};

class Container : public Streamable {
protected:
	Container( ) { }
public:
	enum Order { dontcare, ascending, descending };
	class Functor;
	class Exception;

	virtual ~Container( ) { }

	virtual void add( const Key& key ) { add( &key, 1 ); }
	virtual void add( const Key keys[], size_t size ) = 0;

	virtual void remove( const Key& key ) { remove( &key, 1 ); }
	virtual void remove( const Key keys[], size_t size ) = 0;

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

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

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

	virtual int teamNr( ) const = 0;
	virtual int themeNr( ) const = 0;
};

class Container::Exception : public Streamable {
	std::string msg;
	virtual std::ostream& put( std::ostream& o ) const { return o << "Container::Exception (" << msg << ")"; }
public:
	Exception( const std::string& msg ) : msg( msg ) {}
	const std::string& getMsg() const { return msg; }
	virtual ~Exception( ) {}
};

class Container::Functor {
public:
	virtual bool operator( )( const Key& key ) const = 0;
	virtual ~Functor( ) {}
};

#endif //CONTAINER_H

and it's also given:

One example of binary tree, adnwe're looking for

*
      Defaultkonstruktor ContainerImpl() 
    *
      void add( const Key[], size_t ) 
    *
      void add( const Key& ) 
    *
      bool isMember( const Key& ) const 
    *
      int teamNr( ) const 
    *
      int themeNr( ) const

------------------------------------

ContainerImpl.h

#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 );
  bool isMember_( Node* node, const Key& key ) const;
  std::ostream& put_( Node* node, std::ostream& o ) const;

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

public:
  ContainerImpl() : root( 0 ) { }
  virtual ~ContainerImpl( ) { }   // not implemented

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

  using Container::remove;
  virtual void remove( const Key keys[], size_t size ) { }  // not implemented

  virtual bool isMember( const Key& key ) const  { return isMember_( root, key ); }
  virtual size_t size( ) const { return 0; }  // not implemented
  virtual bool isEmpty( ) const { return false; }  // not implemented

  virtual void foreach( const Functor& f, Order order = dontcare ) const { } // not implemented

  virtual Key minKey( ) const { return Key(); } // not implemented
  virtual Key maxKey( ) const { return Key(); } // not implemented

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

#endif //CONTAINERIMPL_H

ContainerImpl.C

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

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] );
  }
}

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 );
  }
}

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;
}

to make tests easier, it is also recommend the methode:

std::ostream& put( std::ostream& ) const

[superC]

Using a given Code, I have to implement data structure with insert and search funkctions with a linear hashing.

[Ancient Dragon]

Go ahead, nobody here will stop you :)

[superC]

Hehehe :)

I will, but from where, can you help me?

First step:

I have to make/create one Hashtable?

second to implement insert

and all that with linear hashing?!

[Ancient Dragon]

>>can you help me?
Nope -- don't know a thing about it.