lib/sced/choose.c

/***************************************************************************
SCED - Schematic Capture Editor
JSPICE3 adaptation of Spice3e2 - Copyright (c) Stephen R. Whiteley 1992
Copyright 1990 Regents of the University of California.  All rights reserved.
Authors: 1981 Giles C. Billingsley  (parts of KIC layout editor)
         1992 Stephen R. Whiteley
****************************************************************************/

/*
 * The SCED selection code.
 *
 *
 * The Selection code extensively uses the CD Info field.  The following
 * convention is used:
 *
 *   Info = SQ_OLD     (0) Object is unselected.
 *  *Info = SQ_OLDSEL  (1) Object is selected and in SelectionQ.
 *   Info = SQ_GONE    (2) Object is conditionally deleted and in SelectionQ.
 *   Info = SQ_NEW     (3) Object is conditionally created and in SelectionQ.
 *  *Info = SQ_NEWSEL  (4) Object is conditionally created and in SelectionQ.
 *   Info = SQ_INCMPLT (5) Object is being created.
 *
 *   Info = 6-11           Reserved.
 *  *Info = 11-255         Object has conditionally new layer and is in
 *                         SelectionQ.  OldLayer = Info - 10.
 *
 *  * means that SQShow will highlight these objects.
 *
 */

#include "spice.h"
#include "sced.h"
#include <string.h>


/***********************************************************************
 *
 * Current transform code.
 *
 ***********************************************************************/

extern char *MenuMX;
extern char *MenuMY;
extern char *Menu0;
extern char *Menu90;
extern char *Menu180;
extern char *Menu270;


void
MX()

{
    if (Parameters.kpMX) {
        Parameters.kpMX = False;
        MenuDeselect(MenuMX);
    }
    else {
        Parameters.kpMX = True;
        MenuSelect(MenuMX);
    }
}


void
MY()

{
    if (Parameters.kpMY) {
        Parameters.kpMY = False;
        MenuDeselect(MenuMY);
    }
    else {
        Parameters.kpMY = True;
        MenuSelect(MenuMY);
    }
}


void
Rotat0()

{
    Parameters.kpRotationAngle = 90;
    AlterMenuEntries(Menu0,Menu90);
    MenuSelect(Menu90);
}


void
Rotat90()

{
    Parameters.kpRotationAngle = 180;
    AlterMenuEntries(Menu90,Menu180);
    MenuSelect(Menu180);
}


void
Rotat180()

{
    Parameters.kpRotationAngle = 270;
    AlterMenuEntries(Menu180,Menu270);
    MenuSelect(Menu270);
}


void
Rotat270()

{
    Parameters.kpRotationAngle = 0;
    AlterMenuEntries(Menu270,Menu0);
    MenuDeselect(Menu0);
}


/***********************************************************************
 *
 * Selection operator code.
 *
 ***********************************************************************/

extern char *MenuAREA;
extern char *MenuDESEL;
extern char *MenuSELEC;
extern char *MenuUNDO;

#ifdef __STDC__
static struct ks *select_items(struct ka*,int);
static void sl_free(struct ks*);
static void sl_bb(struct ks*,struct ka*);
static void get_BB(struct o*,struct ka*);
static int  is_BB_visible(struct o*);
static void redisplay_edges(struct ka*);
static struct ks *which_cell(struct ks*);
static void sq_set_NEW(struct o*);
static void sq_delete_dups(void);
static void sq_display_selected(struct o*);
static int  overlap_path(struct p*,struct ka*);
static int  overlap_line(struct ka*,struct ka*);
static int  cross_line(struct ka*,struct ka*);
static int  point_in_poly(int,struct p*,long,long);
#else
static struct ks *select_items();
static void sl_free();
static void sl_bb();
static void get_BB();
static int  is_BB_visible();
static void redisplay_edges();
static struct ks *which_cell();
static void sq_set_NEW();
static void sq_delete_dups();
static void sq_display_selected();
static int  overlap_path();
static int  overlap_line();
static int  cross_line();
static int  point_in_poly();
#endif

#define UpdateBB(BB2,BB1) \
    if (BB1.kaLeft < BB2.kaLeft)     BB2.kaLeft = BB1.kaLeft; \
    if (BB1.kaBottom < BB2.kaBottom) BB2.kaBottom = BB1.kaBottom; \
    if (BB1.kaRight > BB2.kaRight)   BB2.kaRight = BB1.kaRight; \
    if (BB1.kaTop > BB2.kaTop)       BB2.kaTop = BB1.kaTop;


void
Sel(LookedAhead)

