exmrg1.cpp

经典c++程序的实现

#include <iostream.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <assert.h>
#include "..\include\book.h"

typedef short ELEM;

// A swap for integers -- the other swap is for shorts.
inline void iswap(int& a, int& b)
{
  int temp = a;
  a = b;
  b = temp;
}

#define NumRec 2048
#define EMPTY -2  // Signifies no more records in file

// Define indices for run files
#define IN 0
#define IN1 0
#define IN2 1
#define OUT 2
#define OUT1 2
#define OUT2 3

// Maintain info on run files
int Posit[4] = {NumRec, NumRec, 0, 0};
int Recinblock[4] = {0, 0, 0, 0};
ELEM Array[4][NumRec];
FILE* FP[4];
char Name[4][30];

void GSbell(void)
{
  cout << "";
}

bool getnext(int fpindex, ELEM& val) {
  if (Posit[fpindex] >= Recinblock[fpindex]) { // page fault
    Recinblock[fpindex] = fread(&Array[fpindex], 2, NumRec, FP[fpindex]);
    if (Recinblock[fpindex] == 0) { val = EMPTY; return FALSE; }
    Posit[fpindex] = 0;
  }
  val = Array[fpindex][Posit[fpindex]++];
  return TRUE;
}


void putout(int fpindex, ELEM val) {
  int dum;
  if (Posit[fpindex] == NumRec) { // page fault
    if ((dum = fwrite(Array[fpindex], 2, NumRec, FP[fpindex])) != NumRec) {
      cout << "Unable to write a block: " << dum << "\n";
      GSbell();
      exit(1);
    }
    Posit[fpindex] = 0;
  }
  Array[fpindex][Posit[fpindex]++] = val;
}


void myflush(int fpindex) {
  int dum;
  if ((dum = fwrite(Array[fpindex], 2, Posit[fpindex], FP[fpindex])) !=
      Posit[fpindex]) {
    cout << "Unable to write a block: " << dum << "\n";
    GSbell();
    exit(1);
  }
}


// First pass of merge sort -- split into two files
void pass1(int inindex, int outindex1, int outindex2)
{
  ELEM val;
  ELEM last = -1;

  while (getnext(inindex, val)) {
    if (val < last) iswap(outindex1, outindex2);
    putout(outindex1, val);
    last = val;
  }
  myflush(outindex1);
  myflush(outindex2);
}


void exmergesort(int in1, int in2, int out1, int out2, char* outname) {
  ELEM val1, val2;
  ELEM last = -1;
  bool DONE = FALSE;

  pass1(in1, out1, out2);
  while (!DONE) {
cout << "Do Pass\n";
    fclose(FP[in1]);
    if ((FP[in1] = fopen(Name[in1], "w+b")) == NULL) {
      cout << "Unable to open file :" << Name[in1] << ":\n";
      exit(-1);
    }
    if ((FP[in2] = fopen(Name[in2], "w+b")) == NULL) {
      cout << "Unable to open file :" << Name[in2] << ":\n";
      exit(-1);
    }
    iswap(in1, out1);
    iswap(in2, out2);
    fseek(FP[in1], 0L, SEEK_SET);
    fseek(FP[in2], 0L, SEEK_SET);
    Posit[out1] = Posit[out2] = 0;
    Posit[in1] = Posit[in2] = NumRec;
    DONE = TRUE;
    last = -1;
    getnext(in1, val1);  getnext(in2, val2);
    while ((val1 != EMPTY) || (val2 != EMPTY)) {
      if ((val1 < last) && (val2 < last))
	{ iswap(out1, out2); last = -1; DONE = FALSE; }
      if (val1 >= last)
	if (val2 >= last)
	  if (val1 < val2)
	    { putout(out1, val1); last = val1; getnext(in1, val1); }
          else
            { putout(out1, val2); last = val2; getnext(in2, val2); }
        else
          { putout(out1, val1); last = val1; getnext(in1, val1); }
      else
        { putout(out1, val2); last = val2; getnext(in2, val2); }
    }
    myflush(out1);
    myflush(out2);
  }
  fclose(FP[out1]);
  rename(Name[out1], outname);
}


int main(int argc, char** argv) {
  time_t time1, time2;
  struct tms t1, t2;

  if (argc < 3) {
    cout << "Usage: exqsort <infile> <outfile>.\n";
    exit(-1);
  }

  // For first pass, need the original input file.  Won't use again
  if ((FP[IN1] = fopen(argv[1], "rb")) == NULL) {
    cout << "Unable to open file :" << argv[1] << ":\n";
    exit(-1);
  }


  sprintf(Name[IN1], "%s%s", argv[1], ".1");
  sprintf(Name[IN2], "%s%s", argv[1], ".2");
  sprintf(Name[OUT1], "%s%s", argv[2], ".1");
  sprintf(Name[OUT2], "%s%s", argv[2], ".2");

  // Open output files
  if ((FP[OUT1] = fopen(Name[OUT1], "w+b")) == NULL) {
    cout << "Unable to open file :" << argv[1] << ":\n";
    exit(-1);
  }
  if ((FP[OUT2] = fopen(Name[OUT2], "w+b")) == NULL) {
    cout << "Unable to open file :" << argv[1] << ":\n";
    exit(-1);
  }

  times(&t1);
  time1 = time((time_t *)0);
  exmergesort(IN1, IN2, OUT1, OUT2, argv[2]);
  times(&t2);
  time2 = time((time_t *)0);
  printf("utime: %f, stime: %f, wall time: %d\n",
	 (double)(t2.tms_utime - t1.tms_utime)/60.0,
	 (double)(t2.tms_utime - t1.tms_utime)/60.0, time2 - time1);
  return 0;
}