/*
 * Copyright (c) 1987, 1988, 1989 Stanford University
 *
 * Permission to use, copy, modify, distribute, and sell this software and its
 * documentation for any purpose is hereby granted without fee, provided
 * that the above copyright notice appear in all copies and that both that
 * copyright notice and this permission notice appear in supporting
 * documentation, and that the name of Stanford not be used in advertising or
 * publicity pertaining to distribution of the software without specific,
 * written prior permission.  Stanford makes no representations about
 * the suitability of this software for any purpose.  It is provided "as is"
 * without express or implied warranty.
 *
 * STANFORD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS.
 * IN NO EVENT SHALL STANFORD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
 * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
 * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
 * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

/*
 * LooseTray implementation.  Change:
 *	Tray ==> LooseTray
 *	TElement ==> LTElement
 *	TGlue ==> LTGlue
 *	TList ==> LTList
 *	TTermination ==> LTTerminaltion
 *	TNode ==> LTNode
 *	TSolver ==> LTSolver
 */

#include <InterViews/canvas.h>
#include <InterViews/painter.h>
#include <InterViews/shape.h>
#include "loosetray.h"

inline float abs (float f) { return (f < 0) ? -f : f; }

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

class LTElement {
public:
    LTElement(Interactor*);
    LTElement(LTGlue*);
    LTElement();
    ~LTElement();

    float pos, sigma;			/* ultimate values */
    float nat, stretch, shrink;
    boolean combinable;		    /* false for tray elements when calcing */
				    /* shape of tray having no background */
    boolean leftBotHalf;	    /* true if represents left/bottom of a */
				    /* pair of elems modelling an interactor */
    Interactor* owner;
    LTGlue* tglue;

    void HSetShape();
    void VSetShape();
    LTElement* Series(LTElement*);	/* series combination */
    LTElement* Parallel(LTElement*);	/* parallel combination */
    void Reverse();
    void Limit();
};

LTElement::LTElement (Interactor* i) {
    owner = i;
    tglue = nil;
    pos = sigma = 0;
}

LTElement::LTElement (LTGlue* tg) {
    owner = nil;
    tglue = tg;
    pos = sigma = 0;
}

LTElement::LTElement () {
    owner = nil;
    tglue = nil;
    pos = sigma = 0;
}

LTElement::~LTElement () {
    delete tglue;
}

void LTElement::HSetShape () {
    Shape* s;

    if (tglue == nil) {
	s = owner->GetShape();
	nat = float(s->width)/2;
	stretch = float(s->hstretch)/2;
	shrink = float(s->hshrink)/2;
    } else {
	s = tglue->GetShape();
	nat = s->width;
	stretch = s->hstretch;
	shrink = s->hshrink;
    }
}

void LTElement::VSetShape () {
    Shape* s;

    if (tglue == nil) {
	s = owner->GetShape();
	nat = float(s->height)/2;
	stretch = float(s->vstretch)/2;
	shrink = float(s->vshrink)/2;
    } else {
	s = tglue->GetShape();
	nat = s->height;
	stretch = s->vstretch;
	shrink = s->vshrink;
    }
}

LTElement* LTElement::Series (LTElement* e) {
    LTElement* combo = new LTElement;
    register LTElement* c;
    
    combo->combinable = combinable || e->combinable;
    
    if (combinable && e->combinable) {
	combo->nat = nat + e->nat;
	combo->stretch = stretch + e->stretch;
	combo->shrink = shrink + e->shrink;

    } else if (combo->combinable) {
	c = combinable ? this : e;
	combo->nat = c->nat;
	combo->stretch = c->stretch;
	combo->shrink = c->shrink;
    }
    
    return combo;
}

LTElement* LTElement::Parallel (LTElement* e) {
    LTElement* combo = new LTElement;
    register LTElement* c;
    float emin, emax;
    
    emin = max(nat - shrink, e->nat - e->shrink);
    emax = min(nat + stretch, e->nat + e->stretch);
    combo->combinable = combinable || e->combinable;

    if (combinable && e->combinable) {
	combo->nat = max(nat, e->nat);
	combo->stretch = max(0, int(emax - combo->nat));
	combo->shrink = max(0, int(combo->nat - emin));
    } else if (combo->combinable) {
	c = combinable ? this : e;
	combo->nat = c->nat;
	combo->stretch = c->stretch;
	combo->shrink = c->shrink;
    }
    return combo;
}

void LTElement::Reverse () {
    float tmp;

    nat = -nat;
    tmp = stretch;
    stretch = shrink;
    shrink = tmp;
    sigma = -sigma;
    pos -= nat + sigma + 1;
}

void LTElement::Limit () {
    sigma = min(max(-shrink, sigma), stretch);
}

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

class LTList {
public:
    ~LTList();
protected:
    LTList(void* = nil);

    void Append(LTList*);
    void Prepend(LTList*);
    void Remove(LTList*);
    LTList* First();
    LTList* Last();
    LTList* End();
    LTList* Next();
    LTList* Prev();
    boolean Empty();

    void SetContents(void*);
    void* GetContents();
    void Delete(void*);
    LTList* Find(void*);

private:
    void* object;
    LTList* next;
    LTList* prev;
};

inline LTList::LTList (void* o) { next = this; prev = this; object = o; }
inline LTList* LTList::First () { return next; }
inline LTList* LTList::Last () { return prev; }
inline LTList* LTList::End () { return this; }
inline LTList* LTList::Next () { return next; }
inline LTList* LTList::Prev () { return prev; }
inline boolean LTList::Empty () { return next == this; }
inline void LTList::SetContents (void *o) { object = o; }
inline void* LTList::GetContents () { return object; }

inline void LTList::Append (LTList* e) {
    prev->next = e;
    e->prev = prev;
    e->next = this;
    prev = e;
}

inline void LTList::Prepend (LTList* e) {
    next->prev = e;
    e->prev = this;
    e->next = next;
    next = e;
}

inline void LTList::Remove (LTList* e) {
    e->prev->next = e->next;
    e->next->prev = e->prev;
    e->next = e->prev = e;
}

LTList::~LTList () {
    LTList* e;
    
    if (!Empty()) {
	e = First();
	Remove(this);
	delete e;
    }
}

void LTList::Delete (void* o) {
    register LTList* e;

    e = Find(o);
    if (e != nil) {
	Remove(e);
	delete e;
    }
}

LTList* LTList::Find (void* o) {
    register LTList* e;

    for (e = next; e != this; e = e->next) {
	if (e->GetContents() == o) {
	    return e;
	}
    }
    return nil;
}

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

class LTElementList : public LTList {
public:
    LTElementList(LTElement* = nil);
    LTElementList* Copy();

    boolean Includes(LTElement*);
    boolean Includes(Interactor*, LTElement*&);

    void Append(LTElementList*);
    void Remove(LTElementList*);
    LTElementList* First();
    LTElementList* End();
    LTElementList* Next();
    void Delete(LTElement*);
    boolean Empty();
    boolean OnlyOne();
    boolean OnlyTwo();
    LTElement* GetElem();
};

inline LTElement* LTElementList::GetElem () { return (LTElement*) GetContents();}
inline void LTElementList::Append (LTElementList* el) { LTList::Append(el); }
inline void LTElementList::Remove (LTElementList* el) { LTList::Remove(el); }
inline void LTElementList::Delete (LTElement* o) { LTList::Delete(o); }
inline boolean LTElementList::Includes (LTElement* e) { return Find(e) != nil; }
inline LTElementList* LTElementList::First () 
    { return (LTElementList*) LTList::First(); }
inline LTElementList* LTElementList::End ()
    { return (LTElementList*) LTList::End(); }
inline LTElementList* LTElementList::Next () 
    { return (LTElementList*) LTList::Next(); }
inline boolean LTElementList::Empty () { return LTList::Empty(); }
inline boolean LTElementList::OnlyOne () { return !Empty() && First()==Last(); }
inline boolean LTElementList::OnlyTwo ()
    { return !Empty() && !OnlyOne() && First()->Next() == Last(); }

LTElementList::LTElementList (LTElement* o) : LTList(o) { }

