/***********************************************************************\
region converter for Convert PICT which converts graphics from PICT to eps formats.
Copyright (C) 1993 David John Burrowes

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 1, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

The author, David John Burrowes, can be reached at:
	davidjohn@kira.net.netcom.com
	David John Burrowes
	1926 Ivy #10
	San Mateo, CA 94403-1367
\***********************************************************************/

#import "PICTFile.h"
#import "PSFile.h"
#import <stdio.h>
#import <stdlib.h>

#import  "RegionConverter.h"

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//	This class is dedicated to just converting PICT regions.  Really, I suppose it is
//	part of the PICTConverter class, but is just separated for orderliness regions.
//	You really should read the .rtf file for this class, though, because I give a dense
//	little description of the algorithm used here in english.  Some terms and the like
//	are defined there are are used here without any definition.
//	Note: CleanUp contains a known memory leak.
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


@implementation regionConverter

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//	Routine:		init
//	Parameters:	none
//	Returns:		self
//	Stores:		none
//	Description:
//		This just initializes all the instance variables.
//	Bugs:
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- init
{

	ActiveList = EndOfActiveList;
	RegionData = EndOfGroups;
	ShapeStorage = NoShape;
	boundsRect = NULL;
	
	return self;
}


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//	Routine:		ConvertRegionFrom:To:
//	Parameters:	a pict and a ps file object
//	Returns:		self
//	Stores:		error codes
//	Description:
//		This method serves as the govenor of the conversion of PICT Region to PS
//		data.  It does little save for calling other methods, and assuring that all went
//		well with each.
//	Bugs:
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- ConvertRegionFrom: PictFile  To: PsFile
{
	SegmentAddr			theSegment;
	SegmentGroupAddr	firstGroup;
	[self   ResetResults];
	//
	//	Read in the region.  If nothing went wrong, then proceed.
	//
	[self   ReadInRegionFrom: PictFile];
	if ([self   GetErrorCode] >= ERR_OK)	// Note a place where a 'severity' would be good
	{
		//
		//	If there are groups (segments on a line), then process them.
		//
		if (RegionData != EndOfGroups)
		{
			//
			//	Prime the conversion by adding all the lines from th first group
			//	to the set of started shapes (which also adds them to the active list).
			//	We do this because they're going to end up there anyway.  And, by doing
			//	it now, we save on time, and potentially allow ConvertRegionData
			//	to avoid having to deal with initial-case data.
			//
			firstGroup = RegionData;
			theSegment = [self   GetNextSegmentFromGroup: firstGroup];
			while (theSegment != NullSegment)
			{
				[self   AddShapeFrom: theSegment->left To: theSegment->right
					At: firstGroup->y];
				free (theSegment);
				theSegment = [self   GetNextSegmentFromGroup: firstGroup];
			}
			//
			//	With the active list now set up, proceeed to convert any others.
			//
			[self   ConvertRegionData];
		}
		//
		//	Finally, write out whatever data we have converted.
		//
		[self  WriteTo: PsFile];
		[self   CleanUp];
	}
	return self;
}


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//	Routine:		ReadInRegionFrom:
//	Parameters:	a pict file instance
//	Returns:		self
//	Stores:		error codes
//	Description:
//		This performs the relatively mundane task of reading in a pict region and
//		storing it in 0 or more groups in this instance.  When this finishes, the
//		current position in the pict file will be immediately after the last 0x7FFF in the
//		pict file, and the instance variable regionData will contain a full set of group
//		structures describing the Region.
//		For details about the format of both regions and the groups, see the
//		documentation for this class.
//	Bugs:
//		This routine basically always works.  That is, it never detects a condition
//		so bad that it thinks it should stop.  This is, of course, bad because such an
//		occasion would well occurr.
//		I've seemingly arbitrarily decided to support the case where the x coordinates of
//		a segment are reversed.  I serously doubt taht this would happen, and perhaps it
//		is really the indication of a serious error.  But, since  there's no spec on how regions are
//		to behave, I'm assuming as leniant a stance as I can.
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- ReadInRegionFrom: PictFile
{
	Integer	RegionSize;
	Integer	y;
	Integer	x1;
	Integer	x2;
	SegmentGroupAddr	Group		= EndOfGroups;
	SegmentGroupAddr	newGroup	= EndOfGroups;
	PositiveInteger		bytesConsumed;
	//
	//	Read in the first 10 bytes (size and bounding rect).  Store the bounding rect.
	//	These should always be here.
	//
	RegionSize = [PictFile   GetINTEGER];
	boundsRect = [PictFile   GetRect];
	//
	//	If the region is only 10 bytes long, then we're done (this is probably the most common
	//	region type that one will see).
	//
	if (RegionSize == 10)
		[self   StoreErrorCode: ERR_OK AndText: "Read Region OK"];
	else if (RegionSize < 10)
	{
		//
		//	If the region size is less than 10, it seems likely that the region is
		//	corrupted, and we should abort.
		//
		[self   StoreErrorCode: ERR_BADDATA
				AndText: "Region declared to be < 10 bytes.  Possible data corruption?"];
	}
	else
	{
		bytesConsumed = 10;
		//
		//	The region is made up of more than just a bounding rectangle, so start
		//	reading in the data.  Stop when our Y value is declared to be 32767 or when
		//	we've reached the number of bytes in a region (these should be simultaneous)
		//
		y = [PictFile   GetINTEGER];
		bytesConsumed +=2;
		while  ( (y != EndOfRegion)  ||  (bytesConsumed != RegionSize))
		{
			//
			//	Each set of segments at 1 y value get stored in a group.  Create the new
			//	group and add it to the end of the current group chain.  Link it into
			//	the instance variable RegionData if it is the first.  In any case, point Group,
			//	the pointer to the current group being added to, to this new group.
			//
			newGroup = (SegmentGroupAddr) malloc(sizeof(SegmentGroup));
			newGroup->y = y;
			newGroup->segmentData = EndOfChain;
			newGroup->next = EndOfGroups;
			if (RegionData == EndOfGroups)
				RegionData = newGroup;
			else
				Group->next =  newGroup;
			Group = newGroup;
			//
			//	Read in the pairs of x coordinate data until we find an end of region line.
			//	Merge each segment with the current group as we go.
			//
			x1 = [PictFile   GetINTEGER];
			bytesConsumed +=2;
			while (x1 != EndOfRegionLine)
			{
				x2 = [PictFile   GetINTEGER];
				//
				//	Store the segment in the current group.  Deal with the unlikely
				//	case the x1 and x2 values might be reversed for our needs.
				//
				if (x1 < x2)
					[self   AddSegmentFrom: x1  To: x2 ToGroup: Group];
				else
				{
					[self   AddSegmentFrom: x2  To: x1 ToGroup: Group];
					[self   StoreErrorCode: ERR_WEIRDDATA
						AndText: "x1 and x2 were reversed in region data!"];
				}
				x1 = [PictFile   GetINTEGER];
				bytesConsumed += 4;
			}
			y = [PictFile   GetINTEGER];
			bytesConsumed +=2;
		}
		//
		//	If if the last number read wasn't 7FFF and we've reached the end of the
		//	region, or vice versa, set an error.
		//
		if ( y != EndOfRegion)
			[self   StoreErrorCode: ERR_BADDATA
				AndText: "We did not find the end of the region!!  File may not be a PICT file!"];
		else if ( bytesConsumed  != RegionSize)
			[self   StoreErrorCode: ERR_BADSIZE
				AndText: "End of region found prematurely.  Is file corrupted?"];
	}
	return self;
}


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//	Routine:		AddSegmentFrom:To:ToGroup:
//	Parameters:	A left x and a right x coordinate and a group
//	Returns:		self
//	Stores:		none
//	Description:
//		Given the bounds of a segment, add a new segment to the chain of segments in the
//		specified group.
//	Bugs:
//	History:
//		93.11.07	djb	Fixed a subtle problem.  If there was 1 segment in group, and the one
//					we were adding belonged on the end of the chain, we were nevertheless
//					adding it first.  oops.
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-AddSegmentFrom: (Integer) left  To: (Integer) right  ToGroup: (SegmentGroupAddr) group;
{
	SegmentLinkAddr	location;
	SegmentLinkAddr	newSegment;
	//
	//	First, create the Segment link that we're going to add
	//
	newSegment = (SegmentLinkAddr) malloc(sizeof(SegmentLink));
	newSegment->left = left;
	newSegment->right = right;
	//
	//	If this is the first segment, then point the global to it
	//
	if (group->segmentData == EndOfChain)
	{
		newSegment->nextSegment = EndOfChain;
		group->segmentData = newSegment;
	}
	else
	{
		//
		//	Otherwise, walk down the chain, and look for a nice place to add
		//	the segment.  A 'nice place' means a location at the end of the chain, OR, to the
		//	left of a segment that starts with a larger x coordinate in left.  In this way,
		//	we try to keep the segments sorted by starting x coordinate.
		//
		location = group->segmentData;
		while ( (location->nextSegment != EndOfChain) &&
					(location->nextSegment->left < newSegment->left) )
			location = location->nextSegment;
		//
		//	If we actually go as the first segment, stick us in.  Otherwise,
		//	stick us before the segment we have found to have a greater value than the
		//	the our left x value 
		//
		if (location == group->segmentData)
		{
			if (location->left < newSegment->left)
			{
				newSegment->nextSegment = location->nextSegment;
				location->nextSegment = newSegment;
			}
			else
			{
				newSegment->nextSegment = group->segmentData;
				group->segmentData = newSegment;
			}
		}
		else
		{
			newSegment->nextSegment = location->nextSegment;
			location->nextSegment = newSegment;
		}
	}
	return self;
}


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//	Routine:		GetNextSegmentFromGroup:
//	Parameters:	A segment group
//	Returns:		the address of a segment that has been removed from the group
//	Stores:		error codes
//	Description:
//		This removes the next segment from thegroup, and returns it.  If there
//		are no remaining segments, and error is stored, and a NullSegmentAddress
//		is returned.
//	Bugs:
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

