reg01.c

nucleus 文件系统,内核和彩色图形系统,在小系统上非常好用

/*************************************************************************/
/*                                                                       */
/*         Copyright (c) 1997 - 1999 Accelerated Technology, Inc.        */
/*                                                                       */
/* PROPRIETARY RIGHTS of Accelerated Technology are involved in the      */
/* subject matter of this material.  All manufacturing, reproduction,    */
/* use, and sales rights pertaining to this subject matter are governed  */
/* by the license agreement.  The recipient of this software implicitly  */
/* accepts the terms of the license.                                     */
/*                                                                       */
/*************************************************************************/

/*************************************************************************/
/*                                                                       */
/* FILE NAME                                            VERSION          */
/*                                                                       */
/*      REG01.c                                          1.9             */
/*                                                                       */
/* COMPONENT                                                             */
/*                                                                       */
/*      All                                                              */
/*                                                                       */
/* DESCRIPTION                                                           */
/*                                                                       */
/*      This file contains the mwRLSRT function.                         */
/*                                                                       */
/* AUTHOR                                                                */
/*                                                                       */
/*      Giac Dinh, Accelerated Technology, Inc.                          */
/*                                                                       */
/* DATA STRUCTURES                                                       */
/*                                                                       */
/*      None                                                             */
/*                                                                       */
/* FUNCTIONS                                                             */
/*                                                                       */
/*      None                                                             */
/*                                                                       */
/* DEPENDENCIES                                                          */
/*                                                                       */
/*      None                                                             */
/*                                                                       */
/* HISTORY                                                               */
/*                                                                       */
/*         NAME            DATE                    REMARKS               */
/*                                                                       */
/*		   BobB			  5/5/98		Corrected to sort the first      */
/* rectangle in the list.                                                */
/*         BobB           11/9/99       Removed unneeded line            */
/*                                                                       */
/*************************************************************************/

#include "meta_wnd.h"
#include "metconst.h"    /* MetaWINDOW Constant & Stucture Definitions */
#include "metports.h"    /* MetaWINDOW Port & Bitmap Definitions */
#include "grafdata.h"
#include "metmacs3.h"


/* Module REG01 is the rectangle list conversion to global coordinates / YX
sorting function. The passed-in rectangle list is sorted either
in place (if DESTRECTS is NULL) or copied to the destination list first (if
DESTRECTS is non-NULL).  The primary sort key is upper left corner Y
coordinate; the secondary key is upper left corner X coordinate. This
prepares the list to be fed to RectListToRegion() to describe a region.

Note: sorting is done via Shellsort, which has O(n**1.5) performance. If more
performance is needed, Quicksort is the obvious candidate, but Shellsort is
simpler and requires no auxiliary storage. Shellsort reference:
_Algorithms_, by Robert Sedgewick, Addison-Wesley, 1990. Note that the C
version of the book, _Algorithms in C_, has two bugs in the C implementation,
so don't take it too seriously!  */
void mwRLSRT( int numRects, rect *srcRects, rect *destRects)
{
	int rectCnt;
	rect *rectEnd;
	int hSpan;
	rect *hSortedStart;
	rect *listToSort;
	int tempa, tempb;
	short minX, minY, maxX, maxY;
	rect *temRectSt;
	rect *temRect;
	rect *temSave;
	rect *snPtr;

/* Point to destination  */
	if(destRects == 0)
		temRect = srcRects;
	else
	{
		temRect = destRects;
		temSave = srcRects;
		for (rectCnt = 0; rectCnt < numRects; rectCnt++)
		{
			*destRects++ = *temSave++;
		}
		destRects = temRect;
	}

/* BobB 11/9/99 - removed the following line since variable is never used
	temSave = temRect; */

/* Convert all rects to global  */

	listToSort = temRect;

	if(numRects < 2)
		return;			/* task termination  */
	
	rectCnt = numRects ;

/* Convert to global loop  */
	if(globalLevel > 0)
	{
		do{
			U2GR(*temRect, temRect,0);
			temRect++;
		}while(--rectCnt > 0);
	}
	
/* Already in global all rects are converted then sort them */
	
	rectEnd = listToSort + numRects;

	tempb = 1; 
/* Calculate the initial sort skip distance the largest
	value in sequence 1, 4, 13, 40, 121, 364 ... that's
	less than the number of rects  */
	do{
		tempa = tempb;
		tempb = (3 * tempb) + 1;
	} while ((tempb < numRects));

/* Loop through, shorting all spaced, subfiles for each 
   at which point the rects are sorted  */

	do{
		hSpan = tempa;
		hSortedStart = listToSort + hSpan;
		temRect = hSortedStart;
		do{
	/* Perform an insertion sort on the current element
	   within its space subfile  */
			minX = temRect->Xmin;
			minY = temRect->Ymin;
			maxX = temRect->Xmax;
			maxY = temRect->Ymax;
			temRectSt = temRect;
			snPtr = temRect;		
			do{
				snPtr -= hSpan;
				if ((snPtr->Ymin < minY) || ((snPtr->Ymin == minY)
					&& (snPtr->Xmin <= minX))) break;

				*temRect = *snPtr;
				temRect = snPtr;

/* BobB 5/5/98 - corrected the following line to sort the first rectangle
   in the list.
			}while (temRect > hSortedStart); */
			}while (temRect >= hSortedStart);

		temRect->Xmin = minX;
		temRect->Ymin = minY;
		temRect->Xmax = maxX;
		temRect->Ymax = maxY;
		temRect = temRectSt + 1;
		}while(temRect != rectEnd);

		tempa = tempa / 3;
	}while(tempa > 0);

	return;
}