/*
		Copyright (c) Uwe Hoffmann, 1995.
                  All Rights Reserved.

Filename: MiscLayoutTree.m
Author:   Uwe Hoffmann
Date:	  Sep 03, 1995

$Id: MiscLayoutTree.m,v 1.1 1995/09/03 11:22:00 Uwe Hoffmann Exp $
 $Log: MiscLayoutTree.m,v $
*/

#import <foundation/foundation.h>
#import <foundation/NSArchiver.h>

#import "MiscLayoutTree.h"

//************************************************************************

@interface MiscLayoutTreeEnumerator:NSEnumerator
{
	MiscLayoutTree *current;
	MiscLayoutTree *root;
	BOOL depth;
	int level;
}

- initWithRoot:(MiscLayoutTree *)aNode traverseDepth:(BOOL)aBool;

@end

@implementation MiscLayoutTreeEnumerator

- initWithRoot:(MiscLayoutTree *)aNode traverseDepth:(BOOL)aBool
{
	[super init];
	current = nil;
	root = aNode;
	depth = aBool;
	level = 0;
	return self;
}

- nextObject
{
	MiscLayoutTree *t;
	int l;
	int f;
	BOOL found;
	
	if(!current){
		current = root;
		return root;
	}
	t = current;
	if(depth){
		if([t child])
			t = [t child];
		else if([t sibling])
			t = [t sibling];
		else {
			while([t parent] && ![t sibling])
				t = [t parent];
			if([t sibling])	
				t = [t sibling];
			else
				t = nil;
		}
	} else {
		if([t sibling])
			t = [t sibling];
		else {
			l = level;
			f = 0;
			found = NO;
			while(f < 2 && !found){
				while([t parent] && ![t sibling]){
					l--;
					t = [t parent];
				}
				if([t sibling])	
					t = [t sibling];
				else {
					level++;
					f++;
				}
				while(level > l && [t child]){
					t = [t child];
					l++;
				}
				if(level == l)
					found = YES;
			}
			if(!found)
				t = nil;
		}
	}
	current = t;
	return t;
}

@end

//************************************************************************

static float horizontalmerge(MiscPolygon *c1,MiscPolygon *c2, NSZone *zone);
static float verticalmerge(MiscPolygon *c1,MiscPolygon *c2, NSZone *zone);
static float offset(float p1,float p2,float a1,float a2,float b1,float b2);
static MiscPolyline *horizontalbridge(MiscPolyline *line1,MiscPolyline *line2,
				float x1,float y1,float x2,float y2, NSZone *zone);
static MiscPolyline *verticalbridge(MiscPolyline *line1,MiscPolyline *line2,
				float x1,float y1,float x2,float y2, NSZone *zone);
static MiscPolyline *allocLine(float aX,float aY,MiscPolyline *aLink, NSZone *zone);
static MiscPolyline *copyLine(MiscPolyline *aSource,MiscPolyline **aTail, NSZone *zone);
static void freeLine(MiscPolyline *aLine, NSZone *zone);
static void partialFreeLine(MiscPolyline *aLine, MiscPolyline *toEnd, NSZone *zone);
static NSRect makeRectFromPolygon(MiscPolygon *aPol, NSPoint ipl, NSPoint ipu);

//************************************************************************
								 
@interface MiscLayoutTree(PrivateMethods)

- (void)_internalHorizontalAttachParent:(float)h;
- (void)_internalHorizontalLayoutLeaf;
- (float)_internalHorizontalJoin;
- (void)_internalVerticalAttachParent:(float)h;
- (void)_internalVerticalLayoutLeaf;
- (float)_internalVerticalJoin;
- _internalCopyWithZone:(NSZone *)zone parent:aParent;
- (void)_internalPositionFrom:(NSPoint)aPoint;
- (void)_internalInvalidateLayout;
- (void)_internalSetDistanceToParent:(float)aDistance;
- (void)_internalSetBorder:(float)aBorder;
- (void)_internalSetLayoutType:(MiscLayoutTreeType)aType;
- (void)_internalSetOrientation:(MiscLayoutTreeOrientation)anOrientation;
- (void)_internalHorizontalLayout;
- (void)_internalVerticalLayout;
- _internalFindRoot;

@end

//************************************************************************