- (SegmentAddr) GetNextSegmentFromGroup: (SegmentGroupAddr) group
{
	SegmentAddr			newSegment;
	SegmentLinkAddr	firstSegment = group->segmentData;

	if (firstSegment == EndOfChain)
	{
		newSegment = NullSegment;
		[self   StoreErrorCode: ERR_NOSEGMENTS
				AndText: "There are no more segments in this group!"];
	}
	else
	{
		//
		//	Create a segment to be returned, and fill it in.  Remove the current segment.
		//
		newSegment = (SegmentAddr) malloc(sizeof(Segment));
		newSegment->left = firstSegment->left;
		newSegment->right = firstSegment->right;
		group->segmentData = firstSegment->nextSegment;
		free(firstSegment);
		[self   StoreErrorCode: ERR_OK AndText: "Got the segment."];
	}

	return newSegment;
}


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//	Routine:		AddShapeFrom:To:At:
//	Parameters:	The left and right coordinates of the first segment of the shape, and their
//				y coordinate.
//	Returns:		self
//	Stores:		none
//	Description:
//		This adds a new shape to the linked list of shapes stored so far.
//		Since this list isn't sorted, we just stick the shape in at thefirst place we find.
//	Bugs:
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- AddShapeFrom: (Integer) left  To: (Integer) right  At: (Integer) y
{
	ShapeAddr			newShape	= (ShapeAddr) malloc(sizeof(Shape));
	LineSegmentAddr		newLine		= (LineSegmentAddr) malloc(sizeof(LineSegment));
	//
	//	Fill in the line and shape structures
	//
	newLine->leftNext = NoLine;
	newLine->rightNext = NoLine;
	newLine->left.x = left;
	newLine->left.y = y;
	newLine->right.x = right;
	newLine->right.y = y;
	newLine->used = NO;
	newShape-> theLine = newLine;
	//
	//	Store the shapes in the linked list (we don't need to worry about whether
	//	there was anything in there already)
	//
	newShape->nextShape = ShapeStorage;
	ShapeStorage = newShape;
	//
	//	As a curtesy, add an Active segment as well, since a new shape with one line
	//	automatically has an active segment coresponding to that line.
	//
	[self   AddActiveFrom: left To: right WithLeft: newLine  AndRight: newLine];
	return self;
}


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//	Routine:		AddAntiShapeFrom:To:At:
//	Parameters:	The left and right coordinates of the first segment of the shape
//	Returns:		the newly created line
//	Stores:		none
//	Description:
//		This adds a new shape to the linked list of shapes stored so far.
//		This is interesting in that we do NOT add an active area.  This is because a shape
//		of this variety is appearing within another, and it's 'area' is actually the lack of
//		an area...
//	Bugs:
//	History:
//		93.11.07	djb	AT LAST!!  Found that I wasn't seting the used 'flag' to NO which
//					was causing seemingly random damage to the regions when they
//					were written out.
//					Also changed it so anti shapes are appended to the end of the list
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- (LineSegmentAddr)  AddAntiShapeFrom: (Integer) left  To: (Integer) right  At: (Integer) y
{
	ShapeAddr			newShape	= (ShapeAddr) malloc(sizeof(Shape));
	LineSegmentAddr		newLine		= (LineSegmentAddr) malloc(sizeof(LineSegment));
	ShapeAddr			tempShape;
	//
	//	Fill in the line and shape structures
	//
	newLine->leftNext = NoLine;
	newLine->rightNext = NoLine;
	newLine->left.x = left;
	newLine->left.y = y;
	newLine->right.x = right;
	newLine->right.y = y;
	newLine->used = NO;
	newShape-> theLine = newLine;
	//
	//	Store the shapes in the linked list.  We store them at the end of the list.  Why?
	//	Sometimes an antishape is merely the underside of an existing shape.  At the end
	//	of the list, they'll be visited by the writeout routine last, and so if they were such,
	//	they'll already have been makred as being used.  If this isn't done, the underside
	//	of the region may be written out before it's upper side, and this can cause strange
	//	effects when framing because the framing code may assume that any new shape
	//	starts with its top segment.
	//
	if (ShapeStorage == NoShape)
	{
		ShapeStorage = newShape;
		newShape->nextShape = NoShape;
	}
	else
	{
		tempShape = ShapeStorage;
		while (tempShape->nextShape != NoShape)
			tempShape = tempShape->nextShape;
		newShape->nextShape = NoShape;
		tempShape->nextShape = newShape;
	}
	return newLine;
}


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//	Routine:		AddLineFrom:To:At:WithLeft:AndRight:
//	Parameters:	The left and right coordinates of the first segment of the shape,
//				plus the pointers to the line(s) that this one is 'adjacent' to.
//	Returns:		the new line segment
//	Stores:		none
//	Description:
//		Given the specified data, build a new line segment, and and connect it to
//		other lines in a shape.  See documentation for this class for more info.
//	Bugs:
//		If one asks to add a line that has neither left nor right neighbors, then this
//		will duitfully not link this to other segments, and it's entirely possible that
//		trouble will result.  More simply: Make sure this always called with at least
//		one neighboring line segment.
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- (LineSegmentAddr) AddLineFrom: (Integer) left  To: (Integer) right  At: (Integer) y
	WithLeft: (LineSegmentAddr) leftline  AndRight: (LineSegmentAddr) rightline
{
	LineSegmentAddr		newLine		= (LineSegmentAddr) malloc(sizeof(LineSegment));
	//
	//	Fill in the line and shape structures
	//
	newLine->leftNext = leftline;
	newLine->rightNext = rightline;
	newLine->left.x = left;
	newLine->left.y = y;
	newLine->right.x = right;
	newLine->right.y = y;
	newLine->used = NO;
	//
	//	Link the other line(s) to this line.  Compare our left and right coordinates
	//	with those of the line(s) we are connected to.  Our left end should be
	//	connected to a line with the same x coordinate on one of its ends (either its
	//	left or right end could be attached to our end).
	//
	if (leftline != NoLine)
	{
		if (leftline->left.x == left)
			leftline->leftNext = newLine;
		else
			leftline->rightNext = newLine;
	}
	if (rightline != NoLine)
	{
		if (rightline->right.x == right)
			rightline->rightNext = newLine;
		else
			rightline->leftNext = newLine;
	}

	return newLine;
}


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//	Routine:		AddActiveFrom:To:WithLeft:AndRight:
//	Parameters:	A segment
//	Returns:		self
//	Stores:		none
//	Description:
//		Given a segment, add it to the set of active segments.
//	Bugs:
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