int *LookedAhead;
{
    struct ka AOI;
    int FirstTime = True;

    MenuSelect(MenuSELEC);
    ShowPrompt("Point to select.");
    loop {
        switch (PointLoop(LookedAhead)) {
            case PL_CMD:
            case PL_ESC:
                goto quit;
            case PL_UND:
                if (FirstTime == True) goto quit;
                MenuSelect(MenuUNDO);
                Selection(&AOI);
                MenuDeselect(MenuUNDO);
                continue;
            case PL_PCW:
                AOI.kaLeft   = AOI.kaRight = SCursor.kcRawX;
                AOI.kaBottom = AOI.kaTop   = SCursor.kcRawY;
                ErasePrompt();
                Selection(&AOI);
                FirstTime = False;
        }
    }
quit:
    MenuDeselect(MenuSELEC);
    ErasePrompt();
}


void
Area(LookedAhead)

int *LookedAhead;
{
    struct ka AOI;
    long OldRawX,OldRawY;
    int FirstTime = True;

    MenuSelect(MenuAREA);
top:
    loop {
        ShowPrompt("Point to endpoints of diagonal.");
        switch (PointLoop(LookedAhead)) {
            case PL_ESC:
            case PL_CMD:
                goto quit;
            case PL_UND:
                if (FirstTime == True) goto quit;
                MenuSelect(MenuUNDO);
                Selection(&AOI);
                MenuDeselect(MenuUNDO);
                goto top;
            case PL_PCW:
                FBSetRubberBanding('R');
                OldRawX = SCursor.kcRawX;
                OldRawY = SCursor.kcRawY;
        }
        ShowPrompt("Point to second endpoint.");
        switch (PointLoop(LookedAhead)) {
            case PL_ESC:
            case PL_CMD:
                goto quit;
            case PL_UND:
                FBSetRubberBanding(0);
                goto top;
            case PL_PCW:
                FBSetRubberBanding(0);
                break;
        }
        AOI.kaLeft   = Min(OldRawX,SCursor.kcRawX);
        AOI.kaBottom = Min(OldRawY,SCursor.kcRawY);
        AOI.kaRight  = Max(OldRawX,SCursor.kcRawX);
        AOI.kaTop    = Max(OldRawY,SCursor.kcRawY);
        Selection(&AOI);
        FirstTime = False;
    }

quit:
    FBSetRubberBanding(0);
    MenuDeselect(MenuAREA);
    ErasePrompt();
}


void
Desel()

{
    MenuSelect(MenuDESEL);
    SQComputeBB();
    if (SelectQHead != NULL) {
        SQClear();
        /* Take care of Instance markers */
        OversizeBox(&SelectQBB,200);
        EraseBox(&SelectQBB);
        Redisplay(&SelectQBB);
    }
    MenuDeselect(MenuDESEL);
}


void
Selection(AOI)

/* Select items and link into SelectionQ, compute BB. */
struct ka *AOI;
{
    struct ks *SList, *S;
    struct ka BB,OldSelectQBB;

    if (AOI->kaLeft == AOI->kaRight) {
        /* Point selection. */

        SList = select_items(AOI,True);
        if (SList == NULL) return;
        if (SList->ksPointer->oType == CDSYMBOLCALL) {
            /* no geometry found, get one symbol */
            S = which_cell(SList);
            if (S) {
                if (S->ksPointer->oInfo == SQ_OLDSEL) {
                    /* already selected, deselect and break */
                    S->ksPointer->oInfo = SQ_OLD;
                    SQDelete(S->ksPointer);
                    get_BB(S->ksPointer,&BB);
                    redisplay_edges(&BB);
                }
                else {
                    /* add to select Q */
                    S->ksPointer->oInfo = SQ_OLDSEL;
                    SQInsert(S->ksPointer);
                    sq_display_selected(S->ksPointer);
                }
            }
            SQComputeBB();
            sl_free(SList);
            return;
        }
        for (S = SList; S != NULL; S = S->ksSucc) {
            /* keep only geometry */
            if (S->ksPointer->oType == CDSYMBOLCALL) break;

            if (S->ksPointer->oInfo == SQ_OLDSEL) {
                /* already selected, deselect and break */
                S->ksPointer->oInfo = SQ_OLD;
                SQDelete(S->ksPointer);
                get_BB(S->ksPointer,&BB);
                EraseBox(&BB);
                Redisplay(&BB);
                DevUpdate();
                break;
            }
            else {
                /* add to select Q */
                S->ksPointer->oInfo = SQ_OLDSEL;
                SQInsert(S->ksPointer);
                sq_display_selected(S->ksPointer);
            }
        }
        SQComputeBB();
    }
    else {

        /* Area select. */
        SList = select_items(AOI,False);
        if (SList == NULL) return;
        SQComputeBB();
        OldSelectQBB = SelectQBB;

        for (S = SList; S != NULL; S = S->ksSucc) {
            if (S->ksPointer->oType == CDSYMBOLCALL &&
                !is_BB_visible(S->ksPointer)) continue;

            if (S->ksPointer->oInfo == SQ_OLDSEL) {
                /* already selected, deselect */
                S->ksPointer->oInfo = SQ_OLD;
                SQDelete(S->ksPointer);
            }
            else {
                /* add to select Q */
                S->ksPointer->oInfo = SQ_OLDSEL;
                SQInsert(S->ksPointer);
            }
        }
        SQComputeBB();
        UpdateBB(SelectQBB,OldSelectQBB);
        if (SelectQBB.kaLeft == CDINFINITY) return;
        EraseBox(&SelectQBB);
        Redisplay(&SelectQBB);
        DevUpdate();
    }
    sl_free(SList);
}