@implementation MiscLayoutTree
/*"An instance of this class holds a tree data structure that can lay itself out.
The following aesthetic rules are used:

	Siblings of the same parent node lie along a line.
	
	A subtree looks the same, regardless of where it occurs.
	
	A tree is drawn as compact as possible.
	
A tree is layed out vertically or horizontally, depending on the layout type, which can be queried with #layoutType
and can be set to one of the values %MiscHorizontalTreeType or %MiscVerticalTreeType with #setLayoutType:.
	
The layout distance between nodes is defined by two parameters: the distance to the parent %distanceToParent and the border %border. 
Both parameters remain the same for every node. 
Every node in the tree has 3 pointers: a pointer to his parent, a pointer to a sibling and a pointer to his first child. 
This way every node has a uniquely defined predecessor. The position %pos of the node is defined as the %pos of the predecessor plus the %offset of the node.
Every node keeps track of the polygonial contour of its subtree. The layout algorithm makes sure the contours of siblings donÂt overlap.
The algorithm was published by Sven Moen in IEEE Software, July 1990.
The MiscLayoutTree class provides methods for querying and setting the geometric parameters of the node. Setting the position of the node with #setPos: is only allowed for the root node. The method #nodeBounds returns a NSRect with the bounds of the node and the method
#branchBounds returns a NSRect with the bounds of the subtree rooted in the node.
The methods #depthEnumerator and #breadthEnumerator permit sequential access of the elements of the tree, differing only in the way of travel through the elements (depth first or breadth first).
The methods #addBranch:, #insertBranch:at:, #removeBranch: and #removeBranchAt: modify the tree data structure.
A subtree can be collapsed into its root node with the method #collapse. 
All methods modifying the geometric parameters or the tree data structure call #invalidateLayout.
The method #layout lays out the tree and marks the layout as valid."*/    

//************************************************************************

+ tree
/*"Creates, initializes and returns a MiscLayoutTree instance."*/
{
	return [[[self alloc] init] autorelease];
} 

+ treeWithSize:(NSSize)aSize
/*"Creates, initializes and returns a MiscLayoutTree instance with size aSize."*/
{
	return [[[self alloc] initWithSize:aSize] autorelease];
} 

- initWithSize:(NSSize)aSize
/*"Initializes a newly created instance of MiscLayoutTree with aSize. This is the designated initializer of this class."*/
{  
   	self = [super init];
	contour.lower.head = contour.upper.head = NULL;
   	contour.lower.tail = contour.upper.tail = NULL;
	parent = child = sibling = nil;
	offset.x = offset.y = 0.0;
	pos.x = pos.y = 0.0;
	size = aSize;
	distanceToParent = 30;
	border = 10;
	updateLayout = YES;
	collapsed = NO; 
	layoutType = MiscHorizontalTreeType;
	orientation = MiscStandardOrientation;
	tag = -1; 	
   	return self;
}

- init
{  
   return [self initWithSize:NSMakeSize(30,10)];  	
}
   
- (void)dealloc
{
	MiscLayoutTree *c,*b;
	
	if(contour.lower.head)
		freeLine(contour.lower.head, [self zone]);
	if(contour.upper.head)
		freeLine(contour.upper.head, [self zone]);
	c = child;
	while(c){
		b = c;
		c = c->sibling;
		[b release];
	}
   	return [super dealloc];
}

- copyWithZone:(NSZone *)zone
{
   	MiscLayoutTree *theCopy;

   	theCopy = [self copyNodeWithZone:zone];
	if(child)
		theCopy->child = [child _internalCopyWithZone:zone parent:theCopy];
	else
		theCopy->child = nil;
	return theCopy;
}

- copy
{
	return [self copyWithZone:NULL];
}

- copyNodeWithZone:(NSZone *)zone
/*"This method is called by #copy and by #copyWithZone: to copy the node specific instance variables.
You should overwrite this method rather than #copyWithZone: in a subclass. The reason is the method 
#copyWithZone: makes a deep copy of the subtree rooted in the receiver, thus must take care of the tree
structure."*/
{
	MiscLayoutTree *theCopy;
	
	theCopy = (MiscLayoutTree *)NSCopyObject(self, 0, zone);
	theCopy->contour.upper.head = contour.upper.tail = NULL;
	theCopy->contour.lower.head = contour.lower.tail = NULL;
	theCopy->updateLayout = YES;
	theCopy->parent = nil;
	theCopy->sibling = nil;
	return theCopy;
}

//************************************************************************

- (void)layout
/*"Lays out the tree and resets updateLayout to NO. A collapsed subtree is layed out as a leaf. 
This method can only be called on receivers that are root nodes of MiscLayoutTree,
i.e. nodes with the parent pointer nil. Calling this method with other nodes raises a #NSGenericException."*/
{ 	
	if(parent)
		[NSException raise:NSGenericException format:@"Node is not root node"];
	if(!updateLayout)
		return;
	if(layoutType == MiscHorizontalTreeType)
		[self _internalHorizontalLayout];
	else
		[self _internalVerticalLayout];
	if(child)
		[child _internalPositionFrom:pos];
	[self layoutNode];
	return;
}

- (BOOL)needsUpdateLayout
/*"Returns whether the receiver needs to update the layout. This method can only be called on receivers that 
are root nodes of MiscLayoutTree, i.e. nodes with the parent pointer nil. Calling this method with other nodes 
raises a #NSGenericException. Updating is done by sending the receiver the #layout message."*/
{
	if(parent)
		[NSException raise:NSGenericException format:@"Node is not root node"];
	return updateLayout;
}

