Fixed poor handling of RCS logs by last CVS checkin
[dyninst.git] / paradyn / src / UIthread / where4tree.C
1 /*
2  * Copyright (c) 1996 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * This license is for research uses.  For such uses, there is no
12  * charge. We define "research use" to mean you may freely use it
13  * inside your organization for whatever purposes you see fit. But you
14  * may not re-distribute Paradyn or parts of Paradyn, in any form
15  * source or binary (including derivatives), electronic or otherwise,
16  * to any other organization or entity without our permission.
17  * 
18  * (for other uses, please contact us at paradyn@cs.wisc.edu)
19  * 
20  * All warranties, including without limitation, any warranty of
21  * merchantability or fitness for a particular purpose, are hereby
22  * excluded.
23  * 
24  * By your use of Paradyn, you understand and agree that we (or any
25  * other person or entity with proprietary rights in Paradyn) are
26  * under no obligation to provide either maintenance services,
27  * update services, notices of latent defects, or correction of
28  * defects for Paradyn.
29  * 
30  * Even if advised of the possibility of such damages, under no
31  * circumstances shall we (or any other person or entity with
32  * proprietary rights in the software licensed hereunder) be liable
33  * to you or any third party for direct, indirect, or consequential
34  * damages of any character regardless of type of action, including,
35  * without limitation, loss of profits, loss of use, loss of good
36  * will, or computer failure or malfunction.  You agree to indemnify
37  * us (and any other person or entity with proprietary rights in the
38  * software licensed hereunder) for any and all liability it may
39  * incur to third parties resulting from your use of Paradyn.
40  */
41
42 // where4tree.C
43 // Ariel Tamches
44
45 /* $Log: where4tree.C,v $
46 /* Revision 1.19  1999/03/12 22:59:33  pcroth
47 /* Fixed poor handling of RCS logs by last CVS checkin
48 /*
49  * Revision 1.18  1999/03/03 18:16:14  pcroth
50  * Updated to support Windows NT as a front-end platform
51  * Changes made to X code, to use Tcl analogues when appropriate
52  * Also changed in response to modifications in thread library and igen output.
53  *
54  * Revision 1.17  1997/09/24 19:25:16  tamches
55  * use of Tk_GetFontMetrics; other changes for tcl 8.0
56  *
57  * Revision 1.16  1996/11/26 16:07:02  naim
58  * Fixing asserts - naim
59  *
60  * Revision 1.15  1996/08/16 21:07:36  tamches
61  * updated copyright for release 1.1
62  *
63  * Revision 1.14  1996/04/01 22:32:46  tamches
64  * use visibility X events to simulate GraphicsExpose, thus fixing bug
65  * which appeared when scrolling a partially obscured listbox
66  *
67  * Revision 1.13  1996/03/08 00:23:49  tamches
68  * major update -- added support for hidden nodes
69  *
70  * Revision 1.12  1996/02/15 23:14:12  tamches
71  * added a level of indirection to obtain type-specific GCs for the various
72  * kind of arcs drawn in the tree.
73  *
74  * Revision 1.11  1995/11/20 03:25:27  tamches
75  * removed obstacles to compiling on g++ 2.7.1: fixed drawTriangle()
76  * declaration and changed vector<NODEDATA *> to vector<const NODEDATA *>.
77  * expansion no longer unhights the node.
78  *
79  * Revision 1.10  1995/10/17 22:15:12  tamches
80  * The templated class has changed from a unique-id class to a
81  * full root-node class.
82  *
83  * Revision 1.9  1995/09/20 01:24:13  tamches
84  * Major cleanification; too many things to enumerate.  no path items
85  * have negative values.  No more uses of graphical paths.
86  *
87  */
88
89 /* ******************************************************************
90  *
91  * Notes on scrollbars and drawing speed and tk/tcl vs. C:
92  *
93  * 1. Drawing must be fast because some where axes (although not
94  *    the default one) are time-critical since they're rapidly
95  *    changing.  (e.g. the SHG of Perf. Cons)
96  *
97  * 2. Tk scrollbars (in listboxes) are not OK since they're slow
98  *    (unless I am mistaken) and the SHG uses them heavily.
99  *
100  * 3. As always, when we need faster speed, we trade off storage space.
101  *    For example, we should be able to eliminate horiz_offset_to_expanded_child()
102  *    by adding another integer item to childstruct representing that offset.
103  *
104  *    We might also store an array (indexed by explicitly expanded child)
105  *    holding indexes into theChildren.  This would make walking
106  *    through explicitly expanded children O(num-explicitly-expanded-children)
107  *    instead of O(numchildren). [note that we don't bother with implicitly
108  *    expanded children because they're easy to detect -- if no listbox then
109  *    _every_ child is implicitly expanded]
110  * 
111  * ******************************************************************
112  */
113
114 #include "minmax.h"
115 #include "where4tree.h"
116
117 \f
118 /* *****************************************************************************
119  *
120  * The listbox -- contains the title of each unexpanded subtree, with a
121  *    triangle justified with the right box border.
122  *    listbox may have a scrollbar on its left side.
123  *
124  * *****************************************************************************
125  */
126
127 template <class NODEDATA>
128 void where4tree<NODEDATA>::removeListbox() {
129    listboxPixWidth = listboxFullPixHeight = listboxActualPixHeight = 0;
130    theScrollbar.invalidate();
131 }
132
133 template <class NODEDATA>
134 bool where4tree<NODEDATA>::rethinkListboxAfterResize1(const where4TreeConstants &tc) {
135    // Using listboxFullPixHeight and tc.listboxHeightWhereSBappears
136    // (and assuming the latter has changed), rethink scrollbar aspects of listbox.
137    // Returns true iff any changes.
138
139    if (theChildren.size() == 0)
140       return false; // no children --> no listbox needs rethinking
141
142    if (listboxPixWidth == 0)
143       return false; // no listbox needs rethinking
144
145    if (listboxFullPixHeight < tc.listboxHeightWhereSBappears)
146       if (!theScrollbar.isValid())
147          // no SB was up, and no SB is needed now.  The following line
148          // might even be unnecessary (but it doesn't hurt):
149          listboxActualPixHeight = listboxFullPixHeight;
150       else {
151          // An SB was up, but need not be up any longer.  The listbox width decreases
152          // by the width of a scrollbar, and the listbox actual height is set to
153          // listbox full height.
154          theScrollbar.invalidate();
155          listboxPixWidth -= tc.listboxScrollBarWidth;
156          listboxActualPixHeight = listboxFullPixHeight;
157       }
158    else if (!theScrollbar.isValid()) {
159       // no SB was up, but one is needed now
160       theScrollbar.validate();
161       listboxPixWidth += tc.listboxScrollBarWidth;
162       listboxActualPixHeight = tc.listboxHeightWhereSBappears;
163    }
164    else {
165       // An SB was up, and still needs to be up.
166       listboxActualPixHeight = tc.listboxHeightWhereSBappears;
167       theScrollbar.updateForNewBounds(listboxActualPixHeight-2*tc.listboxBorderPix,
168                                       listboxFullPixHeight-2*tc.listboxBorderPix);
169    }
170
171    return true; // changes were made
172 }
173
174 template <class NODEDATA>
175 bool where4tree<NODEDATA>::rethinkListboxAfterResize(const where4TreeConstants &tc) {
176    // Assuming tc.listboxHeightWhereSBappears has changed (presumably due to a window
177    // resize), rethink listbox parameters.
178    // IMPORTANT: After subtree root A has a child B whose listbox dimensions have
179    //            changed, A's allExpandedChildrenWidthAsDrawn and/or
180    //            allExpandedChildrenHeightAsDrawn need updating.
181    // Returns true iff any changes were made to us (the subtree root) or any of
182    // our descendants (in which case _our_ parent should rethink its
183    // allExpandedChildrenWidth/HeightAsDrawn).
184
185    bool anyChildrenHaveChanged = false;
186
187    const unsigned numChildren = theChildren.size();
188    for (unsigned i=0; i < numChildren; i++)
189       if (getChildTree(i)->rethinkListboxAfterResize(tc))
190          anyChildrenHaveChanged = true;
191
192    if (anyChildrenHaveChanged)
193       // Fairly expensive routines: O(numchildren); could be optimized to
194       // O(num-expanded-children).
195       rethink_all_expanded_children_dimensions(tc);
196
197    const bool weHaveChanged = rethinkListboxAfterResize1(tc);
198    return anyChildrenHaveChanged || weHaveChanged;
199 }
200
201 template <class NODEDATA>
202 int where4tree<NODEDATA>::scroll_listbox(const where4TreeConstants &tc,
203                                          int deltaYpix) {
204    // doesn't redraw
205    // returns actual scroll amount (perhaps different from deltaYpix due to pinnning)
206    assert(theScrollbar.isValid());
207
208    const int oldPixFirst = theScrollbar.getPixFirst();
209
210    const int listboxTotalDataPix = listboxFullPixHeight - 2*tc.listboxBorderPix;
211    const int listboxActualDataPixHeight = listboxActualPixHeight - 2*tc.listboxBorderPix;
212  
213    int newPixFirst = oldPixFirst + deltaYpix;
214    ipmax(newPixFirst, 0);
215    ipmin(newPixFirst, listboxTotalDataPix - listboxActualDataPixHeight);
216    assert(newPixFirst >= 0);
217       // <0 implies actualHeight > totalHeight, implying no scrollbar should
218       // have been up to begin with!
219
220    if (newPixFirst == oldPixFirst)
221       return 0;
222
223    const int actualDeltaY = newPixFirst - oldPixFirst;
224    assert(actualDeltaY != 0);
225
226    theScrollbar.setPixFirst(newPixFirst);
227
228    return actualDeltaY;
229 }
230
231 template <class NODEDATA>
232 bool where4tree<NODEDATA>::scroll_listbox(const where4TreeConstants &tc,
233                                           int listboxLeft,
234                                           int listboxTop,
235                                           int deltaYpix) {
236    // returns true iff any changes made.  Redraws.
237    const int actualDeltaY = scroll_listbox(tc, deltaYpix);
238    if (actualDeltaY == 0)
239       return false;
240
241    const int listboxDataLeft = listboxLeft + tc.listboxBorderPix +
242                                tc.listboxScrollBarWidth;
243    const int listboxDataTop  = listboxTop + tc.listboxBorderPix;
244
245    // Under certain conditions, we must resort to one whole draw_listbox() instead
246    // of scrolling and doing a partial draw_listbox().  These conditions are:
247    // (1) the entire 'visible' listbox isn't entirely visible on the screen
248    //     [i.e a piece of it is scrolled off the screen], or
249    // (2) the scroll amount is so high that the XCopyArea() would simply result
250    //     in a nop due to clipping.
251    const int absDeltaY = (actualDeltaY >= 0) ? actualDeltaY : -actualDeltaY;
252    assert(absDeltaY >= 0);
253
254    bool redraw_all = false;
255
256    const int listboxActualDataPixHeight = listboxActualPixHeight -
257                                           2 * tc.listboxBorderPix;
258    if (absDeltaY > listboxActualDataPixHeight)
259       // case (2)
260       redraw_all = true;
261    else if (listboxLeft < 0)
262       // case (1)
263       redraw_all = true;
264    else if ((listboxLeft + listboxPixWidth - 1) > Tk_Width(tc.theTkWindow) - 1)
265       // case (1)
266       redraw_all = true;
267    else if (listboxTop < 0)
268       // case (1)
269       redraw_all = true;
270    else if ((listboxTop + listboxActualPixHeight - 1) > Tk_Height(tc.theTkWindow) - 1)
271       // case (1)
272       redraw_all = true;
273    else if (tc.obscured)
274       // a cheap hack to get around the fact that I can't get tk to recognize
275       // GraphicsExpose events; here, we conservatively assume that any time the
276       // window is obscured even a little, we're gonna have to redraw the whole listbox
277       // due to a graphics-expose.
278       redraw_all = true;
279
280    if (redraw_all) {
281       draw_listbox(tc.theTkWindow, tc, Tk_WindowId(tc.theTkWindow),
282                    listboxLeft, listboxTop, -1, -1);
283       return true;
284    }
285
286    // Set clipping s.t. the copy stays within the bounds of the listbox data area.
287
288    const int listboxActualDataPixWidth = listboxPixWidth - 2*tc.listboxBorderPix -
289                                          tc.listboxScrollBarWidth;
290
291    // This code is new.  By differentiating up from down scrolling,
292    // we can do a cheaper XCopyArea instead of an expensive XCopyArea plus
293    // a clip and an un-clip.
294    if (actualDeltaY < 0) {
295       // the up arrow was pressed; we scroll stuff downwards
296       XCopyArea(tc.display,
297                 Tk_WindowId(tc.theTkWindow), // src drawable
298                 Tk_WindowId(tc.theTkWindow), // dest drawable
299                 tc.listboxCopyAreaGC,
300                 listboxDataLeft, // src left
301                 listboxDataTop,  // src top
302                 listboxActualDataPixWidth, // width of stuff to copy
303                 listboxActualDataPixHeight + actualDeltaY, // height of stuff to copy
304                 listboxDataLeft, // dest left
305                 listboxDataTop - actualDeltaY
306                 );
307    }
308    else {
309       // the down arrow was pressed; we scroll stuff upwards
310       XCopyArea(tc.display,
311                 Tk_WindowId(tc.theTkWindow), // src drawable
312                 Tk_WindowId(tc.theTkWindow), // dest drawable
313                 tc.listboxCopyAreaGC,
314                 listboxDataLeft, // src left
315                 listboxDataTop + actualDeltaY, // src top (note: will be below the data top)
316                 listboxActualDataPixWidth, // width of stuff to copy
317                 listboxActualDataPixHeight - actualDeltaY, // height of stuff to copy
318                 listboxDataLeft, // dest left
319                 listboxDataTop // dest top
320                 );
321    }
322
323    int redrawLbStart; // data y pixel coord relative to top
324    if (actualDeltaY < 0)
325       // scroll upwards (e.g. click on up-arrow).  Contents move downwards;
326       // hole (to redraw) opens up at the top.
327       redrawLbStart = 0;
328    else
329       // scroll downwards (e.g. click on down-arrow).  Contents move upwards;
330       // hole (to redraw) opens up at the bottom.
331       redrawLbStart = (listboxActualDataPixHeight - 1) - actualDeltaY + 1;
332
333    draw_listbox(tc.theTkWindow, tc, Tk_WindowId(tc.theTkWindow),
334                 listboxLeft, listboxTop,
335                 redrawLbStart, absDeltaY);
336
337    return true;
338 }
339
340 template <class NODEDATA>
341 void where4tree<NODEDATA>::rethink_listbox_dimensions(const where4TreeConstants &tc) {
342    // Recalculates listboxPixWidth, listboxFullPixHeight, listboxActualPixHeight,
343    // and theScrollbar.
344
345    // Expensive.  Call only when needed (subtree expansion/unexpansion).
346    // Doesn't assume that a listbox _should_ be up; we'll cheerfully set the
347    // dimensions to indicate no-listbox-is-up if appropriate.
348
349    // Uses values of getWidthAsListboxItem() to cache away terribly expensive
350    // calls to XTextWidth() [can you imagine calling it 1,000 times?  With rbi's
351    // CM-Fortran programs, listboxes can easily get that big.]
352
353    // Step 1: width of text items (loop thru non-explicitly-expanded children)
354    int maxItemWidth = 0;
355    unsigned numItemsInlistbox = 0; // used for height calculation, later on.
356    for (unsigned childlcv=0; childlcv < theChildren.size(); childlcv++) {
357       if (theChildren[childlcv].isExplicitlyExpanded)
358          continue;
359
360       where4tree<NODEDATA> *childPtr = getChildTree(childlcv);
361       if (!childPtr->anything2Draw)
362          continue;
363
364       numItemsInlistbox++;
365
366       ipmax(maxItemWidth, childPtr->theNodeData.getWidthAsListboxItem());
367    }
368
369    if (maxItemWidth == 0) {
370       // No listbox should be up.
371       assert(numItemsInlistbox == 0);
372       removeListbox();
373       return;
374    }
375
376    assert(numItemsInlistbox > 0);
377
378    // set preliminary width (we may add a scrollbar momentarily...)
379    listboxPixWidth = 2*tc.listboxBorderPix +
380                      tc.listboxHorizPadBeforeText +
381                      maxItemWidth +
382                      tc.listboxHorizPadBeforeTriangle +
383                      tc.listboxTriangleWidth +
384                      tc.listboxHorizPadAfterTriangle;
385                            
386    // Step 2: full listbox height
387    Tk_FontMetrics listboxFontMetrics;
388    Tk_GetFontMetrics(tc.listboxFontStruct, &listboxFontMetrics);
389    const int itemHeight = tc.listboxVertPadAboveItem +
390                           listboxFontMetrics.ascent +
391                           tc.listboxVertPadAfterItemBaseline;
392    listboxFullPixHeight = 2*tc.listboxBorderPix +
393                           numItemsInlistbox * itemHeight;
394    
395    // Step 3: Is a scrollbar needed?
396    if (listboxFullPixHeight >= tc.listboxHeightWhereSBappears) {
397       listboxPixWidth += tc.listboxScrollBarWidth;
398       theScrollbar.validate();
399       listboxActualPixHeight = tc.listboxHeightWhereSBappears;
400
401       theScrollbar.updateForNewBounds(listboxActualPixHeight - 2*tc.listboxBorderPix,
402                                          // actual available data pixels
403                                       listboxFullPixHeight - 2*tc.listboxBorderPix
404                                          // total data pixels
405                                       );
406    }
407    else {
408       // No SB needed; entire listbox is visible
409       theScrollbar.invalidate();
410       listboxActualPixHeight = listboxFullPixHeight;
411    }
412 }
413
414 template <class NODEDATA>
415 void where4tree<NODEDATA>::drawTriangle(const where4TreeConstants &tc,
416                                         Drawable theDrawable,
417                                         int triangleEndX,
418                                         int currBaseLine) {
419    // cost is O(XFillPolygon())
420    // This is a fairly generic triangle-drawing routine; hence, I made it static.
421    const int triangleStartX = triangleEndX - tc.listboxTriangleWidth + 1;
422    const int triangleTopY   = currBaseLine - tc.listboxTriangleHeight + 1;
423
424    XPoint thePoints[4];
425    thePoints[0].x = triangleStartX;
426    thePoints[0].y = triangleTopY;
427
428    thePoints[1].x = triangleStartX;
429    thePoints[1].y = currBaseLine;
430
431    thePoints[2].x = triangleEndX;
432    thePoints[2].y = (triangleTopY + currBaseLine) / 2; // average of the two
433
434    XFillPolygon(tc.display, theDrawable,
435                 tc.listboxTriangleGC,
436                 thePoints, 3,
437                 Convex, // no two points inside the polygon will
438                         // intersect the boundaries when connected
439                 CoordModeOrigin);
440 }
441
442 template <class NODEDATA>
443 void where4tree<NODEDATA>::draw_listbox(Tk_Window theTkWindow,
444                                         const where4TreeConstants &tc,
445                                         Drawable theDrawable, // could be offscreen buff
446                                         int left, int top,
447                                         int datapart_relative_starty,
448                                         int datapart_relative_height) const {
449    // Assumes a listbox exists.
450    // Given (left, top) of listbox area, draw it (incl. sb, if applicable)
451    // listboxPixWidth, listboxFullPixHeight, listboxActualPixHeight,
452    // theScrollbar _must_ be up-to-date.
453
454    assert(listboxPixWidth > 0);
455    assert(listboxFullPixHeight > 0);
456    assert(listboxActualPixHeight > 0);
457    assert(existsANonExplicitlyExpandedChild());
458
459    // First, some quick & dirty macroscopic clipping:
460    if (left > Tk_Width(theTkWindow)-1) return; // everything's too far right
461    if (left + listboxPixWidth - 1 < 0) return; // everything's too far left
462    if (top > Tk_Height(theTkWindow)-1) return; // everything's too far down
463    if (top + listboxActualPixHeight - 1 < 0) return; // everything's too high
464
465    int datapart_starty = top + tc.listboxBorderPix;
466    int datapart_finishy = datapart_starty + listboxActualPixHeight -
467                           2*tc.listboxBorderPix-1;
468    
469    if (datapart_relative_starty != -1 && datapart_relative_height != -1) {
470       datapart_starty += datapart_relative_starty;
471       datapart_finishy = datapart_starty + datapart_relative_height - 1;
472    }
473
474    ipmax(datapart_starty, top + tc.listboxBorderPix);
475    ipmin(datapart_finishy, top + listboxActualPixHeight - 1 - tc.listboxBorderPix);
476
477    const bool existsScrollBar = theScrollbar.isValid();
478    if (existsScrollBar)
479       theScrollbar.draw(theTkWindow, tc.listboxScrollbarBorderNormal, theDrawable,
480                         left, top,
481                         top+listboxActualPixHeight-1,
482                         listboxActualPixHeight-2*tc.listboxBorderPix,
483                            // viewable data pix
484                         listboxFullPixHeight-2*tc.listboxBorderPix
485                            // total data pix
486                         );
487
488    // Background (total area of lb, excluding sb)
489    const int backgroundWidth = listboxPixWidth -
490                                (existsScrollBar ? tc.listboxScrollBarWidth : 0);
491
492    const int backgroundLeft = left + (existsScrollBar ? tc.listboxScrollBarWidth : 0);
493
494    // No need to Fill a rectangle; Draw will do just fine.
495    // Why?  Because each individual item is drawn with a Fill.
496    Tk_Draw3DRectangle(theTkWindow, theDrawable,
497                       tc.listboxBorder,
498                       backgroundLeft, top,
499                       backgroundWidth, listboxActualPixHeight,
500                       tc.listboxBorderPix,
501                       TK_RELIEF_RIDGE
502                       );
503
504    const int itemBoxLeft = backgroundLeft + tc.listboxBorderPix;
505    int currItemBoxTop = top - (existsScrollBar ? theScrollbar.getPixFirst() : 0)
506                             + tc.listboxBorderPix;
507
508    Tk_FontMetrics listboxFontMetrics;
509    Tk_GetFontMetrics(tc.listboxFontStruct, &listboxFontMetrics);
510    
511    const int itemBoxWidth = backgroundWidth - tc.listboxBorderPix * 2;
512    const int itemBoxHeight = tc.listboxVertPadAboveItem +
513                              listboxFontMetrics.ascent +
514                              tc.listboxVertPadAfterItemBaseline;
515
516    const int textLeft = itemBoxLeft + tc.listboxHorizPadBeforeText;
517    int currBaseline = currItemBoxTop +
518                       tc.listboxVertPadAboveItem + 
519                       listboxFontMetrics.ascent - 1;
520
521    const int normalItemRelief = TK_RELIEF_RAISED;
522    const int highlightedItemRelief = TK_RELIEF_SUNKEN;
523
524    // XSetClipRectangles() of this GC [but there are several of them!] to
525    // the rectangle corresponding to the body of this listbox (just inside 3d border)
526    XRectangle clipRect={itemBoxLeft,
527                         datapart_starty,
528                         itemBoxWidth,
529                         datapart_finishy - datapart_starty + 1};
530
531    GC lightGC = Tk_3DBorderGC(theTkWindow, tc.listboxBorder, TK_3D_LIGHT_GC);
532    GC darkGC = Tk_3DBorderGC(theTkWindow, tc.listboxBorder, TK_3D_DARK_GC);
533    GC flatGC = Tk_3DBorderGC(theTkWindow, tc.listboxBorder, TK_3D_FLAT_GC);
534
535 #if !defined(i386_unknown_nt4_0)
536    XSetClipRectangles(tc.display, lightGC, 0, 0, &clipRect, 1, YXBanded);
537    XSetClipRectangles(tc.display, darkGC, 0, 0, &clipRect, 1, YXBanded);
538    XSetClipRectangles(tc.display, flatGC, 0, 0, &clipRect, 1, YXBanded);
539
540    XSetClipRectangles(tc.display, tc.listboxTriangleGC, 0, 0, &clipRect, 1, YXBanded);
541 #else // !defined(i386_unknown_nt4_0)
542         // TODO - implement clipping support (?)
543 #endif // !defined(i386_unknown_nt4_0)
544
545    NODEDATA::prepareForDrawingListboxItems(tc.theTkWindow, clipRect);
546                       
547    for (unsigned childlcv=0; childlcv < theChildren.size(); childlcv++) {
548       if (theChildren[childlcv].isExplicitlyExpanded)
549          continue;
550
551       const where4tree<NODEDATA> *childPtr = getChildTree(childlcv);
552       if (!childPtr->anything2Draw)
553          continue;
554
555       if (currItemBoxTop > datapart_finishy)
556          break; // this item is too far down; hence, remaining items will be too.
557
558       if (currItemBoxTop + itemBoxHeight - 1 < datapart_starty) {
559          currBaseline += itemBoxHeight;
560          currItemBoxTop += itemBoxHeight;
561
562          continue; // this item is too high
563       }
564
565       // Change the background
566       Tk_Fill3DRectangle(theTkWindow, theDrawable,
567                          tc.listboxBorder,
568                          itemBoxLeft,
569                          currItemBoxTop,
570                          itemBoxWidth,
571                          itemBoxHeight,
572                          1, // looks much better than the usual value of 3
573                             // (2 also looks pretty good)
574                          theChildren[childlcv].theTree->getNodeData().getHighlighted() ?
575                             highlightedItemRelief : normalItemRelief
576                          );
577
578       NODEDATA &theChildNodeData = theChildren[childlcv].theTree->theNodeData;
579       theChildNodeData.drawAsListboxItem(theTkWindow, theDrawable,
580                                          itemBoxLeft, currItemBoxTop,
581                                          itemBoxWidth, itemBoxHeight,
582                                          textLeft, currBaseline);
583                                             
584       // Draw triangle iff this is non-leaf node
585       if (theChildren[childlcv].theTree->getNumChildren() > 0) {
586          const int triangleEndX = left + listboxPixWidth -
587                                   tc.listboxHorizPadAfterTriangle;
588          drawTriangle(tc, theDrawable, triangleEndX, currBaseline);
589       }
590
591       currBaseline   += itemBoxHeight;
592       currItemBoxTop += itemBoxHeight;
593
594       if (currItemBoxTop > Tk_Height(theTkWindow)-1)
595          break; // everything else would be too far down
596    }
597
598    NODEDATA::doneDrawingListboxItems(tc.theTkWindow);
599
600    // Undo the XSetClipRectangles():
601    XSetClipMask(tc.display, flatGC, None);
602    XSetClipMask(tc.display, darkGC, None);
603    XSetClipMask(tc.display, lightGC, None);
604
605    XSetClipMask(tc.display, tc.listboxTriangleGC, None);
606 }
607
608 template <class NODEDATA>
609 bool where4tree<NODEDATA>::
610 rigListboxScrollbarSliderTopPix(const where4TreeConstants &tc,
611                                 int scrollBarLeft,
612                                    // only needed if redrawing
613                                 int scrollBarTop,
614                                 int scrollBarBottom,
615                                 int newScrollBarSliderTopPix,
616                                 bool redrawNow) {
617    // returns true iff any changes were made
618
619    const int listboxTotalDataPix = listboxFullPixHeight -
620                                    2*tc.listboxBorderPix;
621
622    const int oldPixFirst = theScrollbar.getPixFirst();
623
624    int newScrollbarPixFirst = theScrollbar.pixFirstFromAbsoluteCoord(
625                                      scrollBarTop, scrollBarBottom,
626                                      listboxTotalDataPix,
627                                      newScrollBarSliderTopPix);
628
629    if (redrawNow)
630       return scroll_listbox(tc, scrollBarLeft, scrollBarTop,
631                             newScrollbarPixFirst - oldPixFirst);
632    else
633       return scroll_listbox(tc, newScrollbarPixFirst - oldPixFirst);
634 }
635
636 \f
637 /* ****************************************************************************
638  *
639  * The following routines are O(1) because they access private variables
640  * which have cached layout parameters.  The flipside is that such variables must
641  * be up-to-date.
642  *
643  * ****************************************************************************
644  */
645 template <class NODEDATA>
646 int where4tree<NODEDATA>::
647 horiz_pix_everything_below_root(const where4TreeConstants &tc) const {
648    // simply adds up listbox width, all-expanded-children-width, and
649    // padding where appropriate.
650
651    int result = listboxPixWidth; // may be 0
652    result += allExpandedChildrenWidthAsDrawn; // may be 0
653    if (listboxPixWidth > 0 && allExpandedChildrenWidthAsDrawn > 0)
654       result += tc.horizPixlistbox2FirstExpandedChild;
655
656    return result;
657 }
658
659 template <class NODEDATA>
660 int where4tree<NODEDATA>::vert_pix_everything_below_root() const {
661    return max(listboxActualPixHeight, allExpandedChildrenHeightAsDrawn);
662 }
663
664 template <class NODEDATA>
665 int where4tree<NODEDATA>::entire_width(const where4TreeConstants &tc) const {
666    return max(horiz_pix_everything_below_root(tc), getNodeData().getWidthAsRoot());
667 }
668
669 template <class NODEDATA>
670 int where4tree<NODEDATA>::entire_height(const where4TreeConstants &tc) const {
671    int result = theNodeData.getHeightAsRoot();
672
673    if (theChildren.size() == 0)
674       return result;
675
676    int stuff_below_root = vert_pix_everything_below_root();
677       // may be 0 if all children have anything2Draw == false
678
679    if (stuff_below_root > 0) {
680       result += tc.vertPixParent2ChildTop;
681       result += stuff_below_root;
682    }
683
684    return result;
685 }
686
687 \f
688 /* ****************************************************************************
689  *
690  * Expanded Children Measurements:
691  *
692  * ****************************************************************************
693  */
694 template <class NODEDATA>
695 int where4tree<NODEDATA>::horiz_offset_to_expanded_child(const where4TreeConstants &tc,
696                                                          unsigned childIndex) const {
697    // Gives horiz pixel offset (from the left point of the leftmost item being drawn
698    // below the root, which is the leftmost part of the scrollbar of the listbox IF a
699    // listbox is up; else from the left point of the leftmost child) to the leftmost
700    // point of a certain expanded (implicitly or explicitly) child.
701
702    // First, assert that child #childIndex is indeed expanded
703    const bool allChildrenExpanded = (listboxPixWidth == 0);
704    assert(allChildrenExpanded || theChildren[childIndex].isExplicitlyExpanded);
705
706    // Similarly, assert that the child isn't hidden:
707    assert(getChildTree(childIndex)->anything2Draw);
708
709    int result = listboxPixWidth;
710    if (listboxPixWidth > 0)
711       result += tc.horizPixlistbox2FirstExpandedChild;
712
713    for (unsigned childlcv=0; childlcv < childIndex; childlcv++)
714       if (allChildrenExpanded || theChildren[childlcv].isExplicitlyExpanded)
715          if (getChildTree(childlcv)->anything2Draw) {
716             result += theChildren[childlcv].theTree->entire_width(tc);
717                // a quick routine
718             result += tc.horizPixBetweenChildren;
719          }
720
721    return result;      
722 }
723
724 template <class NODEDATA>
725 int where4tree<NODEDATA>::
726 wouldbe_all_expanded_children_width(const where4TreeConstants &tc) const {
727    // Call this (fairly) expensive routine only to update
728    // "allExpandedChildrenWidthAsDrawn", which speeds up draw().
729    // Time is O(numchildren); could be optimized to O(num-expanded-children)
730
731    // Returns the number of horizontal pixels that would be used up, if 
732    // the expanded children of this subtree were drawn right now.
733
734    // Don't have to assume "allExpandedChildrenWidthAsDrawn" for this node being
735    // up-to-date (but that vrble _must_ be up-to-date for all descendants of this node).
736    // Additionally, each descendant (and this node) must have updated "listboxPixWidth"
737
738    if (theChildren.size() == 0)
739       return 0; // what children?
740
741    const bool allChildrenAreExpanded = (listboxPixWidth == 0);
742       // no listbox --> everyone's either implicitly or explicitly expanded!
743       // (But this doesn't include hidden nodes)
744
745    int result = 0;
746    int numExpandedChildren = 0;
747    const unsigned numChildren = theChildren.size();
748
749    for (unsigned childlcv = 0; childlcv < numChildren; childlcv++) {
750       const where4tree *theChild = getChildTree(childlcv);
751       if (allChildrenAreExpanded || theChildren[childlcv].isExplicitlyExpanded)
752          if (theChild->anything2Draw) {
753             result += theChild->entire_width(tc); // cheap
754             numExpandedChildren++;
755          }
756    }
757
758    if (numExpandedChildren > 0)
759       result += (numExpandedChildren - 1) * tc.horizPixBetweenChildren;
760
761    return result;
762 }
763
764 template <class NODEDATA>
765 int where4tree<NODEDATA>::
766 wouldbe_all_expanded_children_height(const where4TreeConstants &tc) const {
767    // Call this (fairly) expensive routine only to update
768    // "heightOfAllExpandedChildrenAsDrawn", which speeds up draw().
769
770    // Returns the number of vertical pixels that would be used up, if this subtree's
771    // expanded children were drawn right now.  The children of this node must
772    // have vrbles up to date s.t. entire_height() returns the right value for them.
773    // But don't have to assume "allExpandedChildrenHeightAsDrawn" for this node being
774    // up-to-date.
775
776    if (theChildren.size() == 0)
777       return 0; // what children?
778
779    const bool allChildrenAreExpanded = (listboxPixWidth == 0);
780       // no listbox --> everyone's either implicitly or explicitly expanded!
781
782    int result = 0;
783    const unsigned numChildren = theChildren.size();
784    for (unsigned childlcv = 0; childlcv < numChildren; childlcv++)
785       if (allChildrenAreExpanded || theChildren[childlcv].isExplicitlyExpanded)
786          if (getChildTree(childlcv)->anything2Draw)
787             ipmax(result, theChildren[childlcv].theTree->entire_height(tc));
788
789    return result;
790 }
791
792 \f
793 template <class NODEDATA>
794 void where4tree<NODEDATA>::draw(Tk_Window theTkWindow,
795                                 const where4TreeConstants &tc,
796                                 Drawable theDrawable,
797                                 int middlex, int topy,
798                                    // describes position of root node
799                                 bool rootOnly, bool listboxOnly) const {
800    if (!anything2Draw)
801       return;
802
803    const int maxWindowY = Tk_Height(theTkWindow) - 1;
804    if (topy > maxWindowY)
805       return; // everything is too far down
806
807    if (!listboxOnly)
808       theNodeData.drawAsRoot(theTkWindow, theDrawable, middlex, topy);
809
810    if (rootOnly || theChildren.size() == 0)
811       return; // no children to draw...
812
813    const int horizPixEverythingBelowRoot = horiz_pix_everything_below_root(tc);
814       // a very quick routine
815
816    int rayOriginX = middlex;
817    int rayOriginY = topy + theNodeData.getHeightAsRoot(); // don't subtract 1
818  
819    if (rayOriginY > maxWindowY)
820       return; // everything else would be too far down
821
822    int childtopypix = rayOriginY + tc.vertPixParent2ChildTop;
823
824    int currentXpix = middlex - horizPixEverythingBelowRoot / 2;
825
826    // Draw listbox:
827    if (listboxPixWidth > 0) {
828       assert(existsANonExplicitlyExpandedChild());
829       assert(listboxFullPixHeight > 0);
830       assert(listboxActualPixHeight > 0);
831
832       // ray from bottom of root (rayOriginX, rayOriginY) to (centerx, topy) of listbox:
833       if (!listboxOnly) {
834          GC theGC = NODEDATA::getGCforListboxRay(theNodeData,
835                                                  getChildTree(0)->theNodeData);
836          XDrawLine(tc.display, theDrawable, theGC,
837                    rayOriginX, rayOriginY,  // (left, top)
838                    currentXpix + listboxPixWidth / 2, // destx
839                    childtopypix - 1 // desty
840                    );
841       }
842
843       draw_listbox(tc.theTkWindow, tc, theDrawable,
844                    currentXpix, // left
845                    childtopypix, // top
846                    -1, -1);
847
848       currentXpix += listboxPixWidth + tc.horizPixlistbox2FirstExpandedChild;
849    }
850
851    if (listboxOnly)
852       return;
853
854    // Now draw expanded children, if any
855    const bool allChildrenAreExpanded = (listboxPixWidth == 0);
856    const unsigned numChildren = theChildren.size();
857    for (unsigned childlcv=0; childlcv < numChildren; childlcv++) {
858       if (!allChildrenAreExpanded && !theChildren[childlcv].isExplicitlyExpanded)
859          continue; // don't draw this child since it's in the listbox
860
861       if (!getChildTree(childlcv)->anything2Draw)
862          continue;
863
864       const where4tree *theChild = theChildren[childlcv].theTree;
865       const int childEntireWidthAsDrawn = theChild->entire_width(tc);
866          // not expensive
867
868       const int subtree_centerx = currentXpix + childEntireWidthAsDrawn / 2;
869
870       // Ray from (rayOriginX, rayOriginY) to (centerx,topy) of subchild:
871       // Beware: X has only a 16-bit notion of x and y fields; we must pin if
872       //         any value is too far right.  At first I thought the way to go was to
873       //         skip the XDrawLine() if the recursive child's draw() won't draw
874       //         anything due to clipping.  But this is too harsh; just because a
875       //         child subtree is not visible does NOT mean the connecting line
876       //         would be completely invisible!
877       //         So how to draw just the necessary portion of the connecting line;
878       //         and, how to give it the right "downward angle"?
879       // This is our solution:  We draw the connecting line only to the right edge
880       // of the screen.  In other words, we draw the connecting line only to
881       // x=windowMaxX (a known value) and y=(unknown value; need to determine).
882       // Let (x1,y1) be the (known) would-be destination (which we
883       // can't draw directly to because of this 16-bit problem).  Then, the
884       // line's slope is known: (y1-y0)/(x1-x0).  Using the slope value, we can
885       // calculate the unknown y.  The equation is m=(y-y0)/(rightEdge-x0).
886       // y is the only unknown; isolate to get y=y0 + m(rightEdge-x0).
887       // Draw ray from (rayOriginX, rayOriginY) to (windowMaxX, y); done.
888
889 const int maximus = 32768;
890
891       GC lineGC = NODEDATA::getGCforNonListboxRay(getNodeData(),
892                                                   theChild->getNodeData());
893
894       if (subtree_centerx < maximus)
895          XDrawLine(tc.display, theDrawable, lineGC,
896                    rayOriginX, rayOriginY,
897                    subtree_centerx, childtopypix-1);
898       else {
899          // Here's the hairy case, discussed above.
900          double slope = (childtopypix-1) - rayOriginY;
901          slope /= (subtree_centerx - rayOriginX); // any divide by zero possibility?
902
903 //            const int rayDestinationX = windowMaxX;
904          const int rayDestinationX = maximus-1;
905
906          const int rayDestinationY = (int)((double)rayOriginY + slope*(rayDestinationX - rayOriginX));
907
908          XDrawLine(tc.display, theDrawable, lineGC,
909                    rayOriginX, rayOriginY,
910                    rayDestinationX, rayDestinationY);
911       }
912                               
913       // Recursively draw the subtree
914       theChild->draw(tc.theTkWindow, tc, theDrawable,
915                      subtree_centerx, childtopypix,
916                      false, // not root only
917                      false // not listbox only
918                      );
919  
920       currentXpix += childEntireWidthAsDrawn + tc.horizPixBetweenChildren;
921    }
922 }
923
924 \f
925 /* *******************************************************************
926  *
927  * Node explicit expansion / un-expansion
928  *
929  * note: after expansion / un-expansion, you'll probably need to redraw the _entire_
930  *       where axis---for for our ascendants.  Why?  Because changing our width changes
931  *       the total width of our ascendants (and so on), which means everything needs
932  *       recentering.
933  *
934  * *******************************************************************
935  */
936
937 template <class NODEDATA>
938 bool where4tree<NODEDATA>::expandUnexpand1(const where4TreeConstants &tc,
939                                            unsigned childindex, bool expandFlag,
940                                            bool rethinkFlag,
941                                            bool force) {
942    // won't expand a leaf node unless "force" is true
943    // NOTE: Expanding a child will require rethinking the all-expanded-children
944    //       dimensions for ALL ancestors of the expandee.  This routine only takes
945    //       care of updating those dimensions for the immediate ancestor (parent)
946    //       of the expandee.  YOU MUST MANUALLY HANDLE THE REST OF THE PATH!
947
948    if (theChildren[childindex].isExplicitlyExpanded == expandFlag)
949       return false; // nothing would change
950
951    // We don't want to hear about a child that is hidden:
952    assert(getChildTree(childindex)->anything2Draw);
953
954    // do not expand a leaf node unless "force" is true
955    if (expandFlag)
956       if (!force && getChildTree(childindex)->theChildren.size() == 0)
957          return false;
958       else if (listboxPixWidth == 0) {
959          // Already implicitly expanded.  Just make it explicit.
960          theChildren[childindex].isExplicitlyExpanded = expandFlag;
961          return false;
962       }
963
964    theChildren[childindex].isExplicitlyExpanded = expandFlag;
965
966    if (rethinkFlag) {
967       // Note: we _don't_ rethink dimensions for the expanded subtree.  It will
968       // look just at it looked that last time it was expanded.
969       // But we _do_ rethink dimensions for us, the parent.  In particular,
970       // the listbox dimensions can completely change; in addition, variables
971       // tracking the width and height of all expanded children change.
972    
973       rethink_listbox_dimensions(tc);
974          // an expensive routine, O(numchildren).  Could be optimized if the
975          // listbox widths were somehow sorted, because most time is spent
976          // looping through the remaining listbox entries to detemine max pix width...
977    
978       rethink_all_expanded_children_dimensions(tc);
979    }
980
981    return true;
982 }
983
984 template <class NODEDATA>
985 bool where4tree<NODEDATA>::explicitlyExpandSubchild(const where4TreeConstants &tc,
986                                                     unsigned childindex,
987                                                     bool force) {
988    // returns true iff any changes are made.  Won't expand a leaf node.
989    // NOTE: The same warning of expandUnexpand1() applies -- outside code must
990    //       manually rethink_expanded_children_dimensions() for ALL ancestors of
991    //       the expandee; this routine only handles the immeidate ancestor (parent).
992    return expandUnexpand1(tc, childindex, true, true, force);
993 }
994
995 template <class NODEDATA>
996 bool where4tree<NODEDATA>::explicitlyUnexpandSubchild(const where4TreeConstants &tc,
997                                                       unsigned childindex) {
998    // returns true iff any changes are made
999    // NOTE: The same warning of expandUnexpand1() applies -- outside code must
1000    //       manually rethink_expanded_children_dimensions() for ALL ancestors of
1001    //       the expandee; this routine only handles the immeidate ancestor (parent).
1002
1003    const bool allChildrenExpanded = (listboxPixWidth == 0);
1004    if (!allChildrenExpanded && !theChildren[childindex].isExplicitlyExpanded)
1005       return false; // this child is already un-expanded
1006
1007    return expandUnexpand1(tc, childindex, false, true, false);
1008 }
1009
1010 template <class NODEDATA>
1011 bool where4tree<NODEDATA>::expandAllChildren(const where4TreeConstants &tc) {
1012    // expand _all_ non-leaf non-hidden children.  Returns true iff any changes...
1013
1014    bool result = false;
1015    bool anythingLeftInListbox = false;
1016
1017    for (unsigned childlcv=0; childlcv < theChildren.size(); childlcv++) {
1018       if (!getChildTree(childlcv)->anything2Draw)
1019          continue;
1020
1021       if (expandUnexpand1(tc, childlcv, true, // expand
1022                           false, // we'll rethink lb dimensions manually, below
1023                           false // don't force expansion of leaf items
1024                           ))
1025          result = true;
1026       else
1027          anythingLeftInListbox = true;
1028    }
1029
1030    if (!result)
1031       return false; // no changes
1032
1033    if (!anythingLeftInListbox)
1034       removeListbox(); // don't need a listbox anymore
1035    else
1036       rethink_listbox_dimensions(tc);
1037
1038    rethink_all_expanded_children_dimensions(tc);
1039       // allExpandedChildrenWidthAsDrawn and allExpandedChildrenHeightAsDrawn
1040
1041    return true; // changes were made
1042 }
1043
1044 template <class NODEDATA>
1045 bool where4tree<NODEDATA>::unExpandAllChildren(const where4TreeConstants &tc) {
1046    // returns true iff any changes were made
1047    for (unsigned childlcv=0; childlcv < theChildren.size(); childlcv++)
1048       theChildren[childlcv].isExplicitlyExpanded = false;
1049
1050    // We _definitely_ need a listbox now... (unless all children are hidden I guess)
1051    rethink_listbox_dimensions(tc);
1052
1053    // There are no more expanded children:
1054    // (calling rethink_all_expanded_children_dimensions() would work OK --- since
1055    //  we have already properly adjusted the listbox --- but, this is quicker)
1056    allExpandedChildrenWidthAsDrawn  = 0;
1057    allExpandedChildrenHeightAsDrawn = 0;
1058
1059    return true;
1060 }
1061
1062 template <class NODEDATA>
1063 void where4tree<NODEDATA>::rethinkAfterResize(const where4TreeConstants &tc,
1064                                               int horizSpaceToWorkWithThisSubtree) {
1065    const unsigned numChildren = theChildren.size();
1066    if (numChildren == 0)
1067       return; // what's to rethink?  nothing!  This is a measly leaf node.
1068
1069    // If there is a listbox up now, perhaps it doesn't need to stay up
1070    // (but only in the case that the window was made wider, of course)
1071    bool existslistbox = (listboxPixWidth > 0);
1072
1073    if (listboxPixWidth > 0) {
1074       assert(listboxFullPixHeight > 0);
1075       assert(listboxActualPixHeight > 0);
1076       assert(existsANonExplicitlyExpandedChild());
1077    }
1078    
1079    int childrenWidthIfAllExpanded = 0;
1080    for (unsigned childlcv=0; childlcv < numChildren; childlcv++) {
1081       where4tree<NODEDATA> *childPtr = getChildTree(childlcv);
1082       if (!childPtr->anything2Draw) continue;
1083
1084       childrenWidthIfAllExpanded += childPtr->entire_width(tc) +
1085                                     tc.horizPixBetweenChildren;
1086    }
1087
1088    assert(numChildren > 0);
1089    if (childrenWidthIfAllExpanded > 0) // it's possible that all nodes were hidden
1090       childrenWidthIfAllExpanded -= tc.horizPixBetweenChildren;
1091       // last child has no space after it
1092
1093    if (existslistbox && childrenWidthIfAllExpanded <= horizSpaceToWorkWithThisSubtree) {
1094       // All the children fit; no need for a listbox anymore.
1095       removeListbox();
1096
1097       rethink_all_expanded_children_dimensions(tc);
1098
1099       assert(allExpandedChildrenWidthAsDrawn == childrenWidthIfAllExpanded);
1100    }
1101    else if (!existslistbox &&
1102             childrenWidthIfAllExpanded > horizSpaceToWorkWithThisSubtree) {
1103       // We now need a listbox.  Explicitly expanded children
1104       // stay expanded; implicitly expanded children are collapsed into a listbox.
1105
1106       rethink_listbox_dimensions(tc); // expensive, O(numchildren)
1107       rethink_all_expanded_children_dimensions(tc);
1108    }
1109 }
1110
1111 \f
1112 template <class NODEDATA>
1113 int where4tree<NODEDATA>::point2ItemOneStepScrollbar(const where4TreeConstants &tc,
1114                                                      int ypix, int scrollbarTop,
1115                                                      int scrollbarHeight) const {
1116    // -3 for a point in listbox scrollbar up-arrow,
1117    // -4 for point in listbox scrollbar down-arrow,
1118    // -5 for point in listbox scrollbar pageup-region,
1119    // -6 for point in listbox scrollbar pagedown-region,
1120    // -7 for point in listbox scrollbar slider.
1121
1122    const int arrowHeight = theScrollbar.getArrowPixHeight();
1123
1124    const int scrollbarBottom = scrollbarTop + scrollbarHeight - 1;
1125
1126    // Check for top-arrow or bottom-arrow click
1127    if (ypix >= scrollbarTop && ypix <= scrollbarTop + arrowHeight - 1)
1128       return -3;
1129
1130    if (ypix >= scrollbarBottom - arrowHeight + 1 && ypix <= scrollbarBottom)
1131       return -4;
1132
1133    // Now, we need to calculate the coordinates of the slider...
1134    int sliderPixTop;
1135    int sliderPixHeight;
1136    theScrollbar.getSliderCoords(scrollbarTop, scrollbarBottom,
1137                                 listboxActualPixHeight-2*tc.listboxBorderPix,
1138                                 listboxFullPixHeight-2*tc.listboxBorderPix,
1139                                 sliderPixTop, // filled in
1140                                 sliderPixHeight // filled in
1141                                 );
1142
1143    if (ypix < sliderPixTop)
1144       return -5; // pageup-region
1145    if (ypix > (sliderPixTop + sliderPixHeight - 1))
1146       return -6; // pagedown-region
1147
1148    assert(ypix >= sliderPixTop && ypix <= (sliderPixTop + sliderPixHeight - 1));
1149    return -7; // in slider
1150 }
1151
1152 template <class NODEDATA>
1153 int where4tree<NODEDATA>::point2ItemOneStep(const where4TreeConstants &tc,
1154                                             int xpix, int ypix,
1155                                             int root_centerx, int root_topy) const {
1156    // returns -1 for a point in root, 0 thru n-1 for point w/in general
1157    // range of a child subtree [even if child is in a listbox],
1158    // -2 for a point on nothing,
1159    // -3 for a point in listbox scrollbar up-arrow,
1160    // -4 for point in listbox scrollbar down-arrow,
1161    // -5 for point in listbox scrollbar pageup-region,
1162    // -6 for point in listbox scrollbar pagedown-region,
1163    // -7 for point in listbox scrollbar slider.
1164
1165    assert(ypix >= 0 && xpix >= 0);
1166    assert(anything2Draw);
1167
1168    const int posRelativeToRoot = theNodeData.pointWithinAsRoot(xpix, ypix,
1169                                                                root_centerx, root_topy);
1170    if (posRelativeToRoot == 2)
1171       return -2; // too high
1172    if (posRelativeToRoot == 4 || posRelativeToRoot == 5)
1173       return -2; // good ypix but bad xpix (directly to the left or right of root)
1174    if (posRelativeToRoot == 1)
1175       return -1; // bingo; in root node
1176
1177    assert(posRelativeToRoot == 3); // below root...check listbox & expanded children
1178
1179    const int childrenTop = root_topy + getNodeData().getHeightAsRoot() +
1180                            tc.vertPixParent2ChildTop;
1181    if (ypix < childrenTop)
1182       return -2; // nothing
1183
1184    const int horizPixEverythingBelowRoot = horiz_pix_everything_below_root(tc);
1185       // a quick routine
1186
1187    int currentX = root_centerx - horizPixEverythingBelowRoot / 2;
1188
1189    if (xpix < currentX)
1190       return -2; // too far left for any children
1191    if (xpix > currentX + horizPixEverythingBelowRoot - 1)
1192       return -2; // too far right for any children
1193
1194    const int vertPixEverythingBelowRoot = vert_pix_everything_below_root();
1195
1196    if (ypix > childrenTop + vertPixEverythingBelowRoot - 1)
1197       return -2; // too far down for any children
1198
1199    // Check listbox:
1200    if (listboxPixWidth > 0) {
1201       const int listboxRight = currentX + listboxPixWidth - 1;
1202       
1203       if (xpix >= currentX && xpix <= listboxRight) {
1204          // xpix indicates that it can only be a point w/in listbox
1205
1206          const int listboxBottom = childrenTop + listboxActualPixHeight - 1;
1207
1208          if (ypix >= childrenTop && ypix <= listboxBottom) {
1209             // point is in listbox!  But scrollbar part or data part?
1210             const bool scrollBarIsUp = theScrollbar.isValid();
1211             if (scrollBarIsUp && xpix < currentX + tc.listboxScrollBarWidth)
1212                return point2ItemOneStepScrollbar(tc,
1213                                  ypix, // click point (note that xcoord is not needed)
1214                                  childrenTop, // scrollbar top
1215                                  listboxActualPixHeight // scrollbar height
1216                                                  );
1217                                                  
1218             // Wasn't a click in scrollbar.
1219             int listboxLocalX = xpix - currentX;
1220             if (scrollBarIsUp)
1221                listboxLocalX -= tc.listboxScrollBarWidth;
1222             if (listboxLocalX < tc.listboxBorderPix)
1223                return -2; // sorry, you clicked on the left border
1224                  
1225             int listboxLocalY = ypix - childrenTop;
1226             if (listboxLocalY < tc.listboxBorderPix)
1227                return -2; // sorry, you clicked on the top border
1228
1229             if (scrollBarIsUp)
1230                listboxLocalY += theScrollbar.getPixFirst();
1231
1232             assert(listboxLocalX >= 0);
1233             assert(listboxLocalX < listboxPixWidth -
1234                                    (scrollBarIsUp ? tc.listboxScrollBarWidth : 0));
1235
1236             assert(listboxLocalY >= 0);
1237             assert(listboxLocalY < listboxFullPixHeight);
1238
1239             return point2ItemWithinListbox(tc, listboxLocalX, listboxLocalY);
1240          }
1241
1242          return -2; // correct xpix but wrong ypix for listbox
1243       }
1244
1245       // point wasn't in listbox; we'll try the expanded children
1246       currentX += listboxPixWidth + tc.horizPixlistbox2FirstExpandedChild;
1247    }
1248
1249    // Check expanded, non-hidden children (both implicitly and explicitly expanded ones)
1250    const bool allChildrenAreExpanded = (listboxPixWidth == 0);
1251    const unsigned numChildren = theChildren.size();
1252    for (unsigned childlcv = 0; childlcv < numChildren; childlcv++) {
1253       const where4tree<NODEDATA> *childPtr = getChildTree(childlcv);
1254
1255       if (!childPtr->anything2Draw)
1256          continue;
1257
1258       if (allChildrenAreExpanded || theChildren[childlcv].isExplicitlyExpanded) {
1259          const int thisChildEntireWidth = childPtr->entire_width(tc);
1260
1261          if (xpix >= currentX && xpix <= currentX + thisChildEntireWidth - 1)
1262             // Judging by x-coords, point can only fall w/in this subtree
1263             return childlcv;
1264
1265          currentX += thisChildEntireWidth + tc.horizPixBetweenChildren;
1266          if (xpix < currentX)
1267             return -2;
1268       }
1269    }
1270
1271    return -2;
1272 }
1273
1274 template <class NODEDATA>
1275 int where4tree<NODEDATA>::point2ItemWithinListbox(const where4TreeConstants &tc,
1276                                                   int localx, int localy) const {
1277    // Given point relative to the data part (not scrollbar part) of the 
1278    // listbox (may assert that a listbox exists for this subtree and
1279    // that the provided points lie within its bounds), return index of item
1280    // that was clicked on, or -2 for nothing.
1281
1282    // called by point2ItemOneStep()
1283
1284    // Important note: localy is between 0 and (_Full_PixHeight-1).
1285    //                 That's what I mean by relative.  Scrollbar has already
1286    //                 taken into account.  Borders have also been taken into account.
1287
1288    assert(listboxPixWidth > 0);
1289    assert(listboxFullPixHeight > 0);
1290    assert(listboxActualPixHeight > 0);
1291
1292    assert(0 <= localx);
1293    assert(localx < listboxPixWidth);
1294    assert(0 <= localy);
1295    assert(localy < listboxFullPixHeight);
1296
1297    Tk_FontMetrics listboxFontMetrics;
1298    Tk_GetFontMetrics(tc.listboxFontStruct, &listboxFontMetrics);
1299    
1300    const int itemHeight = tc.listboxVertPadAboveItem +
1301                           listboxFontMetrics.ascent +
1302                           tc.listboxVertPadAfterItemBaseline;
1303    int theRelativeItem = localy / itemHeight;
1304    assert(theRelativeItem >= 0);
1305
1306    // If we could find expanded, non-hidden child #i in constant time, then this
1307    // operation could be made much faster.
1308
1309    const unsigned numChildren = theChildren.size();
1310    for (unsigned childlcv=0; childlcv < numChildren; childlcv++) {
1311       if (!getChildTree(childlcv)->anything2Draw) continue;
1312
1313       // listbox exists --> _all_ non-explicitly-expanded children are in the listbox.
1314       if (!theChildren[childlcv].isExplicitlyExpanded)
1315          if (theRelativeItem == 0)
1316             return childlcv;
1317          else
1318             theRelativeItem--;
1319    }
1320
1321    return -2; // nothing
1322 }
1323
1324 template <class NODEDATA>
1325 int where4tree<NODEDATA>::string2Path(whereNodePosRawPath &thePath,
1326                                       const where4TreeConstants &tc,
1327                                       const string &str,
1328                                       where4tree *beginSearchFrom,
1329                                       bool testRootNode) {
1330    // If not found, thePath is left undefined, and 0 is returned.
1331    // Otherwise, modifies "thePath" and:
1332    //    -- returns 1 if no expansions are necessary (can scroll)
1333    //    -- returns 2 if expansions are necessary before scrolling
1334
1335    // Depth first search (dive into listbox children, then expanded ones)
1336
1337    // NOTE: "thePath" must start out initialized as usual...
1338
1339    bool match = anything2Draw && testRootNode && str.prefix_of(getRootName());
1340    if (match) {
1341       // If beginSearchFrom==NULL, then we truly have a match.
1342       // Else, if beginSearchFrom==this, then set beginSearchFrom to NULL
1343       //       and continue the search as if no match were made.
1344       // Else, continue the search as if no match were made.
1345
1346       if (beginSearchFrom==NULL)
1347          return 1; // found; no expansion necessary
1348       else if (beginSearchFrom==this)
1349          beginSearchFrom=NULL;
1350       else
1351          ;
1352    }
1353
1354    // Check all children.  In order to set the path correctly, we'll need
1355    // to distinguish listbox from non-listbox items.
1356    const bool allChildrenExpanded = (listboxPixWidth == 0);
1357
1358    // First, the listbox children:
1359    unsigned numChildren = theChildren.size();
1360    for (unsigned i=0; i < numChildren; i++) {
1361       if (!getChildTree(i)->anything2Draw) continue;
1362
1363       const bool childIsInListbox = !allChildrenExpanded &&
1364                                     !theChildren[i].isExplicitlyExpanded;
1365       if (childIsInListbox) {
1366          const string &childName = theChildren[i].theTree->getRootName();
1367          match = str.prefix_of(childName);
1368          if (match)
1369             if (beginSearchFrom==theChildren[i].theTree) {
1370                match = false;
1371                beginSearchFrom=NULL;
1372             }
1373             else if (beginSearchFrom != NULL)
1374                match = false;
1375
1376          thePath.append(i);
1377
1378          if (match)
1379             return 1; // found; no exp necessary
1380
1381          where4tree *theChild = getChildTree(i);
1382
1383          if (theChild->string2Path(thePath, tc, str, beginSearchFrom, false) != 0)
1384             return 2; // found; expansion necessary.
1385          else
1386             // undo the path item we appended
1387             thePath.rigSize(thePath.getSize()-1);
1388       }
1389    }
1390  
1391    // Next, the non-listbox children
1392    for (unsigned j=0; j < numChildren; j++) {
1393       if (!getChildTree(j)->anything2Draw) continue;
1394
1395       const bool childIsExpanded = allChildrenExpanded ||
1396                                    theChildren[j].isExplicitlyExpanded;
1397       if (childIsExpanded) {
1398          thePath.append(j);
1399
1400          where4tree *theChild = getChildTree(j);
1401
1402          int result = theChild->string2Path(thePath, tc, str, beginSearchFrom, true);
1403          if (result == 0)
1404             // undo the path item which we appended
1405             thePath.rigSize(thePath.getSize()-1);
1406          else
1407             return result;
1408       }
1409    }
1410
1411    return 0; // not found
1412 }
1413
1414 \f
1415 /* ********************************************************************
1416  *
1417  * High-level tree actions (highlighting, expanding) given paths.
1418  *
1419  * ********************************************************************
1420  */
1421
1422 template <class NODEDATA>
1423 bool where4tree<NODEDATA>::path2lbItemExpand(const where4TreeConstants &tc,
1424                                              const whereNodePosRawPath &thePath,
1425                                              unsigned pathIndex) {
1426    // returns true iff any changes.
1427
1428    // new feature: whenever a node A is explicitly expanded, so are all of its
1429    //              ancestors.
1430
1431    assert(anything2Draw);
1432
1433    const unsigned pathSize = thePath.getSize();
1434    assert(pathIndex < pathSize);
1435
1436    if (pathIndex < pathSize-1) {
1437       // recurse...then, if changes were made to a descendant, rethink our
1438       // child params...
1439       unsigned childnum = thePath[pathIndex];
1440
1441       bool anyChanges = getChildTree(childnum)->
1442                         path2lbItemExpand(tc, thePath, pathIndex+1);
1443
1444       if (explicitlyExpandSubchild(tc, childnum, false)) // false --> no force
1445          anyChanges = true;
1446
1447       if (anyChanges)
1448          rethink_all_expanded_children_dimensions(tc);
1449
1450       return anyChanges;
1451    }
1452
1453    assert(pathIndex == pathSize-1);
1454    unsigned lastItem = thePath.getLastItem();
1455
1456    return explicitlyExpandSubchild(tc, lastItem, false); // false --> don't force
1457 }
1458
1459 template <class NODEDATA>
1460 bool where4tree<NODEDATA>::expandEntirePath(const where4TreeConstants &tc,
1461                                             const whereNodePosRawPath &thePath,
1462                                             unsigned index) {
1463    // Save as path2lbItemExpand, except we won't expand a listbox item at the
1464    // end of the path -- we just want to "make the entire path visible".
1465    // Returns true iff any changes were made
1466
1467    assert(anything2Draw);
1468
1469    if (thePath.getSize() == 0)
1470       return false; // we never need to expand the root node
1471    if (index == thePath.getSize()-1)
1472       // we never expand the item at the end of the path.
1473       // Why not?  Well, if it's a listbox item, then we want to keep it there.
1474       // And, if it's not a listbox item, then by definition it's already expanded.
1475       return false;
1476    
1477    // follow the next link along the path...
1478    const unsigned childindex = thePath[index];
1479
1480    const bool allChildrenExpanded = (listboxPixWidth == 0);
1481    if (!allChildrenExpanded && !theChildren[childindex].isExplicitlyExpanded) {
1482       // Aha! the next link is in a listbox.  Let's expand him.  BUT, we wait until
1483       // we finish the recursion first (necessary for correct rethinking of layout).
1484
1485       assert(getChildTree(childindex)->anything2Draw);
1486
1487       (void)getChildTree(childindex)->expandEntirePath(tc, thePath, index+1);
1488          // recurse
1489
1490       bool aflag;
1491       aflag=(explicitlyExpandSubchild(tc, childindex, false)); 
1492       // false --> don't force
1493       assert(aflag);
1494          // rethinks stuff, too (like allExpandedChildrenWidthAsDrawn)
1495
1496       return true; // expansion(s) were made
1497    }
1498    else {
1499       const bool result = getChildTree(childindex)->
1500                           expandEntirePath(tc, thePath, index+1);
1501
1502       if (result)
1503          rethink_all_expanded_children_dimensions(tc);
1504
1505       return result;
1506    }
1507 }
1508
1509 template <class NODEDATA>
1510 bool where4tree<NODEDATA>::path2lbItemUnexpand(const where4TreeConstants &tc,
1511                                                const whereNodePosRawPath &thePath,
1512                                                unsigned pathIndex) {
1513    // returns true iff any changes were made
1514    assert(anything2Draw);
1515
1516    const unsigned pathSize = thePath.getSize();
1517    if (pathIndex == pathSize-1) {
1518       // We (i.e., "this") are the _parent_ of the node to un-expand.
1519
1520       const unsigned childIndex = thePath.getLastItem();
1521
1522       // Unhighlight the child (doesn't redraw):
1523       assert(getChildTree(childIndex)->anything2Draw);
1524       getChildTree(childIndex)->unhighlight();
1525
1526       // and un-expand (rethinks listbox size and other layout vrbles)
1527       return explicitlyUnexpandSubchild(tc, childIndex);
1528    }
1529    else {
1530       // recurse...then, if changes were made to a descendant, rethink our
1531       // child params...
1532       unsigned thisItem = thePath[pathIndex];
1533       assert(getChildTree(thisItem)->anything2Draw);
1534       const bool result = getChildTree(thisItem)->path2lbItemUnexpand
1535                             (tc, thePath, pathIndex + 1);
1536       if (result)
1537          // Changes were made to a descendant of child #theItem.  We
1538          // need to update some of our internal variables.  Why?  Because the
1539          // descendant action probably changed some width/height sizes.
1540          rethink_all_expanded_children_dimensions(tc);
1541
1542       return result;
1543    }
1544 }
1545
1546 template <class NODEDATA>
1547 bool where4tree<NODEDATA>::path2ExpandAllChildren(const where4TreeConstants &tc,
1548                                                   const whereNodePosRawPath &thePath,
1549                                                   unsigned pathIndex) {
1550    // returns true iff any changes.
1551    // new feature: in general, when we explicitly expand node A, we also
1552    //              explicitly expand all of its ancestors.  At first, this seems
1553    //              silly (how could we have explicitly expanded A if its ancestors
1554    //              were not visible to begin with?)  The key is that the ancestors
1555    //              may have been implicitly expanded.
1556
1557    assert(anything2Draw);
1558    if (pathIndex < thePath.getSize()) {
1559       // recurse...then, if changes were made to a descendant [of course there were;
1560       // we're expanding all of its children!], then rethink our child size params...
1561       unsigned childnum = thePath[pathIndex];
1562       assert(getChildTree(childnum)->anything2Draw);
1563       bool result = getChildTree(childnum)->path2ExpandAllChildren
1564                                                 (tc, thePath, pathIndex+1);
1565
1566       if (explicitlyExpandSubchild(tc, childnum, false)) // don't force
1567          result = true;
1568       else {
1569          // we didn't end up expanding anything; however, we still need
1570          // to rethink our all-expanded-width, etc.
1571          rethink_all_expanded_children_dimensions(tc);
1572          result = true;
1573       }
1574
1575       return result;
1576    }
1577
1578    return expandAllChildren(tc);
1579 }
1580
1581 template <class NODEDATA>
1582 bool where4tree<NODEDATA>::path2UnExpandAllChildren(const where4TreeConstants &tc,
1583                                                     const whereNodePosRawPath &thePath,
1584                                                     unsigned pathIndex) {
1585    // returns true iff any changes were made.  Doesn't redraw
1586
1587    assert(anything2Draw);
1588    if (pathIndex < thePath.getSize()) {
1589       // recurse...then, if changes were made to a descendant [of course there were;
1590       // we're un-expanding all of its children!], then rethink our child size params...
1591       unsigned thisItem = thePath[pathIndex];
1592       assert(getChildTree(thisItem)->anything2Draw);
1593
1594       const bool result = getChildTree(thisItem)->
1595                           path2UnExpandAllChildren(tc, thePath, pathIndex+1);
1596
1597       if (result)
1598          rethink_all_expanded_children_dimensions(tc);
1599
1600       return result;
1601    }
1602
1603    return unExpandAllChildren(tc);
1604 }
1605
1606 \f
1607 /* ***************************************************************************
1608  *
1609  * Constructor, Destructor
1610  *
1611  * ***************************************************************************
1612  */
1613 template <class NODEDATA>
1614 where4tree<NODEDATA>::where4tree(const NODEDATA &iNodeData) :
1615                                      theNodeData(iNodeData) {
1616    // theChildren [] is initialized to empty vector
1617
1618    // We'll assume that the new node is a leaf node; hence, the right way to
1619    // initialize anything2Draw is to simply extract the value from the node-data.
1620    // Things can change when we actually add this child!
1621    anything2Draw = theNodeData.anything2draw();
1622    
1623    removeListbox();
1624    
1625    allExpandedChildrenWidthAsDrawn  = 0;
1626    allExpandedChildrenHeightAsDrawn = 0;
1627       // since all that exists of this subtree is the root, so far.
1628  
1629    numChildrenAddedSinceLastSort = 0;
1630 }
1631
1632 template <class NODEDATA>
1633 bool where4tree<NODEDATA>::updateAnything2Draw1(const where4TreeConstants &tc) {
1634    // called by updateAnything2Draw(), below.  Simply a non-recursive version
1635    // of that routine.
1636    bool old_anything2Draw = anything2Draw;
1637
1638    anything2Draw = false; // so far...
1639    
1640    // loop thru children; if any of them have anything to draw, then we have
1641    // something to draw (by definition)
1642    for (unsigned childlcv=0; childlcv < theChildren.size() && !anything2Draw;
1643         childlcv++)
1644       if (getChildTree(childlcv)->anything2Draw)
1645          anything2Draw = true;
1646
1647    if (!anything2Draw)
1648       // Our children have nothing to draw, but we the root node have one last chance:
1649       anything2Draw = getNodeData().anything2draw();
1650
1651    if (anything2Draw == old_anything2Draw)
1652       return false; // nothing changed
1653
1654    // Stuff changed.  Update spatial variables now!  We assume that our children have
1655    // already done that; so we just update our (the root node's) vrbles:
1656    rethink_all_expanded_children_dimensions(tc);
1657    rethink_listbox_dimensions(tc);
1658    
1659    return true;
1660 }
1661
1662 template <class NODEDATA>
1663 bool where4tree<NODEDATA>::updateAnything2Draw(const where4TreeConstants &tc) {
1664    // Outside code should call this when it has changed the NODEDATA anything2draw()
1665    // component of one or more nodes.  We will update "anything2Draw" for each node
1666    // recursively (bottom-up)
1667
1668    bool anyChanges = false; // so far...
1669
1670    // First, do the children recursively:
1671    for (unsigned childlcv=0; childlcv < theChildren.size(); childlcv++)
1672       if (getChildTree(childlcv)->updateAnything2Draw(tc))
1673          anyChanges = true;
1674
1675    // Now, do the root node:
1676    if (updateAnything2Draw1(tc))
1677       anyChanges = true;
1678
1679    return anyChanges;
1680 }
1681
1682 template <class NODEDATA>
1683 where4tree<NODEDATA>::~where4tree() {
1684    // the children need explicit deleting
1685    const unsigned numChildren = theChildren.size();
1686    for (unsigned childlcv = 0; childlcv < numChildren; childlcv++) {
1687       where4tree *theChild = getChildTree(childlcv);
1688       delete theChild;
1689    }
1690 }
1691
1692 \f
1693 /* ****************************************************************************
1694  *
1695  * Adding children
1696  * ---
1697  *     important, crude rule: unless explicitlyExpanded is specified for a
1698  *     given new child, it will be put into a listbox.
1699  * ---
1700  *
1701  * ****************************************************************************
1702  */
1703
1704 template <class NODEDATA>
1705 void where4tree<NODEDATA>::addChild(where4tree *theNewChild,
1706                                     bool explicitlyExpanded,
1707                                     const where4TreeConstants &tc,
1708                                     bool rethinkLayoutNow,
1709                                     bool resortNow) {
1710    // theNewChild _must_ have been created with C++ new -- not negotiable
1711    // theNewChild _must_ be fully initialized, too.
1712    // NOTE: In the current implementation, we always put the child into the listbox
1713    //       unless explicitlyExpanded is true.
1714    // NOTE: Even if you pass rethinkLayoutNow as true, we only rethink the listbox
1715    //       dimensions and/or the all-expanded-children dimensions, as needed.
1716    //       In all likelihood, you'll also need to rethink all-expanded-children
1717    //       dimensions for all ancestors of this node; you must do this manually.
1718
1719    const childstruct cs={theNewChild, explicitlyExpanded};
1720    this->theChildren += cs;
1721    this->numChildrenAddedSinceLastSort++;
1722
1723    if (rethinkLayoutNow && theNewChild->anything2Draw)
1724       if (explicitlyExpanded)
1725          // no need to rethink listbox dimensions, but a need to
1726          // rethink expanded children dimensions
1727          rethink_all_expanded_children_dimensions(tc);
1728       else
1729          rethink_listbox_dimensions(tc);
1730
1731    if (resortNow)
1732       this->sortChildren();
1733 }
1734
1735 template <class NODEDATA>
1736 void where4tree<NODEDATA>::doneAddingChildren(const where4TreeConstants &tc,
1737                                               bool sortNow) {
1738    // Needed only if you call ::addChild() one or more times with
1739    // rethinkGraphicsNow==false
1740    if (!updateAnything2Draw1(tc)) { // non-recursive; just affects root node
1741       // well, nothing changed w.r.t. anything2Draw, so the call didn't
1742       // update listbox/children dimensions.  Hence, we do the update manually:
1743       rethink_listbox_dimensions(tc); // this one must come first...
1744       rethink_all_expanded_children_dimensions(tc);
1745    }
1746
1747    if (sortNow)
1748       sortChildren();
1749 }
1750
1751 template <class NODEDATA>
1752 void where4tree<NODEDATA>::
1753 recursiveDoneAddingChildren(const where4TreeConstants &tc, bool sortNow) {
1754    unsigned numChildren = theChildren.size();
1755    for (unsigned i=0; i < numChildren; i++)
1756       getChildTree(i)->recursiveDoneAddingChildren(tc, sortNow);
1757
1758    doneAddingChildren(tc, sortNow);
1759 }
1760
1761 template <class NODEDATA>
1762 void where4tree<NODEDATA>::sortChildren() {
1763    // Ideal sort is as follows:
1764    // 1) if only a handful of items have been added since the last
1765    //    sort (say, <= 10), then use selection sort.
1766    // 2) if more than a handful of items have been added since the
1767    //    last sort, and there were only a handful of items previously
1768    //    in existence (say, <= 10), then just quicksort the whole thing.
1769    // 3) else, we have inserted more than a few items (unsorted), and more
1770    //    than a few items were already there (already sorted).
1771    //    Quicksort the newly-added items only.  Now we have two sorted
1772    //    subsections.  Merge those two with a mergesort's "merge".
1773    //    (But how to do an in-place mergesort?)
1774
1775    if (numChildrenAddedSinceLastSort > 0 && theChildren.size() > 1)
1776       theChildren.sort(childstruct::cmpfunc); // Vector::sort()
1777
1778    numChildrenAddedSinceLastSort = 0;
1779 }
1780
1781 template <class NODEDATA>
1782 bool where4tree<NODEDATA>::
1783 selectUnSelectFromFullPathName(const char *name, bool selectFlag) {
1784    // Use char* instead of string because the string class lacks
1785    // certain operations such as name++ to strip off 1 character.
1786    // returns true iff found
1787
1788    if (name == NULL)
1789       return false;
1790
1791    if (!anything2Draw)
1792       return false;
1793
1794    if (name[0] != '/') {
1795       // name does _not_ begin with a slash --> we are expected to
1796       // match the first part of "name".  And, if there is nothing
1797       // after the first part, we have a match.  Otherwise, continue...
1798
1799       const char *firstSlash = strchr(name, '/');
1800       if (firstSlash == NULL) {
1801          // There are no slashes.  That means we are at the end.
1802          // Either name==root-node-name or we return false
1803
1804          const bool result = (0==strcmp(name, getRootName().string_of()));
1805          if (result)
1806             if (selectFlag)
1807                highlight();
1808             else
1809                unhighlight();
1810          return result;
1811       }
1812       else {
1813          // There is at least one slash --> hence, we are not at the end
1814          // of the trail.  Let's check to see that the first component
1815          // (upto but not including the first slash) equals getRootName().
1816          // If not, we've been barking down the wrong subtree, and we return false.
1817          // Else, advance "name" to "firstSlash" and continue the walk.
1818
1819          const unsigned firstPartLen = firstSlash-name;
1820          if (firstPartLen != getRootName().length())
1821             return false;
1822
1823          // okay, lengths match...now to match the actual characters
1824          if (strstr(name, getRootName().string_of()) != name)
1825             return false;
1826
1827          name = firstSlash; // advance to the point where we begin
1828                             // searching children
1829       }
1830    }
1831
1832    // Name begins with a slash --> search children
1833    assert(*name == '/');
1834
1835    name++; // skip by the slash
1836
1837    for (unsigned i=0; i < theChildren.size(); i++)
1838       if (theChildren[i].theTree->selectUnSelectFromFullPathName(name, selectFlag))
1839          return true;
1840
1841    return false;
1842 }
1843
1844 template <class NODEDATA>
1845 vector<const NODEDATA *> where4tree<NODEDATA>::getSelections() const {
1846    // NOTE: Things would be faster if this function returned void and
1847    // takes in a reference to a vector<NODEDATA*> which is appended to
1848    // in-place...
1849
1850    vector<const NODEDATA *> result; // initially empty
1851       
1852    if (getNodeData().getHighlighted()) {
1853       const NODEDATA &theNodeData = getNodeData();
1854       result += &theNodeData;
1855    }
1856
1857    for (unsigned i=0; i < theChildren.size(); i++)
1858       result += theChildren[i].theTree->getSelections();
1859
1860    return result;
1861 }
1862
1863 template <class NODEDATA>
1864 void where4tree<NODEDATA>::recursiveClearSelections() {
1865    theNodeData.unhighlight();
1866   
1867    unsigned numChildren = theChildren.size();
1868    for (unsigned i=0; i < numChildren; i++)
1869       theChildren[i].theTree->recursiveClearSelections();
1870 }