TestSpeedExp.cpp

#include "targetver.h"
#include <windows.h>
#include <iostream>
#include <tchar.h>
#include <assert.h>

using namespace std;

class VivaMeteringTimeStruct {
public:
  VivaMeteringTimeStruct();
  void StartMeteringTime();
  void StopMeteringTime();
  double GetUserSeconds() const;
private:
  __int64 GetCurrentUserTime() const;
  __int64 m_userTime;
  bool m_isStoped;
};

VivaMeteringTimeStruct::VivaMeteringTimeStruct() {
  m_userTime = 0;
  m_isStoped = true;
}

__int64 VivaMeteringTimeStruct::GetCurrentUserTime() const {
  FILETIME creationTime;
  FILETIME exitTime;
  FILETIME kernelTime;
  FILETIME userTime;
  bool result = GetThreadTimes(GetCurrentThread(), &creationTime, &exitTime,
                               &kernelTime, &userTime) != 0;
  assert(result);
  UNREFERENCED_PARAMETER(result);
  __int64 curTime;
  curTime = userTime.dwHighDateTime;
  curTime <<= 32;
  curTime += userTime.dwLowDateTime;
  return curTime;
}

void VivaMeteringTimeStruct::StartMeteringTime() {
  assert(m_isStoped);
  m_isStoped = false;
  m_userTime = GetCurrentUserTime();
}

void VivaMeteringTimeStruct::StopMeteringTime() {
  assert(!m_isStoped);
  m_isStoped = true;
  __int64 curUserTime = GetCurrentUserTime();
  assert(m_userTime <= curUserTime);
  m_userTime = curUserTime - m_userTime;
}

double VivaMeteringTimeStruct::GetUserSeconds() const {
  assert(m_isStoped);
  return static_cast<double>(m_userTime) / 10000000.0;
}


const unsigned ArrayWidth_32 = 11;
const unsigned ArrayHeight_32 = 14;
const size_t ArrayWidth_64 = ArrayWidth_32;
const size_t ArrayHeight_64 = ArrayHeight_32;

const unsigned StartX_32 = 3;
const unsigned StartY_32 = 3;
const unsigned FinishX_32 = ArrayWidth_32 - StartX_32;
const unsigned FinishY_32 = ArrayHeight_32 - StartY_32;

const size_t StartX_64 = StartX_32;
const size_t StartY_64 = StartY_32;
const size_t FinishX_64 = FinishX_32;
const size_t FinishY_64 = FinishY_32;

typedef char FieldCell;
#define FREE_CELL 1
#define BARRIER_CELL 2
#define TRAVERSED_PATH_CELL 3

unsigned FindMinPathFromPoint32(FieldCell (*field)[ArrayHeight_32], unsigned x,
                                unsigned y, unsigned bestPathLen,
                                unsigned currentPathLen) {
  ++currentPathLen;
  if (currentPathLen >= bestPathLen)
    return UINT_MAX;
  if (x == FinishX_32 && y == FinishY_32)
    return currentPathLen;
  FieldCell oldState = field[x][y];
  field[x][y] = TRAVERSED_PATH_CELL;
  unsigned len = UINT_MAX;
  if (x > 0 && field[x - 1][y] == FREE_CELL) {
    unsigned reslen = FindMinPathFromPoint32(field, x - 1, y, bestPathLen, currentPathLen);
    len = min(reslen, len);
  }
  if (x < ArrayWidth_32 - 1 && field[x + 1][y] == FREE_CELL) {
    unsigned reslen = FindMinPathFromPoint32(field, x + 1, y, bestPathLen, currentPathLen);
    len = min(reslen, len);
  }
  if (y > 0 && field[x][y - 1] == FREE_CELL) {
    unsigned reslen = FindMinPathFromPoint32(field, x, y - 1, bestPathLen, currentPathLen);
    len = min(reslen, len);
  }
  if (y < ArrayHeight_32 - 1 && field[x][y + 1] == FREE_CELL) {
    unsigned reslen = FindMinPathFromPoint32(field, x, y + 1, bestPathLen, currentPathLen);
    len = min(reslen, len);
  }
  field[x][y] = oldState;
  
  if (len >= bestPathLen)
    return UINT_MAX;
  return len;
}