LTElementList* LTElementList::Copy () {
    register LTElementList* t;
    LTElementList* newlist = new LTElementList;
    
    for (t = First(); t != End(); t = t->Next()) {
	newlist->Append(new LTElementList(t->GetElem()));
    }
    return newlist;
}

boolean LTElementList::Includes (Interactor* i, LTElement*& e) {
    register LTElementList* t;

    for (t = First(); t != End(); t = t->Next()) {
	e = t->GetElem();
	if (e->owner == i) {
	    return true;
	}
    }
    return false;
}

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

class LTTermination {
public:
    Alignment alignment, toAttached;
    LTElement* dangling, *attached;

    LTTermination(Alignment, LTElement*, Alignment, LTElement*);
};

LTTermination::LTTermination (
    Alignment a, LTElement* d, Alignment to, LTElement* e
) {
    alignment = a;
    dangling = d;
    toAttached = to;
    attached = e;
}

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

class TLoop {
public:
    Alignment toAttached;
    LTElement* looped, *attached;
    
    TLoop(LTElement*, Alignment, LTElement*);
};

TLoop::TLoop (LTElement* l, Alignment to, LTElement* e) {
    looped = l;
    toAttached = to;
    attached = e;
}    

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

class LTNode {
    friend class LTNodeList;
public:
    LTNode(LTElementList* = nil, LTElementList* = nil);
    LTNode(Alignment, LTElement*, Alignment = BottomLeft, LTElement* = nil);
    ~LTNode();
    LTNode* Copy();
    void DeleteElements();
    
    void Merge(LTNode*);
    void Exclude(LTElement*);
    boolean Includes(LTElement*);
    boolean Includes(Alignment&, LTElement*);
    boolean Overlaps(LTNode*);
    boolean Empty();
    boolean Degenerate(LTElement*&);
    boolean Degenerate(Alignment&, LTElement*&);
    boolean Series(LTElement*&, LTElement*&);
    boolean Stub(LTElement*&);
    boolean Loop(LTElement*&);

    void SetPosition(float);
    float GetPosition();
private:
    LTElementList* lbElems, *rtElems;
    float position;

    LTElementList* LeftBottomElements();
    LTElementList* RightTopElements();
    void DeleteElements(LTElementList*);
};

inline boolean LTNode::Includes (LTElement* e) 
    { Alignment dummy; return Includes(dummy, e); }
inline boolean LTNode::Empty () { return lbElems->Empty() && rtElems->Empty(); }
inline void LTNode::SetPosition (float p) { position = p; }
inline float LTNode::GetPosition () { return position; }
inline LTElementList* LTNode::LeftBottomElements () { return lbElems; }
inline LTElementList* LTNode::RightTopElements () { return rtElems; }

LTNode::LTNode (LTElementList* l1, LTElementList* l2) {
    lbElems = l1;
    rtElems = l2;
    position = 0;
}
    
LTNode::LTNode (Alignment a1, LTElement* e1, Alignment a2, LTElement* e2) {
    lbElems = new LTElementList;
    rtElems = new LTElementList;

    if (a1 == BottomLeft) {
	rtElems->Append(new LTElementList(e1));
    } else {
	lbElems->Append(new LTElementList(e1));
    }
    if (e2 != nil) {
	if (a2 == BottomLeft) {
	    rtElems->Append(new LTElementList(e2));
	} else {
	    lbElems->Append(new LTElementList(e2));
	}
	position = 0;
    }
}

LTNode::~LTNode () { delete lbElems; delete rtElems; }

void LTNode::DeleteElements () {
    register LTElementList* t;
    
    for (t = lbElems->First(); t != lbElems->End(); t = t->Next()) {
        rtElems->Delete(t->GetElem());
    }
    DeleteElements(lbElems);
    DeleteElements(rtElems);
}

void LTNode::DeleteElements (LTElementList* elems) {
    register LTElementList* t;

    for (t = elems->First(); t != elems->End(); t = t->Next()) {
        delete t->GetElem();
    }
}

LTNode* LTNode::Copy () { 
    LTNode* node = new LTNode(lbElems->Copy(), rtElems->Copy());
    node->SetPosition(GetPosition());
    return node;
}

void LTNode::Merge (LTNode* n) {
    register LTElementList* nelems, *next;
    LTElementList* cur;
    
    nelems = n->lbElems;
    for (cur = nelems->First(); cur != nelems->End(); cur = next) {
	next = cur->Next();
	nelems->Remove(cur);
	if (lbElems->Includes(cur->GetElem())) {
            delete cur;
        } else {
	    lbElems->Append(cur);
	}
    }
    nelems = n->rtElems;
    for (cur = nelems->First(); cur != nelems->End(); cur = next) {
	next = cur->Next();
	nelems->Remove(cur);
	if (rtElems->Includes(cur->GetElem())) {
            delete cur;
        } else {
	    rtElems->Append(cur);
	}
    }
}

void LTNode::Exclude (LTElement* e) {
    lbElems->Delete(e);
    rtElems->Delete(e);
}

boolean LTNode::Includes (Alignment& a, LTElement* e) {
    if (lbElems->Includes(e)) {
	a = TopRight;
	return true;
    } else if (rtElems->Includes(e)) {
	a = BottomLeft;
	return true;
    };
    return false;
}

boolean LTNode::Overlaps (LTNode* n) {
    register LTElementList* nelems;
    register LTElementList* cur;
    
    nelems = n->lbElems;
    for (cur = nelems->First(); cur != nelems->End(); cur = cur->Next()) {
	if (lbElems->Includes(cur->GetElem())) {
	    return true;
	}
    }
    nelems = n->rtElems;
    for (cur = nelems->First(); cur != nelems->End(); cur = cur->Next()) {
	if (rtElems->Includes(cur->GetElem())) {
	    return true;
	}
    }
    return false;
}

boolean LTNode::Degenerate (LTElement*& e) {
    Alignment dummy; 

    return Degenerate(dummy, e);
}

boolean LTNode::Degenerate (Alignment& a, LTElement*& e) {
    if (!lbElems->Empty() && rtElems->Empty()) {
	if (lbElems->OnlyOne()) {
	    e = lbElems->First()->GetElem();
	    a = TopRight;
	    return true;
	}
    } else if (lbElems->Empty() && !rtElems->Empty()) {
	if (rtElems->OnlyOne()) {
	    e = rtElems->First()->GetElem();
	    a = BottomLeft;
	    return true;
	}
    }
    return false;
}

boolean LTNode::Series (LTElement*& e1, LTElement*& e2) {
    if (
	!lbElems->Empty() && !rtElems->Empty() &&
	lbElems->OnlyOne() && rtElems->OnlyOne()
    ) {
	e1 = lbElems->First()->GetElem();
	e2 = rtElems->First()->GetElem();
	if (e1 != e2) {
	    return true;
	}
    }
    return false;
}

boolean LTNode::Stub (LTElement*& e) {
    if (lbElems->OnlyTwo() && rtElems->Empty()) {
	e = lbElems->First()->GetElem();
	return true;

    } else if (lbElems->Empty() && rtElems->OnlyTwo()) {
	e = rtElems->First()->GetElem();
	return true;
    }
    return false;
}

boolean LTNode::Loop (LTElement*& e) {
    register LTElementList* cur;
    
    for (cur = lbElems->First(); cur != lbElems->End(); cur = cur->Next()) {
	e = cur->GetElem();
	if (rtElems->Includes(e)) {
	    return true;
	}
    }
    return false;
}

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

class LTNodeList : public LTList {
public:
    LTNodeList(LTNode* = nil);
    LTNodeList* Copy();

    void Include(Alignment, LTElement*, Alignment = BottomLeft, LTElement* =nil);
    void Exclude(LTElement*);
    boolean Includes(LTNode*);
    void Nodes(LTElement*, LTNode*&, LTNode*&);
    LTNode* Node(Alignment, LTElement*);
    LTNode* OtherNode(LTElement*, LTNode*);
    void AddMissingNodes(LTElement*);

    void Append(LTNodeList*);
    void Remove(LTNodeList*);
    LTNodeList* First();
    LTNodeList* End();
    LTNodeList* Next();
    LTNodeList* Last();
    void Delete(LTNode*);
    boolean Empty();
    boolean OnlyOne();
    LTNode* GetNode();
    
