double hashing na zadati container.h

Code:

#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 );
    friend std::ostream& operator<<( std::ostream& o, const Streamable* const s );
public:
    virtual ~Streamable( ) {}
};

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

class Container : public Streamable {
protected:
    Container( ) { }

public:
    typedef unsigned long Key;
    enum Order { dontcare, ascending, descending };
    class Functor;
    class Exception;

    virtual ~Container( ) { }

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

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

    virtual bool isMember( Key key ) const = 0;
    virtual unsigned long 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 ) {}
    virtual ~Exception( ) {}
};

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


#endif //CONTAINER_H

Code:
#ifndef TIMER_H
#define TIMER_H

#include <ctime>
#include <iostream>
#include <iomanip>

#define PRECISION 5

class Timer {
 
  bool running;
  clock_t start_clock;
  time_t start_time;
  double acc_time;

public:
  friend std::ostream& operator<<(std::ostream& os, Timer& t);

  // 'running' is initially false.  A timer needs to be explicitly started
  // using 'start' or 'restart'
  Timer() : running(false), start_clock(0), start_time(0), acc_time(0) { }

  double elapsed_time();
  
  void start(const char* msg = 0);
  void restart(const char* msg = 0);
  void stop(const char* msg = 0);
  void check(const char* msg = 0);
  char* timeToString(time_t time_stamp, char* time_format);
  char* timeToString(time_t time_stamp);
}; // class Timer

//===========================================================================
// Return the total time that the timer has been in the "running"
// state since it was first "started" or last "restarted". For
// "short" time periods (less than an hour), the actual cpu time
// used is reported instead of the elapsed time.
inline double Timer::elapsed_time() {
  time_t acc_sec = time(0) - start_time;
  if (acc_sec < 3600)
    return (double)(clock() - start_clock) / CLOCKS_PER_SEC;
  else
    return acc_sec;
} // Timer::elapsed_time

//===========================================================================
// Start a timer.  If it is already running, let it continue running.
// Print an optional message.
inline void Timer::start(const char* msg) {
  // Print an optional message, something like "Starting timer t";
  if (msg) std::cout << msg << std::endl;

  // Return immediately if the timer is already running
  if (running) return;

  // Change timer status to running
  running = true;

  // Set the start time;
  start_clock = clock();
  start_time = time(0);
} // Timer::start

//===========================================================================
// Turn the timer off and start it again from 0.  Print an optional message.
inline void Timer::restart(const char* msg) {
  // Print an optional message, something like "Restarting timer t";
  if (msg) std::cout << msg << std::endl;

  // Set the timer status to running
  running = true;

  // Set the accumulated time to 0 and the start time to now
  acc_time = 0;
  start_clock = clock();
  start_time = time(0);
} // Timer::restart

//===========================================================================
// Stop the timer and print an optional message.
inline void Timer::stop(const char* msg) {
  // Print an optional message, something like "Stopping timer t";
  if (msg) std::cout << msg << std::endl;

  // Recalculate and store the total accumulated time up until now
  if (running) acc_time += elapsed_time();

  running = false;
} // Timer::stop

//===========================================================================
// Print out an optional message followed by the current timer timing.
inline void Timer::check(const char* msg) {
  // Print an optional message, something like "Checking timer t";
  if (msg) std::cout << msg << " : ";

  std::cout << "Elapsed time [" << std::setiosflags(std::ios::fixed)
            << std::setprecision(PRECISION)
            << acc_time + (running ? elapsed_time() : 0) 
      << "] seconds\n";
} // Timer::check

//===========================================================================
// Allow timers to be printed to ostreams using the syntax 'os << t'
// for an ostream 'os' and a timer 't'.  For example, "cout << t" will
// print out the total amount of time 't' has been "running".
inline std::ostream& operator<<(std::ostream& os, Timer& t) {
  os << std::setprecision(PRECISION) 
     << std::setiosflags(std::ios::fixed)
     << t.acc_time + (t.running ? t.elapsed_time() : 0);
  return os;
} // Timer::ostream

//===========================================================================
// represents a timestamp as a string in a specified format
// get actual timestamp with: time_t now = time (0);
// @see http://www.opengroup.org/onlinepubs/007908799/xsh/strftime.html
inline char* timeToString(time_t time_stamp, char* time_format) {
  char* time_buffer = new char[40];
  const struct tm *tm = localtime ( &time_stamp );
  strftime ( time_buffer, 40, time_format, tm );
  return time_buffer;
} // timeToString

//===========================================================================
// represents a timestamp as a string in the standardformat given by the
// asctime-function
// @see http://www.cplusplus.com/ref/ctime/
inline char* timeToString(time_t time_stamp) {
  struct tm * timeinfo = localtime ( &time_stamp );
  return asctime (timeinfo);
} // timeToString

#endif // TIMER_H

Code:

#ifndef GENERATOR_H
#define GENERATOR_H

// siehe http://www.dreamincode.net/forums/showtopic24225.htm

#include <iostream>
#include <ctime>

class Generator {
public:
  enum Mode { asc, desc, rand };

private:
  unsigned long iCurrent;
  Mode mode;

public:
  Generator( Mode m = rand, unsigned long iSeed = 0L ) : iCurrent ( iSeed ), mode ( m ) { }
  virtual ~Generator( ) { }