- (void)invalidateLayout
/*"Marks the layout of the receiver as invalid. The layout of the receiverÂs parent will also be invalid and so on 
up to the root node of the tree the receiver belongs to. If you overwrite this method make %{[super invalidateLayout]} 
the first statement of your methods body."*/ 
{
	[self _internalInvalidateLayout];
}

- (void)layoutNode
{
	return;
}

//************************************************************************

- (void)setPos:(NSPoint)aPos
/*"Sets the position of the receiver to aPos. This method can only be called on receivers that are root nodes of
MiscLayoutTree, i.e. nodes with the parent pointer nil. Calling this method with other nodes raises a #NSGenericException.
The position of a child node is calculated from the position of the predecessor node and the offset of the child node."*/
{
	if(parent)
		[NSException raise:NSGenericException format:@"Node is not root node"];
	pos = aPos;
	if(child)
		[child _internalPositionFrom:pos];
	[self layoutNode];
}

- (void)setSize:(NSSize)aSize
/*"Sets the size of the receiver to aSize and marks the layout as invalid with #invalidateLayout."*/
{
	size = aSize;
	[self invalidateLayout];
}

- (void)setDistanceToParent:(float)aDistance
/*"Sets the distance to parent of the receiver to aDistance. The distance to the parent node is a property 
concerning the whole tree, so this method can only be called on receivers that are root 
nodes of a MiscLayoutTree, i.e. nodes with the parent pointer nil. Calling this method with 
other nodes raises a #NSGenericException. Marks the layout as invalid with #invalidateLayout."*/ 
{
	if(parent)
		[NSException raise:NSGenericException format:@"Node is not root node"];
	[self _internalSetDistanceToParent:aDistance];
}

- (void)setBorder:(float)aBorder
/*"Sets the border of the receiver to aDistance. The border is a property 
concerning the whole tree, so this method can only be called on receivers that are root 
nodes of a MiscLayoutTree, i.e. nodes with the parent pointer nil. Calling this method with 
other nodes raises a #NSGenericException. Marks the layout as invalid with #invalidateLayout."*/
{
	if(parent)
		[NSException raise:NSGenericException format:@"Node is not root node"];
	[self _internalSetBorder:aBorder];
}

- (NSPoint)pos
/*"Returns the position of the receiver."*/
{
	return pos;
}

- (NSPoint)offset
/*"Returns the offset of the receiver relative to its predecessor."*/
{
	return offset;
}

- (NSSize)size
/*"Returns the size of the receiver."*/
{
	return size;
}

- (float)distanceToParent
/*"Returns the distance to parent property of the tree the receiver belongs to."*/
{
	return distanceToParent;
}

- (float)border
/*"Returns the border property of the tree the receiver belongs to."*/
{
	return border;
}

- (float)width
/*"Returns the width of the receiver."*/
{
	return size.width;
}

- (float)height
/*"Returns the height of the receiver."*/
{
	return size.height;
}

- (NSRect)nodeBounds
/*"Returns the node bounds of the receiver."*/
{	
	return NSMakeRect(pos.x,pos.y,size.width,size.height);
}

- (NSRect)branchBounds
/*"Returns the bounds of the subtree rooted in the receiver."*/
{
	NSRect r;
	
	if(updateLayout)
		[self layout];
	if(layoutType == MiscHorizontalTreeType)
		r = makeRectFromPolygon(&contour,
			NSMakePoint(pos.x - border,pos.y + size.height + border), NSMakePoint(pos.x - border,pos.y - border));
	else
		r = makeRectFromPolygon(&contour,
			NSMakePoint(pos.x + size.width + border,pos.y - border),NSMakePoint(pos.x - border,pos.y - border));
	r.origin.x += border;
	r.origin.y += border;
	r.size.width -= 2 * border;
	r.size.height -= 2 * border; 
	return r;
}

- (MiscLayoutTreeType)layoutType
/*"Returns the type of the tree (MiscHorizontalTreeType for horizontal layout 
 or MiscVerticalTreeType vertical for vertical layout)."*/
{
	return layoutType;
}

- (void)setLayoutType:(MiscLayoutTreeType)aType
/*"Sets the layout type of the receiver to aType. The layout type is a property 
concerning the whole tree, so this method can only be called on receivers that are root 
nodes of a MiscLayoutTree, i.e. nodes with the parent pointer nil. Calling this method with 
other nodes raises a #NSGenericException. Marks the layout as invalid with #invalidateLayout."*/
{
	if(parent)
		[NSException raise:NSGenericException format:@"Node is not root node"];
	if(aType != layoutType)
		[self _internalSetLayoutType:aType];
}

- (MiscLayoutTreeOrientation)orientation
/*"Returns the orientation of the tree."*/
{
	return orientation;
}

