5 files changed, 283 insertions, 2 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index df18b97..0f3395e 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -131,6 +131,7 @@ fluxbox_SOURCES = AtomHandler.hh ArrowButton.hh ArrowButton.cc \
         PlacementStrategy.hh \
         CascadePlacement.hh CascadePlacement.cc \
         ColSmartPlacement.hh ColSmartPlacement.cc \
+        MinOverlapPlacement.hh MinOverlapPlacement.cc \
         RowSmartPlacement.hh RowSmartPlacement.cc \
         ScreenPlacement.hh ScreenPlacement.cc \
         UnderMousePlacement.hh UnderMousePlacement.cc \
diff --git a/src/MinOverlapPlacement.cc b/src/MinOverlapPlacement.cc
new file mode 100644
index 0000000..121109f
--- /dev/null
+++ b/src/MinOverlapPlacement.cc
@@ -0,0 +1,182 @@
+// MinOverlapPlacement.cc
+// Copyright (c) 2007 Fluxbox Team (fluxgen at fluxbox dot org)
+//
+// Permission is hereby granted, free of charge, to any person obtaining a
+// copy of this software and associated documentation files (the "Software"),
+// to deal in the Software without restriction, including without limitation
+// the rights to use, copy, modify, merge, publish, distribute, sublicense,
+// and/or sell copies of the Software, and to permit persons to whom the
+// Software is furnished to do so, subject to the following conditions:
+//
+// The above copyright notice and this permission notice shall be included in
+// all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR (*it)
+// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR (*it)WISE, ARISING
+// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR (*it)
+// DEALINGS IN THE SOFTWARE.
+
+// $Id$
+
+#include "MinOverlapPlacement.hh"
+
+#include "Window.hh"
+#include "Screen.hh"
+
+ScreenPlacement::PlacementPolicy MinOverlapPlacement::s_policy = ScreenPlacement::ROWMINOVERLAPPLACEMENT;
+ScreenPlacement::RowDirection MinOverlapPlacement::s_row_dir = ScreenPlacement::LEFTRIGHT;
+ScreenPlacement::ColumnDirection MinOverlapPlacement::s_col_dir = ScreenPlacement::TOPBOTTOM;
+
+MinOverlapPlacement::MinOverlapPlacement(ScreenPlacement::PlacementPolicy policy) {
+    s_policy = policy;
+}
+
+bool MinOverlapPlacement::placeWindow(
+        const std::list<FluxboxWindow *> &windowlist,
+        const FluxboxWindow &win, int &place_x, int &place_y) {
+
+    // view (screen + head) constraints
+    int head = (signed) win.screen().getCurrHead();
+    int head_left = (signed) win.screen().maxLeft(head);
+    int head_right = (signed) win.screen().maxRight(head);
+    int head_top = (signed) win.screen().maxTop(head);
+    int head_bot = (signed) win.screen().maxBottom(head);
+
+    const ScreenPlacement &screen_placement = 
+        dynamic_cast<const ScreenPlacement &>(win.screen().placementStrategy());
+    s_row_dir = screen_placement.rowDirection();
+    s_col_dir = screen_placement.colDirection();
+
+    int win_w = win.width() + win.fbWindow().borderWidth()*2 + win.widthOffset();
+    int win_h = win.height() + win.fbWindow().borderWidth()*2 + win.heightOffset();
+
+    // we keep a set of open spaces on the desktop, sorted by size/location
+    std::set<Region> region_set;
+
+    // initialize the set of regions to contain the entire head
+    region_set.insert(Region(Region::TOPLEFT, head_left, head_top));
+    region_set.insert(Region(Region::TOPRIGHT, head_right - win_w, head_top));
+    region_set.insert(Region(Region::BOTTOMLEFT, head_left, head_bot - win_h));
+    region_set.insert(Region(Region::BOTTOMRIGHT, head_right - win_w,
+                             head_bot - win_h));
+
+    // go through the list of windows, creating other reasonable placements
+    // at the end, we'll find the one with minimum overlap
+    // the size of this set is at most 2(n+2)(n+1) (n = number of windows)
+    // finding overlaps is therefore O(n^3), but it can probably be improved
+    std::list<FluxboxWindow *>::const_reverse_iterator it = windowlist.rbegin(),
+                                                   it_end = windowlist.rend();
+    for (; it != it_end; ++it) {
+
+        // get the dimensions of the window
+        int bottom = (*it)->y() + (*it)->height() +
+            2*(*it)->frame().window().borderWidth();
+        int top = (*it)->y();
+        int right = (*it)->x() + (*it)->width() +
+            2*(*it)->frame().window().borderWidth();
+        int left = (*it)->x();
+
+        // go through the list of regions
+        // if this window overlaps that region and the new window still fits,
+        // it will create new regions to test
+        std::set<Region>::iterator reg_it = region_set.begin();
+        for (; reg_it != region_set.end(); ++reg_it) {
+
+            switch (reg_it->corner) {
+                case Region::TOPLEFT:
+                    if (right > reg_it->x && bottom > reg_it->y) {
+                        if (bottom + win_h <= head_bot)
+                            region_set.insert(Region(Region::TOPLEFT,
+                                                     reg_it->x, bottom));
+                        if (right + win_w <= head_right)
+                            region_set.insert(Region(Region::TOPLEFT,
+                                                     right, reg_it->y));
+                    }
+                    break;
+                case Region::TOPRIGHT:
+                    if (left < reg_it->x + win_w && bottom > reg_it->y) {
+                        if (bottom + win_h <= head_bot)
+                            region_set.insert(Region(Region::TOPRIGHT,
+                                                     reg_it->x, bottom));
+                        if (left - win_w >= head_left)
+                            region_set.insert(Region(Region::TOPRIGHT,
+                                                     left - win_w, reg_it->y));
+                    }
+                    break;
+                case Region::BOTTOMRIGHT:
+                    if (left < reg_it->x + win_w && top < reg_it->y + win_h) {
+                        if (top - win_h >= head_top)
+                            region_set.insert(Region(Region::BOTTOMRIGHT,
+                                                     reg_it->x, top - win_h));
+                        if (left - win_w >= head_left)
+                            region_set.insert(Region(Region::BOTTOMRIGHT,
+                                                     left - win_w, reg_it->y));
+                    }
+                    break;
+                case Region::BOTTOMLEFT:
+                    if (right > reg_it->x && top < reg_it->y + win_h) {
+                        if (top - win_h >= head_top)
+                            region_set.insert(Region(Region::BOTTOMLEFT,
+                                                     reg_it->x, top - win_h));
+                        if (right + win_w <= head_right)
+                            region_set.insert(Region(Region::BOTTOMLEFT,
+                                                     right, reg_it->y));
+                    }
+                    break;
+            }
+
+        }
+    }
+
+    // choose the region with minimum overlap
+    int min_so_far = win_w * win_h * windowlist.size() + 1;
+    std::set<Region>::iterator min_reg = region_set.end();
+
+    std::set<Region>::iterator reg_it = region_set.begin();
+    for (; reg_it != region_set.end(); ++reg_it) {
+
+        int overlap = 0;
+        it = windowlist.rbegin();
+        for (; it != windowlist.rend(); ++it) {
+
+            // get the dimensions of the window
+            int bottom = (*it)->y() + (*it)->height() +
+                2*(*it)->frame().window().borderWidth();
+            int top = (*it)->y();
+            int right = (*it)->x() + (*it)->width() +
+                2*(*it)->frame().window().borderWidth();
+            int left = (*it)->x();
+
+            // get the coordinates of the overlap region
+            int min_right = (right > reg_it->x + win_w) ?
+                reg_it->x + win_w : right;
+            int min_bottom = (bottom > reg_it->y + win_h) ?
+                reg_it->y + win_h : bottom;
+            int max_left = (left > reg_it->x) ? left : reg_it->x;
+            int max_top = (top > reg_it->y) ? top : reg_it->y;
+
+            // now compute the overlap and add to running total
+            if (min_right > max_left && min_bottom > max_top)
+                overlap += (min_right - max_left) * (min_bottom - max_top);
+
+        }
+
+        // if this placement is better, use it
+        if (overlap < min_so_far) {
+            min_reg = reg_it;
+            min_so_far = overlap;
+            if (overlap == 0) // can't do better than this
+                break;
+        }
+
+    }
+
+    // place window
+    place_x = min_reg->x;
+    place_y = min_reg->y;
+
+    return true;
+}
diff --git a/src/MinOverlapPlacement.hh b/src/MinOverlapPlacement.hh
new file mode 100644
index 0000000..20b5c95
--- /dev/null
+++ b/src/MinOverlapPlacement.hh
@@ -0,0 +1,83 @@
+// MinOverlapPlacement.hh
+// Copyright (c) 2007 Fluxbox Team (fluxgen at fluxbox dot org)
+//
+// Permission is hereby granted, free of charge, to any person obtaining a
+// copy of this software and associated documentation files (the "Software"),
+// to deal in the Software without restriction, including without limitation
+// the rights to use, copy, modify, merge, publish, distribute, sublicense,
+// and/or sell copies of the Software, and to permit persons to whom the
+// Software is furnished to do so, subject to the following conditions:
+//
+// The above copyright notice and this permission notice shall be included in
+// all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+// DEALINGS IN THE SOFTWARE.
+
+// $Id$
+
+#ifndef MINOVERLAPPLACEMENT_HH
+#define MINOVERLAPPLACEMENT_HH
+
+#include "ScreenPlacement.hh"
+
+class MinOverlapPlacement: public PlacementStrategy {
+public:
+    MinOverlapPlacement(ScreenPlacement::PlacementPolicy policy);
+
+    bool placeWindow(const std::list<FluxboxWindow *> &windowlist,
+                     const FluxboxWindow &win,
+                     int &place_x, int &place_y);
+
+private:
+    class Region {
+    public:
+
+        enum Corner {
+            TOPLEFT,
+            TOPRIGHT,
+            BOTTOMLEFT,
+            BOTTOMRIGHT
+        } corner; // indicates the corner of the window that will be placed
+
+        Region(Corner _corner, int _x, int _y):
+            corner(_corner), x(_x), y(_y) { };
+
+        // do all STL set implementations use this for sorting?
+        bool operator <(const Region &o) const {
+            // for now, I'm assuming RowSmartPlacement, so y is more important
+            switch (MinOverlapPlacement::s_policy) {
+                case ScreenPlacement::ROWMINOVERLAPPLACEMENT:
+                    // if we're making rows, y-value is most important
+                    if (y != o.y)
+                        return ((y < o.y) ^ (s_col_dir == ScreenPlacement::BOTTOMTOP));
+                    if (x != o.x)
+                        return ((x < o.x) ^ (s_row_dir == ScreenPlacement::RIGHTLEFT));
+                    return (corner < o.corner);
+                case ScreenPlacement::COLMINOVERLAPPLACEMENT:
+                    // if we're making columns, x-value is most important
+                    if (x != o.x)
+                        return ((x < o.x) ^ (s_row_dir == ScreenPlacement::RIGHTLEFT));
+                    if (y != o.y)
+                        return ((y < o.y) ^ (s_col_dir == ScreenPlacement::BOTTOMTOP));
+                    return (corner < o.corner);
+                default:
+                    return false;
+            }
+        }
+
+        // position where the top left corner of the window will be placed
+        int x, y;
+    };
+
+    static ScreenPlacement::PlacementPolicy s_policy;
+    static ScreenPlacement::RowDirection s_row_dir;
+    static ScreenPlacement::ColumnDirection s_col_dir;
+};
+
+#endif // MINOVERLAPPLACEMENT_HH
diff --git a/src/ScreenPlacement.cc b/src/ScreenPlacement.cc
index 6ba4b6f..fb79d88 100644
--- a/src/ScreenPlacement.cc
+++ b/src/ScreenPlacement.cc
@@ -25,6 +25,7 @@
 
 
 #include "RowSmartPlacement.hh"