    boolean Degenerate(LTElement*&);
    boolean FoundTermination(LTTermination*&, LTNode*, LTNode*);
    boolean FoundSeries(LTElement*&, LTElement*&, LTNode*, LTNode*);
    boolean FoundStub(LTElement*&);
    boolean FoundParallel(LTElement*&, LTElement*&);
    boolean FoundCrossover(LTElement*&);
    boolean FoundLoop(TLoop*&);
    void Reverse(LTElement*);
    
    void RemoveTermination(LTTermination*);
    void RemoveSeries(LTElement*, LTElement*, LTElement*);
    void RemoveParallel(LTElement*, LTElement*, LTElement*);
    void RemoveLoop(TLoop*);

    void ReplaceTermination(LTTermination*);
    void ReplaceSeries(LTElement*, LTElement*, LTElement*);
    void ReplaceParallel(LTElement*, LTElement*, LTElement*);
    void ReplaceLoop(TLoop*);

    void ApplyToTermination(LTTermination*);
    void ApplyToSeries(LTElement*, LTElement*, LTElement*);
    void ApplyToParallel(LTElement*, LTElement*, LTElement*);
    void ApplyToLoop(TLoop*);

    void FindElements(Interactor*, LTElement*&, LTElement*&);
    void FindElement(LTGlue*, LTElement*&);
private:
    boolean FoundParallel(LTNode*, LTElement*&, LTElement*&);
    boolean FoundParallel(LTElementList*, LTNode*, LTElement*&, LTElement*&);
    boolean FoundCrossover(LTNode*, LTElement*&);
    void FindElements(LTElementList*, Interactor*, LTElement*&, LTElement*&);
    void FindElement(LTElementList*, LTGlue*, LTElement*&);
    Alignment Inverse(Alignment);
    void GetElemOtherThan(LTElement*, LTNode*, Alignment&, LTElement*&);
};

inline boolean LTNodeList::Includes (LTNode* t) { return LTList::Find(t) != nil; }
inline LTNode* LTNodeList::GetNode () { return (LTNode*) GetContents(); }
inline boolean LTNodeList::FoundParallel (
    LTNode* n, LTElement*& e1, LTElement*& e2
) {
    return    
	FoundParallel(n->LeftBottomElements(), n, e1, e2) ||
	FoundParallel(n->RightTopElements(), n, e1, e2);
}
inline void LTNodeList::Append (LTNodeList* t) { LTList::Append(t); }
inline void LTNodeList::Remove (LTNodeList* t) { LTList::Remove(t); }
inline void LTNodeList::Delete (LTNode* o) { LTList::Delete(o); }
inline LTNodeList* LTNodeList::First () { return (LTNodeList*) LTList::First(); }
inline LTNodeList* LTNodeList::End () { return (LTNodeList*) LTList::End(); }
inline LTNodeList* LTNodeList::Next () { return (LTNodeList*) LTList::Next(); }
inline LTNodeList* LTNodeList::Last () { return (LTNodeList*) LTList::Last(); }
inline boolean LTNodeList::Empty () { return LTList::Empty(); }
inline boolean LTNodeList::OnlyOne () { return !Empty() && First() == Last(); }
inline Alignment LTNodeList::Inverse (Alignment a)
    { return (a == BottomLeft) ? TopRight : BottomLeft; }

LTNodeList::LTNodeList (LTNode* o) : LTList(o) { }

LTNodeList* LTNodeList::Copy () {
    register LTNodeList* t;
    LTNodeList* newlist = new LTNodeList;
    LTNode* node;
    
    for (t = First(); t != End(); t = t->Next()) {
	node = t->GetNode();
	newlist->Append(new LTNodeList(node->Copy()));
    }
    return newlist;
}

void LTNodeList::Include (
    Alignment a1, LTElement* e1, Alignment a2, LTElement* e2
) {
    register LTNodeList* t;
    LTNode pass1(a1, e1, a2, e2);
    LTNode* node, *pass2;
    
    for (t = First(); t != End(); t = t->Next()) {
	node = t->GetNode();
	if (node->Overlaps(&pass1)) {
	    node->Merge(&pass1);
	    pass2 = node;
	    break;
	}
    }
    if (t == End()) {
	Append(new LTNodeList(pass1.Copy()));

    } else {
	for (t = First(); t != End(); t = t->Next()) {
	    node = t->GetNode();
	    if (node != pass2 && node->Overlaps(pass2)) {
		node->Merge(pass2);
		Delete(pass2);
		delete pass2;
		break;
	    }
	}
    }
}

void LTNodeList::Exclude (LTElement* e) {
    register LTNodeList* t, *next;
    LTNode* node;
    int n = 0;
    
    for (t = First(); t != End() && n <= 1; t = next) {
	next = t->Next();
	node = t->GetNode();
	if (node->Includes(e)) {
	    ++n;
	    node->Exclude(e);
	    if (node->Empty()) {
		Remove(t);
		delete t;
	    }
	}
    }
}

boolean LTNodeList::Degenerate (LTElement*& e) {
    LTElement* alt;
    LTNode* nfirst = First()->GetNode();
    LTNode* nlast = Last()->GetNode();

    return
	First()->Next() == Last() &&
	nfirst->Degenerate(e) && nlast->Degenerate(alt) &&
	e == alt;
}

boolean LTNodeList::FoundTermination (
    LTTermination*& term, LTNode* lbMagic, LTNode* rtMagic
) {
    register LTNodeList* t;
    LTElement* dangling, *attached;
    Alignment a, toAttached;
    LTNode* degenTest, *attachment;
    
    for (t = First(); t != End(); t = t->Next()) {
	degenTest = t->GetNode();

	if (
	    degenTest != lbMagic && degenTest != rtMagic &&
	    degenTest->Degenerate(a, dangling)
	) {
	    attachment = OtherNode(dangling, degenTest);
            GetElemOtherThan(dangling, attachment, toAttached, attached);
            if (attached != nil) {
                term = new LTTermination(a, dangling, toAttached, attached);
                return true;
            }
	}
    }
    return false;
}

boolean LTNodeList::FoundSeries (
    LTElement*& e1, LTElement*& e2, LTNode* lbMagic, LTNode* rtMagic
) {
    register LTNodeList* t;
    LTNode* node;
    
    for (t = First(); t != End(); t = t->Next()) {
	node = t->GetNode();
	if (node != lbMagic && node != rtMagic && node->Series(e1, e2)) {
	    return true;
	}
    }
    return false;
}

boolean LTNodeList::FoundStub (LTElement*& e) {
    register LTNodeList* t;
    LTNode* node;
    
    for (t = First(); t != End(); t = t->Next()) {
	node = t->GetNode();
	if (node->Stub(e)) {
	    return true;
	}
    }
    return false;
}

boolean LTNodeList::FoundParallel (LTElement*& e1, LTElement*& e2) {
    register LTNodeList* t;
    LTNode* node;
    
    for (t = First(); t != End(); t = t->Next()) {
	node = t->GetNode();
	if (FoundParallel(node, e1, e2)) {
	    return true;
	}
    }
    return false;
}

boolean LTNodeList::FoundParallel (
    LTElementList* elems, LTNode* n, LTElement*& e1, LTElement*& e2
) {
    register LTElementList* cur, *test;
    LTNode* ncur, *ntest;
    
    for (cur = elems->First(); cur != elems->End(); cur = cur->Next()) {
	e1 = cur->GetElem();
	ncur = OtherNode(e1, n);

	if (ncur != nil) {
	    for (
		test = cur->Next();
		test != elems->End();
		test = test->Next()
	    ) {
		e2 = test->GetElem();
		ntest = OtherNode(e2, n);
		if (ntest == ncur) {
		    return true;
		}
	    }
	}
    }
    return false;
}

boolean LTNodeList::FoundCrossover (LTElement*& e) {
    register LTNodeList* t;
    LTNode* node;
    
    for (t = First(); t != End(); t = t->Next()) {
	node = t->GetNode();
	if (FoundCrossover(node, e)) {
	    return true;
	}
    }
    return false;
}