- AddActiveFrom: (Integer) left  To: (Integer) right  WithLeft:
		(LineSegmentAddr) leftline  AndRight: (LineSegmentAddr) rightline
{
	ActiveSegmentAddr	location;
	ActiveSegmentAddr	previous;
	ActiveSegmentAddr	newSegment;
	//
	//	First, create the Segment link that we're going to add
	//
	newSegment = (ActiveSegmentAddr) malloc(sizeof(ActiveSegment));
	newSegment->left = left;
	newSegment->right = right;
	newSegment->leftLine = leftline;
	newSegment->rightLine = rightline;
	//
	//	If this is the first segment, then point the global to it
	//
	if (ActiveList == EndOfActiveList)
	{
		newSegment->next = EndOfActiveList;
		newSegment->previous = EndOfActiveList;
		ActiveList = newSegment;
	}
	else
	{
		//
		//	Otherwiese, walk down the list, and look for a nice place
		//	to add the new one.  A 'nice place' means a location at the end of the chain,
		//	OR, to the left of a segment that starts with a larger x coordinate in left.
		//	In this way, we try to keep the segments sorted by starting x coordinate.
		//
		location = ActiveList;
		previous = EndOfActiveList;
		while ( (location != EndOfActiveList) &&
			(location->left < newSegment->left) )
		{
			previous = location;
			location = location->next;
		}
		if (location == ActiveList)
		{
			newSegment->previous = EndOfActiveList;
			newSegment->next = location;
			location->previous = newSegment;
			ActiveList = newSegment;
		}
		else
		{
			newSegment->previous = previous;
			newSegment->next = previous->next;
			previous->next = newSegment;
			if (location != EndOfActiveList)
				location->previous = newSegment;
		}
	}
	return self;
}


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//	Routine:		RemoveActive:
//	Parameters:	A segment
//	Returns:		self
//	Stores:		none
//	Description:
//		Given an active segment, link it's previous and following active segments
//		together, and then nuke the active segment.  (it's for the ease of removing an
//		active that these structures are doubly linked)
//	Bugs:
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