- (void)setOrientation:(MiscLayoutTreeOrientation)anOrientation
/*"Sets the orientation of the receiver to aType. The orientation is a property 
concerning the whole tree, so this method can only be called on receivers that are root 
nodes of a MiscLayoutTree, i.e. nodes with the parent pointer nil. Calling this method with 
other nodes raises a #NSGenericException. Marks the layout as invalid with #invalidateLayout.
Note: Has no effect in this version (i.e. layout is independent of this parameter).
This is due to a restriction in the layout algorithm which requires a certain
monotony property in the polylines."*/
{
	if(parent)
		[NSException raise:NSGenericException format:@"Node is not root node"];
	if(anOrientation != orientation)
		[self _internalSetOrientation:anOrientation];
}
	
//************************************************************************

- (MiscLayoutTree *)sibling
/*"Returns the sibling of the receiver."*/
{
   	return sibling;
}

- (MiscLayoutTree *)child
/*"Returns the first child of the receiver."*/
{
	return child;
}

- (MiscLayoutTree *)parent
/*"Returns the parent of the receiver."*/
{
	return parent;
}

- (NSEnumerator *)depthEnumerator
/*"Returns an enumerator object that lets you access each node in the tree, starting with the root node
 and traversing the tree depth first."*/
{
	return [[[MiscLayoutTreeEnumerator allocWithZone:[self zone]] 
		initWithRoot:[self _internalFindRoot] traverseDepth:YES] autorelease];
}  

- (NSEnumerator *)breadthEnumerator;
/*"Returns an enumerator object that lets you access each node in the tree, starting with the root node
 and traversing the tree breadth first."*/
{
	return [[[MiscLayoutTreeEnumerator allocWithZone:[self zone]] 
		initWithRoot:[self _internalFindRoot] traverseDepth:NO] autorelease];
}  

- (unsigned)numberOfChildren
/*"Returns the number of children of the receiver."*/
{
	unsigned i = 0;
	MiscLayoutTree *c = child;
	
	while(c){
		i++;
		c = c->sibling;
	}
	return i;
}

- (MiscLayoutTree *)branchAt:(unsigned)index
/*"Returns the child numbered index (starting at zero) in the list of children of the receiver."*/
{
	unsigned i = 0;
	MiscLayoutTree *c = child;
	
	while(c && i < index){
		i++;
		c = c->sibling;
	}
	if(i == index)
		return c;
	else
		return nil;
}

- (void)addBranch:(MiscLayoutTree *)branch
/*"Adds the branch to the receiverÂs list of children. Marks the layout as invalid with #invalidateLayout."*/
{
	MiscLayoutTree *c;
	
	if(!branch)
		return;
	[branch retain];
	[branch setDistanceToParent:distanceToParent];
	[branch setBorder:border];
	branch->parent = self;
	if(!child){
		child = branch;
	} else {
		c = child;
		while(c->sibling)
			c = c->sibling;
		c->sibling = branch;
		branch->sibling = nil;
	}
	[self invalidateLayout];
}

- (void)insertBranch:(MiscLayoutTree *)branch at:(unsigned)index
/*"Inserts the branch in the receiverÂs list of children at position index. Marks the layout as invalid with #invalidateLayout."*/
{
	MiscLayoutTree *c;
	unsigned i;
	
	if(!branch)
		return;
	[branch retain];
	[branch setDistanceToParent:distanceToParent];
	[branch setBorder:border];
	branch->parent = self;
	c = child;
	i = 0;
	while(c->sibling && i < index){
		i++;
		c = c->sibling;
	}
	if(i == index){
		branch->sibling = c->sibling;
		c->sibling = branch;
	}
	[self invalidateLayout];
}

- (void)removeBranch:(MiscLayoutTree *)branch
/*"Removes branch from the receiverÂs list of children. Marks the layout as invalid with #invalidateLayout."*/
{
	MiscLayoutTree *c,*f;
	
	if(!child || !branch)
		return;
	c = child;
	f = child;
	while(f && ![f isEqual:branch]){
		c = f;
		f = f->sibling;
	}
	if([f isEqual:branch]){
		if(c == f)
			child = child->sibling;
		else
			c->sibling = f->sibling;
		[f release];
	}
	[self invalidateLayout];
}

- (void)removeBranchAt:(unsigned)index
/*"Removes the branch at position index in the receiverÂs list of children. Marks the layout as invalid with #invalidateLayout."*/
{
	MiscLayoutTree *c,*f;
	unsigned i;
	
	if(!child)
		return;
	c = child;
	f = child;
	i = 0;
	while(f && i != index){
		i++;
		c = f;
		f = f->sibling;
	}
	if(i == index){
		if(c == f)
			child = child->sibling;
		else
			c->sibling = f->sibling;
		[f release];
	}
	[self invalidateLayout];
}