boolean LTNodeList::FoundLoop (TLoop*& loop) {
    register LTNodeList* t;
    LTElement* looped, *attached;
    Alignment toAttached;
    LTNode* loopTest;
    
    for (t = First(); t != End(); t = t->Next()) {
	loopTest = t->GetNode();
	if (loopTest->Loop(looped)) {
	    GetElemOtherThan(looped, loopTest, toAttached, attached);
	    loop = new TLoop(looped, toAttached, attached);
	    return true;
	}
    }
    return false;
}

boolean LTNodeList::FoundCrossover (LTNode* n, LTElement*& e1) {
    LTElementList* lbElems, *rtElems, *cur, *test;
    LTElement* e2;
    LTNode* ncur, *ntest;
    
    lbElems = n->LeftBottomElements();
    rtElems = n->RightTopElements();
    
    for (cur = lbElems->First(); cur != lbElems->End(); cur = cur->Next()) {
	e1 = cur->GetElem();
	ncur = OtherNode(e1, n);
	
	if (ncur != nil) {
	    for (
		test = rtElems->First(); 
		test != rtElems->End(); 
		test = test->Next()
	    ) {
		e2 = test->GetElem();
		ntest = OtherNode(e2, n);
		if (ntest == ncur) {
		    return true;
		}
	    }
	}
    }
    return false;
}

LTNode* LTNodeList::OtherNode (LTElement* e, LTNode* n) {
    register LTNodeList* t;
    LTNode* ntest;
    
    for (t = First(); t != End(); t = t->Next()) {
	ntest = t->GetNode();
	if (ntest != n && ntest->Includes(e)) {
	    return ntest;
	}
    }
    return nil;
}

void LTNodeList::RemoveTermination (LTTermination* t) {
    LTNode* degen, *attachment = Node(t->toAttached, t->attached);

    attachment->Exclude(t->dangling);
    degen = OtherNode(t->dangling, attachment);
    Delete(degen);
    delete degen;
}

void LTNodeList::RemoveSeries (LTElement* equiv, LTElement* e1, LTElement* e2) {
    LTNode* n1lb, *n2lb, *n2rt;
    LTNode eqlb(BottomLeft, equiv);
    LTNode eqrt(TopRight, equiv);
    
    Nodes(e2, n2lb, n2rt);
    n1lb = OtherNode(e1, n2lb);
    if (n1lb == nil) {			// check for ends tied together
	n1lb = n2rt;
    } else if (n2rt == nil) {
	n2rt = n1lb;
    }
    n1lb->Merge(&eqlb);
    n2rt->Merge(&eqrt);
    n1lb->Exclude(e1);
    n2rt->Exclude(e2);
    Delete(n2lb);
    delete n2lb;
}

void LTNodeList::Reverse (LTElement* e) {
    LTNode* nlb, *nrt;
    LTNode elb(BottomLeft, e);
    LTNode ert(TopRight, e);
    
    Nodes(e, nlb, nrt);
    nlb->Exclude(e);
    nrt->Exclude(e);
    nlb->Merge(&ert);
    nrt->Merge(&elb);
    e->Reverse();
}

void LTNodeList::RemoveParallel (LTElement* equiv, LTElement* e1, LTElement* e2) {
    LTNode* n1lb, *n1rt;
    LTNode eqlb(BottomLeft, equiv);
    LTNode eqrt(TopRight, equiv);
    
    Nodes(e1, n1lb, n1rt);
    n1lb->Merge(&eqlb);
    n1rt->Merge(&eqrt);
    n1lb->Exclude(e1);
    n1lb->Exclude(e2);
    n1rt->Exclude(e1);
    n1rt->Exclude(e2);
}

void LTNodeList::RemoveLoop (TLoop* l) {
    LTNode* attachment;
    
    if (l->attached == nil) {		    // isolated loop
	attachment = OtherNode(l->looped, nil);
	Delete(attachment);
	delete attachment;
    } else {
	attachment = Node(l->toAttached, l->attached);
	attachment->Exclude(l->looped);
    }
}

void LTNodeList::ReplaceTermination (LTTermination* t) {
    LTNode* degen, *attachment = Node(t->toAttached, t->attached);
    float apos;

    Alignment a = Inverse(t->alignment);
    LTElement* e = t->dangling;
    LTNode temp(a, e);
    attachment->Merge(&temp);
    apos = attachment->GetPosition();
    degen = new LTNode(t->alignment, t->dangling);

    if (t->alignment == BottomLeft) {
	degen->SetPosition(apos - t->dangling->nat - t->dangling->sigma);
    } else {
	degen->SetPosition(apos + t->dangling->nat + t->dangling->sigma);
    }
    Append(new LTNodeList(degen));
}

void LTNodeList::ReplaceSeries (LTElement* equiv, LTElement* e1, LTElement* e2) {
    LTNode* eqlb, *eqrt, *nctr;
    
    Nodes(equiv, eqlb, eqrt);
    if (eqlb == nil) {			// check for ends tied together
	eqlb = eqrt;
    } else if (eqrt == nil) {
	eqrt = eqlb;
    }
    LTNode nlb(BottomLeft, e1);
    LTNode nrt(TopRight, e2);
    eqlb->Merge(&nlb);
    eqrt->Merge(&nrt);
    eqlb->Exclude(equiv);
    eqrt->Exclude(equiv);
    nctr = new LTNode(TopRight, e1, BottomLeft, e2);
    nctr->SetPosition(e2->pos);
    Append(new LTNodeList(nctr));
}

void LTNodeList::ReplaceParallel (
    LTElement* equiv, LTElement* e1, LTElement* e2
) {
    LTNode* eqlb, *eqrt;
    LTNode nlb(BottomLeft, e1, BottomLeft, e2);
    LTNode nrt(TopRight, e1, TopRight, e2);
    
    Nodes(equiv, eqlb, eqrt);
    eqlb->Merge(&nlb);
    eqrt->Merge(&nrt);
    eqlb->Exclude(equiv);
    eqrt->Exclude(equiv);
}

void LTNodeList::ReplaceLoop (TLoop* l) {
    LTNode* attachment;
    
    if (l->attached == nil) {
	attachment = new LTNode(BottomLeft, l->looped, TopRight, l->looped);
	Append(new LTNodeList(attachment));

    } else {
	attachment = Node(l->toAttached, l->attached);
	LTNode node(BottomLeft, l->looped, TopRight, l->looped);
	attachment->Merge(&node);
    }
}

void LTNodeList::FindElements (
    Interactor* i, LTElement*& lbElem, LTElement*& rtElem
) {
    register LTNodeList* nl;
    LTNode* node;
    LTElementList* el;

    lbElem = rtElem = nil;
    
    for (
	nl = First(); 
	nl != End() && (lbElem == nil || rtElem == nil);
	nl = nl->Next()
    ) {
	node = nl->GetNode();
	el = node->LeftBottomElements();
	FindElements(el, i, lbElem, rtElem);

	if (lbElem == nil || rtElem == nil) {
	    el = node->RightTopElements();
	    FindElements(el, i, lbElem, rtElem);
	}
    }
}	    

void LTNodeList::FindElement (LTGlue* tg, LTElement*& elem) {
    register LTNodeList* nl;
    LTNode* node;
    LTElementList* el;

    elem = nil;
    
    for (nl = First(); nl != End() && elem == nil; nl = nl->Next()) {
	node = nl->GetNode();
	el = node->LeftBottomElements();
	FindElement(el, tg, elem);

	if (elem == nil) {
	    el = node->RightTopElements();
	    FindElement(el, tg, elem);
	}
    }
}	    

void LTNodeList::FindElements (
    LTElementList* el, Interactor* i, LTElement*& lbElem, LTElement*& rtElem
) {
    register LTElementList* cur;
    LTElement* test;

    for (
	cur = el->First(); 
	cur != el->End() && (lbElem == nil || rtElem == nil);
	cur = cur->Next()
    ) {
	test = cur->GetElem();
	if (test->owner == i) {
	    if (test->leftBotHalf) {
		lbElem = test;
	    } else {
		rtElem = test;
	    }
	}
    }
}

void LTNodeList::FindElement (LTElementList* el, LTGlue* tg, LTElement*& elem) {
    register LTElementList* cur;
    LTElement* test;

    for (cur = el->First(); cur != el->End(); cur = cur->Next()) {
	test = cur->GetElem();
	if (test->tglue == tg) {
	    elem = test;
	    return;
	}
    }
}