- RemoveActive: (ActiveSegmentAddr) theActive
{
	if (theActive->previous == EndOfActiveList)
		ActiveList = theActive->next;
	else
		theActive->previous->next = theActive->next;

	if (theActive->next != EndOfActiveList)
		theActive->next->previous = theActive->previous;

	free(theActive);
	return self;
}



//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//	Routine:		FindFirstActiveLeftIn:To:
//	Parameters:	A first and last x coordinate
//	Returns:		The address of an active segment
//	Stores:		none
//	Description:
//		This walks through the active segment list, and looks for an active whose left
//		boundrary is in (left,right].  If it finds such a beastie, it returns the address of
//		that active, otherwise it returns EndOfActiveList.
//	Bugs:
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

- (ActiveSegmentAddr) FindFirstActiveLeftIn: (Integer) left  To: (Integer) right
{
	ActiveSegmentAddr	location;
	Boolean				found = NO;

	location = ActiveList;

	while ( (location != EndOfActiveList) && (found != YES))
	{
		if ( (location->left > left) && (location->left <= right) )
			found = YES;
		else
			location = location->next;
	}

	return location;
}


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//	Routine:		ConvertRegionData
//	Parameters:	none
//	Returns:		self
//	Stores:		error codes
//	Description:
//		This assumes that the first group of segments has been dealt with, and so it
//		walks through the remaining data in the rows.
//		Basics of algorithm: Take a segment from the current group.  Walk down the
//		active list until we find one with some kinda overlap with the segment.
//		modify all things accordingly, and move on to the next segment (If the segment
//		extended to the right of the matching active, we modify it and send it through
//		for continued processing).  If a line never overlaps with
//		any of the actives, it falls out of the inner loop with an overlap of None, and is
//		added as the start of a new shape.
//	Bugs:
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