- (void)moveBranchAt:(unsigned)index to:(unsigned)otherIndex
/*"Changes position of branch in the receiverÂs list of children from index to otherIndex. Marks the layout as invalid with #invalidateLayout."*/
{
	MiscLayoutTree *c,*f;
	unsigned i;
	
	c = child;
	f = child;
	i = 0;
	while(f && i != index){
		i++;
		c = f;
		f = f->sibling;
	}
	if(i != index)
		return;
	if(c == f)
		child = child->sibling;
	else
		c->sibling = f->sibling;
	c = child;
	i = 0;
	while(c->sibling && i < otherIndex){
		i++;
		c = c->sibling;
	}
	if(i == otherIndex){
		f->sibling = c->sibling;
		c->sibling = f;
	}
	[self invalidateLayout];
}

- (BOOL)isCollapsed
/*"Returns whether receiver is a collapsed subtree."*/
{
	return collapsed;
}

- (void)collapse
/*"Collapses the subtree rooted in the receiver and marks the layout as invalid with #invalidateLayout. Does nothing if subtree is already collapsed."*/
{
	if(!collapsed){
		collapsed = YES;
		[self invalidateLayout];
	}
}

- (void)expand
/*"Expands the collapsed subtree rooted in the receiver and marks the layout as invalid with #invalidateLayout. Does nothing if subtree is already expanded."*/
{
	if(!collapsed){
		collapsed = NO;
		[self invalidateLayout];
	}
}

- (void)toggleCollapse
/*"Expands or collapses the subtree rooted in the receiver according to its current state and marks the layout as invalid with #invalidateLayout."*/
{
	collapsed = !collapsed;
	[self invalidateLayout];
}

//************************************************************************

- (void)setTag:(int)aTag
/*"Provides a way to identify nodes."*/
{
	tag = aTag;
}

- (int)tag
/*"Returns the tag of the node."*/
{
	return tag;
}

//************************************************************************

- (void)encodeWithCoder:(NSCoder *)coder
{
	[super encodeWithCoder:coder];
	[coder encodeValuesOfObjCTypes:"{ff}{ff}{ff}ff", &pos, &offset, &size, &distanceToParent, &border];
	[coder encodeValuesOfObjCTypes:"iiii", &collapsed, &layoutType, &orientation, &tag];
	[coder encodeConditionalObject:parent];
	[coder encodeObject:child];
	[coder encodeObject:sibling];
}

- initWithCoder:(NSCoder *)coder
{
	self = [super initWithCoder:coder];
	[coder decodeValuesOfObjCTypes:"{ff}{ff}{ff}ff", &pos, &offset, &size, &distanceToParent, &border];
	[coder decodeValuesOfObjCTypes:"iiii", &collapsed, &layoutType, &orientation, &tag];
	parent = [coder decodeObject];
	child = [[coder decodeObject] retain];
	sibling = [[coder decodeObject] retain];
	contour.lower.head = contour.upper.head = NULL;
   	contour.lower.tail = contour.upper.tail = NULL;
	updateLayout = YES;
	return self;
}
			              
@end

//************************************************************************

@implementation MiscLayoutTree(PrivateMethods)

- (void)_internalHorizontalAttachParent:(float)h
{
    float x,y1,y2;

    x = border + distanceToParent;
    y2 = (h - size.height) / 2 - border;
    y1 = y2 + size.height + 2 * border - h;
	child->offset.x = x + size.width;
	child->offset.y = y1;  
    contour.upper.head = allocLine(size.width,0,allocLine(x,y1,contour.upper.head,[self zone]),[self zone]);
    contour.lower.head = allocLine(size.width,0,allocLine(x,y2,contour.lower.head,[self zone]),[self zone]);
}

- (void)_internalHorizontalLayoutLeaf
{
	if(contour.lower.head)
		freeLine(contour.lower.head, [self zone]);
	if(contour.upper.head)
		freeLine(contour.upper.head, [self zone]);
    contour.upper.tail = allocLine(size.width + 2 * border,0,NULL,[self zone]);
    contour.upper.head = contour.upper.tail;
    contour.lower.tail = allocLine(0, - size.height - 2 * border,NULL,[self zone]);
    contour.lower.head = allocLine(size.width + 2 * border,0,contour.lower.tail,[self zone]);
}