  virtual void next( unsigned long * puffer, unsigned long size = 1) { //get the next random number
    if (mode == asc) {
      for (unsigned long i=0; i < size; i++) puffer[i] = ++iCurrent;
    } else if (mode == desc) {
      for (unsigned long i=0; i < size; i++) puffer[i] = --iCurrent;
    } else if (mode == rand) {
      for (unsigned long i=0; i < size; i++) {
        unsigned long iOutput;
        unsigned long iTemp;
        //I only want to take the top two bits
        //This will shorten our period to (2^32)/16=268,435,456
        //Which seems like plenty to me.
        for(int r=0; r<16; r++) {
          //Since this is mod 2^32 and our data type is 32 bits long
          // there is no need for the MOD operator.
          iCurrent = (3039177861UL * iCurrent + 1);
          iTemp = iCurrent >> 30;
          iOutput = iOutput << 2;
          iOutput = iOutput + iTemp;
        }
        puffer[i] = iOutput;
      }
    }
  }
};

#endif // GENERATOR_H

Code:
    http://rapidshare.com/files/34...timer_cc_generator_cc.zip.html

Code:
#include "ContainerImpl.h"
#include "Container.h"
#include <iostream>
#include <string>

using namespace std;
int s;

int x;
int b;
int groesse;

int arraygreat;
int *was;

const int HT_FREE = 0 ;
const int HT_FREE_AGAIN = 1 ;
const int HT_USED = 2 ;

Container::Container(int s){

if (s%2==0)
{
    groesse=s+1;
}
else 

{
    groesse=s;
}

hashtable=new Key[groesse]; 
hilfstabelle=new int[groesse];
//hashtable[2]=2;
zaehler=0;
}

Container::~Container(){}

void Container::add( Key keys[], unsigned long size ) {
    unsigned long i=0;
    double belegungsfaktor=(zaehler+size)/groesse;
    if (belegungsfaktor>0.7)
    {
        resize((groesse+size)*2);
    } 
    Key auslager;
    
    while (i<size)
    {int position=0;
        auslager=keys[i];                     
                
        int stepsize=auslager%(groesse-2);
                    //stepsize für double hashing
        if (stepsize==0)
        {
            stepsize=1;
        }
//        log ( "stepsize fuer :" + auslager + " = " + stepsize);
        position=auslager%groesse;
                            
                            
        while (hilfstabelle[position]==HT_USED)        //Prüfung ob Tabelle bei 1. Hashwert frei ist 
        {
            position=position+stepsize;
            if(position>=groesse)
            {
                cout << "durchlaufe :" << position << endl;
                cout << "key :" << auslager << endl;
                position=position-groesse;
                
            }
        }
            
        hilfstabelle[position]=HT_USED;
            hashtable[position]=auslager;
            zaehler++;
            
        
i++;
  }
}

long Container::hashget (Key key) const
{
    
    
    Key auslager;
    auslager=key;
    
        int position=0;                                //ktuelle zu hashender Wert
        int stepsize=auslager%(groesse-2);            //stepsize für double hashing
        position=auslager%groesse;                    //1. Hashwert
        while (hilfstabelle[position]==HT_USED || hilfstabelle[position]==HT_FREE_AGAIN)        //Prüfung ob Tabelle bei 1. Hashwert frei ist 
        {
            if (hashtable[position]==auslager&&hilfstabelle[position]==HT_USED)
            {
                return position;
            }
            position=position+stepsize;
            if(position>=groesse)
            {
                position=position-groesse;
                
            }
            
        }
            
        
        

  
    
return -1;
}

void Container::remove( Key keys[], unsigned long size ){

unsigned long i=0;
    
    Key auslager;
    while (i<size)
    {
        auslager=keys[i];         

int entfernen;
entfernen=hashget(auslager);
if (entfernen > -1)
{
    hilfstabelle[entfernen]=HT_FREE_AGAIN;
    zaehler--;

  }
  i++;
}
}
void Container::furz()
{
    cout << "ich bin" << endl;
}

/*void ContainerImpl::log ( string parTheString )
{
  #ifdef DEBUGOUTPUT    
    
  cout << parTheString << endl;
  
  #endif
}
*/

bool Container::isMember( Key key ) const {
    Key wert;
    wert=key;
    
    return (hashget(key)>-1);
}
   unsigned long Container::size( ) const {
       return zaehler;
   }
       
       
   
   void Container::resize(int newsize)
  {
      
        Key *oldhashtable;
        oldhashtable=hashtable;
        int oldsize=groesse;
        int *oldhilfstabelle;
        oldhilfstabelle=hilfstabelle;
        
        if (newsize%2==0)
{
    groesse=newsize+1;
}
else
{
    groesse=newsize;
}

hashtable=new Key[groesse]; 
hilfstabelle=new int[groesse];
zaehler=0;
Key LTheNewKeyValue[1];
for(int i=0; i < oldsize; i++)
{
    if (oldhilfstabelle[i]==HT_USED)
    {
        LTheNewKeyValue[0]=oldhashtable[i];
        add(LTheNewKeyValue,1);
    }
        
    
}
delete oldhashtable;
delete oldhilfstabelle;
  }