size_t FindMinPath32(FieldCell (*field)[ArrayHeight_32]) {
  unsigned BestPathLen = UINT_MAX;
  field[StartX_32][StartY_32] = TRAVERSED_PATH_CELL;
  unsigned ret = FindMinPathFromPoint32(field, StartX_32, StartY_32, BestPathLen, 0);
  if (ret == UINT_MAX)
    return SIZE_MAX;
  return ret;
}

size_t FindMinPathFromPoint64(FieldCell (*field)[ArrayHeight_64], size_t x,
                              size_t y, size_t bestPathLen,
                              size_t currentPathLen) {
  ++currentPathLen;
  if (currentPathLen >= bestPathLen)
    return SIZE_MAX;
  if (x == FinishX_64 && y == FinishY_64)
    return currentPathLen;
  FieldCell oldState = field[x][y];
  field[x][y] = TRAVERSED_PATH_CELL;
  size_t len = SIZE_MAX;
  if (x > 0 && field[x - 1][y] == FREE_CELL) {
    size_t reslen = FindMinPathFromPoint64(field, x - 1, y, bestPathLen, currentPathLen);
    len = min(reslen, len);
  }
  if (x < ArrayWidth_64 - 1 && field[x + 1][y] == FREE_CELL) {
    size_t reslen = FindMinPathFromPoint64(field, x + 1, y, bestPathLen, currentPathLen);
    len = min(reslen, len);
  }
  if (y > 0 && field[x][y - 1] == FREE_CELL) {
    size_t reslen = FindMinPathFromPoint64(field, x, y - 1, bestPathLen, currentPathLen);
    len = min(reslen, len);
  }
  if (y < ArrayHeight_64 - 1 && field[x][y + 1] == FREE_CELL) {
    size_t reslen = FindMinPathFromPoint64(field, x, y + 1, bestPathLen, currentPathLen);
    len = min(reslen, len);
  }
  field[x][y] = oldState;
  
  if (len >= bestPathLen)
    return SIZE_MAX;
  return len;
}

size_t FindMinPath64(FieldCell (*field)[ArrayHeight_64]) {
  unsigned BestPathLen = UINT_MAX;
  field[StartX_64][StartY_64] = TRAVERSED_PATH_CELL;
  return FindMinPathFromPoint64(field, StartX_64, StartY_64, BestPathLen, 0);
}

int _tmain(int argc, _TCHAR* argv[])
{
  int nRetCode = 0; 
  try {
    FieldCell (*field)[ArrayHeight_64] = new FieldCell[ArrayWidth_64][ArrayHeight_64];

    DWORD startTime = GetTickCount();

    for (size_t x = 0; x != ArrayWidth_64; ++x)
      for (size_t y = 0; y != ArrayHeight_64; ++y)
        field[x][y] = rand() % 3 == 1 ? BARRIER_CELL : FREE_CELL;
    field[StartX_64][StartY_64] = FREE_CELL;
    field[FinishX_64][FinishY_64] = FREE_CELL;

    for (size_t x = 0; x != ArrayWidth_64; ++x) {
      for (size_t y = 0; y != ArrayHeight_64; ++y) {
        char symbol;
        switch (field[x][y]) {
          case FREE_CELL: symbol = '.'; break;
          case BARRIER_CELL: symbol = 'O'; break;
          case TRAVERSED_PATH_CELL: symbol = '*'; break;
          default: symbol = 'E'; assert(false); break;
        }
        cout << symbol;
      }
      cout << endl;
    }

    VivaMeteringTimeStruct metric;
    size_t minLen;

    metric.StartMeteringTime();
    minLen = FindMinPath32(field);
    metric.StopMeteringTime();
    cout << endl << "32 bit type:" << endl;
    if (minLen == SIZE_MAX)
      cout << "No path found" << endl;
    else
      cout << "Minimal path len = " << minLen << endl;
    cout << "Total time : " << metric.GetUserSeconds() << endl;

    cout << endl;

    cout << endl << "64 bit type:" << endl;
    metric.StartMeteringTime();
    minLen = FindMinPath64(field);
    metric.StopMeteringTime();
    if (minLen == SIZE_MAX)
      cout << "No path found" << endl;
    else
      cout << "Minimal path len = " << minLen << endl;
    cout << "Total time : " << metric.GetUserSeconds() << endl;
    delete [] field;
  }
  catch (...) {
    cout << "Fatal Error: some exception..." << endl;
    nRetCode = 1;
  }
  return 0;
}