void LTNodeList::Nodes (LTElement* e, LTNode*& nlb, LTNode*& nrt) {
    register LTNodeList* t;
    LTNode* node;
    Alignment a;
    
    nlb = nrt = nil;
    for (t = First(); t != End() && (nlb==nil || nrt==nil); t = t->Next()) {
	node = t->GetNode();
	if (node->Includes(a, e)) {
	    if (a == BottomLeft) {	/* node is below/left of element */
		nlb = node;
	    } else {
		nrt = node;
	    }
	}
    }
}

LTNode* LTNodeList::Node (Alignment a, LTElement* e) {
    register LTNodeList* t;
    LTNode* node;
    Alignment test;
    
    for (t = First(); t != End(); t = t->Next()) {
	node = t->GetNode();
	if (node->Includes(test, e) && test == a) {
	    return node;
	}
    }
    return 0;
}

void LTNodeList::AddMissingNodes (LTElement* e) {
    LTNode* nlb, *nrt;
    LTNodeList* lb, *rt;
    
    Nodes(e, nlb, nrt);
    if (nlb == nil) {
	nlb = new LTNode(BottomLeft, e);
	nlb->SetPosition(e->pos);
	lb = new LTNodeList(nlb);
	Append(lb);

    } 
    if (nrt == nil) {
	nrt = new LTNode(TopRight, e);
	nrt->SetPosition(e->pos + e->nat + e->sigma);
	rt = new LTNodeList(nrt);
	Append(rt);
    }
}

void LTNodeList::GetElemOtherThan (
    LTElement* avoid, LTNode* n, Alignment& a, LTElement*& e
) {
    register LTElementList* cur;
    LTElementList* lbElems, *rtElems;
    
    lbElems = n->LeftBottomElements();
    rtElems = n->RightTopElements();
    
    for (cur = lbElems->First(); cur != lbElems->End(); cur = cur->Next()) {
	e = cur->GetElem();
	if (e != avoid) {
	    a = TopRight;
	    return;
	}
    }
    for (cur = rtElems->First(); cur != rtElems->End(); cur = cur->Next()) {
	e = cur->GetElem();
	if (e != avoid) {
	    a = BottomLeft;
	    return;
	}
    }
    e = nil;
}

void LTNodeList::ApplyToTermination (LTTermination* t) {
    LTNode* n = Node(t->toAttached, t->attached);

    if (t->alignment == BottomLeft) {
	t->dangling->pos = n->GetPosition() - t->dangling->nat;

    } else {
	t->dangling->pos = n->GetPosition();

    }
    t->dangling->sigma = 0;
}

void LTNodeList::ApplyToSeries (LTElement* equiv, LTElement* e1, LTElement* e2) {
    float d = equiv->nat + equiv->sigma - e1->nat - e2->nat;
    float s1, s2;
    
    if (d < 0) {
	s1 = e1->shrink;
	s2 = e2->shrink;
    } else {
	s1 = e1->stretch;
	s2 = e2->stretch;
    }
    if (s1 == 0 && s2 == 0) {
	e1->sigma = e2->sigma = 0;
    } else {
	e1->sigma = equiv->sigma * s1 / (s1 + s2);
    }

    e1->Limit();
    e2->sigma = equiv->sigma - e1->sigma;
    e2->Limit();
    e1->pos = equiv->pos;
    e2->pos = e1->pos + e1->nat + e1->sigma;
}

void LTNodeList::ApplyToParallel (LTElement* equiv, LTElement* e1, LTElement* e2) {
    e1->pos = e2->pos = equiv->pos;
    e1->sigma = equiv->nat + equiv->sigma - e1->nat;
    e2->sigma = equiv->nat + equiv->sigma - e2->nat;
    e1->Limit();
    e2->Limit();
}

void LTNodeList::ApplyToLoop (TLoop* l) {
    LTNode* n = Node(l->toAttached, l->attached);

    l->looped->pos = n->GetPosition();
    l->looped->sigma = -l->looped->shrink;
}

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

class LTSolver {
public:
    LTSolver(LooseTray*, Interactor*);
    ~LTSolver();

    void AddAlignment(Alignment, Interactor*, LTGlue* = nil);
    void AddAlignment(
	Alignment, Interactor*, Alignment, Interactor*, LTGlue* = nil
    );
    void DeleteAlignmentsTo(Interactor*);
    void SetShape(Interactor*);
    void Solve(int, int);
    void CalcShape(Shape*);
    void GetPlacement(Interactor*, Coord&, Coord&, Coord&, Coord&);
private:
    LTNodeList* hnodes, *vnodes;
    LTNode* lmagic, *rmagic, *bmagic, *tmagic;
    LooseTray* tray;
    Interactor* background;

    Interactor* BgFilter(Interactor*);
    void Solve(
	LTNodeList*, LTNode*, LTNode*, int size, int& nat, int& shr, int& str
    );
    void GetPlacement(LTNodeList*, Interactor*, int, Coord&, Coord&);

    void HOrder(Alignment, Interactor*&, Interactor*&);
    void VOrder(Alignment, Interactor*&, Interactor*&);
    void HConvert(Interactor*, LTElement*&, LTElement*&);
    void HConvert(LTGlue*, LTElement*&);
    void VConvert(Interactor*, LTElement*&, LTElement*&);
    void VConvert(LTGlue*, LTElement*&);
    void HAddAlignment(
	Alignment, LTElement*, LTElement*, Alignment, LTElement*, LTElement*,
	LTElement*
    );
    void VAddAlignment(
	Alignment, LTElement*, LTElement*, Alignment, LTElement*, LTElement*,
	LTElement*
    );
    void Include(
	LTNodeList*, Alignment, LTElement*, Alignment, LTElement*, LTElement*
    );
    void LooseTrayNodes(LTNodeList*, LTNode*&, LTNode*&);
    void UpdateMagicNodes();
    void DeleteDanglingGlue(LTNodeList*, LTNode*);
    void DeleteNodesAndElements(LTNodeList*);
};

LTSolver::LTSolver (LooseTray* t, Interactor* bg) {
    hnodes = new LTNodeList;
    vnodes = new LTNodeList;
    tray = t;
    background = bg;
    lmagic = rmagic = bmagic = tmagic = nil;
}

LTSolver::~LTSolver () {
    DeleteNodesAndElements(hnodes);
    DeleteNodesAndElements(vnodes);
    delete hnodes;
    delete vnodes;
}

void LTSolver::DeleteNodesAndElements (LTNodeList* nodes) {
    LTNode* merged;
    register LTNodeList* t = nodes->First();
    
    if (t == nodes->End()) {
        return;
    }
    merged = t->GetNode();

    for (t = t->Next(); t != nodes->End(); t = t->Next()) {
        LTNode* doomed = t->GetNode();
        merged->Merge(doomed);
        delete doomed;
    }
    merged->DeleteElements();
    delete merged;
}

inline boolean HAlignment (Alignment a) {
    return a != Bottom && a != VertCenter && a != Top;
}

inline boolean VAlignment (Alignment a) {
    return a != Left && a != HorizCenter && a != Right;
}

void LTSolver::AddAlignment (
    Alignment a1, Interactor* i1, Alignment a2, Interactor* i2, LTGlue* tg
) {
    LTElement* e1l, *e1r, *e2l, *e2r, *e3;
    
    i1 = BgFilter(i1);
    i2 = BgFilter(i2);
    
    if (HAlignment(a1) && HAlignment(a2)) {
	HConvert(i1, e1l, e1r);
	HConvert(i2, e2l, e2r);
	HConvert(tg, e3);
	HAddAlignment(a1, e1l, e1r, a2, e2l, e2r, e3);
    }

    if (VAlignment(a1) && VAlignment(a2)) {
	VConvert(i1, e1l, e1r);
	VConvert(i2, e2l, e2r);
	VConvert(tg, e3);
	VAddAlignment(a1, e1l, e1r, a2, e2l, e2r, e3);
    }
    UpdateMagicNodes();
}
 