static struct ks *
select_items(AOI,PointSelect)

/* Return a list of visible objects in the neighborhood of AOI as returned
 * from the generator.  Only types in Parameters.kpSelectTypes are listed,
 * all are listed if this is NULL.  The flag PointSelect is set for
 * a point selection.
 */
struct ka *AOI;
int PointSelect;
{
    struct g *GenDesc;
    struct o *Pointer;
    struct ka BB;
    struct ks *SPointer = NULL, *S;
    struct p *Path;
    long Width;
    int Delta,Layer;

    if (PointSelect) {
        /* expand the point to finite size */
        if (SCursor.kcInFine == True)
            Delta = 3.0/View->kvFineRatio;
        else
            Delta = 3.0/View->kvCoarseRatio;
        OversizeBox(AOI,Delta);
    }

    if (Not CDInitGen(Parameters.kpCellDesc,1,AOI->kaLeft,AOI->kaBottom,
        AOI->kaRight,AOI->kaTop,&GenDesc)) MallocFailed();
    loop {
        CDGen(Parameters.kpCellDesc,GenDesc,&Pointer);
        if (Pointer == NULL) break;
        if (Pointer->oInfo == SQ_GONE) continue;
        if (Parameters.kpSelectTypes &&
            !strchr(Parameters.kpSelectTypes,Pointer->oType)) continue;

        switch (Pointer->oType) {
            case CDWIRE:
                CDWire(Pointer,&Layer,&Width,&Path);
                if (PointSelect) {
                    if (InPath(Delta+(int)Width/2,Path,
                        AOI->kaLeft+Delta,AOI->kaBottom+Delta) != NULL)
                        break;
                }
                else {
                    if (overlap_path(Path,AOI)) break;
                    if (InBox(Path->pX,Path->pY,AOI)) break;
                }
                continue;

            case CDPOLYGON:
                CDPolygon(Pointer,&Layer,&Path);
                if (PointSelect) {
                    if (point_in_poly(Delta,Path,
                        AOI->kaLeft+Delta,AOI->kaBottom+Delta))
                        break;
                }
                else {
                    if (point_in_poly(0,Path,AOI->kaLeft,AOI->kaBottom))
                        break;
                    if (overlap_path(Path,AOI)) break;
                    if (InBox(Path->pX,Path->pY,AOI)) break;
                }
                continue;

            case CDLABEL:
            case CDBOX:
                break;

            default:
                continue;
        }
        if (SPointer == NULL)
            S = SPointer = alloc(ks);
        else {
            S->ksSucc = alloc(ks);
            S = S->ksSucc;
        }
        if (S == NULL) MallocFailed();
        S->ksPointer = Pointer;
        S->ksSucc = NULL;
    }


    /* Now for the instances... */

    if (Parameters.kpSelectTypes &&
        !strchr(Parameters.kpSelectTypes,CDSYMBOLCALL)) {
        if (PointSelect) OversizeBox(AOI,-Delta);
        return (SPointer);
    }

    if (Not CDInitGen(Parameters.kpCellDesc,0,AOI->kaLeft,AOI->kaBottom,
        AOI->kaRight,AOI->kaTop,&GenDesc)) MallocFailed();
    loop {
        CDGen(Parameters.kpCellDesc,GenDesc,&Pointer);
        if (Pointer == NULL) break;

        if (Pointer->oInfo == SQ_GONE) continue;
        if (SPointer == NULL)
            S = SPointer = alloc(ks);
        else {
            S->ksSucc = alloc(ks);
            S = S->ksSucc;
        }
        if (S == NULL) MallocFailed();
        S->ksPointer = Pointer;
        S->ksSucc = NULL;
    }
    if (PointSelect) OversizeBox(AOI,-Delta);
    return (SPointer);
}


static void
sl_free(SList)

/* Free a list as returned from select_items(). */
struct ks *SList;
{
    struct ks *SQDesc,*SQNext;

    for (SQDesc = SList; SQDesc; SQDesc = SQNext) {
        SQNext = SQDesc->ksSucc;
        tfree(SQDesc);
    }
}


static void
sl_bb(SList,BB)

/* Compute the BB of the objects in SList. */
struct ks *SList;
struct ka *BB;
{
    struct ks *S;
    struct ka NBB,OBB;

