a_sort.cpp

一个不错

/* Copyright is licensed under GNU LGPL.                 by I.J.Wang 2006

  Mimic utility sort (different lexicographical order)

  Build: make a_sort
*/
#include "../src/wy_uty.h"
#include "../src/wyregfile.h"
#include "../src/wy_atdestroy.h"
#include "../src/wystr.h"
#include "../src/wy_array.h"

// [Syn] Read lines from infile and store the read lines as WyStr elements into
//       obuf
//
// [Ret] Ok
//       ...
//
static WyRet get_input(WyByteFlow& infile, Wy_Array<WyStr>& obuf)
{
 WyRet r;
 WyStr ibuf;

 obuf.reset();
 for(;;) {
   const static size_t RdCap=1024;
   size_t n_rd;

   // read and append RdCap characters from infile device
   if((r=infile.read(ibuf,RdCap,n_rd))!=Ok) {
     WY_RETURN(r);
   }
   if(n_rd==0) {
     if(ibuf.size()!=0) {
       obuf.push_back(ibuf);
     }
     ibuf.reset();
     break;
   }

   // 1. find LF and create WyCSeg elelment pointing to the line
   // 2. push the WyCSeg element into obuf
   // 3. erase the the line from ibuf
   size_t sidx=0;
   for( ; ibuf.find(&n_rd,sidx,'\n'); sidx=n_rd) {
     ++n_rd;
     obuf.push_back( ibuf.cseg(sidx,n_rd-sidx) );
   }
   ibuf.erase(0,sidx);
 }
 return(Ok);
};

// [Syn] Sort WyCSeg array v of range form index start_idx to end_idx
//       (one-past-the-last index)
//
static void qsort_cs(Wy_Array<WyCSeg>& v, size_t start_idx, size_t end_idx)
{
 const size_t VLen( end_idx-start_idx );

 // sort manually if array v size is small enough
 if(VLen==2) {
   if(v[start_idx+1]._strcmp(v[start_idx])<0) {
     v[start_idx].swap(v[start_idx+1]);
   }
   return;
 }
 if(VLen<=1) {
   return;
 }
 const WyCSeg Piv(v[start_idx]);  // use 1st element as the pivot
                                  // (note: use the pivot from random index may
                                  //  be better, code is slightly different)
 size_t ge_bgn=start_idx;         // begin index of the array that is
                                  // 'greater or equal' to the pivot

 // rearrange (bipartite) the array by Piv
 for(size_t s=start_idx+1; s<end_idx; ++s) {
   if(v[s]._strcmp(Piv)<0) {
     v[ge_bgn].swap(v[s]);
     ++ge_bgn;
   }
 }
 if(ge_bgn==start_idx) {
   qsort_cs(v,start_idx+1,end_idx);  // worst pass, Piv is the smallest
   return;
 }

 // recursively sort the bipartited array
 qsort_cs(v,start_idx,ge_bgn);
 qsort_cs(v,ge_bgn,end_idx);
};

int main(int argc, char* argv[])
try {
 static const char *cmd_syntax=
    " Sort lines from standard input and write to standard output\n"
    " [Usage]$a_sort [-h][-cddd]\n"
    ;

 WyRet r;
 size_t sort_col(0);    // not used

 // Command-line option process
 //
 {
  const char optstr[]="hc:";
  int optch;
  
  while((optch=::getopt(argc,argv,optstr))!=-1) {
    switch(optch) {
      case 'h':
	      Wy::cout << cmd_syntax;
	      return(0);
      case 'c':
              if((r=Wy::_strnum(sort_col,NULL,WyCSeg(optarg)))!=Ok) {
                Wy::cerr << "Sort column unidentified\n";
                return(-1);
              }
              break;
      case ':':     // missing parameter
      case '?':     // unknown option
	      Wy::cerr << "parameter error\n";
	      Wy::cerr << cmd_syntax;
              return(-1);
      default:
	      Wy::cerr << "parameter fault\n";
              return(-1);
    }
  }
 }

 Wy_Array<WyStr> lnbuf;
 if((r=get_input(Wy::cin, lnbuf))!=Ok) {
   throw r;
 }

 // Setup segbuf for the sort
 //
 // Note: lnbuf cannot be modified, because WyCSeg is pointing into
 //       it's internal array (actually, using just WyStr is enough)
 //
 Wy_Array<WyCSeg> segbuf;
 for(size_t i=0; i<lnbuf.size(); ++i) {
   segbuf.push_back(lnbuf[i].cseg());
 }
 qsort_cs(segbuf,0,segbuf.size());

 // Write segbuf pointed data to standard output
 //
 for(size_t i=0; i<segbuf.size(); ++i) {
   Wy::cout << segbuf[i];
 }
 return(0);
}
catch(const WyRet& e) {
 Wy::cerr << Wy::wrd(e) << '\n';
 return(e->c_repcode());
}
catch(...) {
 Wy::cerr << "main caught(...)\n";
 return(-1);
};