void LTSolver::AddAlignment (Alignment a, Interactor* i, LTGlue* tg) {
    LTElement* e1l, *e1r, *e2l, *e2r, *e3;
    Interactor* i1 = i;
    Interactor* i2 = tray;
    
    if (i == background || i == tray) {
	return;
    }

    if (HAlignment(a)) {
	HOrder(a, i1, i2);
	HConvert(i1, e1l, e1r);
	HConvert(i2, e2l, e2r);
	HConvert(tg, e3);
	HAddAlignment(a, e1l, e1r, a, e2l, e2r, e3);
    }

    if (VAlignment(a)) {
	VOrder(a, i1, i2);
	VConvert(i1, e1l, e1r);
	VConvert(i2, e2l, e2r);
	VConvert(tg, e3);
	VAddAlignment(a, e1l, e1r, a, e2l, e2r, e3);
    }
    UpdateMagicNodes();
}

void LTSolver::HOrder (Alignment a, Interactor*& i1, Interactor*& i2) {
    Interactor* i = (i1 == tray) ? i2 : i1;
    
    if (a == BottomRight || a == CenterRight || a == TopRight || a == Right) {
	i1 = i;
	i2 = tray;
    } else {
	i1 = tray;
	i2 = i;
    }
}

void LTSolver::VOrder (Alignment a, Interactor*& i1, Interactor*& i2) {
    Interactor* i = (i1 == tray) ? i2 : i1;
    
    if (a == TopLeft || a == TopCenter || a == TopRight || a == Top) {
	i1 = i;
	i2 = tray;
    } else {
	i1 = tray;
	i2 = i;
    }
}

void LTSolver::DeleteAlignmentsTo (Interactor* i) {
    LTElement* e1, *e2;
    LTNode* lb, *rt;
    
    i = BgFilter(i);
    hnodes->FindElements(i, e1, e2);
    lb = hnodes->Node(BottomLeft, e1);
    rt = hnodes->Node(TopRight, e2);
    hnodes->Exclude(e1);
    hnodes->Exclude(e2);
    delete e1;
    delete e2;
    DeleteDanglingGlue(hnodes, lb);
    DeleteDanglingGlue(hnodes, rt);

    vnodes->FindElements(i, e1, e2);
    lb = vnodes->Node(BottomLeft, e1);
    rt = vnodes->Node(TopRight, e2);
    vnodes->Exclude(e1);
    vnodes->Exclude(e2);
    delete e1;
    delete e2;
    DeleteDanglingGlue(vnodes, lb);
    DeleteDanglingGlue(vnodes, rt);
}

void LTSolver::SetShape (Interactor* i) {
    LTElement* lbElem, *rtElem;
    
    i = BgFilter(i);
    
    hnodes->FindElements(i, lbElem, rtElem);
    if (lbElem == nil) {
	return;
    }
    lbElem->HSetShape();
    rtElem->HSetShape();

    vnodes->FindElements(i, lbElem, rtElem);
    if (lbElem == nil) {
	return;
    }
    lbElem->VSetShape();
    rtElem->VSetShape();
}

void LTSolver::Solve (int w, int h) {
    int dummy;

    if (lmagic != nil) {
        lmagic->SetPosition(0);
        rmagic->SetPosition(w);
        Solve(hnodes, lmagic, rmagic, w, dummy, dummy, dummy);
    }
    if (bmagic != nil) {
        bmagic->SetPosition(0);
        tmagic->SetPosition(h);
        Solve(vnodes, bmagic, tmagic, h, dummy, dummy, dummy);
    }
}

void LTSolver::CalcShape (Shape* s) {
    LTElement* ltray, *rtray, *btray, *ttray;
    
    hnodes->FindElements(tray, ltray, rtray);
    vnodes->FindElements(tray, btray, ttray);

    if (ltray != nil && lmagic != nil) {
        ltray->combinable = rtray->combinable = false;
        Solve(hnodes, lmagic, rmagic, 0, s->width, s->hshrink, s->hstretch);
        ltray->combinable = rtray->combinable = true;
    }

    if (btray != nil && bmagic != nil) {
        btray->combinable = ttray->combinable = false;
        Solve(vnodes, bmagic, tmagic, 0, s->height, s->vshrink, s->vstretch);
        btray->combinable = ttray->combinable = true;
    }
}

void LTSolver::GetPlacement (
    Interactor* i, Coord& l, Coord& b, Coord& r, Coord& t
) {
    Shape* s = i->GetShape();

    GetPlacement(hnodes, i, s->width, l, r);
    GetPlacement(vnodes, i, s->height, b, t);
}

void LTSolver::GetPlacement (
    LTNodeList* nodes, Interactor* i, int dfault, Coord& lb, Coord& rt
) {
    LTElement* lbElem, *rtElem;

    nodes->FindElements(i, lbElem, rtElem);
    if (lbElem == nil) {
	lb = 0;
	rt = dfault - 1;
    } else {
	lb = round(lbElem->pos);
	rt = round(
	    lbElem->pos + lbElem->nat + lbElem->sigma +
	    rtElem->nat + rtElem->sigma - 1
	);
    }
}

void LTSolver::Solve (
    LTNodeList* nodes, LTNode* lbMagic, LTNode* rtMagic, int size,
    int& nat, int& shr, int& str
) {
    LTElement* e1, *e2, *e3;
    LTTermination* t;
    TLoop* l;
    LTNode* n;
    
    if (nodes->Empty()) {
	/* no alignments; do nothing */
	
    } else if (nodes->Degenerate(e1)) {
	nat = round(e1->nat);
	shr = round(e1->shrink);
	str = round(e1->stretch);
	e1->pos = (lbMagic == nil) ? 0 : lbMagic->GetPosition();
	e1->sigma = (rtMagic == nil) ? e1->nat : size - round(e1->nat);
	e1->Limit();

    } else if (nodes->FoundSeries(e1, e2, lbMagic, rtMagic)) {
	e3 = e1->Series(e2);
	nodes->RemoveSeries(e3, e1, e2);
	Solve(nodes, lbMagic, rtMagic, size, nat, shr, str);
	nodes->ApplyToSeries(e3, e1, e2);
	nodes->ReplaceSeries(e3, e1, e2);
	delete e3;

    } else if (nodes->FoundParallel(e1, e2)) {
	e3 = e1->Parallel(e2);
	nodes->RemoveParallel(e3, e1, e2);
	Solve(nodes, lbMagic, rtMagic, size, nat, shr, str);
	nodes->ApplyToParallel(e3, e1, e2);
	nodes->ReplaceParallel(e3, e1, e2);
	delete e3;

    } else if (nodes->FoundTermination(t, lbMagic, rtMagic)) {
	nodes->RemoveTermination(t);
	Solve(nodes, lbMagic, rtMagic, size, nat, shr, str);
	nodes->ApplyToTermination(t);
	nodes->ReplaceTermination(t);
	delete t;
	
    } else if (nodes->FoundStub(e1) || nodes->FoundCrossover(e1)) {
	nodes->Reverse(e1);
	Solve(nodes, lbMagic, rtMagic, size, nat, shr, str);
	nodes->Reverse(e1);

    } else if (nodes->FoundLoop(l)) {
	nodes->RemoveLoop(l);
	Solve(nodes, lbMagic, rtMagic, size, nat, shr, str);
	nodes->ApplyToLoop(l);
	nodes->ReplaceLoop(l);
	delete l;

    } else if (nodes->OnlyOne()) {
	n = nodes->First()->GetNode();
	if (n != lbMagic && n != rtMagic) {
	    n->SetPosition(0);
	}
	nat = str = shr = 0;
    }
}

void LTSolver::HConvert (Interactor* i, LTElement*& el, LTElement*& er) {
    if (i == nil) {
	el = er = nil;

    } else {
	hnodes->FindElements(i, el, er);
	if (el == nil) {
	    el = new LTElement(i);
	    el->combinable = true;
	    el->leftBotHalf = true;
	    el->HSetShape();
	
	    er = new LTElement(i);
	    er->combinable = true;
	    er->leftBotHalf = false;
	    er->HSetShape();
	    hnodes->Include(TopRight, el, BottomLeft, er);
	}
    }
}
 
void LTSolver::HConvert (LTGlue* tg, LTElement*& e) {
    if (tg == nil) {
	e = nil;

    } else {
	hnodes->FindElement(tg, e);
	if (e == nil) {
	    e = new LTElement(tg);
	    e->combinable = true;
	    e->leftBotHalf = true;
	    e->HSetShape();
	}
    }
}

void LTSolver::VConvert (Interactor* i, LTElement*& eb, LTElement*& et) {
    if (i == nil) {
	eb = et = nil;

    } else {
	vnodes->FindElements(i, eb, et);
	if (eb == nil) {
	    eb = new LTElement(i);
	    eb->combinable = true;
	    eb->leftBotHalf = true;
	    eb->VSetShape();
	
	    et = new LTElement(i);
	    et->combinable = true;
	    et->leftBotHalf = false;
	    et->VSetShape();
	    vnodes->Include(TopRight, eb, BottomLeft, et);
	}
    }
}

void LTSolver::VConvert (LTGlue* tg, LTElement*& e) {
    if (tg == nil) {
	e = nil;

    } else {
	vnodes->FindElement(tg, e);
	if (e == nil) {
	    e = new LTElement(tg);
	    e->combinable = true;
	    e->leftBotHalf = true;
	    e->VSetShape();
	}
    }
}

void LTSolver::HAddAlignment (
    Alignment a1, LTElement* e1l, LTElement* e1r,
    Alignment a2, LTElement* e2l, LTElement* e2r,
    LTElement* tg
) {
    LTElement* e1, *e2;
    Alignment na1, na2;
    
    switch (a1) {
	case TopLeft:
	case CenterLeft:
	case BottomLeft:
	case Left:
	    e1 = e1l;
	    na1 = BottomLeft;
	    break;
	case TopCenter:
	case Center:
	case BottomCenter:
	case HorizCenter:
	    e1 = e1l;
	    na1 = TopRight;
	    break;
	case TopRight:
	case CenterRight:
	case BottomRight:
	case Right:
	    e1 = e1r;
	    na1 = TopRight;
	    break;
    }
    switch (a2) {
	case TopLeft:
	case CenterLeft:
	case BottomLeft:
	case Left:
	    e2 = e2l;
	    na2 = BottomLeft;
	    break;
	case TopCenter:
	case Center:
	case BottomCenter:
	case HorizCenter:
	    e2 = e2l;
	    na2 = TopRight;
	    break;
	case TopRight:
	case CenterRight:
	case BottomRight:
	case Right:
	    e2 = e2r;
	    na2 = TopRight;
	    break;
    }
    hnodes->AddMissingNodes(e1l);
    hnodes->AddMissingNodes(e1r);
    hnodes->AddMissingNodes(e2l);
    hnodes->AddMissingNodes(e2r);
    Include(hnodes, na1, e1, na2, e2, tg);
}

void LTSolver::VAddAlignment (
    Alignment a1, LTElement* e1b, LTElement* e1t,
    Alignment a2, LTElement* e2b, LTElement* e2t,
    LTElement* tg
) {
    LTElement* e1, *e2;
    Alignment na1, na2;
    
    switch (a1) {
	case BottomLeft:
	case BottomCenter:
	case BottomRight:
	case Bottom:
	    e1 = e1b;
	    na1 = BottomLeft;
	    break;
	case CenterLeft:
	case Center:
	case CenterRight:
	case VertCenter:
	    e1 = e1b;
	    na1 = TopRight;
	    break;
	case TopLeft:
	case TopCenter:
	case TopRight:
	case Top:
	    e1 = e1t;
	    na1 = TopRight;
	    break;
    }
    switch (a2) {
	case BottomLeft:
	case BottomCenter:
	case BottomRight:
	case Bottom:
	    e2 = e2b;
	    na2 = BottomLeft;
	    break;
	case CenterLeft:
	case Center:
	case CenterRight:
	case VertCenter:
	    e2 = e2b;
	    na2 = TopRight;
	    break;
	case TopLeft:
	case TopCenter:
	case TopRight:
	case Top:
	    e2 = e2t;
	    na2 = TopRight;
	    break;
    }
    vnodes->AddMissingNodes(e1b);
    vnodes->AddMissingNodes(e1t);
    vnodes->AddMissingNodes(e2b);
    vnodes->AddMissingNodes(e2t);
    Include(vnodes, na1, e1, na2, e2, tg);
}

void LTSolver::Include (
    LTNodeList* nodes, 
    Alignment na1, LTElement* e1, Alignment na2, LTElement* e2, LTElement* tg
) {
    if (e1->owner == e2->owner && na1 == na2) {
	/* aligned a node to itself; do nothing */
    
    } else if (tg == nil) {
	nodes->Include(na1, e1, na2, e2);

    } else if (na1 == BottomLeft && na2 == TopRight) {
	nodes->Include(BottomLeft, e1, TopRight, tg);
	nodes->Include(TopRight, e2, BottomLeft, tg);

    } else {
	nodes->Include(na1, e1, BottomLeft, tg);
	nodes->Include(na2, e2, TopRight, tg);
    }
}

void LTSolver::LooseTrayNodes (LTNodeList* nodes, LTNode*& nlb, LTNode*& nrt) {
    LTNode *ctr;
    LTElement* elb, *ert;

    nodes->FindElements(tray, elb, ert);
    if (elb == nil) {
	nlb = nrt = nil;
    } else {
	nodes->Nodes(elb, nlb, ctr);
	nrt = nodes->OtherNode(ert, ctr);
    }
}

void LTSolver::UpdateMagicNodes () {
    LooseTrayNodes(hnodes, lmagic, rmagic);
    LooseTrayNodes(vnodes, bmagic, tmagic);
}

void LTSolver::DeleteDanglingGlue (LTNodeList* nodes, LTNode* n) {
    LTElement* e;

    if (n->Degenerate(e) && e->tglue != nil) {
        nodes->Exclude(e);
        delete e;
    }
}

Interactor* LTSolver::BgFilter (Interactor* i) {
    return (i == background) ? tray : i;
}

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

class LooseTrayElement {
public:
    /* NEW FOR LooseTray */
    int x,y,h,w;			    /* Absolute x,y,h,w coords */
    /* NOTE: If we ever allow LooseTray elements to change shape and/or move,
     * then the LooseTray will have to be notified for any such change so it
     * can update these coords.
     */   

    Interactor* child;
    boolean visible;
    LooseTrayElement* next;
};

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

LTGlue::LTGlue (int w, int h, int hstr, int vstr) {
    shape = new Shape;
    shape->width = w;
    shape->height = h;
    shape->hshrink = 0;
    shape->hstretch = hstr;
    shape->vshrink = 0;
    shape->vstretch = vstr;
}

LTGlue::LTGlue (int w, int h, int hshr, int hstr, int vshr, int vstr) {
    shape = new Shape;
    shape->width = w;
    shape->height = h;
    shape->hshrink = hshr;
    shape->hstretch = hstr;
    shape->vshrink = vshr;
    shape->vstretch = vstr;
}

LTGlue::~LTGlue () {
    delete shape;
}

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

inline boolean LooseTray::LooseTrayOrBg (Interactor* i) { return i == this || i == bg; }

LooseTray::LooseTray (Interactor* b) {
    Init(b);
}

LooseTray::LooseTray (const char* name, Interactor* b) {
    SetInstance(name);
    Init(b);
}

void LooseTray::Init (Interactor* b) {
    SetClassName("LooseTray");
    nelements = 0;
    head = nil;
    tail = nil;
    bg = b;
    tsolver = new LTSolver(this, bg);
}

LooseTray::~LooseTray () {
    register LooseTrayElement* e, *next;

    delete tsolver;

    for (e = head; e != nil; e = next) {
        next = e->next;
        delete e->child;
	delete e;
    }
    if (bg != nil) {
	delete bg;
    }
}

void LooseTray::ComponentBounds (int& w, int& h) {
    register LooseTrayElement* e, *next;
    Shape* s;
    
    w = h = 0;
    for (e = head; e != nil; e = next) {
        next = e->next;
        s = e->child->GetShape();
	w = max(w, s->width);
	h = max(h, s->height);
    }
}    