    NBB.kaLeft   = CDINFINITY;
    NBB.kaBottom = CDINFINITY;
    NBB.kaRight  = -CDINFINITY;
    NBB.kaTop    = -CDINFINITY;

    for (S = SList; S != NULL; S = S->ksSucc) {
        get_BB(S->ksPointer,&OBB);
        UpdateBB(NBB,OBB);
    }
    *BB = NBB;
}


static void
get_BB(Pointer,BB)

struct o *Pointer;
struct ka *BB;
{
    if (Pointer->oType == CDLABEL)
        BBLabel(View->kvCoarseWindow,Pointer,BB);
    else
        CDStatusInt = CDBB(Parameters.kpCellDesc,Pointer,&BB->kaLeft,
            &BB->kaBottom,&BB->kaRight,&BB->kaTop);
}


static int
is_BB_visible(Pointer)

struct o *Pointer;
{
    struct ka BB;

    /* will edges show in coarse window? */
    CDStatusInt = CDBB(Parameters.kpCellDesc,Pointer,
        &BB.kaLeft,&BB.kaBottom,&BB.kaRight,&BB.kaTop);
    if (BB.kaLeft <= View->kvCoarseWindow->kaLeft &&
        BB.kaRight  >= View->kvCoarseWindow->kaRight &&
        BB.kaBottom <= View->kvCoarseWindow->kaBottom &&
        BB.kaTop    >= View->kvCoarseWindow->kaTop)
        return (False);
    return (True);
}


static void
redisplay_edges(BB)

/* redisplay the edges of BB */
struct ka *BB;
{
    struct ka EdgeOfBB;

    /* Left edge. */
    EdgeOfBB.kaLeft   = BB->kaLeft-300;
    EdgeOfBB.kaRight  = BB->kaLeft+300;
    EdgeOfBB.kaTop    = BB->kaTop+300;
    EdgeOfBB.kaBottom = BB->kaBottom-300;
    EraseBox(&EdgeOfBB);
    Redisplay(&EdgeOfBB);

    /* Right edge. */
    EdgeOfBB.kaRight  = BB->kaRight+300;
    EdgeOfBB.kaLeft   = BB->kaRight-300;
    EdgeOfBB.kaTop    = BB->kaTop+300;
    EdgeOfBB.kaBottom = BB->kaBottom-300;
    EraseBox(&EdgeOfBB);
    Redisplay(&EdgeOfBB);

    /* Bottom edge. */
    EdgeOfBB.kaBottom = BB->kaBottom-300;
    EdgeOfBB.kaTop    = BB->kaBottom+300;
    EdgeOfBB.kaRight  = BB->kaRight;
    EdgeOfBB.kaLeft   = BB->kaLeft;
    EraseBox(&EdgeOfBB);
    Redisplay(&EdgeOfBB);

    /* Top edge. */
    EdgeOfBB.kaBottom = BB->kaTop-300;
    EdgeOfBB.kaTop    = BB->kaTop+300;
    EdgeOfBB.kaRight  = BB->kaRight;
    EdgeOfBB.kaLeft   = BB->kaLeft;
    EraseBox(&EdgeOfBB);
    Redisplay(&EdgeOfBB);

    DevUpdate();
}


static struct ks *
which_cell(SList)

/* Resolve ambiguity (multiple instances selected) */
struct ks *SList;
{
    struct ks *S,*Sret;
    char *SymbolName;
    struct ka BB;
    double A,Area;

    /* find the smallest cell */
    sl_bb(SList,&BB);
    Area = BB.kaRight - BB.kaLeft;
    Area *= BB.kaTop - BB.kaBottom;
    Sret = SList;
    for (S = SList; S != NULL; S = S->ksSucc) {
        CDStatusInt = CDBB(Parameters.kpCellDesc,S->ksPointer,
            &BB.kaLeft,&BB.kaBottom,&BB.kaRight,&BB.kaTop);
        A = BB.kaRight - BB.kaLeft;
        A *= BB.kaTop - BB.kaBottom;
        if (A < Area) {
            Sret = S;
            Area = A;
        }
    }
    if (!is_BB_visible(Sret->ksPointer)) return (NULL);

    SymbolName = ((struct c *)Sret->ksPointer->oRep)->cMaster->mName;
    sprintf(TypeOut,"You have selected an instance of %s.",SymbolName);
    ShowPrompt(TypeOut);
    return (Sret);
}


int
AreTypesInQ(Types)

/* Returns True if one of Types is in SelectionQ and is selected,
 * or of anything selected is in the Q if Types is NULL.
 */
char *Types;
{
    struct ks *SQDesc;

    for (SQDesc = SelectQHead; SQDesc; SQDesc = SQDesc->ksSucc) {
        if (Types == NULL || strchr(Types,SQDesc->ksPointer->oType))
            if (SQDesc->ksPointer->oInfo == SQ_OLDSEL) return (True);
    }
    return (False);
}