+#include "MinOverlapPlacement.hh"
 #include "UnderMousePlacement.hh"
 #include "ColSmartPlacement.hh"
 #include "CascadePlacement.hh"
@@ -68,6 +69,10 @@ bool ScreenPlacement::placeWindow(const std::list<FluxboxWindow *> &windowlist,
         case COLSMARTPLACEMENT:
             m_strategy.reset(new ColSmartPlacement());
             break;
+        case ROWMINOVERLAPPLACEMENT:
+        case COLMINOVERLAPPLACEMENT:
+            m_strategy.reset(new MinOverlapPlacement(*m_placement_policy));
+            break;
         case CASCADEPLACEMENT:
             m_strategy.reset(new CascadePlacement(win.screen()));
             break;
@@ -137,6 +142,10 @@ void FbTk::Resource<ScreenPlacement::PlacementPolicy>::setFromString(const char
         *(*this) = ScreenPlacement::ROWSMARTPLACEMENT;
     else if (strcasecmp("ColSmartPlacement", str) == 0)
         *(*this) = ScreenPlacement::COLSMARTPLACEMENT;
+    else if (strcasecmp("RowMinOverlapPlacement", str) == 0)
+        *(*this) = ScreenPlacement::ROWMINOVERLAPPLACEMENT;
+    else if (strcasecmp("ColMinOverlapPlacement", str) == 0)
+        *(*this) = ScreenPlacement::COLMINOVERLAPPLACEMENT;
     else if (strcasecmp("UnderMousePlacement", str) == 0)
         *(*this) = ScreenPlacement::UNDERMOUSEPLACEMENT;
     else if (strcasecmp("CascadePlacement", str) == 0)
@@ -152,6 +161,10 @@ std::string FbTk::Resource<ScreenPlacement::PlacementPolicy>::getString() const
         return "RowSmartPlacement";
     case ScreenPlacement::COLSMARTPLACEMENT:
         return "ColSmartPlacement";
+    case ScreenPlacement::ROWMINOVERLAPPLACEMENT:
+        return "RowMinOverlapPlacement";
+    case ScreenPlacement::COLMINOVERLAPPLACEMENT:
+        return "ColMinOverlapPlacement";
     case ScreenPlacement::UNDERMOUSEPLACEMENT:
         return "UnderMousePlacement";
     case ScreenPlacement::CASCADEPLACEMENT:
diff --git a/src/ScreenPlacement.hh b/src/ScreenPlacement.hh
index 4326c91..79d6c21 100644
--- a/src/ScreenPlacement.hh
+++ b/src/ScreenPlacement.hh
@@ -43,8 +43,10 @@ class ScreenPlacement: public PlacementStrategy {
 public:
     enum PlacementPolicy { 
         ROWSMARTPLACEMENT, 
-        COLSMARTPLACEMENT,                            
-        CASCADEPLACEMENT, 
+        COLSMARTPLACEMENT,
+        COLMINOVERLAPPLACEMENT,
+        ROWMINOVERLAPPLACEMENT,
+        CASCADEPLACEMENT,
         UNDERMOUSEPLACEMENT
     };