void LooseTray::CalcShape () {
    int w, h;

    if (bg == nil) {
	ComponentBounds(w, h);
	tsolver->CalcShape(shape);
	shape->width = max(shape->width, w);
	shape->height = max(shape->height, h);
    } else {
	*shape = *bg->GetShape();
    }
    tsolver->SetShape(this);
}

void LooseTray::Reconfig () {
    register LooseTrayElement* e;

    for (e = head; e != nil; e = e->next) {
	tsolver->SetShape(e->child);
    }
    CalcShape();
}

void LooseTray::DoInsert (Interactor* i, boolean, 
	Coord &x, Coord &y) {
/*
    Place(i, x, y, x+20, y+20);
 */
    ++nelements;
    register LooseTrayElement* e = new LooseTrayElement;
    e->child = i;
    e->next = nil;
    if (head == nil) {
        head = e;
        tail = e;
    } else {
        tail->next = e;
        tail = e;
    }
    /* NEW FOR LooseTray: */
    /* We'd like to use l,b,r,t, but we only have x,y from scene.  Maybe later.
       e->l = l;
       e->b = b;
       e->r = r;
       e->t = t;
    */

    /* Stuff based on x,y instead of l,b,r,t: */
      e->x = x;
      e->y = y;
      Shape* s = i->GetShape();
      e->h = s->height;
      e->w = s->width;
}

void LooseTray::DoChange (Interactor* i) {
    tsolver->SetShape(i);
    CalcShape();
}

void LooseTray::DoRemove (Interactor* i) {
    register LooseTrayElement* e, * prev;

    if (i == bg) {
	bg = nil;
	tsolver->DeleteAlignmentsTo(i);
    } else {
	--nelements;
	prev = nil;
	for (e = head; e != nil; e = e->next) {
	    if (e->child == i) {
		if (prev == nil) {
		    head = e->next;
		} else {
		    prev->next = e->next;
		}
		if (e == tail) {
		    tail = prev;
		}
		delete e;
		tsolver->DeleteAlignmentsTo(i);
		break;
	    }
	    prev = e;
	}
    }
}

void LooseTray::Resize () {
    register LooseTrayElement* e;

    canvas->SetBackground(output->GetBgColor());
    if (bg != nil) {
	Place(bg, 0, 0, xmax, ymax);
    }

    for (e = head; e != nil; e = e->next) {
	tsolver->SetShape(e->child);
    }

    tsolver->Solve(xmax+1, ymax+1);

    for (e = head; e != nil; e = e->next) {
	PlaceElement(e);
    }
}



boolean LooseTray::AlreadyInserted (Interactor* i) {
    register LooseTrayElement* e;

    if (i == this || i == bg) {
	return true;
    }
    
    for (e = head; e != nil; e = e->next) {
	if (e->child == i) {
	    return true;
	}
    }
    return false;
}

void LooseTray::PlaceElement (LooseTrayElement* e) {
    Coord l, b, r, t, tmp;
    /* NEW FOR LooseTray */
    if ((e->x >= 0)) {
	/* If we had l,b,r,t, we'd do this, but alas not:
	   l = e->l;
	   b = e->b;
	   r = e->r;
	   t = e->t;
        */
	/* So, we compute l,b,r,t from x,y,h,w */
	  l = e->x;
	  b = e->y;
	  r = e->x + e->w;
	  t = e->y + e->h;
    }
    else
        tsolver->GetPlacement(e->child, l, b, r, t);

    if (
	r > 0 && l < xmax && t > 0 && b < ymax && 
	l - r != -1 && t - b != -1
    ) {
	e->visible = true;
	tmp = min(l, r);
	r = max(l, r);
	l = tmp;
	tmp = min(b, t);
	t = max(b, t);
	b = tmp;
	Place(e->child, l, b, r, t);
    } else {
	e->visible = false;
    }
}

void LooseTray::Draw () {
    register LooseTrayElement* e;

    if (bg != nil) {
	bg->Draw();
    }
    for (e = head; e != nil; e = e->next) {
        if (e->visible) {
            e->child->Draw();
        }
    }
}

void LooseTray::Reshape (Shape& s) {
    *shape = s;
    Scene* p = Parent();
    if (p != nil) {
	p->Change(this);
    }
}

void LooseTray::GetComponents (Interactor** c, int nc, Interactor**& a, int& n) {
    register LooseTrayElement* e;
    register Interactor** ap;

    n = nelements;
    if (bg != nil) {
	++n;
    }
    a = (n <= nc) ? c : new Interactor*[n];
    ap = a;
    for (e = head; e != nil; e = e->next) {
        *ap++ = e->child;
    }
    if (bg != nil) {
	*ap = bg;
    }
}

void LooseTray::Align (
    Alignment a1, Interactor* i1, Alignment a2, Interactor* i2, LTGlue* tg
) {
    if (!AlreadyInserted(i1)) {
	Insert(i1);
    }
    if (!AlreadyInserted(i2)) {
	Insert(i2);
    }
    tsolver->AddAlignment(a1, i1, a2, i2, tg);
}

void LooseTray::Align (Alignment a, Interactor* i, LTGlue* tg) {
    if (!AlreadyInserted(i)) {
	Insert(i);
    }
    tsolver->AddAlignment(a, i, tg);
}

static void LoadInteractorArray (
    Interactor* i[], Interactor* i0, Interactor* i1,
    Interactor* i2, Interactor* i3, Interactor* i4,
    Interactor* i5, Interactor* i6
) {
    i[0] = i0;
    i[1] = i1;
    i[2] = i2;
    i[3] = i3;
    i[4] = i4;
    i[5] = i5;
    i[6] = i6;
}

void LooseTray::Align (
    Alignment a, Interactor* i0, Interactor* i1,
    Interactor* i2, Interactor* i3, Interactor* i4,
    Interactor* i5, Interactor* i6
) {
    const int n = 7;
    Interactor* i[n];
    int k;
    
    LoadInteractorArray(i, i0, i1, i2, i3, i4, i5, i6);
    
    for (k = 0; k < n && i[k] != nil; ++k) {
	if (!AlreadyInserted(i[k])) {
	    Insert(i[k]);
	}
    }
    for (k = 1; k < n && i[k] != nil; ++k) {
	tsolver->AddAlignment(a, i[k-1], a, i[k]);
    }    
}

void LooseTray::HBox (
    Interactor* i0, Interactor* i1,
    Interactor* i2, Interactor* i3, Interactor* i4,
    Interactor* i5, Interactor* i6
) {
    const int n = 7;
    Interactor* i[n];
    int k, last = n - 1;
    
    LoadInteractorArray(i, i0, i1, i2, i3, i4, i5, i6);
    
    for (k = 0; k < n && i[k] != nil; ++k) {
	if (!AlreadyInserted(i[k])) {
	    Insert(i[k]);
	}
    }
    for (k = 1; k < n && i[k] != nil; ++k) {
	if (LooseTrayOrBg(i[0]) && k == 1) {
	    tsolver->AddAlignment(Left, this, Left, i[1]);

	} else if (LooseTrayOrBg(i[k]) && (k == last || i[k+1] == nil)) {
	    tsolver->AddAlignment(Right, i[k-1], Right, this);

	} else {
	    tsolver->AddAlignment(Right, i[k-1], Left, i[k]);
	}
    }    
}

void LooseTray::VBox (
    Interactor* i0, Interactor* i1,
    Interactor* i2, Interactor* i3, Interactor* i4,
    Interactor* i5, Interactor* i6
) {
    const int n = 7;
    Interactor* i[n];
    int k, last = n - 1;
    
    LoadInteractorArray(i, i0, i1, i2, i3, i4, i5, i6);
    
    for (k = 0; k < n && i[k] != nil; ++k) {
	if (!AlreadyInserted(i[k])) {
	    Insert(i[k]);
	}
    }
    for (k = 1; k < n && i[k] != nil; ++k) {
	if (LooseTrayOrBg(i[0]) && k == 1) {
	    tsolver->AddAlignment(Top, this, Top, i[1]);

	} else if (LooseTrayOrBg(i[k]) && (k == last || i[k+1] == nil)) {
	    tsolver->AddAlignment(Bottom, i[k-1], Bottom, this);

	} else {
	    tsolver->AddAlignment(Bottom, i[k-1], Top, i[k]);
	}
    }    
}