void
SelectTypes(Types)

/* Perform a point select, selecting only Types, or anything if
 * Types is NULL.
 */
char *Types;
{
    struct ka BB;
    char TTmp[8];

    BB.kaLeft   = BB.kaRight = SCursor.kcRawX;
    BB.kaBottom = BB.kaTop   = SCursor.kcRawY;
    if (Types == NULL) {
        Selection(&BB);
        return;
    }
    strcpy(TTmp,Parameters.kpSelectTypes);
    strncpy(Parameters.kpSelectTypes,Types,8);
    Parameters.kpSelectTypes[7] = '\0';
    Selection(&BB);
    strcpy(Parameters.kpSelectTypes,TTmp);
}


void
SQInit()

{
    SelectQHead = NULL;
}


void
SQClear()

/* Clear the SelectionQ. */
{
    struct ks *SQDesc,*SQNext;

    for (SQDesc = SelectQHead; SQDesc; SQDesc = SQNext) {
        SQNext = SQDesc->ksSucc;
        SQDesc->ksPointer->oInfo = SQ_OLD;
        tfree(SQDesc);
    }
    SelectQHead = NULL;
}


void
SQInsert(Pointer)

/* Insert Pointer into the SelectionQ (no checking for duplication). */
struct o *Pointer;
{
    struct ks *SQDesc;

    if ((SQDesc = alloc(ks)) == NULL) MallocFailed();

    /* SelectQHead is most recent addition */
    SQDesc->ksPointer = Pointer;
    SQDesc->ksSucc = SelectQHead;
    SelectQHead = SQDesc;
}


void
SQDelete(Pointer)

/* Delete Pointer from SelectionQ if it is there. */
struct o *Pointer;
{
    struct ks *SQDesc,*SQPrev,*SQNext;

    SQPrev = NULL;

    for (SQDesc = SelectQHead; SQDesc; SQPrev = SQDesc,SQDesc = SQNext) {
        SQNext = SQDesc->ksSucc;

        if (SQDesc->ksPointer != Pointer) continue;
        Pointer->oInfo = SQ_OLD;

        if (SQPrev == NULL)
            SelectQHead = SQNext;
        else
            SQPrev->ksSucc = SQNext;
        tfree(SQDesc);
        return;
    }
}


void
SQComputeBB()

/* Compute the BB of the queued and selected objects. */
{
    struct ks *SQDesc;
    struct ka BB;
    int Info;

    SelectQBB.kaLeft   = CDINFINITY;
    SelectQBB.kaBottom = CDINFINITY;
    SelectQBB.kaRight  = -CDINFINITY;
    SelectQBB.kaTop    = -CDINFINITY;

    for (SQDesc = SelectQHead; SQDesc != NULL; SQDesc = SQDesc->ksSucc) {
        Info = SQDesc->ksPointer->oInfo;
        if (Info == SQ_OLDSEL || Info == SQ_NEWSEL ||
            (Info > 10 && Info <= 255)) {
            get_BB(SQDesc->ksPointer,&BB);
            UpdateBB(SelectQBB,BB);
        }
    }
}


/* Theory behind SQRestore() and SQDesel();
 *
 * In commands which modify objects such as Move, the original object(s)
 * are conditionally deleted, and new objects are conditionally created.
 * All objects are left in the SelectionQ for a time to allow Undo.
 * For example, suppose the SelectionQ is empty, and the user points at
 * an object.
 *
 *  operation:         SelectionQ:
 *  select             OLD (Info = SQ_OLDSEL)
 *  move               NEW (Info = SQ_NEW), OLD (Info = SQ_GONE)
 * User now selects newly moved object (the complicated case):
 *  select NEW         NEW (Info = SQ_OLDSEL), NEW (Info = SQ_OLDSEL),
 *                     OLD (Info = SQ_GONE)
 * Now undo undoes the selection
 *  Undo (SQDesel())   NEW (Info = SQ_NEW), OLD (Info = SQ_GONE)
 * Next undo undoes the move, leaving original item selected (conditionally).
 *  Undo (SQRestore(1)) OLD (Info = SQ_NEWSEL)
 * Next undo undoes the selection
 *  Undo (SQDesel())   OLD (Info = SQ_NEW)
 * The next undo repeats the move, etc.
 *
 * SQRestore(0) unsets the conditionality of objects in the SelectionQ
 * and should be called when things are "final," i.e., before function
 * exit or next operation.
 */


void
SQRestore(Undo)

/* Restore the conditionally created objects in the SelectionQ
 * and delete duplicates if Undo is False.  Otherwise undo the
 * last operation.
 */