- (float)_internalHorizontalJoin
{
    MiscLayoutTree *c;
    float d,h,sum;
	MiscPolygon p;

    c = child;
	if(contour.lower.head)
		freeLine(contour.lower.head, [self zone]);
	if(contour.upper.head)
		freeLine(contour.upper.head, [self zone]);
    if(c->contour.upper.head)
   		contour.upper.head = copyLine(c->contour.upper.head,&(contour.upper.tail),[self zone]);
	else
		contour.upper.head = contour.upper.tail = NULL;
	if(c->contour.lower.head)
   		contour.lower.head = copyLine(c->contour.lower.head,&(contour.lower.tail),[self zone]);
	else
		contour.lower.head = contour.lower.tail = NULL;
    sum = h = c->size.height + 2 * c->border;
    c = [c sibling];
    while(c){
		if(c->contour.upper.head)
   			p.upper.head = copyLine(c->contour.upper.head,&(p.upper.tail),[self zone]);
		else
			p.upper.head = p.upper.tail = NULL;
		if(c->contour.lower.head)
   			p.lower.head = copyLine(c->contour.lower.head,&(p.lower.tail),[self zone]);
		else
			p.lower.head = p.lower.tail = NULL;
        d = horizontalmerge(&contour,&p,[self zone]);
		c->offset.x = 0;
		c->offset.y = d + h;
        h = c->size.height + 2 * c->border;
        sum += d + h;
        c = [c sibling];
    } 
    return sum;
}

- (void)_internalVerticalAttachParent:(float)h
{
	float x1,x2,y;
	
	y = border + distanceToParent;
	x2 = (h - size.width) / 2 - border;
    x1 = x2 + size.width + 2 * border - h;
	child->offset.x = x1;
	child->offset.y = y + size.height;
	contour.upper.head = allocLine(0,size.height,allocLine(x1,y,contour.upper.head,[self zone]),[self zone]);
    contour.lower.head = allocLine(0,size.height,allocLine(x2,y,contour.lower.head,[self zone]),[self zone]);
}

- (void)_internalVerticalLayoutLeaf
{
	if(contour.lower.head)
		freeLine(contour.lower.head, [self zone]);
	if(contour.upper.head)
		freeLine(contour.upper.head, [self zone]);
    contour.upper.tail = allocLine(0,size.height + 2 * border,NULL,[self zone]);
    contour.upper.head = contour.upper.tail;
    contour.lower.tail = allocLine(- size.width - 2 * border,0,NULL,[self zone]);
    contour.lower.head = allocLine(0,size.height + 2 * border,contour.lower.tail,[self zone]);
}

- (float)_internalVerticalJoin
{
    MiscLayoutTree *c;
    float d,h,sum;
	MiscPolygon p;

    c = child;
	if(contour.lower.head)
		freeLine(contour.lower.head, [self zone]);
	if(contour.upper.head)
		freeLine(contour.upper.head, [self zone]);
    if(c->contour.upper.head)
   		contour.upper.head = copyLine(c->contour.upper.head,&(contour.upper.tail),[self zone]);
	else
		contour.upper.head = contour.upper.tail = NULL;
	if(c->contour.lower.head)
   		contour.lower.head = copyLine(c->contour.lower.head,&(contour.lower.tail),[self zone]);
	else
		contour.lower.head = contour.lower.tail = NULL;
    sum = h = c->size.width + 2 * c->border;
    c = [c sibling];
    while(c){
		if(c->contour.upper.head)
   			p.upper.head = copyLine(c->contour.upper.head,&(p.upper.tail),[self zone]);
		else
			p.upper.head = p.upper.tail = NULL;
		if(c->contour.lower.head)
   			p.lower.head = copyLine(c->contour.lower.head,&(p.lower.tail),[self zone]);
		else
			p.lower.head = p.lower.tail = NULL;
        d = verticalmerge(&contour,&p,[self zone]);
		c->offset.y = 0;
		c->offset.x = d + h;
        h = c->size.width + 2 * c->border;
        sum += d + h;
        c = [c sibling];
    } 
    return sum;
}

- _internalCopyWithZone:(NSZone *)zone parent:aParent
{
   	MiscLayoutTree *theCopy;

   	theCopy = [self copyNodeWithZone:zone];
	theCopy->parent = aParent;
	if(child)
		theCopy->child = [child _internalCopyWithZone:zone parent:theCopy];
	else
		theCopy->child = nil;
	if(sibling)
		theCopy->sibling = [sibling _internalCopyWithZone:zone parent:aParent];
	else
		theCopy->sibling =	nil;
   	return theCopy;
}

- (void)_internalPositionFrom:(NSPoint)aPoint 
{
	pos.x = aPoint.x + offset.x;
	pos.y = aPoint.y + offset.y;
	if(child)
		[child _internalPositionFrom:pos];
	if(sibling)
		[sibling _internalPositionFrom:pos];
	[self layoutNode];
}

- (void)_internalInvalidateLayout
{
	updateLayout = YES;
	if(parent)
		[parent _internalInvalidateLayout];
}

- (void)_internalSetDistanceToParent:(float)aDistance
{
	distanceToParent = aDistance;
	if(child)
		[child _internalSetDistanceToParent:aDistance];
	if(sibling)
		[sibling _internalSetDistanceToParent:aDistance];
	updateLayout = YES;
}

