📄 aruqsort.c
字号:
/*
Copyright (c) 2003, Dan Kranz and Arnold Rom
All rights reserved.
Redistribution and use in source and binary forms, with or
without modification, are permitted provided that the following
conditions are met:
* Redistributions of source code must retain the above
copyright notice, this list of conditions and the following
disclaimer.
* Redistributions in binary form must reproduce the above
copyright notice, this list of conditions and the following
disclaimer in the documentation and/or other materials
provided with the distribution.
* The names of its contributors may not be used to endorse or
promote products derived from this software without specific
prior written permission.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <roots.h>
/* ############################################################################# */
/* # */
/* UQSORT (BLOCK,CPL,NLINE,FIELDS,NF,FIRST,LNEXTL,LFRSTL,LLASTL,TMP) # */
/* ----------------------------------------------------------------------- # */
/* # */
/* UQSORTS sorts and groups BLOCK of dimension CPL*NLINE by the NF # */
/* FIELDS. The physical BLOCK line arrangement is not altered. # */
/* # */
/* LNEXTL, LFRSTL, LLASTL, and TMP are INTEGER*2 arrays of length NLINE # */
/* each. # */
/* # */
/* TMP is a temporary array needed by UQSORT. # */
/* # */
/* LNEXTL, LFRSTL, and LLASTL are output from UQSORT. These arrays # */
/* contain the list structure reflecting the sorted groups of BLOCK. The # */
/* list components are as follows: # */
/* # */
/* FIRST,LNEXTL contains all lines with unique BLOCK(FIELDS). The unique # */
/* lines appear in ascending sort sequence. # */
/* # */
/* LFRSTL(L),LNEXTL contains the clones of L, for any L of FIRST,LNEXTL. # */
/* # */
/* Let L be a line of FIRST,LNEXTL; # */
/* # */
/* then BLOCK(FIEDLS,L)=BLOCK(FIELDS,LC); # */
/* # */
/* For all LC of LC1=LFRSTL(L), LC2=LNEXTL(LC1) ... 0=LNEXTL(LCN). # */
/* # */
/* LLASTL(L) is the final clone in a sub-list of clones starting with # */
/* LFRSTL(L). N.B. LLASTL may be ignored unless one wants to re-structure # */
/* the list. i.e. LNEXTL(LLASTL(L))=0 for LLASTL(L).NE.0. # */
/* # */
/* L's of FIRST,LNEXTL with LFRSTL(L)=0 have no clones and are therfore # */
/* unique with respect to the entire BLOCK. # */
/* # */
/* UQSORT is used mainly to derive tables of unique entries; however, a # */
/* simple re-structuring of the output list yields a list of all lines in # */
/* sort sequence. UQSORT is several times faster than CHSORT for BLOCKS # */
/* with a large clone population. # */
/* # */
/* ############################################################################# */
#define Compare_q_p_and_branch_Low_High_Equal(low,high,equal) \
ppoint=block+*cpl*p; \
qpoint=block+*cpl*q; \
for (j=0,fld=field; j<*nf; j++,fld+=2) { \
rc = compare(qpoint+*(fld),ppoint+*(fld),*(fld+1),types[j]); \
if (rc!=0) \
break; \
} \
if (rc<0) goto low; \
if (rc>0) goto high; \
goto equal;
void uqsort(BYTE *block, long *cpl, long *nline, long *field,
short *types, long *nf, long *first, unsigned short *lnextl,
unsigned short *lfrstl, unsigned short *llastl,
unsigned short *temp,
int (*compare)(const void *el, const void *e2, size_t count, short type))
/* --------------------------------------------------------- */
{ /* uqsort START */
/* --------------------------------------------------------- */
/* local data */
BYTE *ppoint,*qpoint;
unsigned short p,q,ngroup,prevp,k,npairs,pair,last,nextq,lastp,lastq;
unsigned short g1;
long *fld;
int rc,j;
/* ---------------------------------------------------- */
/* validate the arguments */
/* ---------------------------------------------------- */
if (*nf<=0 ||
*cpl<=0 ||
*nline<0 ||
*nline>MAXLIN ||
*field<=0 ||
*(field+1)<=0 ||
*(field+1)>*cpl ||
*field + *(field+1) - 1 > *cpl)
{
RootsSOS("uqsort sos exit\n");
abort();
}
/* ---------------------------------------------------- */
/* adjust arrays for relative zero addressing */
/* ---------------------------------------------------- */
block-=*cpl; --block; --lnextl; --lfrstl; --llastl; --temp;
/* ------------------------------------------------------ */
/* intialize for trivial case and leave if nline<=1. */
/* ------------------------------------------------------ */
*(lnextl+1)=*(lfrstl+1)=*(llastl+1)=0;
*(temp+1)=1;
if(*nline<=1) {*first=*nline; return;}
/* ---------------------------------------------------------------- */
/* derive intial natural groups */
/* ---------------------------------------------------------------- */
ngroup=p=prevp=1;
for(q=2; q<=*nline; q++)
{
*(lfrstl+q)=*(lnextl+q)=*(llastl+q)=0;
Compare_q_p_and_branch_Low_High_Equal(newgroup,oldgroup,iclone)
iclone: if(*(llastl+prevp)==0) *(lfrstl+prevp)=*(llastl+prevp)=q; /* new */
else
{
k=*(llastl+prevp); /* old */
*(llastl+prevp)=q; /* llastl(prevp)=q */
*(lnextl+k)=q; /* lnextl(old llastl(prevp))=q */
}
p=q; continue;
newgroup: ++ngroup;
*(temp+ngroup)=q;
prevp=q;
p=q;
continue;
oldgroup: *(lnextl+prevp)=q;
prevp=q;
p=q;
continue;
}
/* --------------------------------------------------------------------------- */
/* merge process */
/* --------------------------------------------------------------------------- */
while((npairs=ngroup/2)!=0)
/* --------------------- */
{ /* merge START */
/* --------------------- */
pair=0;
while(++pair<=npairs)
/* -------------------------------- */
{ /* merge current pair START */
/* -------------------------------- */
last=0;
g1=2*(pair-1)+1;
p=*(temp+g1); q=*(temp+g1+1);
Compare_q_p_and_branch_Low_High_Equal(storeq1,storep1,clone1)
/* ----------------------------------------------- */
/* p is the first member of new output list */
/* ----------------------------------------------- */
storep1: last=*(temp+pair)=p; p=*(lnextl+p);
if(p==0){*(lnextl+last)=q; continue;} /* append remaining q's */
Compare_q_p_and_branch_Low_High_Equal(storeqn,storepn,clonen)
/* ----------------------------------------------- */
/* q is the first member of new output list */
/* ----------------------------------------------- */
storeq1: last=*(temp+pair)=q; q=*(lnextl+q);
if(q==0){*(lnextl+last)=p; continue;} /* append remaining p's */
Compare_q_p_and_branch_Low_High_Equal(storeqn,storepn,clonen)
/* ----------------------------------------------- */
/* store p in established output list */
/* ----------------------------------------------- */
storepn: *(lnextl+last)=p; last=p; p=*(lnextl+p);
if(p==0){*(lnextl+last)=q; continue;} /* append remaining q's */
Compare_q_p_and_branch_Low_High_Equal(storeqn,storepn,clonen)
/* ----------------------------------------------- */
/* store q in established output list */
/* ----------------------------------------------- */
storeqn: *(lnextl+last)=q; last=q; q=*(lnextl+q);
if(q==0){*(lnextl+last)=p; continue;} /* append remaining p's */
Compare_q_p_and_branch_Low_High_Equal(storeqn,storepn,clonen)
/* -------------------------------------------------------------- */
/* remove redundant q and store as a clone of p for first */
/* -------------------------------------------------------------- */
clone1: nextq=*(lnextl+q);
/* connect q to p's clones */
if((lastp=*(llastl+p))==0) *(lfrstl+p)=q; else *(lnextl+lastp)=q;
*(lnextl+q)=*(lfrstl+q);
if((lastq=*(llastl+q))==0) *(llastl+p)=q; else *(llastl+p)=lastq;
*(lfrstl+q)=*(llastl+q)=0;
/* move to next q and store p (no compare needed) */
if((q=nextq)!=0)
{ /* copy storep1 */
last=*(temp+pair)=p; p=*(lnextl+p);
if(p==0){*(lnextl+last)=q; continue;} /* append remaining q's */
Compare_q_p_and_branch_Low_High_Equal(storeqn,storepn,clonen)
}
/* q's exhausted */
if(last!=0) {*(lnextl+last)=p; continue;} /* store remaining p's */
/* in unique list */
*(temp+pair)=p; continue; /* p is the first of the */
/* stack */
/* ---------------------------------------------------------- */
/* remove redundant q and store as a clone of p for n */
/* ---------------------------------------------------------- */
clonen: nextq=*(lnextl+q);
/* connect q to p's clones */
if((lastp=*(llastl+p))==0) *(lfrstl+p)=q; else *(lnextl+lastp)=q;
*(lnextl+q)=*(lfrstl+q);
if((lastq=*(llastl+q))==0) *(llastl+p)=q; else *(llastl+p)=lastq;
*(lfrstl+q)=*(llastl+q)=0;
/* move to next q and store p (no compare needed) */
if((q=nextq)!=0)
{ /* copy of storepn */
*(lnextl+last)=p; last=p; p=*(lnextl+p);
if(p==0){*(lnextl+last)=q; continue;} /* append remaining q's */
Compare_q_p_and_branch_Low_High_Equal(storeqn,storepn,clonen)
}
/* q's exhausted */
if(last!=0) {*(lnextl+last)=p; continue;} /* store remaining p's */
/* in unique list */
*(temp+pair)=p; continue; /* p is the first of the */
/* stack */
/* -------------------------------- */
} /* merge current pair END */
/* -------------------------------- */
/* redefine ngroup */
/* odd case. add odd ball to new groups */
if(ngroup%2==1)
{
*(temp+npairs+1)=*(temp+ngroup);
ngroup=npairs+1;
continue;
}
/* even case */
ngroup=npairs;
/* --------------------- */
} /* merge END */
/* --------------------- */
*first=*(temp+1);
return;
/* --------------------------------------------------------- */
} /* uqsort END */
/* --------------------------------------------------------- */
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -