gui: Add QuadTree and tests

1 files changed, 387 insertions, 0 deletions

diff --git a/gui/quadtree.h b/gui/quadtree.h
new file mode 100644
index 00000000..2b5a9df5
--- /dev/null
+++ b/gui/quadtree.h
@@ -0,0 +1,387 @@
+/*
+ *  nextpnr -- Next Generation Place and Route
+ *
+ *  Copyright (C) 2018  Serge Bazanski <q3k@symbioticeda.com>
+ *
+ *  Permission to use, copy, modify, and/or distribute this software for any
+ *  purpose with or without fee is hereby granted, provided that the above
+ *  copyright notice and this permission notice appear in all copies.
+ *
+ *  THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ *  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ *  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ *  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ *  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ *  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ *  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ */
+
+#ifndef QUADTREE_H
+#define QUADTREE_H
+
+// This file implements a quad tree used for comitting 2D axis aligned
+// bounding boxes and then retrieving them by 2D point.
+
+NEXTPNR_NAMESPACE_BEGIN
+
+// A node of a QuadTree. Internal.
+template <typename CoordinateT, typename ElementT>
+class QuadTreeNode
+{
+  public:
+    class BoundingBox {
+      friend class QuadTreeNode;
+      private:
+        CoordinateT x0_, x1_, y0_, y1_;
+      public:
+        // Standard constructor for a given (x0,y0), (x1,y1) bounding box
+        //
+        // @param x0 x coordinate of top-left corner of box
+        // @param y0 y coordinate of top-left corner of box
+        // @param x1 x coordinate of bottom-right corner of box
+        // @param y1 y coordinate of bottom-right corner of box
+        BoundingBox(CoordinateT x0, CoordinateT y0, CoordinateT x1, CoordinateT y1) :
+                x0_(x0), x1_(x1), y0_(y0), y1_(y1) {}
+
+        BoundingBox(const BoundingBox &other) :
+                x0_(other.x0_), x1_(other.x1_), y0_(other.y0_), y1_(other.y1_) {}
+
+        // Whether a bounding box contains a given points.
+        // A point is defined to be in a bounding box when it's not lesser than
+        // the lower coordinate or greater than the higher coordinate, eg:
+        // A BoundingBox of x0: 20, y0: 30, x1: 100, y1: 130 fits the following
+        // points:
+        //   [ (50, 50), (20, 50), (20, 30), (100, 130) ]
+        inline bool contains(CoordinateT x, CoordinateT y) const
+        {
+            if (x < x0_ || x > x1_)
+                return false;
+            if (y < y0_ || y > y1_)
+                return false;
+            return true;
+        }
+    };
+
+  private:
+    // A pair of Element and BoundingBox that contains it.
+    class BoundElement {
+      friend class QuadTreeNode;
+      private:
+        BoundingBox bb_;
+        ElementT elem_;
+      public:
+        BoundElement(BoundingBox bb, ElementT elem) :
+                bb_(bb), elem_(elem) {}
+    };
+
+    // The bounding box that this node describes.
+    BoundingBox bound_;
+    // How many elements should be contained in this node until it splits into
+    // sub-nodes.
+    const size_t max_elems_;
+    // Four sub-nodes or nullptr if it hasn't split yet.
+    std::unique_ptr<QuadTreeNode<CoordinateT, ElementT>[]> children_ = nullptr;
+    // Coordinates of the split.
+    // Anything < split_x is west.
+    CoordinateT splitx_;
+    // Anything < split_y is north.
+    CoordinateT splity_;
+
+    // Elements contained directly within this node and not part of children
+    // nodes.
+    std::vector<BoundElement> elems_;
+    // Depth at which this node is - root is at 0, first level at 1, etc.
+    int depth_;
+
+    // Checks whether a given bounding box fits within this node - used for 
+    // sanity checking on insertion.
+    // @param b bounding box to check
+    // @returns whether b fits in this node entirely
+    bool fits(const BoundingBox &b) const
+    {
+        if (b.x0_ < bound_.x0_ || b.x0_ > bound_.x1_) {
+            return false;
+        } else if (b.x1_ < bound_.x0_ || b.x1_ > bound_.x1_) {
+            return false;
+        } else if (b.y0_ < bound_.y0_ || b.y0_ > bound_.y1_) {
+            return false;
+        } else if (b.y1_ < bound_.y0_ || b.y1_ > bound_.y1_) {
+            return false;
+        }
+        return true;
+    }
+
+    // Used to describe one of 5 possible places an element can exist:
+    //  - the node itself (THIS)
+    //  - any of the 4 children nodes.
+    enum Quadrant {
+        THIS = -1,
+        NW = 0,
+        NE = 1,
+        SW = 2,
+        SE = 3
+    };
+
+    // Finds the quadrant to which a bounding box should go (if the node
+    // is / were to be split).
+    // @param b bounding box to check
+    // @returns quadrant in which b belongs to if the node is were to be split
+    Quadrant quadrant(const BoundingBox &b) const
+    {
+        if (children_ == nullptr) {
+            return THIS;
+        }
+
+        bool west0 = b.x0_ < splitx_;
+        bool west1 = b.x1_ < splitx_;
+        bool north0 = b.y0_ < splity_;
+        bool north1 = b.y1_ < splity_;
+
+        if (west0 && west1 && north0 && north1)
+            return NW;
+        if (!west0 && !west1 && north0 && north1)
+            return NE;
+        if (west0 && west1 && !north0 && !north1)
+            return SW;
+        if (!west0 && !west1 && !north0 && !north1)
+            return SE;
+        return THIS;
+    }
+
+    // Checks whether this node should split.
+    bool should_split() const
+    {
+        // The node shouldn't split if it's not large enough to merit it.
+        if (elems_.size() < max_elems_)
+            return false;
+
+        // The node shouldn't split if its' level is too deep (this is true for
+        // 100k+ entries, where the amount of splits causes us to lose
+        // significant CPU time on traversing the tree, or worse yet causes a
+        // stack overflow).
+        if (depth_ > 5)
+            return false;
+
+        return true;
+    }
+
+
+  public:
+    // Standard constructor for node.
+    // @param b BoundingBox this node covers.
+    // @param depth depth at which this node is in the tree
+    // @max_elems how many elements should this node contain before it splits
+    QuadTreeNode(BoundingBox b, int depth, size_t max_elems = 4) :
+            bound_(b), max_elems_(max_elems), depth_(depth)
+    {
+    }
+    // Disallow copies.
+    QuadTreeNode(const QuadTreeNode &other) = delete;
+    QuadTreeNode &operator=(const QuadTreeNode &other) = delete;
+    // Allow moves.
+    QuadTreeNode(QuadTreeNode &&other) :
+            bound_(other.bound_), max_elems_(other.max_elems_), children_(std::move(other.children_)),
+            splitx_(other.splitx_), splity_(other.splity_), elems_(std::move(other.elems_)), depth_(other.depth_)
+    {
+        other.children_ = nullptr;
+    }
+    QuadTreeNode &operator=(QuadTreeNode &&other)
+    {
+        if (this == &other)
+            return *this;
+        bound_ = other.bound_;
+        max_elems_ = other.max_elems_;
+        children_ = other.max_children_;
+        children_ = other.children_;
+        splitx_ = other.splitx_;
+        splity_ = other.splity_;
+        elems_ = std::move(other.elems_);
+        depth_ = other.depth_;
+        other.children_ = nullptr;
+        return *this;
+    }
+
+    // Insert an element at a given bounding box.
+    bool insert(const BoundingBox &k, ElementT v)
+    {
+        // Fail early if this BB doesn't fit us at all.
+        if (!fits(k)) {
+            return false;
+        }
+
+        // Do we have children?
+        if (children_ != nullptr) {
+           // Put the element either recursively into a child if it fits
+           // entirely or keep it for ourselves if not.
+           auto quad = quadrant(k);
+           if (quad == THIS) {
+               elems_.push_back(BoundElement(k, std::move(v)));
+           } else {
+               return children_[quad].insert(k, std::move(v));
+           }
+        } else {
+            // No children and not about to have any.
+            if (!should_split()) {
+                elems_.push_back(BoundElement(k, std::move(v)));
+                return true;
+            }
+            // Splitting. Calculate the split point.
+            splitx_ = (bound_.x1_ - bound_.x0_) / 2 + bound_.x0_;
+            splity_ = (bound_.y1_ - bound_.y0_) / 2 + bound_.y0_;
+            // Create the new children.
+            children_ = decltype(children_)(new QuadTreeNode<CoordinateT, ElementT>[4] {
+                // Note: not using [NW] = QuadTreeNode because that seems to
+                //       crash g++ 7.3.0.
+                /* NW */ QuadTreeNode<CoordinateT, ElementT>(BoundingBox(bound_.x0_, bound_.y0_, splitx_, splity_), depth_+1, max_elems_),
+                /* NE */ QuadTreeNode<CoordinateT, ElementT>(BoundingBox(splitx_, bound_.y0_, bound_.x1_, splity_), depth_+1, max_elems_),
+                /* SW */ QuadTreeNode<CoordinateT, ElementT>(BoundingBox(bound_.x0_, splity_, splitx_, bound_.y1_), depth_+1, max_elems_),
+                /* SE */ QuadTreeNode<CoordinateT, ElementT>(BoundingBox(splitx_, splity_, bound_.x1_, bound_.y1_), depth_+1, max_elems_),
+            });
+            // Move all elements to where they belong.
+            auto it = elems_.begin();
+            while (it != elems_.end()) {
+                auto quad = quadrant(it->bb_);
+                if (quad != THIS) {
+                    // Move to one of the children.
+                    if (!children_[quad].insert(it->bb_, std::move(it->elem_)))
+                        return false;
+                    // Delete from ourselves.
+                    it = elems_.erase(it);
+                } else {
+                    // Keep for ourselves.
+                    it++;
+                }
+            }
+            // Insert the actual element now that we've split.
+            return insert(k, std::move(v));
+        }
+        return true;
+    }
+
+    // Dump a human-readable representation of the tree to stdout.
+    void dump(int level) const
+    {
+        for (int i = 0; i < level; i++) printf("  ");
+        printf("loc: % 3d % 3d % 3d % 3d\n", bound_.x0_, bound_.y0_, bound_.x1_, bound_.y1_);
+        if (elems_.size() != 0) {
+            for (int i = 0; i < level; i++) printf("  ");
+            printf("elems: %zu\n", elems_.size());
+        }
+
+        if (children_ != nullptr) {
+            for (int i = 0; i < level; i++) printf("  ");
+            printf("children:\n");
+            children_[NW].dump(level+1);
+            children_[NE].dump(level+1);
+            children_[SW].dump(level+1);
+            children_[SE].dump(level+1);
+        }
+    }
+
+    // Return count of BoundingBoxes/Elements contained.
+    // @returns count of elements contained.
+    size_t size(void) const
+    {
+        size_t res = elems_.size();
+        if (children_ != nullptr) {
+            res += children_[NW].size();
+            res += children_[NE].size();
+            res += children_[SW].size();
+            res += children_[SE].size();
+        }
+        return res;
+    }
+
+    // Retrieve elements whose bounding boxes cover the given coordinates.
+    //
+    // @param x X coordinate of points to query.
+    // @param y Y coordinate of points to query.
+    // @returns vector of found bounding boxes
+    void get(CoordinateT x, CoordinateT y, std::vector<ElementT> &res) const
+    {
+        if (!bound_.contains(x, y))
+            return;
+
+        for (const auto &elem : elems_) {
+            const auto &bb = elem.bb_;
+            if (bb.contains(x, y)) {
+                res.push_back(elem.elem_);
+            }
+        }
+        if (children_ != nullptr) {
+            children_[NW].get(x, y, res);
+            children_[NE].get(x, y, res);
+            children_[SW].get(x, y, res);
+            children_[SE].get(x, y, res);
+        }
+    }
+};
+
+// User facing method to manage a quad tree.
+//
+// @param CoodinateT scalar type of the coordinate system - int, float, ...
+// @param ElementT type of the contained element. Must be movable or copiable.
+template <typename CoordinateT, typename ElementT>
+class QuadTree
+{
+  private:
+    // Root of the tree.
+    QuadTreeNode<CoordinateT, ElementT> root_;
+
+  public:
+    // To let user create bounding boxes of the correct type.
+    // Bounding boxes are composed of two 2D points, which designate their
+    // top-left and bottom-right corners. All its' edges are axis aligned.
+    using BoundingBox = typename QuadTreeNode<CoordinateT, ElementT>::BoundingBox;
+
+    // Standard constructor.
+    //
+    // @param b Bounding box of the entire tree - all comitted elements must
+    //          fit within in.
+    QuadTree(BoundingBox b) :
+       root_(b, 0)
+    {
+    }
+
+    // Inserts a new value at a given bounding box.e
+    // BoundingBoxes are not deduplicated - if two are pushed with the same
+    // coordinates, the first one will take precendence.
+    //
+    // @param k Bounding box at which to store value.
+    // @param v Value at a given bounding box.
+    // @returns Whether the insert was succesful.
+    bool insert(const BoundingBox &k, ElementT v)
+    {
+        return root_.insert(k, v);
+    }
+
+    // Dump a human-readable representation of the tree to stdout.
+    void dump(void) const
+    {
+        root_.dump(0);
+    }
+
+    // Return count of BoundingBoxes/Elements contained.
+    // @returns count of elements contained.
+    size_t size(void) const
+    {
+        return root_.size();
+    }
+
+    // Retrieve elements whose bounding boxes cover the given coordinates.
+    //
+    // @param x X coordinate of points to query.
+    // @param y Y coordinate of points to query.
+    // @returns vector of found bounding boxes
+    std::vector<ElementT> get(CoordinateT x, CoordinateT y) const
+    {
+        std::vector<ElementT> res;
+        root_.get(x, y, res);
+        return std::move(res);
+    }
+};
+
+NEXTPNR_NAMESPACE_END
+
+#endif