/* If Undo is True:
 *  Previously deleted objects become conditionally selected:
 *   Info = SQ_GONE   -> Info = SQ_NEWSEL.
 *  New objects are deleted from SelectionQ and database:
 *   Info = SQ_NEW    deleted from queue and database.
 *   Info = SQ_NEWSEL deleted from queue and database.
 * Else
 *  Conditionally deleted objects are really deleted:
 *   Info = SQ_GONE   deleted from queue and database.
 *  New objects are now Old objects, selected or otherwise:
 *   Info = SQ_NEW    -> Info = SQ_OLD, deleted from queue.
 *   Info = SQ_NEWSEL -> Info = SQ_OLDSEL.
 */

int Undo;
{
    struct ks *SQDesc,*SQNext;
    struct prpty *PDesc;
    int Info;
    struct o *Pointer;

    /* Properties added have the Info field set to "new", so we can
     * remove them during Undo.
     */
    PDesc = Parameters.kpCellDesc->sPrptyList;
    if (Undo == True) {
        while (PDesc) {
            if (PDesc->prpty_Info &&
                !strcmp(PDesc->prpty_Info,"new")) {
                Parameters.kpCellDesc->sPrptyList =
                    PDesc->prpty_Succ;
                free(PDesc->prpty_Data);
                free(PDesc);
                PDesc = Parameters.kpCellDesc->sPrptyList;
                continue;
            }
            break;
        }
    }
    else {
        while (PDesc) {
            if (PDesc->prpty_Info &&
                !strcmp(PDesc->prpty_Info,"new")) {
                PDesc->prpty_Info = NULL;
                PDesc = PDesc->prpty_Succ;
                continue;
            }
            break;
        }
    }

    for (SQDesc = SelectQHead; SQDesc; SQDesc = SQNext) {
        SQNext = SQDesc->ksSucc;
        Pointer = SQDesc->ksPointer;
        Info = Pointer->oInfo;

        if (Info == SQ_GONE) {
            if (Undo == True)
                Pointer->oInfo = SQ_NEWSEL;
            else {
                SQDelete(Pointer);
                CDDelete(Parameters.kpCellDesc,Pointer);
            }
            continue;
        }
        if (Info == SQ_NEW) {
            SQDelete(Pointer);
            if (Undo == True) {
                Pointer->oInfo = SQ_GONE;
                CDDelete(Parameters.kpCellDesc,Pointer);
            }
            else
                Pointer->oInfo = SQ_OLD;
            continue;
        }
        if (Info == SQ_NEWSEL) {
            if (Undo == True) {
                SQDelete(Pointer);
                Pointer->oInfo = SQ_GONE;
                CDDelete(Parameters.kpCellDesc,Pointer);
            }
            else
                Pointer->oInfo = SQ_OLDSEL;
        }
    }
    if (Undo == False)
        sq_delete_dups();
}


void
SQDesel(Types)

/* Undo a selection operation. */

/* Info = SQ_OLDSEL deleted from queue, and duplicates set to Info = SQ_NEW.
 * Info = SQ_NEWSEL -> Info = SQ_NEW.
 * Ignores objects with type not listed in Types.
 */

char *Types;
{
    struct ks *SQDesc, *SQNext;
    struct o *Pointer;
    int Info;
    char Type;

    for (SQDesc = SelectQHead; SQDesc; SQDesc = SQNext) {
        SQNext = SQDesc->ksSucc;
        Type = SQDesc->ksPointer->oType;
        if (Types And !strchr(Types,Type)) continue;
        Info = SQDesc->ksPointer->oInfo;

        /* Have to be careful here.  If selected object is already
         * in queue have to reset Info of second entry to SQ_NEW.
         */

        if (Info == SQ_OLDSEL) {
            Pointer = SQDesc->ksPointer;
            Pointer->oInfo = SQ_OLD;
            SQDelete(Pointer);
            sq_set_NEW(Pointer);
            continue;
        }
        if (Info == SQ_NEWSEL)
            SQDesc->ksPointer->oInfo = SQ_NEW;
    }
}


void
SQShow()

/* Show selected objects by highlighting their BBs. */
{
    struct ks *SQDesc;
    int Info;

    if (Not Parameters.kpEnableSelectQRedisplay) return;
    for (SQDesc = SelectQHead; SQDesc; SQDesc = SQDesc->ksSucc) {
        Info = SQDesc->ksPointer->oInfo;
        /* Test for user interrupt */
        if (Parameters.kpSIGINTERRUPT) {
            RedisplayAfterInterrupt();
            return;
        }
        if (Info == SQ_OLDSEL || Info == SQ_NEWSEL ||
            (Info > 10 && Info <= 255)) {
            /* Show Selected Objects */
            sq_display_selected(SQDesc->ksPointer);
        }
    }
}


static void
sq_set_NEW(Pointer)

/* If object is in queue, set Info to SQ_NEW. */
struct o *Pointer;
{
    struct ks *SQDesc;
    int Info;

    for (SQDesc = SelectQHead; SQDesc; SQDesc = SQDesc->ksSucc) {
        if (SQDesc->ksPointer == Pointer) {
            SQDesc->ksPointer->oInfo = SQ_NEW;
            return;
        }
    }
}