- ConvertRegionData
{
	SegmentGroupAddr	currentGroup;
	Integer				currentY;
	SegmentAddr			curSeg;
	OverlapKind			overlap;
	ActiveSegmentAddr	Active, temp;
	ActiveSegmentAddr	first;
	Integer				firstX;
	LineSegmentAddr		newline;
	Boolean				DoMore	= NO;	// do more loops to continue prossessing the segment
	//
	//	Set currentGroup to point to the second group.
	//
	currentGroup = RegionData->next;
	while (currentGroup != EndOfGroups)
	{
		currentY = currentGroup->y;
		curSeg = [self   GetNextSegmentFromGroup: currentGroup];
		while (curSeg != NullSegment)
		{
			overlap = None;	// default overlap to none in case no actives presently.
			Active = ActiveList;
			while (Active != EndOfActiveList)
			{
				DoMore = NO;
				overlap = [self   CheckHowSegment: curSeg   Intersects: Active];
				switch (overlap)
				{
					//
					//	These are all the ways in which the line segment can overlap with
					//	an active segment.  I have diagrams for each which I can't
					//	include here which make the operations make much more sense.
					//	A line segment may in fact overlap an arbitrary number of active segments,
					//	but we only examine one at a time, and then after having dealt with
					//	the intersections, pass what remains of the segment for more.
					//
					case None :
						break;
					case Equal :
						[self   AddLineFrom:  curSeg->left To: curSeg->right At: currentY
							WithLeft: Active->leftLine  AndRight: Active->rightLine];
						break;
					case Larger:
						[self   AddLineFrom:  Active->left  To: Active->right At: currentY
							WithLeft: Active->leftLine  AndRight: Active->rightLine];
						[self   AddShapeFrom: curSeg->left To: Active->left At: currentY];
						//
						//	Since the right part might intersect with other actives,
						//	just store it as a segment, and we'll process it shortly
						//
						curSeg->left = Active->right;
						DoMore = YES;
						break;
					case Within:
						newline = [self   AddAntiShapeFrom:  curSeg->left
							To: curSeg->right  At: currentY];
						[self   AddActiveFrom: Active->left   To: curSeg->left
							WithLeft: Active->leftLine  AndRight: newline];
						[self   AddActiveFrom: curSeg->right   To: Active->right
							WithLeft: newline  AndRight: Active->rightLine];
						break;
					case TouchOuterLeft:
						newline = [self   AddLineFrom:  curSeg->left  To: curSeg->right
							At: currentY  WithLeft:NoLine AndRight: Active->leftLine];
						[self   AddActiveFrom: curSeg->left   To: Active->right
							WithLeft: newline  AndRight: Active->rightLine];
						break;
					case TouchOuterRight:
						first = [self   FindFirstActiveLeftIn: curSeg->left To: curSeg->right];
						if (first != EndOfActiveList)
							firstX = first->left;
						else
							firstX = 100000;  // definitely beyond any curSeg->right.
						if (firstX < curSeg->right)
						{
							newline = [self   AddLineFrom:  curSeg->left  To: firstX
								At: currentY  WithLeft: Active->rightLine
								AndRight: NoLine];
							[self   AddActiveFrom: Active->left   To: firstX
								WithLeft: Active->leftLine  AndRight: newline];
							curSeg->left = firstX;
							DoMore = YES;
						}
						else if (firstX == curSeg->right)
						{
							newline = [self   AddLineFrom:  curSeg->left  To: curSeg->right
								At: currentY  WithLeft: Active->rightLine
								AndRight: first->leftLine];
							[self   AddActiveFrom: Active->left   To: first->right
								WithLeft: Active->leftLine  AndRight: first->rightLine];
							[self   RemoveActive: first];
						}
						else // firstX > curSeg->right  // segment is totally 'ours'
						{
							newline = [self   AddLineFrom:  curSeg->left  To: curSeg->right
								At: currentY  WithLeft: Active->rightLine
								AndRight: NoLine];
							[self   AddActiveFrom: Active->left   To: curSeg->right
								WithLeft: Active->leftLine  AndRight: newline];
						}
						break;
					case TouchInnerLeft:
						newline = [self   AddLineFrom:  curSeg->left  To: curSeg->right
							At: currentY WithLeft: Active->leftLine AndRight: NoLine];
						[self   AddActiveFrom: curSeg->right   To: Active->right
							WithLeft: newline  AndRight: Active->rightLine];
						break;
					case TouchInnerRight:
						newline = [self   AddLineFrom:  curSeg->left  To: curSeg->right
							At: currentY WithLeft: NoLine  AndRight: Active->rightLine];
						[self   AddActiveFrom: Active->left   To: curSeg->left
							WithLeft: Active->leftLine  AndRight: newline];
						break;
					case TouchInnerLeftExtendRight:
						(void)  [self   AddLineFrom:  Active->left  To: Active->right
							At: currentY WithLeft: Active->leftLine
							AndRight: Active->rightLine];
						//
						//	Modify the current segment, and continue processing.
						//
						curSeg->left = Active->right;
						DoMore = YES;
						break;
					case TouchInnerRightExtendLeft:
						[self   AddLineFrom:  Active->left  To: Active->right At:currentY
							WithLeft: Active->leftLine  AndRight: Active->rightLine];
						[self   AddShapeFrom: curSeg->left To: Active->left At: currentY];
						break;
					case LeftOverlap:
						newline = [self   AddLineFrom:  Active->left  To: curSeg->right
							At: currentY WithLeft: Active->leftLine  AndRight: NoLine];
						[self AddActiveFrom: curSeg->right To:  Active->right
							WithLeft: newline  AndRight: Active->rightLine];
						[self   AddShapeFrom: curSeg->left To: Active->left At: currentY];
						break;
					case RightOverlap:
						newline = [self   AddLineFrom:  curSeg->left  To: Active->right
							At: currentY WithLeft: NoLine  AndRight: Active->rightLine];
						[self AddActiveFrom: Active->left To:  curSeg->left
							WithLeft: Active->leftLine  AndRight: newline];
						//
						//	Modify the current segment, and continue processing.
						//
						curSeg->left = Active->right;
						DoMore = YES;
						break;
				}
				if ( (overlap == None)  || (DoMore == YES) )
				{
					temp = Active;
					Active = Active->next;
					if (DoMore == YES)
						[self   RemoveActive: temp];
				}
				else 
				{
					[self   RemoveActive: Active];
					Active = EndOfActiveList;  // force processing of next segment
				}
			}
			if ( (overlap == None)  || (DoMore == YES) )
				[self   AddShapeFrom: curSeg->left To: curSeg->right At: currentY];
			free(curSeg);
			curSeg = [self   GetNextSegmentFromGroup: currentGroup];
		}
		currentGroup = currentGroup->next;
	}
	return self;
}


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//	Routine:		CheckHowSegment:Intersects:
//	Parameters:	A segment and an active segment
//	Returns:		an enumerated value indicating what kind of intersection there is
//	Stores:		none
//	Description:
//		This takes two segments, and figures out what kind of intersection they have.
//		The kinds of intersection are all named relative to the active segment
//		(i.eTouchInnerRight says that the segment touches the inner right edge of
//		the active segment (the left of the segment touches the right of the active, and
//		the rest of it is completely within the active's span).  ).  There are 13 cases
//		to consider.
//	Bugs:
//		This should be rtf code, so I could include illustrations of what these mean.
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

