Xw/Traversal.c

   1 /*************************************<+>*************************************
   2  *****************************************************************************
   3  **
   4  **   File:       Traversal.c
   5  **
   6  **   Project:     X Widgets
   7  **
   8  **   Description: Code to support a generalized traversal handler for
   9  **                subclasses of XwManager.
  10  **
  11  *****************************************************************************
  12  **
  13  **   Copyright (c) 1988 by Hewlett-Packard Company
  14  **   Copyright (c) 1988 by the Massachusetts Institute of Technology
  15  **
  16  **   Permission to use, copy, modify, and distribute this software
  17  **   and its documentation for any purpose and without fee is hereby
  18  **   granted, provided that the above copyright notice appear in all
  19  **   copies and that both that copyright notice and this permission
  20  **   notice appear in supporting documentation, and that the names of
  21  **   Hewlett-Packard or  M.I.T.  not be used in advertising or publicity
  22  **   pertaining to distribution of the software without specific, written
  23  **   prior permission.
  24  **
  25  *****************************************************************************
  26  *************************************<+>*************************************/
  27
  28 #include <X11/IntrinsicP.h>
  29 #include <X11/Intrinsic.h>
  30 #include <X11/Xutil.h>
  31 #include <X11/StringDefs.h>
  32 #include <Xw/Xw.h>
  33 #include <Xw/XwP.h>
  34 #include <stdlib.h>   /* abs */
  35
  36
  37 static int Overlap();
  38 static void MoveNext();
  39 static void MovePrev();
  40 static void MoveTraversal();
  41 static void Start();
  42 static void Home();
  43 static void TraverseToChild ();
  44 static void ClearKbdFocus();
  45 static Widget RightCheck();
  46 static Widget LeftCheck();
  47 static Widget UpCheck();
  48 static Widget DownCheck();
  49 static Widget ValidChoice();
  50 static Boolean _XwManagerIsTraversable();
  51
  52
  53 /* Structures used to maintain the traversal checklist */
  54
  55 typedef enum {
  56    XwVERIFY_ONLY,
  57    XwADD_TO_CHOSEN_LIST,
  58    XwADD_TO_ACTIVE_LIST,
  59    XwCLEAR_ACTIVE_LIST
  60 } XwValidChoiceActions;
  61
  62 typedef enum {
  63    XwNONE,
  64    XwCHOSEN,
  65    XwACTIVE
  66 } XwEntryType;
  67
  68 typedef struct {
  69    Widget widget;
  70    XwEntryType type;
  71 } _XwCheckListEntry;
  72
  73
  74 /*
  75  * Globals used to maintain a list of those widgets already checked
  76  * during a traversal request.
  77  */
  78
  79 _XwCheckListEntry * _XwCheckList = NULL;
  80 int                 _XwCheckListSize = 0;
  81 int                 _XwCheckListIndex = 0;
  82
  83 /*
  84
  85 A manager's traversal handler will be invoked with:
  86
  87     Upper Left Point:  (x1, y1)
  88     Lower Right Point: (x2, y2)
  89     Direction:         XwTRAVERSE_CURRENT
  90                        XwTRAVERSE_LEFT
  91                        XwTRAVERSE_RIGHT
  92                        XwTRAVERSE_UP
  93                        XwTRAVERSE_DOWN
  94                        XwTRAVERSE_NEXT
  95                        XwTRAVERSE_PREV
  96                        XwTRAVERSE_HOME
  97                        XwTRAVERSE_NEXT_TOP
  98
  99
 100
 101
 102 A manager has an active child which may be NULL.  Widgets under
 103 consideration to receive the keyboard focus are called candidate widgets.
 104 In order to be a candidate, a widget must be traversable.  This means
 105 that it must be:
 106
 107       1) a subclass of primitive, and
 108               sensitive (it and its ancestor)
 109               visible
 110               managed
 111               have its "mapped_when_managed" flag set to TRUE, and
 112               traversal_type=XwHIGHLIGHT_TRAVERSAL
 113
 114       2) a composite with a traversable primitive
 115
 116
 117
 118
 119 Step 1:  See if the manager contains any children which are traversable.
 120          If not, set the "active_child" to NULL and
 121             if the parent of this manager is a subclass of manager AND
 122             that parent has traversal on, then invoke its traversal
 123             handling procedure directly, otherwise return focus to
 124             the root.
 125
 126             <<<<NOTE TEST WHETHER THIS IS THE CORRECT THING TO DO, WE
 127                 MAY NEED 2 DIFFERENT ACTIONS DEPENDING ON THE FOCUS MODEL
 128                 IN EFFECT.>>>>
 129
 130          If we do have someone who can accept the focus, then continue.
 131
 132
 133 Step 2:  The caller of this procedure supplies POINT1, POINT2 and the
 134          DIRECTION.  Pass control to the specified direction handler.
 135
 136 */
 137
 138
 139
 140 /**********************************/
 141 /* Globals for Traversal Routines */
 142 /**********************************/
 143 static int widget_type;
 144 static   XwManagerWidget parent;
 145 static   Boolean parent_is_manager;
 146
 147 void mgr_traversal (mgr, ul, lr, direction)
 148
 149    XwManagerWidget mgr;
 150    XPoint ul, lr;
 151    int direction;
 152
 153 {
 154    XPoint newUl, newLr;
 155
 156    parent = (XwManagerWidget)mgr->core.parent;
 157    parent_is_manager = XtIsSubclass((Widget)parent,XwmanagerWidgetClass);
 158
 159    if (direction == XwTRAVERSE_NEXT_TOP)
 160      {
 161        if (parent_is_manager)
 162        {
 163             newUl.x = newUl.y = newLr.x = newLr.y = 0;
 164
 165             (*(((XwManagerWidgetClass)(parent->core.widget_class)) ->
 166                   manager_class.traversal_handler))
 167                      ((Widget)parent, newUl, newLr, direction);
 168        }
 169        else
 170        {
 171             XtCallCallbacks((Widget)mgr, XtNnextTop, NULL);
 172        }
 173        return;
 174      }
 175
 176
 177    if ((_XwFindTraversablePrim (mgr) == FALSE) ||
 178        (!_XwManagerIsTraversable(mgr)))
 179       {
 180        if (mgr->manager.active_child != NULL)
 181               mgr->manager.active_child = (Widget)NULL;
 182
 183
 184          if (parent_is_manager && parent->manager.traversal_on)
 185          {
 186                newUl.x = ul.x + mgr->core.x;
 187                newUl.y = ul.y + mgr->core.y;
 188                newLr.x = lr.x + mgr->core.x;
 189                newLr.y = lr.y + mgr->core.y;
 190                (*(((XwManagerWidgetClass)(parent->core.widget_class)) ->
 191                   manager_class.traversal_handler))
 192                      ((Widget)parent, newUl, newLr, direction);
 193          }
 194          else
 195             ClearKbdFocus((Widget) mgr);
 196          return;
 197       }
 198
 199    /************************************
 200     *
 201     * THERE IS A CHILD TO TRAVERSE TO,
 202     * DETERMINE DIRECTION & DO TRAVERSAL
 203     *
 204     ************************************/
 205     switch(direction)
 206        {
 207         case XwTRAVERSE_NEXT:
 208           MoveNext((XwManagerWidget)mgr,ul, lr, direction); return;
 209         case XwTRAVERSE_PREV:
 210           MovePrev((XwManagerWidget)mgr,ul, lr, direction); return;
 211         case XwTRAVERSE_DOWN:
 212         case XwTRAVERSE_UP:
 213         case XwTRAVERSE_RIGHT:
 214         case XwTRAVERSE_LEFT:
 215           MoveTraversal((XwManagerWidget)mgr,ul, lr, direction); return;
 216         case XwTRAVERSE_CURRENT:
 217           Start((XwManagerWidget)mgr, ul, lr ,direction);  return;
 218         case XwTRAVERSE_HOME:
 219           Home((XwManagerWidget)mgr, ul, lr ,direction);  return;
 220        }
 221 }
 222
 223 /*
 224
 225 DIRECTION = RIGHT  (All other directions are just variations of this)
 226 =================
 227
 228 Step 1) Find the widget to the right of the active child.
 229
 230 If widget A is the current active child and its upper left and lower right
 231 points are defined by (x1,y1) and (x2,y2) respectively; and widget B is
 232 a candidate widget whose upper left and lower right points are defined by
 233 (x1',y1') and (x2',y2').  Then widget B is to the right of widget A
 234
 235              IFF  ((x1 < x1') OR (if (x1 = x1') then (x2' > x2))
 236                   AND (y1 <= y2') AND (y2 >= y1')
 237
 238 If there is more than 1 candidate then choose the candidate with the
 239 smallest value for:
 240
 241              (x1' - x1)
 242
 243 If 2 or more candidates have the same value for (x1'-x1) then choose the
 244 candidate with the smallest value for:
 245
 246              |(x2' - x2)|
 247
 248 If 2 or more candidates have the same value for |(x2'-x2)| then choose
 249 the candidate with the largest overlap of widget A along its y dimension:
 250
 251
 252          if (y2' >= y2)
 253            then
 254               if (y1' <= y1)
 255                 then
 256                    overlap = height of active child
 257                 else
 258                    overlap = y2 - y1'
 259            else
 260               if (y1' <= y1)
 261                then
 262                   overlap = y2' - y1
 263                else
 264                   overlap = height of candidate
 265
 266 If 2 or more candidates have the same overlap then choose the widget with
 267 the smallest value for y1'.
 268
 269 If 2 or more candidates have the same value for y1' then choose the widget with
 270 the smallest value for y2'.
 271
 272 It should not be possible for 2 candidates to get this far since it would
 273 mean that one exactly overlaps the other, which should mean that the
 274 visibility flag of the obscured widget should be FALSE (thus making it
 275 un-traversable), however, if we do get this far, arbitrarily choose the
 276 first candidate.
 277
 278
 279 Step 2) If no widget is to the right of the active child then:
 280
 281     if widget A's grandparent is a subclass of XwManager
 282         then
 283            -set manager's active child field to NULL
 284            -invoke grandparent's traversal handler with:
 285
 286               Upper Left Point: x1=x1+parent's x coordinate
 287                                 y1=y1+parent's y coordinate
 288
 289
 290               Lower Right Point: x2=x2+parent's x coordinate
 291                                  y2=y2+parent's y coordinate
 292
 293               Direction = XwTRAVERSE_RIGHT
 294
 295
 296
 297      if widget A's grandparent is NOT a subclass of XwManager
 298         then
 299           -set manager's active child field to NULL
 300           -invoke parent's traversal handler with:
 301
 302                Upper Left Point: x1=0, y1=y1;
 303
 304                Lower Right Point: x2=0, y2=y2;
 305
 306                Direction = XwTRAVERSE_RIGHT
 307
 308
 309 Step 3) If a candidate has been chosen, then set it as the active child of
 310         its parent and:
 311
 312           if it is a subclass of XwPrimitive
 313             then
 314               -give it keyboard focus using XSetInputFocus function.
 315
 316
 317             else (its a manager subclass)
 318               -invoke its traversal handler with:
 319
 320                    Upper Left Point: x1=x1 - x1';  y1=y1 - y1'
 321
 322                    Lower Right Point: x2=x2 - x2'; y2=y2 - y2'
 323
 324                    Direction = XwTRAVERSE_RIGHT
 325
 326 */
 327
 328 static void MoveTraversal (mw, ul, lr, direction)
 329
 330   XwManagerWidget mw;
 331   XPoint ul, lr;
 332   int direction;
 333 {
 334   Widget candidate, chosen;
 335   int chosen_widget_type;
 336   int i=(-1);
 337   XPoint cand_ul, cand_lr;
 338
 339   chosen = NULL;
 340
 341   while (++i < mw->composite.num_children)
 342   {
 343       candidate = mw->composite.children[i];
 344       if ((candidate != mw->manager.active_child) &&
 345               XwTestTraversability(candidate, &widget_type))
 346       {
 347          cand_ul.x = candidate->core.x;
 348          cand_ul.y = candidate->core.y;
 349          cand_lr.x = candidate->core.x + candidate->core.width +
 350                      (candidate->core.border_width << 1) - 1;
 351          cand_lr.y = candidate->core.y + candidate->core.height +
 352                      (candidate->core.border_width << 1) - 1;
 353
 354          switch (direction)
 355          {
 356             case XwTRAVERSE_RIGHT:
 357                chosen=RightCheck (chosen, ul, lr, candidate, cand_ul, cand_lr);
 358                break;
 359
 360             case XwTRAVERSE_LEFT:
 361                chosen = LeftCheck (chosen, ul, lr, candidate, cand_ul, cand_lr);
 362                break;
 363
 364             case XwTRAVERSE_UP:
 365                chosen = UpCheck (chosen, ul, lr, candidate, cand_ul, cand_lr);
 366                break;
 367
 368             case XwTRAVERSE_DOWN:
 369                chosen = DownCheck (chosen, ul, lr, candidate, cand_ul, cand_lr);
 370                break;
 371
 372          }
 373       }
 374
 375       if (chosen == candidate) chosen_widget_type = widget_type;
 376    }
 377
 378    if (chosen == NULL)  /* no widget in specified direction! */
 379    {
 380       /*
 381        * Since our parent is a manager, see if there is another sibling
 382        * of ours which can be traversed to.
 383        */
 384       mw->manager.active_child = NULL;
 385       if (parent_is_manager)  /* really grandparent of active child */
 386       {
 387          /* Add ourselves to the active list */
 388          ValidChoice (mw, mw, XwADD_TO_ACTIVE_LIST);
 389
 390          ul.x +=  mw->core.x;
 391          ul.y +=  mw->core.y;
 392          lr.x +=  mw->core.x;
 393          lr.y +=  mw->core.y;
 394          (*(((XwManagerWidgetClass)(parent->core.widget_class)) ->
 395            manager_class.traversal_handler))
 396             ((Widget)parent, ul, lr, direction);
 397       }
 398       else
 399       {
 400          /* Wrap to opposite edge */
 401
 402          /* Clear the active traversal list */
 403          ValidChoice (NULL, NULL, XwCLEAR_ACTIVE_LIST);
 404
 405          switch (direction)
 406          {
 407             case XwTRAVERSE_RIGHT:
 408             {
 409                ul.x = -10000;
 410                lr.x = -10000;
 411                break;
 412             }
 413
 414             case XwTRAVERSE_LEFT:
 415             {
 416                ul.x = mw->core.width + (mw->core.border_width << 1);
 417                lr.x =  mw->core.width + (mw->core.border_width << 1);
 418                break;
 419             }
 420
 421             case XwTRAVERSE_UP:
 422             {
 423                ul.y = mw->core.height + (mw->core.border_width << 1);
 424                lr.y =  mw->core.height + (mw->core.border_width << 1);
 425                break;
 426             }
 427
 428             case XwTRAVERSE_DOWN:
 429             {
 430                ul.y = -10000;
 431                lr.y = -10000;
 432                break;
 433             }
 434          }
 435
 436          (*(((XwManagerWidgetClass)(mw->core.widget_class)) ->
 437             manager_class.traversal_handler))
 438               ((Widget)mw, ul, lr, direction);
 439       }
 440    }
 441    else
 442    {
 443       ValidChoice(chosen, chosen, XwADD_TO_CHOSEN_LIST);
 444       TraverseToChild(mw, chosen, ul, lr, direction);
 445    }
 446 }
 447
 448
 449
 450 static void Start (mw, ul, lr, direction)
 451   XwManagerWidget mw;
 452   XPoint ul, lr;
 453   int direction;
 454 {
 455   Widget candidate, chosen;
 456   int i=0;
 457
 458    chosen = NULL;
 459
 460   /* To prevent endless recursion, see if the child has already been checked */
 461   if ((mw->manager.active_child != NULL) &&
 462       (ValidChoice(NULL, mw->manager.active_child, XwVERIFY_ONLY)))
 463     {
 464       if (XwTestTraversability(mw->manager.active_child, &widget_type))
 465       {
 466          ValidChoice(chosen, chosen, XwADD_TO_CHOSEN_LIST);
 467          TraverseToChild (mw, mw->manager.active_child, ul, lr, direction);
 468       }
 469     }
 470    else
 471      {
 472         while (i < mw->composite.num_children)
 473           {
 474             candidate = mw->composite.children[i];
 475             if (XwTestTraversability(candidate, &widget_type))
 476               {
 477                 if (chosen==NULL)
 478                    chosen = ValidChoice(chosen, candidate, XwVERIFY_ONLY);
 479                 else
 480
 481                   {
 482                     if ((candidate->core.x+candidate->core.y) <
 483                               (chosen->core.x+chosen->core.y))
 484                             chosen = ValidChoice(chosen, candidate,
 485                                                  XwVERIFY_ONLY);
 486
 487                   }
 488               }
 489           i++;
 490           }
 491
 492       ValidChoice(chosen, chosen, XwADD_TO_CHOSEN_LIST);
 493       TraverseToChild(mw, chosen, ul, lr, direction);
 494
 495      }
 496 }
 497
 498
 499
 500 /* We are guaranteed that there is a child to traverse to! */
 501
 502 static void MoveNext (mw, ul, lr, direction)
 503   XwManagerWidget mw;
 504   XPoint ul, lr;
 505   int direction;
 506 {
 507   int i=0;
 508
 509    parent = (XwManagerWidget)mw->core.parent;
 510    parent_is_manager = XtIsSubclass((Widget)parent,XwmanagerWidgetClass);
 511
 512   if (mw->manager.active_child != NULL)
 513     {
 514       ul.x = (mw->manager.active_child)->core.x;
 515       ul.y = (mw->manager.active_child)->core.y;
 516       lr.x = ul.x + (mw->manager.active_child)->core.width +
 517              ((mw->manager.active_child)->core.border_width << 1) - 1;
 518       lr.y = ul.y + (mw->manager.active_child)->core.height +
 519              ((mw->manager.active_child)->core.border_width << 1) - 1;
 520
 521       /* FIND INDEX OF CURRENTLY ACTIVE CHILD */
 522       while ((mw->composite.children[i] != mw->manager.active_child) &&
 523                (i < mw->composite.num_children))i++;
 524     }
 525    else
 526      /* START LOOKING AT START OF LIST + 1 (TO ALLOW FOR 1ST DECREMENT)
 527       * NOTE: THIS ALSO TAKES CARE OF THE DEGENERATE CASE WHEN THERE
 528       * ARE NO CHILDREN.  IN THIS CASE THE PARENT "MUST" BE A SUBCLASS
 529       * OF XWMANAGER OR WE WOULD NEVER HAVE GOTTEN HERE.
 530       */
 531      i = -1;
 532
 533    /*
 534     * IF WE'VE COME TO THE END OF THE WIDGET LIST AND THE PARENT
 535     * IS ALSO A SUBCLASS OF XWMANAGER, THEN INVOKE THE PARENT'S
 536     * TRAVERSAL HANDLER, OTHERWISE, WRAP THE COUNTER TO START LOOKING
 537     * AT THE LIST AGAIN.
 538     */
 539    if (++i >= mw->composite.num_children)
 540      {
 541       if (parent_is_manager)
 542         {
 543           mw->manager.active_child = NULL;
 544           (*(((XwManagerWidgetClass)(parent->core.widget_class)) ->
 545               manager_class.traversal_handler))
 546                      ((Widget)parent, ul, lr, direction);
 547           return;
 548          }
 549        else
 550          i=0;
 551        }
 552
 553    /* FIND NEXT TRAVERSABLE WIDGET --THERE MUST BE ONE! */
 554    while (! XwTestTraversability(mw->composite.children[i], &widget_type))
 555             if (++i >= mw->composite.num_children) i=0;
 556
 557    TraverseToChild(mw, mw->composite.children[i], ul, lr, direction);
 558 }
 559
 560
 561
 562
 563 /* We are guaranteed that there is a child to traverse to! */
 564
 565 static void MovePrev (mw, ul, lr, direction)
 566   XwManagerWidget mw;
 567   XPoint ul, lr;
 568   int direction;
 569 {
 570   int i;
 571
 572    parent = (XwManagerWidget)mw->core.parent;
 573    parent_is_manager = XtIsSubclass((Widget)parent,XwmanagerWidgetClass);
 574
 575    if (mw->manager.active_child != NULL)
 576     {
 577       ul.x = (mw->manager.active_child)->core.x;
 578       ul.y = (mw->manager.active_child)->core.y;
 579       lr.x = ul.x + (mw->manager.active_child)->core.width +
 580              ((mw->manager.active_child)->core.border_width << 1) - 1;
 581       lr.y = ul.y + (mw->manager.active_child)->core.height +
 582              ((mw->manager.active_child)->core.border_width << 1) - 1;
 583
 584       /* FIND INDEX OF CURRENTLY ACTIVE CHILD */
 585       i=mw->composite.num_children -1;
 586       while ((mw->composite.children[i] != mw->manager.active_child) &&
 587                (i > 0))i--;
 588     }
 589    else
 590      /* START LOOKING AT END OF LIST + 1 (TO ALLOW FOR 1ST DECREMENT)
 591       * NOTE: THIS ALSO TAKES CARE OF THE DEGENERATE CASE WHEN THERE
 592       * ARE NO CHILDREN.  IN THIS CASE THE PARENT "MUST" BE A SUBCLASS
 593       * OF XWMANAGER OR WE WOULD NEVER HAVE GOTTEN HERE.
 594       */
 595      i = mw->composite.num_children;
 596
 597
 598    /*
 599     * IF WE'VE COME TO THE END OF THE WIDGET LIST AND THE PARENT
 600     * IS ALSO A SUBCLASS OF XWMANAGER, THEN INVOKE THE PARENT'S
 601     * TRAVERSAL HANDLER, OTHERWISE, WRAP THE COUNTER TO START LOOKING
 602     * AT THE LIST AGAIN.
 603     */
 604    if (--i < 0)
 605      {
 606       if (parent_is_manager)
 607         {
 608           mw->manager.active_child = NULL;
 609           (*(((XwManagerWidgetClass)(parent->core.widget_class)) ->
 610               manager_class.traversal_handler))
 611                      ((Widget)parent, ul, lr, direction);
 612           return;
 613          }
 614        else
 615          i = (mw->composite.num_children)-1;
 616        }
 617
 618
 619    /* FIND NEXT TRAVERSABLE WIDGET --THERE MUST BE ONE! */
 620    while (! XwTestTraversability(mw->composite.children[i], &widget_type))
 621         if (--i < 0) i = (mw->composite.num_children)-1;
 622
 623    TraverseToChild (mw, mw->composite.children[i], ul, lr, direction);
 624 }
 625
 626
 627
 628
 629
 630
 631 static int Overlap (pt1, pt2, w)
 632   XPoint pt1, pt2;
 633   Widget w;
 634 {
 635   XPoint pt1_prime, pt2_prime;
 636
 637   pt1_prime.x = w->core.x;
 638   pt1_prime.y = w->core.y;
 639   pt2_prime.x = w->core.x + w->core.width + (w->core.border_width << 1) - 1;
 640   pt2_prime.y = w->core.y + w->core.height + (w->core.border_width << 1) - 1;
 641
 642   if (pt2_prime.y >= pt2.y)
 643   {
 644    if (pt1_prime.y <= pt1.y)
 645     return(pt2.y - pt1.y);
 646    else
 647     return(pt2.y - pt1_prime.y);
 648   }
 649   else
 650   {
 651    if (pt1_prime.y <= pt1.y)
 652     return(pt2_prime.y - pt1.y);
 653    else
 654     return(w->core.height);
 655   }
 656 }
 657
 658
 659 /* CALCULATE OVERLAP IN X DIRECTION */
 660 static int xOverlap (pt1, pt2, w)
 661   XPoint pt1, pt2;
 662   Widget w;
 663 {
 664   XPoint pt1_prime, pt2_prime;
 665
 666   pt1_prime.x = w->core.x;
 667   pt1_prime.y = w->core.y;
 668   pt2_prime.x = w->core.x + w->core.width + (w->core.border_width << 1) - 1;
 669   pt2_prime.y = w->core.y + w->core.height + (w->core.border_width << 1) - 1;
 670
 671   if (pt2_prime.x >= pt2.x)
 672   {
 673    if (pt1_prime.x <= pt1.x)
 674     return(pt2.x - pt1.x);
 675    else
 676     return(pt2.x - pt1_prime.x);
 677   }
 678   else
 679   {
 680    if (pt1_prime.x <= pt1.x)
 681     return(pt2_prime.x - pt1.x);
 682    else
 683     return(w->core.width);
 684   }
 685 }
 686
 687
 688 /*
 689  * HOME:  If I get called there is NO guarantee that there is something
 690  *        which is traversable.  This is due to the way that X generates
 691  *        its visiblity events; the manager is notified before its children.
 692  *        Thus, the manager may still think it has traversable children,
 693  *        when in fact it doesn't.  That is why we must have a special
 694  *        check to see that a child really was chosen.
 695  */
 696
 697 static void Home (mw, ul, lr, direction)
 698   XwManagerWidget mw;
 699   XPoint ul, lr;
 700   int direction;
 701 {
 702   Widget candidate, chosen;
 703   int chosen_widget_type;
 704   int i=(-1);
 705
 706    chosen = NULL;
 707
 708  /*
 709     search thru list of children to find child which is closest to
 710     origin and which is traversable.
 711  */
 712   while (++i < mw->composite.num_children)
 713    {
 714      candidate = mw->composite.children[i];
 715      if (XwTestTraversability(candidate, &widget_type))
 716       {
 717         if (chosen==NULL)
 718            chosen = ValidChoice(chosen, candidate, XwVERIFY_ONLY);
 719         else
 720          {
 721            if ((candidate->core.x+candidate->core.y) <
 722                 (chosen->core.x+chosen->core.y))
 723                    chosen = ValidChoice(chosen, candidate, XwVERIFY_ONLY);
 724           }
 725        }
 726       if (chosen == candidate) chosen_widget_type = widget_type;
 727      }
 728
 729    /*
 730     * If the closest to home widget is NOT the current active child then
 731     * make it the active child.  Otherwise, try and go up a level.
 732     */
 733
 734    if (mw->manager.active_child != chosen)
 735        {
 736           mw->manager.active_child=chosen;
 737           ValidChoice(chosen, chosen, XwADD_TO_CHOSEN_LIST);
 738
 739           if (chosen_widget_type == XwPRIMITIVE)
 740
 741             TraverseToChild(mw, chosen, ul, lr, direction);
 742
 743           else
 744                (*(((XwManagerWidgetClass)(chosen->core.widget_class)) ->
 745                   manager_class.traversal_handler))
 746                      (chosen, ul, lr, direction);
 747
 748        }
 749        else   /* WE ARE ALREADY HOMED IN THIS MANAGER, GO UP */
 750          {
 751            if (parent_is_manager)  /* really grandparent of active child */
 752              {
 753                mw->manager.active_child = NULL;
 754                (*(((XwManagerWidgetClass)(parent->core.widget_class)) ->
 755                   manager_class.traversal_handler))
 756                      ((Widget)parent, ul, lr, direction);
 757              }
 758
 759            /*  If our parent is not a manager, then we are already
 760                as HOME as we are going to get, so do nothing. */
 761          }
 762 }
 763
 764
 765
 766 static void TraverseToChild (mw, chosen, ul, lr, direction)
 767   XwManagerWidget mw;
 768   Widget chosen;
 769   XPoint ul, lr;
 770   int direction;
 771
 772 {
 773    Widget topmost_manager= (Widget) mw;
 774
 775    mw->manager.active_child = chosen;
 776    if (XtIsSubclass(chosen, XwprimitiveWidgetClass))
 777      {
 778         while ((topmost_manager->core.parent != NULL) &&
 779                XtIsSubclass((Widget)(topmost_manager->core.parent),
 780                  XwmanagerWidgetClass))
 781            topmost_manager = topmost_manager->core.parent;
 782
 783         XtSetKeyboardFocus(topmost_manager, chosen);
 784       }
 785    else
 786         {
 787                ul.x -= chosen->core.x;
 788                ul.y -= chosen->core.y;
 789                lr.x -= chosen->core.x;
 790                lr.y -= chosen->core.y;
 791                (*(((XwManagerWidgetClass)(chosen->core.widget_class)) ->
 792                   manager_class.traversal_handler))
 793                      (chosen, ul, lr, direction);
 794         }
 795
 796 }
 797
 798
 799 \f
 800 /*************************************<->*************************************
 801  *
 802  *  XwMoveFocus(w)
 803  *
 804  *   Description:
 805  *   -----------
 806  *    Useful when an application has created multiple top level
 807  *    hierarchies of widgets, is using keyboard traversal and
 808  *    wishes to move between them.
 809  *
 810  *
 811  *   Inputs:  w  = widget which is the new top level widget.
 812  *   ------
 813  *
 814  *************************************<->***********************************/
 815
 816
 817 void XwMoveFocus(w)
 818
 819  Widget w;
 820
 821 {
 822  /* MOVE MOUSE INTO NEW WINDOW HIERARCHY */
 823   XWarpPointer(XtDisplay(w), None, XtWindow(w),0,0,0,0,1,1);
 824
 825  /* SET FOCUS HERE, SHOULD WORK FOR ALL FOCUS MODES */
 826  XSetInputFocus (XtDisplay(w), XtWindow(w), RevertToParent,
 827                  CurrentTime);
 828
 829
 830 }
 831
 832 static Widget RightCheck (chosen, ul, lr, candidate, cand_ul, cand_lr)
 833
 834    Widget chosen, candidate;
 835    XPoint ul, lr, cand_ul, cand_lr;
 836
 837 {
 838    if (((ul.x < cand_ul.x) || ((ul.x == cand_ul.x) && (lr.x < cand_lr.x))) &&
 839         (ul.y <= cand_lr.y) && (lr.y >= cand_ul.y))
 840    {
 841       if (chosen == NULL)
 842          chosen = ValidChoice(chosen, candidate, XwVERIFY_ONLY);
 843       else
 844       {
 845          if (chosen->core.x > cand_ul.x)
 846             chosen = ValidChoice(chosen, candidate, XwVERIFY_ONLY);
 847          else
 848             if (cand_ul.x == chosen->core.x)
 849             {
 850                if (abs(cand_lr.x - lr.x) <
 851                    abs((chosen->core.x+chosen->core.width +
 852                          (chosen->core.border_width << 1))-lr.x))
 853                      chosen = ValidChoice(chosen, candidate, XwVERIFY_ONLY);
 854                else
 855                   if (abs(cand_lr.x - lr.x) ==
 856                       abs((chosen->core.x+chosen->core.width+
 857                            (chosen->core.border_width << 1))-lr.x))
 858
 859                      if (Overlap(ul, lr, candidate) > Overlap(ul, lr, chosen))
 860                         chosen = ValidChoice(chosen, candidate, XwVERIFY_ONLY);
 861                      else
 862                      {
 863                         if (Overlap(ul,lr,candidate) == Overlap(ul,lr,chosen))
 864                            if (cand_ul.y < chosen->core.y)
 865                               chosen = ValidChoice(chosen, candidate,
 866                                                    XwVERIFY_ONLY);
 867                             else
 868                             {
 869                                 if (cand_ul.y == chosen->core.y)
 870                                    if (cand_lr.y < chosen->core.y +
 871                                        chosen->core.height +
 872                                        (chosen->core.border_width << 1))
 873                                            chosen = ValidChoice(chosen,
 874                                                                 candidate,
 875                                                               XwVERIFY_ONLY);
 876                              }
 877                      }
 878             }
 879       }
 880    }
 881    return (chosen);
 882 }
 883
 884
 885 static Widget LeftCheck (chosen, ul, lr, candidate, cand_ul, cand_lr)
 886
 887    Widget chosen, candidate;
 888    XPoint ul, lr, cand_ul, cand_lr;
 889
 890 {
 891    if (((cand_ul.x < ul.x) || ((cand_ul.x == ul.x) && (cand_lr.x < lr.x))) &&
 892        (ul.y <= cand_lr.y) && (lr.y >= cand_ul.y))
 893    {
 894       if (chosen == NULL)
 895          chosen = ValidChoice(chosen, candidate, XwVERIFY_ONLY);
 896       else
 897       {
 898          if (cand_ul.x > chosen->core.x)
 899               chosen = ValidChoice(chosen, candidate, XwVERIFY_ONLY);
 900          else
 901             if (cand_ul.x == chosen->core.x)
 902             {
 903                if (abs(cand_lr.x - lr.x) < abs(chosen->core.x+
 904                    chosen->core.width+(chosen->core.border_width<<1)-lr.x))
 905                   chosen = ValidChoice(chosen, candidate, XwVERIFY_ONLY);
 906                else
 907                   if (abs(cand_lr.x - lr.x) == abs(chosen->core.x+
 908                       chosen->core.width+(chosen->core.border_width<<1)-lr.x))
 909                      if (Overlap(ul, lr, candidate) > Overlap(ul, lr, chosen))
 910                         chosen = ValidChoice(chosen, candidate, XwVERIFY_ONLY);
 911                      else
 912                      {
 913                         if (Overlap(ul,lr,candidate) == Overlap(ul,lr,chosen))
 914                            if (cand_ul.y > chosen->core.y)
 915                               chosen = ValidChoice(chosen, candidate,
 916                                                    XwVERIFY_ONLY);
 917                            else
 918                            {
 919                               if (cand_ul.y == chosen->core.y)
 920                                  if (cand_lr.y >
 921                                      chosen->core.y + chosen->core.height +
 922                                      (chosen->core.border_width << 1))
 923                                        chosen = ValidChoice(chosen, candidate,
 924                                                             XwVERIFY_ONLY);
 925                            }
 926                       }
 927             }
 928       }
 929    }
 930    return (chosen);
 931 }
 932
 933
 934 static Widget UpCheck (chosen, ul, lr, candidate, cand_ul, cand_lr)
 935
 936    Widget chosen, candidate;
 937    XPoint ul, lr, cand_ul, cand_lr;
 938
 939 {
 940    if (((cand_ul.y < ul.y) || ((cand_ul.y == ul.y) && (cand_lr.y < lr.y))) &&
 941        (ul.x <= cand_lr.x) && (lr.x >= cand_ul.x))
 942    {
 943       if (chosen == NULL)
 944          chosen = ValidChoice(chosen, candidate, XwVERIFY_ONLY);
 945       else
 946       {
 947          if (cand_ul.y > chosen->core.y)
 948             chosen = ValidChoice(chosen, candidate, XwVERIFY_ONLY);
 949          else
 950             if (cand_ul.y == chosen->core.y)
 951             {
 952                if (abs(cand_lr.y - lr.y) < abs(chosen->core.y+
 953                    chosen->core.height+(chosen->core.border_width<<1)-lr.y))
 954                   chosen = ValidChoice(chosen, candidate, XwVERIFY_ONLY);
 955                else
 956                   if (abs(cand_lr.y - lr.y) == abs(chosen->core.y+
 957                       chosen->core.height+(chosen->core.border_width<<1)-lr.y))
 958                      if (xOverlap(ul, lr, candidate) > xOverlap(ul, lr, chosen))
 959                         chosen = ValidChoice(chosen, candidate, XwVERIFY_ONLY);
 960                      else
 961                      {
 962                         if (xOverlap(ul, lr, candidate) ==
 963                             xOverlap(ul, lr, chosen))
 964                            if (cand_ul.x > chosen->core.x)
 965                               chosen = ValidChoice(chosen, candidate,
 966                                                    XwVERIFY_ONLY);
 967                            else
 968                            {
 969                               if (cand_ul.x == chosen->core.x)
 970                                  if (cand_lr.x >
 971                                      chosen->core.x + chosen->core.width +
 972                                      (chosen->core.border_width << 1))
 973                                      chosen = ValidChoice(chosen,candidate,
 974                                                           XwVERIFY_ONLY);
 975                            }
 976                       }
 977             }
 978       }
 979    }
 980    return (chosen);
 981 }
 982
 983
 984 static Widget DownCheck (chosen, ul, lr, candidate, cand_ul, cand_lr)
 985
 986    Widget chosen, candidate;
 987    XPoint ul, lr, cand_ul, cand_lr;
 988
 989 {
 990    if (((ul.y < cand_ul.y) || ((ul.y == cand_ul.y) && (lr.y < cand_lr.y))) &&
 991        (ul.x <= cand_lr.x) && (lr.x >= cand_ul.x))
 992    {
 993       if (chosen == NULL)
 994          chosen = ValidChoice(chosen, candidate, XwVERIFY_ONLY);
 995       else
 996       {
 997          if (chosen->core.y > cand_ul.y)
 998             chosen = ValidChoice(chosen, candidate, XwVERIFY_ONLY);
 999          else
1000             if (cand_ul.y == chosen->core.y)
1001             {
1002                if (abs(cand_lr.y - lr.y) <
1003                    abs((chosen->core.y+chosen->core.height+
1004                       (chosen->core.border_width << 1))-lr.y))
1005                       chosen = ValidChoice(chosen, candidate, XwVERIFY_ONLY);
1006                else
1007                   if (abs(cand_lr.y - lr.y) ==
1008                       abs((chosen->core.y+chosen->core.height+
1009                       (chosen->core.border_width << 1))-lr.y))
1010
1011                      if (xOverlap(ul, lr, candidate) > xOverlap(ul, lr, chosen))
1012                         chosen = ValidChoice(chosen, candidate, XwVERIFY_ONLY);
1013                      else
1014                      {
1015                         if (xOverlap(ul, lr, candidate) ==
1016                             xOverlap(ul, lr, chosen))
1017                            if (cand_ul.x < chosen->core.x)
1018                               chosen = ValidChoice(chosen, candidate,
1019                                                    XwVERIFY_ONLY);
1020                            else
1021                            {
1022                               if (cand_ul.x == chosen->core.x)
1023                                  if (cand_lr.x <
1024                                      chosen->core.x + chosen->core.width +
1025                                     (chosen->core.border_width << 1))
1026                                      chosen = ValidChoice(chosen, candidate,
1027                                                           XwVERIFY_ONLY);
1028                            }
1029                      }
1030             }
1031       }
1032
1033    }
1034    return (chosen);
1035 }
1036
1037 /*
1038  * To prevent the traversal mechanism from getting into an infinite
1039  * recursion, we need to keep a list of those widgets already checked
1040  * during a given traversal request.  If a candidate has already been
1041  * checked once, we don't want to give it a second chance.  This is
1042  * normally a problem only when a traversal request causes the search
1043  * to wrap to the opposite edge.
1044  *
1045  * There are two types of entries maintained on the list: active entries
1046  * and chosen entries.  An entry is a chosen entry if its parent has
1047  * determined that the entry can possible accept the traversal request,
1048  * and has thus chosen it to in turn check its children to see if they
1049  * can accept the traversal.  An entry is an active entry if it is part
1050  * of the current traversal path, but it does not have any children which
1051  * can currently accept the traversal request; a widget is added to this
1052  * list only if it is not already on the chosen list, AND it is passing
1053  * the traversal request up to its parent.
1054  *
1055  * The active list prevents any of the widgets in the current traversal
1056  * path from being rechecked by their parent, once they have already
1057  * decided they can't accept the traversal request, until the upper most
1058  * manager decides to wrap at an edge and start looking again; at this
1059  * point, all active entries are cleared from the list, so that they can
1060  * have a chance to regain the traversal if no other widget can.
1061  *
1062  * If an entry is marked as being on the
1063  * active list, and then a request comes to place it on the chosen list,
1064  * then the move will occur.  If, however, a widget is on the chosen list,
1065  * and it asks to move to the active list, this will be denied, since we
1066  * don't want this widget to have the chance of being chosen again.  An
1067  * entry on the active list has not yet been chosen, it mearly was part of
1068  * the original active child list.
1069  */
1070
1071 static Widget ValidChoice (chosen, candidate, action)
1072
1073    Widget chosen, candidate;
1074    XwValidChoiceActions action;
1075
1076 {
1077    int i;
1078
1079    /* If candidate is already on the list, then don't reprocess it */
1080    if (action == XwVERIFY_ONLY)
1081    {
1082       /* Don't consider it unless it has some traversable primitives */
1083       if (XtIsSubclass(candidate, XwmanagerWidgetClass) &&
1084          _XwFindTraversablePrim(candidate) == False)
1085            return (chosen);
1086
1087       for (i = 0; i < _XwCheckListIndex; i++)
1088       {
1089          if ((_XwCheckList[i].widget == candidate) &&
1090              (_XwCheckList[i].type != XwNONE))
1091             return (chosen);
1092       }
1093    }
1094
1095    if ((action == XwADD_TO_CHOSEN_LIST) || (action == XwADD_TO_ACTIVE_LIST))
1096    {
1097       /* See if already on the list; then just update type field */
1098       for (i = 0; i < _XwCheckListIndex; i++)
1099       {
1100          if (_XwCheckList[i].widget == candidate)
1101          {
1102             if (_XwCheckList[i].type != XwCHOSEN)
1103             {
1104                _XwCheckList[_XwCheckListIndex].type =
1105                        (action == XwADD_TO_CHOSEN_LIST) ? XwCHOSEN : XwACTIVE;
1106             }
1107             return (candidate);
1108          }
1109       }
1110
1111       /* See if the list needs to grow */
1112       if (_XwCheckListIndex >= _XwCheckListSize)
1113       {
1114          _XwCheckListSize += 20;
1115          _XwCheckList = (_XwCheckListEntry *)XtRealloc((char *)_XwCheckList,
1116                               (sizeof(_XwCheckListEntry) * _XwCheckListSize));
1117       }
1118
1119       /* Add to the checklist */
1120       _XwCheckList[_XwCheckListIndex].widget = candidate;
1121       _XwCheckList[_XwCheckListIndex].type = (action == XwADD_TO_CHOSEN_LIST) ?
1122                                              XwCHOSEN : XwACTIVE;
1123       _XwCheckListIndex++;
1124    }
1125
1126    /* Clear all entries which were not on the chosen list */
1127    if (action == XwCLEAR_ACTIVE_LIST)
1128    {
1129       for (i = 0; i < _XwCheckListIndex; i++)
1130       {
1131          if (_XwCheckList[i].type == XwACTIVE)
1132             _XwCheckList[i].type = XwNONE;
1133       }
1134    }
1135
1136    return (candidate);
1137 }
1138
1139 void _XwInitCheckList()
1140
1141 {
1142    /* Initialize the traversal checklist */
1143    if (_XwCheckList == NULL)
1144    {
1145       _XwCheckList=(_XwCheckListEntry *)XtMalloc(sizeof(_XwCheckListEntry)*20);
1146       _XwCheckListSize = 20;
1147    }
1148
1149    /* Always reset the checklist to the beginning */
1150    _XwCheckListIndex = 0;
1151 }
1152
1153
1154 /*
1155  * This function verifies that all of the ancestors of a manager
1156  * have traversal enabled.
1157  */
1158
1159 static Boolean _XwManagerIsTraversable (w)
1160
1161    XwManagerWidget w;
1162
1163 {
1164    while (w && XtIsSubclass((Widget)w, XwmanagerWidgetClass))
1165    {
1166       if ((w->manager.traversal_on == FALSE) || (w->core.visible == False))
1167          return (False);
1168
1169       w = (XwManagerWidget)w->core.parent;
1170    }
1171
1172    return (True);
1173 }
1174
1175
1176 static void ClearKbdFocus (topmost_manager)
1177
1178    Widget topmost_manager;
1179
1180 {
1181    while ((topmost_manager->core.parent != NULL) &&
1182            XtIsSubclass((Widget)(topmost_manager->core.parent),
1183            XwmanagerWidgetClass))
1184       topmost_manager = topmost_manager->core.parent;
1185
1186    XtSetKeyboardFocus(topmost_manager, NULL);
1187 }