/* Helpers for smartPlacement: */

typedef struct _PosNode PosNode;

struct _PosNode
{
    gint pos;
    PosNode *lo;
    PosNode *hi;
    PosNode *next;
};

static void
add_pos (PosNode * node, PosNode ** next)
{
    gint pos = (*next)->pos;

    for (;;)
    {
        if (pos < node->pos)
        {
            if (node->lo)
            {
                node = node->lo;
                continue;
            }
            else
            {
                node->lo = (*next)++;
                break;
            }
        }
        if (pos > node->pos)
        {
            if (node->hi)
            {
                node = node->hi;
                continue;
            }
            else
            {
                node->hi = (*next)++;
                break;
            }
        }
        break; /* Position already in tree */
    }
}

static PosNode **
sort_pos (PosNode * node, PosNode ** addr)
{
    if (node->lo)
        addr = sort_pos (node->lo, addr);
    *addr = node;
    addr = &node->next;
    if (node->hi)
        addr = sort_pos (node->hi, addr);
    return addr;
}

static unsigned long
overlap_all (Client * c, gint * px, gint * py, gint frame_w, gint frame_h,
             gint full_x, gint full_y, gint full_w, gint full_h)
{
    gint i, d, x2, y2, w2, h2, mod_x, mod_y;
    Client *c2;
    ScreenInfo *screen_info = c->screen_info;
    unsigned long sum_ovl = 0;
    gint x = *px;
    gint y = *py;

    for (c2 = screen_info->clients, i = 0; i < screen_info->client_count; c2 = c2->next, i++)
    {
        if ((c2 != c) && (c2->type != WINDOW_DESKTOP)
            && (c->win_workspace == c2->win_workspace)
            && FLAG_TEST (c2->xfwm_flags, XFWM_FLAG_VISIBLE))
        {
            x2 = frameX (c2);
            y2 = frameY (c2);
            w2 = frameWidth (c2);
            h2 = frameHeight (c2);
            if (x == x2 && y == y2 && frame_w == w2 && frame_h == h2)
            {
                /* Avoid identical windows at the same position.
                 * Try a slightly shifted position instead, if possible.
                 */
                d = frameTop (c);
                if ((x - full_x) * 2 > full_w - frame_w)
                    mod_x = x - d/2;
                else
                    mod_x = x + d/2;
                if ((y - full_y) * 2 > full_h - frame_h)
                    mod_y = y - d;
                else
                    mod_y = y + d;
                if (mod_x >= full_x && mod_x + frame_w <= full_x + full_w &&
                    mod_y >= full_y && mod_y + frame_h <= full_y + full_h)
                {
                    *px = mod_x;
                    *py = mod_y;
                    return overlap_all (c, px, py, frame_w, frame_h,
                                        full_x, full_y, full_w, full_h);
                }
            }
            sum_ovl += overlap (x, y, x + frame_w, y + frame_h,
                                x2, y2, x2 + w2, y2 + h2);
        }
    }

    return sum_ovl;
}

static void
smartPlacement (Client * c, int full_x, int full_y, int full_w, int full_h)
{
    Client *c2;
    ScreenInfo *screen_info;
    guint i, count;
    gint pos, x, y, best_x, best_y, min_x, min_y, max_x, max_y;
    gint frame_width, frame_height;
    PosNode *root_h, *root_v, *next, *first_h, *first_v, *pos_h, *pos_v;
    unsigned long ovl, best_ovl;

    g_return_if_fail (c != NULL);
    TRACE ("entering smartPlacement");

    screen_info = c->screen_info;
    frame_width = frameWidth (c);
    frame_height = frameHeight (c);
    min_x = full_x + frame_width;
    min_y = full_y + frame_height;
    max_x = full_x + full_w - frame_width;
    max_y = full_y + full_h - frame_height;
    if (max_x < full_x)
        max_x = full_x;
    if (max_y < full_y)
        max_y = full_y;
    best_x = full_x;
    best_y = full_y;
    best_ovl = ULONG_MAX;
    count = 0;

    for (c2 = screen_info->clients, i = 0; i < screen_info->client_count; c2 = c2->next, i++)
    {
        if ((c2 != c) && (c2->type != WINDOW_DESKTOP)
            && (c->win_workspace == c2->win_workspace)
            && FLAG_TEST (c2->xfwm_flags, XFWM_FLAG_VISIBLE))
        {
            count++;
        }
    }

    root_h = g_malloc0 ((count + 1) * sizeof *root_h * 4);
    root_v = root_h + 1;
    next = root_v + 1;

    /* Windows may lie at the edges of the placement area */
    root_h->pos = full_x;
    root_v->pos = full_y;
    next->pos = max_x;
    add_pos (root_h, &next);
    next->pos = max_y;
    add_pos (root_v, &next);

    /* Windows may be adjacent to another window.
     * Add possible horizontal and vertical positions into a sorted binary
     * tree. This will eliminate duplicates.
     */
    for (c2 = screen_info->clients, i = 0; i < count; c2 = c2->next)
    {
        if ((c2 != c) && (c2->type != WINDOW_DESKTOP)
            && (c->win_workspace == c2->win_workspace)
            && FLAG_TEST (c2->xfwm_flags, XFWM_FLAG_VISIBLE))
        {
            pos = frameX (c2);
            if (pos > min_x)
            {
                next->pos = pos - frame_width;
                add_pos (root_h, &next);
            }
            pos += frameWidth (c2);
            if (pos < max_x)
            {
                next->pos = pos;
                add_pos (root_h, &next);
            }
            pos = frameY (c2);
            if (pos > min_y)
            {
                next->pos = pos - frame_height;
                add_pos (root_v, &next);
            }
            pos += frameHeight (c2);
            if (pos < max_y)
            {
                next->pos = pos;
                add_pos (root_v, &next);
            }
            i++;
        }
    }

    /* Create sorted linked list of position entries */
    sort_pos (root_h, &first_h);
    sort_pos (root_v, &first_v);

    /* Try all possible positions */
    for (pos_v = first_v; pos_v; pos_v = pos_v->next)
    {
        for (pos_h = first_h; pos_h; pos_h = pos_h->next)
        {
            x = pos_h->pos;
            y = pos_v->pos; /* may be modified by overlap_all */
            ovl = overlap_all (c, &x, &y, frame_width, frame_height,
                               full_x, full_y, full_w, full_h);
            /* Take the first opportunity (upper left) if no overlap or
             * identical overlaps
             */
            if (!ovl)
            {
                best_x = x;
                best_y = y;
                goto out;
            }
            if (ovl < best_ovl)
            {
                best_x = x;
                best_y = y;
                best_ovl = ovl;
            }
        }
    }

out:
    g_free(root_h);
    c->x = best_x + frameLeft (c);
    c->y = best_y + frameTop (c);
}