- (OverlapKind) CheckHowSegment: (SegmentAddr) segment
						Intersects: (ActiveSegmentAddr) active;
{
	OverlapKind		kind;


	if (segment->left > active->left)
	{
		if (segment->left > active->right)
			kind = None;
		else if (segment->left == active->right)
			kind = TouchOuterRight;
		else if (segment->right > active->right)
			kind = RightOverlap;
		else if (segment->right == active->right)
			kind = TouchInnerRight;
		else // (segment->right < active->right)
			kind = Within;
	}
	else if (segment->left == active->left)
	{
		if (segment->right > active->right)
				kind = TouchInnerLeftExtendRight;
		else if (segment->right == active->right)
			kind = Equal;
		else // (segment->right < active->right)
			kind = TouchInnerLeft;
	}
	else // (segment->left < active->left)
	{
		if (segment->right > active->left)
		{
			if (segment->right > active->right)
				kind = Larger;
			else if (segment->right == active->right)
				kind = TouchInnerRightExtendLeft;
			else // if (segment->right < active->right)
				kind = LeftOverlap;
		}
		else if (segment->right == active->left)
			kind = TouchOuterLeft;
		else // (segment->right < active->left)
			kind = None;
	}

	return kind;
}




//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//	Method:		WriteInteger:
//	Parameters:
//		An integer, and the file to write it to
//	Returns: 	self
//	Stores:		none  explicitly (subcalls may)
//	Description:
//		This simply writes out an integer with a trailing space.  ooh ahh. 
//	Bugs:
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- WriteInteger: (Integer) theInt To: theFile
{
	CString	temp	= NewCString(12);
	
	[theFile   WriteTextUsing: temp WithFormat: "%d ", theInt];
	
	FreeCString(temp);
	return self;
}