static void
sq_delete_dups()

/* Delete duplicate entries in selection queue. */
{
    struct ks *SQDesc,*SQDesc1,*SQNext;
    int Info;

    for (SQDesc = SelectQHead; SQDesc; SQDesc = SQNext) {
        SQNext = SQDesc->ksSucc;
        Info = SQDesc->ksPointer->oInfo;
        for (SQDesc1 = SQDesc->ksSucc; SQDesc1; SQDesc1 = SQDesc1->ksSucc)
            if (SQDesc->ksPointer == SQDesc1->ksPointer) {
                SQDelete(SQDesc->ksPointer);
                /* SQDelete sets Info to SQ_OLD, have to undo this */
                SQDesc1->ksPointer->oInfo = Info;
                break;
            }
    }
}


static void
sq_display_selected(Pointer)

struct o *Pointer;
{
    int Layer;
    struct p *Path;
    long Width;
    char OldRD;
    struct ka BB;

    if (Pointer->oType == CDWIRE) {
        CDWire(Pointer,&Layer,&Width,&Path);
        ShowWire(HighlightingColor,Width,Path);
        return;
    }
    if (Pointer->oType == CDSYMBOLCALL) {
        CDStatusInt = CDBB(Parameters.kpCellDesc,Pointer,
            &BB.kaLeft,&BB.kaBottom,&BB.kaRight,&BB.kaTop);
        ShowEmptyBox(HighlightingColor,&BB);
        return;
    }
    if (Pointer->oType == CDLABEL) {

        /* BB of labels must be special-cased.  Can't use CDBB. */

        OldRD = Parameters.kpRedisplayControl;
        if (OldRD != FINEVIEWPORTONLY) {
            Parameters.kpRedisplayControl = COARSEVIEWPORTONLY;
            BBLabel(View->kvCoarseWindow,Pointer,&BB);
            ShowEmptyBox(HighlightingColor,&BB);
        }
        if (OldRD != COARSEVIEWPORTONLY) {
            Parameters.kpRedisplayControl = FINEVIEWPORTONLY;
            BBLabel(View->kvFineWindow,Pointer,&BB);
            ShowEmptyBox(HighlightingColor,&BB);
        }
        Parameters.kpRedisplayControl = OldRD;
        return;
    }
    if (Pointer->oType == CDPOLYGON) {
        CDPolygon(Pointer,&Layer,&Path);
        ShowPath(HighlightingColor,Path,True);
        return;
    }
    if (Pointer->oType == CDBOX) {
        CDStatusInt = CDBB(Parameters.kpCellDesc,Pointer,
            &BB.kaLeft,&BB.kaBottom,&BB.kaRight,&BB.kaTop);
        ShowEmptyBox(HighlightingColor,&BB);
        return;
    }
}


long *
InPath(Delta,Path,X,Y)

/* Is (X,Y) on the path described by <Path>?
 * If yes, return a pointer to x,y that are exactly in path.
 */
int Delta;
struct p *Path;
long X,Y;
{
    struct p *Pair;
    struct ka BB;
    double x1,x2,y1,y2,d0,d1,d2,d3,w;
    static long xy[2];

    if (Delta < 10) Delta = 10;

    if (Path == NULL) return (False);
    for (Pair = Path; Pair->pSucc != NULL; Pair = Pair->pSucc) {

        if (Pair->pX < Pair->pSucc->pX) {
            BB.kaLeft = Pair->pX;
            BB.kaRight = Pair->pSucc->pX;
        }
        else {
            BB.kaRight = Pair->pX;
            BB.kaLeft = Pair->pSucc->pX;
        }
        if (Pair->pY < Pair->pSucc->pY) {
            BB.kaBottom = Pair->pY;
            BB.kaTop = Pair->pSucc->pY;
        }
        else {
            BB.kaBottom = Pair->pSucc->pY;
            BB.kaTop = Pair->pY;
        }
        OversizeBox(&BB,Delta);
        if (!InBox(X,Y,&BB)) continue;

        x1 = Pair->pX - Pair->pSucc->pX;
        y1 = Pair->pY - Pair->pSucc->pY;
        d0 = x1*x1 + y1*y1;

        x1 = Pair->pX - X;
        y1 = Pair->pY - Y;
        d1 = x1*x1 + y1*y1;
        x2 = Pair->pSucc->pX - X;
        y2 = Pair->pSucc->pY - Y;
        d2 = x2*x2 + y2*y2;

        d3 = (d2 - d1)/(2*sqrt(d0));
        w = (d1+d2)/2 - d0/4 - d3*d3;

        if (w <= (long)Delta*Delta) {
            /* should be positive, fabs() just in case */
            d1 = sqrt(fabs(d1-w)/d0);
            xy[0] = Pair->pX + (Pair->pSucc->pX - Pair->pX)*d1;
            xy[1] = Pair->pY + (Pair->pSucc->pY - Pair->pY)*d1;
            return (xy);
        }
    }
    return (NULL);
}


