/*
* XIMQ
*
* Copyright © 1991, 1994 Digital Equipment Corporation
* All rights reserved.
*
* Permission to use, copy, modify, and distribute this software and its
* documentation for any purpose, without fee, and without written agreement is
* hereby granted, provided that the above copyright notice and the following
* two paragraphs appear in all copies of this software.
*
* IN NO EVENT SHALL DIGITAL EQUIPMENT CORPORATION BE LIABLE TO ANY PARTY FOR
* DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
* OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION.
*
* DIGITAL EQUIPMENT CORPORATION SPECIFICALLY DISCLAIMS ANY WARRANTIES,
* INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
* AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
* ON AN "AS IS" BASIS, AND DIGITAL EQUIPMENT CORPORATION HAS NO OBLIGATION TO
* PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
*
* Module:
*
* FIND_POSITION.C
*
* Abstract:
*
* This is a user-mode subroutine that can be used to find the "best"
* location for a new window. The user can specify a compass point
* where the placement should begin, and select X or Y ordering. The
* normal mode searches for unoccluded regions of the screen and then
* gives added value for being near the compass location. The user
* can also provide a associated window that the new window should
* appear near. When the associated window is supplied, some amount
* of occlusion is tolerated in the region around the associated window.
* This routine will work on both Motif and XUI, and it can be used to
* position the new window within the root window - or by supplying a
* user window instead of the root, it can be used to position subwindows.
*
* Routine description:
*
* int
* FindBestWindowPosition( display, rootWindow,
* width, height,
* placement, priority,
* xReturn, yReturn,
* maxDepth, assocWindow)
*
* display - display id
* root - id of the window to use as the root
* width, height - width and height of proposed window in pixels
* placement - placement 0 to 9 (X11 values, default = CenterGravity)
* priority - 0 = programmed, 1 = Scan X first, 2 = Scan Y first
* x, y - address of integers to return proposed location into
* maxDepth - recursion limit (default = 3)
* assocWindow - a window that the new window should be near (may be 0)
*
* Author:
*
* Fred Kleinsorge
*
* Creation date:
*
* April 1991
*
* Modification history:
*
*/
#include
#include
#include
extern int FindBestWindowPosition();
static void BuildWindowMap();
/*
* Motif has a border that is about 10 pixels. So in width there is an
* additional 20 pixels in the actual window that will be created. In
* Y there is another 20 pixel or so banner. So, fudge the window size
* to allow for decoration when doing placement. Also, the returned X,Y
* placement will be offset to anticipate decoration (since the WM may
* place the window at X,Y and let the decoration be -delta).
*
*/
#define FUDGEWIDTH 32
#define FUDGEXOFF 16
#define FUDGEHEIGHT 48
#define FUDGEBANNER 32
/*
* Control the limit of recursion. More recursion doesn't buy anything
* unless the number of layered windows is taken into account in the
* placement (it is not currently). You need a depth of at least 3 for XUI,
* but 1 is sufficient for Motif (3 doesn't hurt, it just wastes a few cycles).
*
*/
#define MAXDEPTH 3
/*
* Resolution. This defines the grid the screen is resolved to. Too many
* and the algorithm is slow, too few and the placement is coarse. The
* higher the number the finer the placement.
*
*/
#define XRES 24
#define YRES 16
/*
* FindBestWindowPosition
*
* Find the "best" position for the proposed window using a low-resolution
* map of subwindows of the "root" window and the placement information
* supplied. The placement allows compass direction of where the window
* should be located - and the priority indicates a preference in which
* direction the search is done in first (X or Y or let the routine pick).
* The "maxDepth" can limit recursion on the search for subwindows (the
* default is 3 to allow the routine to work on both XUI and Motif). The
* assocWindow provides a "gravity well" window that the window should
* appear near if possible. The normal strategy is to find unoccluded
* positions, and there is a bonus value if the position is near the
* compass location (and unoccluded) or if supplied, the associated window.
* When supplied, the assocWindow will allow "some" occlusion within the
* bonus region if there is no unoccluded area within the region.
*
* display - display id
* root - id of window to use as the root
* width, height - width and height of proposed window
* placement - gravity of placement (0-9) default = CenterGravity
* gravity - 0 = default, 1 = X, 2 = Y
* x, y - address of integers to return proposed location
* maxDepth - limit recursion (default 3)
* assocWindow - a window that the proposed window shold be near
*
*/
int FindBestWindowPosition( Display *display, Window rootWindow,
int width, int height, int placement, int gravity,
int *xReturn, int *yReturn, int maxDepth, Window assocWindow)
{
Window foo, root;
XWindowAttributes wat, bonus;
int level = 0, i, j, x, y, chunkX, chunkY, windowMap[XRES][YRES],
xOrder[XRES], yOrder[YRES], widthChunks, heightChunks, maxD,
proposedX1, proposedX2, proposedY1, proposedY2, suggestedX, suggestedY,
perfect = 0, best = 0, score = 0, adjustedWidth, adjustedHeight,
minor, major, priority = 0, bonusX1, bonusY1, bonusX2, bonusY2,
bonusValid = 0, nonOccluded;
/*
* Set X, Y or let the placement pick it priority on search
*
*/
if ((gravity > 2) || (gravity < 0)) priority = 0;
else priority = gravity;
/*
* Set max depth, this is how deep in the structure to look. Normally
* a very shallow look (1 below the root) is all that is needed.
*
*/
if (maxDepth == 0) maxD = MAXDEPTH;
else maxD = maxDepth;
/*
* Get the root window ID. Note, the "root" could simply be a regular
* window - and this call could be to find locations for subwindows.
*
*/
if (rootWindow == 0) root = XDefaultRootWindow(display);
else root = rootWindow;
/*
* Fudge the width and height to account for possible window decorations
*
*/
adjustedWidth = width + FUDGEWIDTH;
adjustedHeight = height + FUDGEHEIGHT;
/*
* Get the root width and height to set up the clipping area
*
*/
XGetWindowAttributes(display, root, &wat);
/*
* Compute the number of bits in each screen chunk for the low-res map
*
*/
chunkX = (wat.width + (XRES-1)) / XRES;
chunkY = (wat.height + (YRES-1)) / YRES;
/*
* Compute the number of chunks in the proposed window (rounded up)
*
*/
widthChunks = (adjustedWidth + (chunkX-1)) / chunkX;
heightChunks = (adjustedHeight + (chunkY-1)) / chunkY;
/*
* See if there is a window to place the new window near, and if there
* is, get it's geometry. To do this, first get the attributes to find
* it's width and then translate (0,0) into the root windows coordinate
* space, and then translate the width and height (which is +1 off) into
* the roots space.
*
*/
if (assocWindow != 0)
{
XGetWindowAttributes(display, assocWindow, &bonus);
/*
* Translate (0,0) to the root coordinate space
*
*/
if (XTranslateCoordinates(display, assocWindow, root,
0, 0,
&bonusX1, &bonusY1, &foo))
{
/*
* If it translated above, the window is on the same screen,
* Now, translate the width and height to get X2 and Y2.
*
*/
XTranslateCoordinates(display, assocWindow, root,
bonus.width-1, bonus.height-1,
&bonusX2, &bonusY2, &foo);
/*
* Turn the coordinates into chunk coordinates. The region for bonus
* points is 1.5 times the width or height of the requested window that
* surrounds the associated window.
*
* +---------------------------+ -
* | Bonus Region | 1.5 x height of requested window
* | +-----------------+ | -
* | | assocWindow | |
* | | | |
* | | | |
* | +-----------------+ |
* | |
* +---------------------------+
* ! !
* + 1.5 x width of requested window
*
*/
bonusX2 = (bonusX2 + (chunkX-1) + (adjustedWidth + (adjustedWidth/2))) / chunkX;
bonusX1 = (bonusX1 - (adjustedWidth + (adjustedWidth/2))) / chunkX;
bonusY2 = (bonusY2 + (chunkY-1) + (adjustedHeight + (adjustedHeight/2))) / chunkY;
bonusY1 = (bonusY1 - (adjustedHeight + (adjustedHeight/2))) / chunkY;
/*
* Clip it to be within the root window
*
*/
if (bonusX1 < 0) bonusX1 = 0;
if (bonusX1 >= XRES) bonusX1 = XRES-1;
if (bonusY1 < 0) bonusY1 = 0;
if (bonusY1 >= YRES) bonusY1 = YRES-1;
if (bonusX2 < 0) bonusX2 = 0;
if (bonusX2 >= XRES) bonusX2 = XRES-1;
if (bonusY2 < 0) bonusY2 = 0;
if (bonusY2 >= YRES) bonusY2 = YRES-1;
/*
* The bonus is valid
*
*/
bonusValid = 1;
}
}
/*
* Clear the window map array. This array is a map of what parts of the
* root are occluded.
*
*/
for (i = 0; i < YRES; i += 1)
{
for (j = 0; j < XRES; j += 1)
{
windowMap[j][i] = 0;
}
}
/*
* Set up the ordered list of the screen sections to search for a free
* area. This routine uses the ...Gravity symbols to select the
* pattern. The default is a center-out search, the north, south, east
* and west patterns vary the search to use top-bottom, bottom-top,
* left-right, right-left search patterns as well.
*
* 0 = CenterGravity (default, equiv to 5)
* 1 = NorthWestGravity
* 2 = NorthGravity 1 2 3
* 3 = NorthEastGravity
* 4 = WestGravity 4 5 6
* 5 = CenterGravity
* 6 = EastGravity 7 8 9
* 7 = SouthWestGravity
* 8 = SouthGravity
* 9 = SouthEastGravity
*
*/
switch (placement)
{
case NorthWestGravity:
for (i = 0; i < XRES; i += 1)
{
xOrder[i] = i;
}
for (i = 0; i < YRES; i += 1)
{
yOrder[i] = i;
}
if (priority == 0) priority = 1;
/*
* Add a bonus if located in the top-left 1/3 of the
* screen unless there is already a gravity well
* established.
*
* +-----+-----+-----+
* | | |
* | | |
* +-----+ +
* | |
* | |
* + +
* | |
* | |
* +-----+-----+-----+
*/
if (!bonusValid)
{
bonusX1 = 0;
bonusY1 = 0;
bonusX2 = XRES/3;
bonusY2 = YRES/3;
bonusValid = 1;
}
break;
case NorthGravity:
for (i = 0; i < XRES; i += 1)
{
if (i & 1) xOrder[i] = (XRES/2)+(i/2);
else xOrder[i] = ((XRES/2)-1)-(i/2);
}
for (i = 0; i < YRES; i += 1)
{
yOrder[i] = i;
}
if (priority == 0) priority = 1;
/*
* Add a bonus if located in the top 1/3 of the
* screen unless there is already a gravity well
* established.
*
* +-----+-----+-----+
* | |
* | |
* +-----------------+
* | |
* | |
* + +
* | |
* | |
* +-----+-----+-----+
*
*/
if (!bonusValid)
{
bonusX1 = 0;
bonusY1 = 0;
bonusX2 = XRES-1;
bonusY2 = YRES/3;
bonusValid = 1;
}
break;
case NorthEastGravity:
for (i = 0; i < XRES; i += 1)
{
xOrder[i] = (XRES-1) - i;
}
for (i = 0; i < YRES; i += 1)
{
yOrder[i] = i;
}
if (priority == 0) priority = 1;
/*
* Add a bonus if located in the top-right 1/3 of the
* screen unless there is already a gravity well
* established.
*
* +-----+-----+-----+
* | | |
* | | |
* + +-----+
* | |
* | |
* + +
* | |
* | |
* +-----+-----+-----+
*
*/
if (!bonusValid)
{
bonusX1 = XRES/3;
bonusY1 = 0;
bonusX2 = XRES-1;
bonusY2 = YRES/3;
bonusValid = 1;
}
break;
case WestGravity:
for (i = 0; i < XRES; i += 1)
{
xOrder[i] = i;
}
for (i = 0; i < YRES; i += 1)
{
if (i & 1) yOrder[i] = (YRES/2)+(i/2);
else yOrder[i] = ((YRES/2)-1)-(i/2);
}
if (priority == 0) priority = 2;
/*
* Add a bonus if located in the left 1/3 of the
* screen unless there is already a gravity well
* established.
*
* +-----+-----+-----+
* | | |
* | | |
* + | +
* | | |
* | | |
* + | +
* | | |
* | | |
* +-----+-----+-----+
*
*/
if (!bonusValid)
{
bonusX1 = 0;
bonusY1 = 0;
bonusX2 = XRES/3;
bonusY2 = YRES-1;
bonusValid = 1;
}
break;
case EastGravity:
for (i = 0; i < XRES; i += 1)
{
xOrder[i] = (XRES-1) - i;
}
for (i = 0; i < YRES; i += 1)
{
if (i & 1) yOrder[i] = (YRES/2)+(i/2);
else yOrder[i] = ((YRES/2)-1)-(i/2);
}
if (priority == 0) priority = 2;
/*
* Add a bonus if located in the right 1/3 of the
* screen unless there is already a gravity well
* established.
*
* +-----+-----+-----+
* | | |
* | | |
* + | +
* | | |
* | | |
* + | +
* | | |
* | | |
* +-----+-----+-----+
*
*/
if (!bonusValid)
{
bonusX1 = XRES/3;
bonusY1 = 0;
bonusX2 = XRES-1;
bonusY2 = YRES-1;
bonusValid = 1;
}
break;
case SouthWestGravity:
for (i = 0; i < XRES; i += 1)
{
xOrder[i] = i;
}
for (i = 0; i < YRES; i += 1)
{
yOrder[i] = (YRES-1) - i;
}
if (priority == 0) priority = 1;
/*
* Add a bonus if located in the bottom-left 1/3 of the
* screen unless there is already a gravity well
* established.
*
* +-----+-----+-----+
* | |
* | |
* + +
* | |
* | |
* +-----+ +
* | | |
* | | |
* +-----+-----+-----+
*
*/
if (!bonusValid)
{
bonusX1 = 0;
bonusY1 = YRES/3;
bonusX2 = XRES/3;
bonusY2 = YRES-1;
bonusValid = 1;
}
break;
case SouthGravity:
for (i = 0; i < XRES; i += 1)
{
if (i & 1) xOrder[i] = (XRES/2)+(i/2);
else xOrder[i] = ((XRES/2)-1)-(i/2);
}
for (i = 0; i < YRES; i += 1)
{
yOrder[i] = (YRES-1) - i;
}
if (priority == 0) priority = 1;
/*
* Add a bonus if located in the bottom 1/3 of the
* screen unless there is already a gravity well
* established.
*
* +-----+-----+-----+
* | |
* | |
* + +
* | |
* | |
* +-----------------+
* | |
* | |
* +-----+-----+-----+
*
*/
if (!bonusValid)
{
bonusX1 = 0;
bonusY1 = YRES/3;
bonusX2 = XRES-1;
bonusY2 = YRES-1;
bonusValid = 1;
}
break;
case SouthEastGravity:
for (i = 0; i < XRES; i += 1)
{
xOrder[i] = (XRES-1) - i;
}
for (i = 0; i < YRES; i += 1)
{
yOrder[i] = (YRES-1) - i;
}
if (priority == 0) priority = 1;
/*
* Add a bonus if located in the bottom-right 1/3 of the
* screen unless there is already a gravity well
* established.
*
* +-----+-----+-----+
* | |
* | |
* + +
* | |
* | |
* + +-----+
* | | |
* | | |
* +-----+-----+-----+
*
*/
if (!bonusValid)
{
bonusX1 = XRES/3;
bonusY1 = YRES/3;
bonusX2 = XRES-1;
bonusY2 = YRES-1;
bonusValid = 1;
}
break;
case CenterGravity:
default:
for (i = 0; i < XRES; i += 1)
{
if (i & 1) xOrder[i] = (XRES/2)+(i/2);
else xOrder[i] = ((XRES/2)-1)-(i/2);
}
for (i = 0; i < YRES; i += 1)
{
if (i & 1) yOrder[i] = (YRES/2)+(i/2);
else yOrder[i] = ((YRES/2)-1)-(i/2);
}
if (priority == 0) priority = 1;
/*
* Add a bonus if located in the middle 1/3 of the
* screen unless there is already a gravity well
* established.
*
* +-----+-----+-----+
* | |
* | |
* + +-----+ +
* | | | |
* | | | |
* + +-----+ +
* | |
* | |
* +-----+-----+-----+
*
*/
if (!bonusValid)
{
bonusX1 = XRES/3;
bonusY1 = YRES/3;
bonusX2 = bonusX1 * 2;
bonusY2 = bonusY1 * 2;
bonusValid = 1;
}
break;
}
/*
* Walk the window tree and build the occlusion map
*
*/
BuildWindowMap( display, root, 0, 0, 0,
chunkX, chunkY, maxD, &windowMap,
wat.x, wat.y, wat.width-1, wat.height-1);
/*
* Now find the best fit. A "perfect score" is the first completely
* empty area found in our scan using the pattern we built earlier.
* If there is a associated window - then a perfect score is double
* the normal perfect score. This means that a unoccluded spot was
* found in the bonus area around the associated window.
*
*/
best = 0;
/*
* Get the score for an unoccluded window
*
*/
nonOccluded = (heightChunks * widthChunks);
/*
* If the bonus area is valid, add it
*
*/
if (bonusValid)
{
/*
* A perfect score would be twice the unoccluded score
*
*/
perfect = nonOccluded * 2;
}
else
perfect = nonOccluded;
/*
* Select X or Y precedence
*
*/
if (priority > 1)
{
major = XRES;
minor = YRES;
}
else
{
major = YRES;
minor = XRES;
}
/*
* Major
*
*/
for (i = 0; i < major; i += 1)
{
/*
* Minor
*
*/
for (j = 0; j < minor; j += 1)
{
/*
* Propose a location. Use the ordered search list and locate
* a rectangle.
*
*/
if (priority > 1)
{
proposedX1 = xOrder[i] - (widthChunks/2);
proposedY1 = yOrder[j] - (heightChunks/2);
}
else
{
proposedX1 = xOrder[j] - (widthChunks/2);
proposedY1 = yOrder[i] - (heightChunks/2);
}
if (proposedX1 < 0) proposedX1 = 0;
if (proposedY1 < 0) proposedY1 = 0;
proposedX2 = proposedX1 + (widthChunks-1);
if (proposedX2 >= XRES) proposedX2 = XRES-1;
proposedY2 = proposedY1 + (heightChunks-1);
if (proposedY2 >= YRES) proposedY2 = YRES-1;
score = 0;
/*
* For each unoccluded chunk, score a point
*
*/
for (y = proposedY1; y <= proposedY2; y += 1)
{
for (x = proposedX1; x <= proposedX2; x += 1)
{
if (windowMap[x][y] == 0) score += 1;
}
}
/*
* Now, try to localize the window
*
*/
if (bonusValid)
{
int xx = proposedX1;
int yy = proposedY1;
/*
* Trivial reject
*
*/
if ((proposedX1 > bonusX2) ||
(proposedY1 > bonusY2) ||
(proposedX2 < bonusX1) ||
(proposedY2 < bonusY1))
{
}
else
{
/*
* Intersect the window with the bonus region
*
*/
if (bonusX1 > proposedX1) proposedX1 = bonusX1;
if (bonusY1 > proposedY1) proposedY1 = bonusY1;
if (bonusX2 < proposedX2) proposedX2 = bonusX2;
if (bonusY2 < proposedY2) proposedY2 = bonusY2;
/*
* If this is a real window, then add 1 for each block that
* intersects and is unoccluded (a strong relationship that
* allows "some" overlap) - if it is synthetic then the bonus
* only counts if there is no occlusion, and it is only worth
* 1 point (a weak relationship that encourages no overlap).
*
*/
if (assocWindow != 0)
{
/*
* For each unoccluded chunk of the bonus region,
* score a point
*
*/
for (y = proposedY1; y <= proposedY2; y += 1)
{
for (x = proposedX1; x <= proposedX2; x += 1)
{
if (windowMap[x][y] == 0) score += 1;
}
}
}
else
if (score >= nonOccluded) score += 1;
}
proposedX1 = xx;
proposedY1 = yy;
}
/*
* Remember the high score as it's suggested location
*
*/
if (score > best)
{
best = score;
suggestedX = proposedX1;
suggestedY = proposedY1;
}
if (score == perfect) break;
}
/*
* Exit from the loop if we detect a perfect score
*
*/
if (score == perfect) break;
}
/*
* Now return the suggestion
*
*/
*xReturn = (suggestedX * chunkX) + FUDGEXOFF;
*yReturn = (suggestedY * chunkY) + FUDGEBANNER;
/*
* Return the score, in case someone is interested
*
*/
return (score);
}
/*
* void BuildWindowMap(display, window, level, xOff, yOff,
* chunkX, chunkY, maxDepth, windowMap,
* clipX1, clipY1, clipX2, clipY2)
*
* Build a map representing the occupied portions of the root window. This
* procedure is recursive to a programmable depth.
*
* display - display ID
* window - window ID of current level
* level - how deep we currently are
* XOff, YOff - Accumulated offset from root (0,0)
* chunkX, chunkY - number of bits for window map resolution
* maxDepth - How deep can the recursion go
* windowMap - Address of window map array
* clip.. - Bounds to clip window against
*
*/
void BuildWindowMap(display, window, level, xOff, yOff,
chunkX, chunkY, maxDepth, windowMap,
clipX1, clipY1, clipX2, clipY2)
Display *display;
Window window;
int level, xOff, yOff, chunkX, chunkY, maxDepth, windowMap[XRES][YRES];
{
Window root, parent, *children;
int nchildren, x, x1, x2, y, y1, y2, w, h, weight;
XWindowAttributes wat;
{
/*
* Get information about the window
*
*/
XGetWindowAttributes(display, window, &wat);
/*
* Ignore unmapped windows
*
*/
if (wat.map_state == IsUnmapped)
{
return;
}
/*
* Get actual x and y positions by accumulating the offset
* from the root.
*
*/
x = wat.x + xOff;
y = wat.y + yOff;
w = x + wat.width;
h = y + wat.height;
/*
* Do a trivial reject for windows that are not on the screen.
*
*/
if ( (w < clipX1) || (h < clipY1) || (x > clipX2) || (y > clipY2))
{
return; /* Window is not in the clipping bounds */
}
/*
* Compute intersection of the clip and the window
*
*/
if (w > clipX2) w = clipX2;
if (h > clipY2) h = clipY2;
if (x < clipX1) x = clipX1;
if (y < clipY1) y = clipY1;
/*
* Find the windows children (if any)
*
*/
XQueryTree(display, window, &root, &parent, &children, &nchildren);
/*
* If this isn't the root, then build the screen map of window coverage
*
*/
if (window != root)
{
x1 = x / chunkX;
y1 = y / chunkY;
x2 = w / chunkX;
y2 = h / chunkY;
/*
* If the window covers the entire area - ignore it. It means
* that there is complete occlusion. So why bother. This
* handles the XUI pseudo-root as well.
*
*/
if ((x1 != 0) || (x2 != XRES-1) || (y1 != 0) || (y2 != YRES-1))
{
for (h = y1; h <= y2; h += 1)
{
for (w = x1; w <= x2; w += 1)
{
windowMap[w][h] += 1;
}
}
}
}
/*
* Recurse for each child until the max depth is reached or there
* are no more children.
*
*/
if (nchildren)
{
register int i;
register Window *child;
/*
* Recurse for every child
*
*/
if (level+1 <= maxDepth)
for (i = 0, child = children; i < nchildren; ++i, ++child)
{
BuildWindowMap(display, *child, level+1, x, y,
chunkX, chunkY, maxDepth, windowMap,
clipX1, clipY1, clipX2, clipY2);
}
/*
* The query allocates a chunk of memory that needs to be freed
*
*/
XFree(children);
}
}
}