- (void)_internalSetBorder:(float)aBorder
{
	border = aBorder;
	if(child)
		[child _internalSetBorder:aBorder];
	if(sibling)
		[sibling _internalSetBorder:aBorder];
	updateLayout = YES;
}

- (void)_internalSetLayoutType:(MiscLayoutTreeType)aType
{
	layoutType = aType;
	if(child)
		[child _internalSetLayoutType:aType];
	if(sibling)
		[sibling _internalSetLayoutType:aType];
	updateLayout = YES;
}

- (void)_internalSetOrientation:(MiscLayoutTreeOrientation)anOrientation
{
	orientation = anOrientation;
	if(child)
		[child _internalSetOrientation:anOrientation];
	if(sibling)
		[sibling _internalSetOrientation:anOrientation];
	updateLayout = YES;
}

- (void)_internalHorizontalLayout
{
    MiscLayoutTree *c;
 	
	if(!updateLayout)
		return;
	if(collapsed){
		[self _internalHorizontalLayoutLeaf];
		updateLayout = NO;
		return;
	}
    for(c = child;c;c = [c sibling])
          [c _internalHorizontalLayout];
    if(child)
          [self _internalHorizontalAttachParent:[self _internalHorizontalJoin]];
    else
          [self _internalHorizontalLayoutLeaf];
	updateLayout = NO;	
	return;
}

- (void)_internalVerticalLayout
{
    MiscLayoutTree *c;
 	
	if(!updateLayout)
		return;
	if(collapsed){
		[self _internalVerticalLayoutLeaf];
		updateLayout = NO;
		return;
	}
    for(c = child;c;c = [c sibling])
          [c _internalVerticalLayout];
    if(child)
          [self _internalVerticalAttachParent:[self _internalVerticalJoin]];
    else
          [self _internalVerticalLayoutLeaf];
	updateLayout = NO;
	return;
}

- _internalFindRoot
{
	MiscLayoutTree *c;
	 
	c = self;
	while([c parent])
		c = [c parent];
	return c;
}
		
@end

//************************************************************************

static float horizontalmerge(MiscPolygon *c1,MiscPolygon *c2, NSZone *zone)
{
    float x,y,total,d;
    MiscPolyline *lower,*upper,*b;

    x = y = total = 0;
    upper = c1->lower.head;
    lower = c2->upper.head;
    while(lower && upper){
        d = offset(x,y,lower->dx,lower->dy,upper->dx,upper->dy);
        y += d;
		total += d;
        if(x + lower->dx <= upper->dx){
               y += lower->dy;
               x += lower->dx;
               lower = lower->link;
        } else {
               y -= upper->dy;
               x -= upper->dx;
               upper = upper->link;
		}  
    }
    if(lower){
        b = horizontalbridge(c1->upper.tail,lower,0,0,x,y,zone);
        c1->upper.tail = (b->link) ? c2->upper.tail : b;
        c1->lower.tail = c2->lower.tail;
		partialFreeLine(c2->upper.head, lower->link, zone);
		freeLine(c1->lower.head, zone);
    } else {
        b = horizontalbridge(c2->lower.tail,upper,x,y,0,0,zone);
        if(!b->link)
            c1->lower.tail = b;
		partialFreeLine(c1->lower.head,upper->link, zone);
		freeLine(c2->upper.head, zone);	
    }
    c1->lower.head = c2->lower.head;
    return total;
}

static float verticalmerge(MiscPolygon *c1,MiscPolygon *c2, NSZone *zone)
{
    float x,y,total,d;
    MiscPolyline *lower,*upper,*b;

    x = y = total = 0;
    upper = c1->lower.head;
    lower = c2->upper.head;
    while(lower && upper){
		d = offset(y,x,lower->dy,lower->dx,upper->dy,upper->dx);
        x += d;
		total += d;
        if(y + lower->dy <= upper->dy){
               y += lower->dy;
               x += lower->dx;
               lower = lower->link;
        } else {
               y -= upper->dy;
               x -= upper->dx;
               upper = upper->link;
		}  
    }
    if(lower){
        b = verticalbridge(c1->upper.tail,lower,0,0,x,y,zone);
        c1->upper.tail = (b->link) ? c2->upper.tail : b;
        c1->lower.tail = c2->lower.tail;
		partialFreeLine(c2->upper.head, lower->link, zone);
		freeLine(c1->lower.head, zone);
    } else {
        b = verticalbridge(c2->lower.tail,upper,x,y,0,0,zone);
        if(!b->link)
            c1->lower.tail = b;
		partialFreeLine(c1->lower.head,upper->link, zone);
		freeLine(c2->upper.head, zone);	
    }
    c1->lower.head = c2->lower.head;
    return total;
}