//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//	Method:		WriteShapeFromLine:
//	Parameters:	A line to start writing a shape from
//	Returns: 	self
//	Stores:		none
//	Description:
//		Walk through the shape, and print out its coordinates as we go.
//		As we visit each line segment, we mark it as used so we kno when to stop
//		when we eventually circle around the shape of the shape.
//		When we are in a line, we can only go in the left direction, or the right, and we
//		we figure that out based on the direction we were going in the previous.
//		(note: the direction dictates the order in which we print the line's coordinates,
//		as well as which edge to go from there).  When preparing to go to another line,
//		we check: is the line one can reach from this next line's left side the same as the current line?
//		if so, then we'll be entering on the left side of the line, and will have to go right.
//		otherwise, we'll be going left.  So, we set the direction flag accordingly, and proceed until we
//		find a null line, or we find a line marked as used. (This happens to work properly when
//		one is dealing with a square where each line segment poins to the other).
//		It's also relevant to note that this data structure only stores horizontal lines, like
//		a region, kinda.  Vertical lines are implied by the pointers between the horozontals.
//		And, of course, there's no such thing as a diagonal line here.
//	Bugs:
//		I'd hoped to deal with cases where the shape is incomplete by dropping edges
//		to QuickDraw infinity (32767).  This proved to be a bit more work than I wanted
//		to bother with, though.  So, I simply drop out, and don't do anything.
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

- WriteShapeFromLine:  (LineSegmentAddr) startLine  To: PsFile
{
	LineSegmentAddr		theLine		= startLine;
	DirectionType		direction		= toRight;
	Integer				lineCount	= 0;
	Integer				numOnLine	= 0;

	while (theLine->used != YES)
	{
		//
		//	Tag the line as used, both so we don't loop around in it forever, as well
		//	as to keep us inadvertantly printing it twice, since it is possible for
		//	the converter to think it's identified two+ shapes when it's really identified
		//	two+ parts of one shape
		//
		theLine->used = YES;

		if (direction == toLeft)
		{
			[self   WriteInteger:  theLine->right.x To: PsFile];
			[self   WriteInteger:  theLine->right.y To: PsFile];
			[PsFile   WriteText: " "];
			[self   WriteInteger:  theLine->left.x To: PsFile];
			[self   WriteInteger:  theLine->left.y To: PsFile];
			if (theLine->leftNext == NoLine)
			{
				//	Do nothing.  This line will be noted as being used in the
				//	While loop condition, and we will drop out.
			}
			else
			{
				if (theLine->leftNext->leftNext == theLine)
					direction = toRight;
				else
					direction = toLeft;
				theLine = theLine->leftNext;
			}
		}
		else
		{
			[self   WriteInteger:  theLine->left.x To: PsFile];
			[self   WriteInteger:  theLine->left.y To: PsFile];
			[PsFile   WriteText: " "];
			[self   WriteInteger:  theLine->right.x To: PsFile];
			[self   WriteInteger:  theLine->right.y To: PsFile];
			if (theLine->rightNext == NoLine)
			{
				//	Do nothing.  This line will be noted as being used in the
				//	While loop condition, and we will drop out.
			}
			else
			{
				if (theLine->rightNext->rightNext == theLine)
					direction = toLeft;
				else
					direction = toRight;
				theLine = theLine->rightNext;
			}
		}
		lineCount++;
		numOnLine++;
		//
		//	If we've written a certain number of points on the output line, then
		//	move on to the next outputline, otherwise separate from the next by a
		//	couple spaces and continue.
		//
		if (numOnLine >= 5)
		{
			[PsFile   ForceNewLine];
			numOnLine = 0;
		}
		else
			[PsFile   WriteText: "  "];
	}
	if (numOnLine != 0)
		[PsFile   ForceNewLine];
	[self   WriteInteger:  (lineCount * 2) To: PsFile]; // write out # of points we wrote
	[PsFile   ForceNewLine];
	return self;
}


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//	Method:		WriteTo:
//	Parameters:	The file object to write to
//	Returns: 	self
//	Stores:		none  explicitly (subcalls may)
//	Description:
//		This walks through the chain of shapes.  If the first line of a shape has not
//		been used (written out), we assume that the shape hasn't been touched, and ask to
//		write it out.  Otherwise, we skip it and go on to the next shape.
//		We assume that WriteShapeFrom: terminates its work with a newline, and
//		we follow this with the total number of shapes we wrote, and the rectangle
//		that bound the whole region.
//	Bugs:
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- WriteTo: PsFile
{
	LineSegmentAddr		theLine;
	Integer				numShapes		= 0;
	ShapeAddr			currentShape	= ShapeStorage;
	
	while (currentShape != NoShape)
	{
		theLine = currentShape->theLine;
		if (theLine->used == NO)
		{
			//
			//	Write out the points that make up the shape
			//
			numShapes++;
			[self   WriteShapeFromLine: theLine  To: PsFile];
		}
		currentShape = currentShape->nextShape;
	}
	[self   WriteInteger:  numShapes To: PsFile];
	[PsFile   ForceNewLine];
	//
	//	Write the bounding rectangle
	//
	[self   WriteInteger: boundsRect->top To: PsFile];
	[self   WriteInteger: boundsRect->left To: PsFile];
	[self   WriteInteger: boundsRect->bottom To: PsFile];
	[self   WriteInteger: boundsRect->right To: PsFile];
	[PsFile   ForceNewLine];

	return self;
}



