statistics.cpp

#include <iostream>
#include <stdlib.h>
#include "dlist.h"
#include "mtflist.h"
#include "transposelist.h"
#include "slist.h"
#define PATTERN_MAX 10
#define SEQ_MAX 1000

using namespace std;

void initArray( int array[], int size, int randMax ) {
  for ( int i = 0; i < size; ) {
    int tmp = ( randMax == -1 ) ? rand( ) : rand( ) % randMax;
    bool hit = false;
    for ( int j = 0; j < i; j++ ) {
      if ( array[j] == tmp ) {
	hit = true;
	break;
      }
    }
    if ( hit )
      continue;
    array[i] = tmp;
    i++;
  }
}

//void printArray( int array[], int size, char arrayName[] ) {
void printArray( int array[], int size, string arrayName ) {
  for ( int i = 0; i < size; i++ )
    cout << arrayName << "[" << i << "] = " << array[i] << endl;
}

int main( int argc, char* argv[] ) {

  // verify argument
  if ( argc != 2 ) {
    cerr << "usage: statistics size" << endl;
    return -1;
  }
  
  // verify size
  int size = atoi( argv[1] );
  if ( size < PATTERN_MAX ) {
    cerr << "usage: size >= " << PATTERN_MAX << endl;
    return -1;
  }

  // initialize list items
  srand( 1 );
  int *items = new int[size];
  initArray( items, size, -1 );
  printArray( items, size, "items" );
    
  // initialize access pattern
  int *pattern = new int[PATTERN_MAX];
  initArray( pattern, PATTERN_MAX, size );
  printArray( pattern, PATTERN_MAX, "pattern" );
 
  // initialize pattern frequency
  int *frequency = new int[PATTERN_MAX];
  for ( int i = 1; i < PATTERN_MAX; i++ )
    frequency[i] = i + frequency[i - 1];
  printArray( frequency, PATTERN_MAX, "frequency" );

  // generate access sequence
  int *sequence = new int[SEQ_MAX];
  for ( int i = 0; i < SEQ_MAX; i++ ) {
    int random = rand( ) % ( frequency[PATTERN_MAX - 1] + 1 );
    int hit;
    for ( hit = 0; hit < PATTERN_MAX; hit++ ) {
      if ( random <= frequency[hit] ) {
	break;
      }
    }
    sequence[i] = items[pattern[hit]];
  }
  printArray( sequence, SEQ_MAX, "sequence" );

  // now conduct performance evaluation
  // doubly linked list
  DList<int> dlist;
  for ( int i = 0; i < size; i++ )
    dlist.insert( items[i], i );

  for ( int i = 0; i < SEQ_MAX; i++ )
    dlist.find( sequence[i] );

  cout << "dlist's find cost = " << dlist.getCost( ) << endl;

  // mtf list
  MtfList<int> mtflist;
  for ( int i = 0; i < size; i++ )
    mtflist.insert( items[i], i );

  for ( int i = 0; i < SEQ_MAX; i++ )
    mtflist.find( sequence[i] );

  cout << "mtflist's find cost = " << mtflist.getCost( ) << endl;

  // transpose list
  TransposeList<int> translist;
  for ( int i = 0; i < size; i++ )
    translist.insert( items[i], i );

  for ( int i = 0; i < SEQ_MAX; i++ )
    translist.find( sequence[i] );

  cout << "translist's find cost = " << translist.getCost( ) << endl;

  // skip list
  SList<int> skiplist;
  for ( int i = 0; i < size; i++ )
    skiplist.insert( items[i] );

  for ( int i = 0; i < SEQ_MAX; i++ )
    skiplist.find( sequence[i] );

  cout << "skip's find cost = " << skiplist.getCost( ) << endl;

  return 0;
}