static float offset(float p1,float p2,float a1,float a2,
                      float b1,float b2)
{
    float d,s,t;

    if(b1 <= p1 || p1 + a1 <= 0)
         return 0;
    t = b1 * a2 - a1 * b2;
    if(t > 0){
        if(p1 < 0)
            s = p1 * a2,d = s / a1 - p2;
        else if(p1 > 0)
            s = p1 * b2,d = s / b1 - p2;
        else
            d = -p2;
    } else if(b1 < p1 + a1)
        s = (b1 - p1) * a2,d = b2 - (p2 + s / a1);
    else if(b1 > p1 + a1)
        s = (a1 + p1) * b2, d = s / b1 - (p2 + a2);
    else
        d = b2 - (p2 + a2);
    return MAX(0,d);
}

static MiscPolyline *horizontalbridge(MiscPolyline *line1,MiscPolyline *line2,float x1,float y1,
                       float x2,float y2, NSZone *zone)
{
    float dx,dy,s;
    MiscPolyline *r;
   
    dx = x2 + line2->dx - x1;
    if(line2->dx == 0)
       dy = line2->dy;
    else
       s = dx * line2->dy,dy = s / line2->dx;
    r = allocLine(dx,dy,line2->link,zone);
    line1->link = allocLine(0,y2 + line2->dy -dy - y1,r,zone);
    return r;
}

static MiscPolyline *verticalbridge(MiscPolyline *line1,MiscPolyline *line2,float x1,float y1,
                       float x2,float y2, NSZone *zone)
{
    float dx,dy,s;
    MiscPolyline *r;
   
    dy = y2 + line2->dy - y1;
    if(line2->dy == 0)
       dx = line2->dx;
    else
       s = dy * line2->dx,dx = s / line2->dy;
    r = allocLine(dx,dy,line2->link,zone);
    line1->link = allocLine(x2 + line2->dx - dx - x1,0,r,zone);
    return r;
}

static MiscPolyline *allocLine(float aX,float aY,MiscPolyline *aLink, NSZone *zone)
{
    MiscPolyline *theAlloced;

    theAlloced = (MiscPolyline *)NSZoneMalloc(zone,sizeof(MiscPolyline));
    theAlloced->dx = aX;
    theAlloced->dy = aY;
    theAlloced->link = aLink; 
    return theAlloced;
}

static MiscPolyline *copyLine(MiscPolyline *aSource,MiscPolyline **aTail, NSZone *zone)
{
    MiscPolyline *aLine,*l,*result;
    
    l = aSource;
    aLine = (MiscPolyline *)NSZoneMalloc(zone,sizeof(MiscPolyline));
    aLine->dx = l->dx;
    aLine->dy = l->dy;
    aLine->link = NULL; 
    result = aLine;
    l = l->link;
    while(l){
        aLine->link = (MiscPolyline *)NSZoneMalloc(zone,sizeof(MiscPolyline));
        aLine = aLine->link;
        aLine->dx = l->dx;
        aLine->dy = l->dy;
        aLine->link = NULL;
        l = l->link;
    }
    *aTail = aLine;
    return result;
}

static void freeLine(MiscPolyline *aLine, NSZone *zone)
{
	MiscPolyline *index,*trailer;
	
	trailer = aLine;
	index = aLine;
	while(index){
		index = index->link;
		NSZoneFree(zone, trailer);
		trailer = index;
	}
}

static void partialFreeLine(MiscPolyline *aLine, MiscPolyline *toEnd, NSZone *zone)
{
	MiscPolyline *index,*trailer;
	
	trailer = aLine;
	index = aLine;
	while(index && index != toEnd){
		index = index->link;
		NSZoneFree(zone, trailer);
		trailer = index;
	}
}

static NSRect makeRectFromPolygon(MiscPolygon *aPol, NSPoint ipl, NSPoint ipu)
{
	float minX, minY, maxX, maxY, x, y;
	MiscPolyline *line;

	minX = minY = 9999;
	maxX = maxY = -9999;
	line = aPol->upper.head;
	x = ipu.x;
	y = ipu.y;
	minX = MIN(minX, x);
	minY = MIN(minY, y);
	maxX = MAX(maxX, x);
	maxY = MAX(maxY, y);
	while(line){
		x += line->dx;
		y += line->dy;
		minX = MIN(minX, x);
		minY = MIN(minY, y);
		maxX = MAX(maxX, x);
		maxY = MAX(maxY, y);
		line = line->link;
	} 
	line = aPol->lower.head;
	x = ipl.x;
	y = ipl.y;
	minX = MIN(minX, x);
	minY = MIN(minY, y);
	maxX = MAX(maxX, x);
	maxY = MAX(maxY, y);
	while(line){
		x += line->dx;
		y += line->dy;
		minX = MIN(minX, x);
		minY = MIN(minY, y);
		maxX = MAX(maxX, x);
		maxY = MAX(maxY, y);
		line = line->link;
	}
	return NSMakeRect(minX, minY, maxX - minX, maxY - minY);
}
	
	
	
	
	
	