//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//	Routine:		CleanUp:
//	Parameters:	none
//	Returns:		self
//	Stores:		none
//	Description:
//		this walks through the instance variables, and frees up all the chains of data.
//		hopefully.
//	Bugs:
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- CleanUp
{
	SegmentGroupAddr	tempGroup	= RegionData;
	SegmentGroupAddr	scratch1;
	SegmentLinkAddr	tempSegmentLink, scratch2;
	ActiveSegmentAddr	scratch3,  tempActiveLink = ActiveList;
	ShapeAddr			scratch4, currentShape = ShapeStorage;
	//
	//	First, purge the data left over from reading in the region
	//
	while (tempGroup != EndOfGroups)
	{
		tempSegmentLink = tempGroup->segmentData;
		while (tempSegmentLink != EndOfChain)
		{
			scratch2 = tempSegmentLink;
			tempSegmentLink = tempSegmentLink->nextSegment;
			free(scratch2);
		}
		scratch1 = tempGroup;
		tempGroup = tempGroup->next;
		free(scratch1);
	}
	RegionData = EndOfGroups;
	//
	//	Clear the active list  (it should already be cleared... but just in case...
	//
	while (tempActiveLink != EndOfActiveList)
	{
		scratch3 = tempActiveLink;
		tempActiveLink = tempActiveLink->next;
		free(scratch3);
	}
	ActiveList = EndOfActiveList;
	//
	//	Clear the shapes.
	//
	while (currentShape != NoShape)
	{
		//
		//	SERIOUS memory leak problem here.  We do not free the individual lines that
		//	make up the shape here.  Why not?  Because a line could be pointed to by more than
		//	one shape, and it is going to be difficult to deal with this, since it means that for every
		//	line we free from a shape, we must first check whether it is pointed to by any of the
		//	remaining shapes.  It's not presently worth the effort, given the very low usage this
		//	will get.
		//
		scratch4 = currentShape;
		currentShape = currentShape->nextShape;
		free(scratch4);
	}
	ShapeStorage =  NoShape;
	//
	//	Write out the bounding rectangle
	//
	if (boundsRect != NULL)
		free(boundsRect);
	boundsRect = NULL;
	return self;
}



@end



#if 0
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//	Method:		FindEndFrom:Going:
//	Parameters:	A line to start walking from, and a direction to go in.
//	Returns: 	The direction, on the final line, that the last coordinate is
//	Stores:		The final line in first_result
//	Description:
//		The purpose of this is to start at a specific line, and continue until we find
//		a line that leasds to (a) a Null line poiner, or (b) a line marked as used.
//		We use a traversal algorithm also used by writeShapeFromLine: that keeps us
//		from walking back the way we came inadvertantly.  When we finish, we return
//		a pointer to the final good line we were on, and a direction (toLeft or toRight)
//		indicating which way were heading when we found the end (hence, if we
//		return toRight, the right coordinate in the line we return is the 'last' coordinate
//		in the shape in this direction.
//	Bugs:
//		This routine isn't actually used for anything.  It's included here merely
//		because I wrote it to start to deal with the 'null line' problem in WriteShapeFromLine:
//		but ended up abandoning the project as being too much work for such a tiny
//		special case.  It remains in case I should ever choose to deal with that case.
//	NOTE:
//		Please read RegionConverter.rtf, since that describes much more about how
//		this object behaves!
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
-(DirectionType) FindEndFrom: (LineSegmentAddr) startLine  Going: (DirectionType) theDir
{
	LineSegmentAddr		theLine		= startLine;
	DirectionType		direction		= theDir;
	Boolean				endFound	= NO;

	while (endFound == NO)
	{
		if (direction == toLeft)
		{
			if ( (theLine->leftNext == NoLine)  || (theLine->leftNext->used  == YES) )
				endFound = YES;
			else
			{
				if (theLine->leftNext->leftNext == theLine)
					direction = toRight;
				else
					direction = toLeft;
				theLine = theLine->leftNext;
			}
		}
		else
		{
			if ( (theLine->rightNext == NoLine)  || (theLine->rightNext->used  == YES) )
				endFound = YES;
			else
			{
				if (theLine->rightNext->rightNext == theLine)
					direction = toLeft;
				else
					direction = toRight;
				theLine = theLine->rightNext;
			}
		}
	}
	[self   StorePointer: (Pointer) theLine];

	return direction;
}
#endif