static int
point_in_poly(Delta,Path,X,Y)

/* Return True if point is enclosed in polygon, or within Delta of a vertex.
 * Algorithm is to sum angle differences to reference point around
 * path.  If the reference point is inside, the sum is 2*PI, otherwise
 * the sum is zero.
 */
int Delta;
struct p *Path;
long X,Y;
{
    struct p *p;
    double Xp,Yp,R,Theta,ThetaLast,Sum,zz;

    Sum =  0;

    for (p = Path; p != NULL; p = p->pSucc) {

        Xp = p->pX - X;
        Yp = p->pY - Y;
        R = sqrt(Xp*Xp + Yp*Yp);
        if (R <= Delta) return (True);
        Theta = asin(Yp/R);
        if (Xp >= 0) {
            if (Yp < 0)
                Theta = 2*M_PI + Theta;
        }
        else
            Theta = M_PI - Theta;
        if (p != Path) {
            zz = (Theta - ThetaLast);
            if (zz > M_PI) zz -= 2*M_PI;
            if (zz < -M_PI) zz += 2*M_PI;
            Sum += zz;
        }
        ThetaLast = Theta;
    }
    if (fabs(Sum) >= 1.99*M_PI) return (True);
    return (False);
}


static int
overlap_path(Path,BB)

/* return True if the path intersects the BB */
struct p *Path;
struct ka *BB;
{
    struct ka Line;

    Line.kaLeft = Path->pX;
    Line.kaBottom = Path->pY;
    Path = Path->pSucc;
    for (; Path != NULL; Path = Path->pSucc) {
        Line.kaRight = Path->pX;
        Line.kaTop = Path->pY;
        if (overlap_line(&Line,BB)) return (True);
        Line.kaLeft = Line.kaRight;
        Line.kaBottom = Line.kaTop;
    }
    return (False);
}


static int
overlap_line(Line,BB)

/* return True if Line intersects BB */
struct ka *Line,*BB;
{
    struct ka LBB;

    LBB.kaLeft = BB->kaLeft;
    LBB.kaRight = BB->kaLeft;
    LBB.kaBottom = BB->kaBottom;
    LBB.kaTop = BB->kaTop;
    if (cross_line(Line,&LBB)) return (True);

    LBB.kaRight = BB->kaRight;
    LBB.kaBottom = BB->kaTop;
    if (cross_line(Line,&LBB)) return (True);

    LBB.kaLeft = BB->kaRight;
    LBB.kaBottom = BB->kaBottom;
    if (cross_line(Line,&LBB)) return (True);

    LBB.kaLeft = BB->kaLeft;
    LBB.kaTop = BB->kaBottom;
    if (cross_line(Line,&LBB)) return (True);

    return (False);
}


static int
cross_line(Line,BB)

/* return True if line segments stored as diagonal of BB, Line
 * intersect.  The line in BB is Manhattan.
 */
struct ka *Line,*BB;
{
    struct ka LineBB,MBB;
    long X,Y;

    MBB = *BB;
    if (MBB.kaTop < MBB.kaBottom)
        SwapInts(MBB.kaTop,MBB.kaBottom);
    if (MBB.kaRight < MBB.kaLeft)
        SwapInts(MBB.kaRight,MBB.kaLeft);
    LineBB = *Line;
    if (LineBB.kaTop < LineBB.kaBottom)
        SwapInts(LineBB.kaTop,LineBB.kaBottom);
    if (LineBB.kaRight < LineBB.kaLeft)
        SwapInts(LineBB.kaRight,LineBB.kaLeft);

    /* return False if BB's don't overlap */
    if (LineBB.kaLeft > MBB.kaRight ||
        LineBB.kaRight < MBB.kaLeft ||
        LineBB.kaBottom > MBB.kaTop ||
        LineBB.kaTop < MBB.kaBottom)
        return (False);

    /* if Line is Manhattan, return True */
    if (Line->kaLeft == Line->kaRight || Line->kaBottom == Line->kaTop)
        return (True);

    if (BB->kaBottom == BB->kaTop) {

        X = (BB->kaBottom - Line->kaBottom)*
            ((double)(Line->kaRight - Line->kaLeft)/
            (Line->kaTop - Line->kaBottom)) +
            Line->kaLeft;
        if (X < BB->kaLeft || X > BB->kaRight) return (False);
    }
    else {

        Y = (BB->kaLeft - Line->kaLeft)*
            ((double)(Line->kaTop - Line->kaBottom)/
            (Line->kaRight - Line->kaLeft))
            + Line->kaBottom;
        if (Y < BB->kaBottom || Y > BB->kaTop) return (False);
    }
    return (True);
}