AbstractSTRtree.h

/**********************************************************************
 *
 * GEOS - Geometry Engine Open Source
 * http://geos.osgeo.org
 *
 * Copyright (C) 2006 Refractions Research Inc.
 *
 * This is free software; you can redistribute and/or modify it under
 * the terms of the GNU Lesser General Public Licence as published
 * by the Free Software Foundation.
 * See the COPYING file for more information.
 *
 **********************************************************************/
 
#ifndef GEOS_INDEX_STRTREE_ABSTRACTSTRTREE_H
#define GEOS_INDEX_STRTREE_ABSTRACTSTRTREE_H
 
#include <geos/export.h>
 
#include <geos/index/strtree/AbstractNode.h> // for inlines
 
#include <vector>
#include <list>
#include <memory> // for unique_ptr
#include <cassert> // for inlines
#include <algorithm>
 
// Forward declarations
namespace geos {
namespace index {
class ItemVisitor;
namespace strtree {
class Boundable;
class AbstractNode;
}
}
}
 
namespace geos {
namespace index { // geos::index
namespace strtree { // geos::index::strtree
 
typedef std::vector<Boundable*> BoundableList;
 
class ItemsList;
 
class ItemsListItem {
public:
    enum type {
        item_is_geometry,
        item_is_list
    };
 
    ItemsListItem(void* item_)
        : t(item_is_geometry)
    {
        item.g = item_;
    }
    ItemsListItem(ItemsList* item_)
        : t(item_is_list)
    {
        item.l = item_;
    }
 
    type
    get_type() const
    {
        return t;
    }
 
    void*
    get_geometry() const
    {
        assert(t == item_is_geometry);
        return item.g;
    }
    ItemsList*
    get_itemslist() const
    {
        assert(t == item_is_list);
        return item.l;
    }
 
    type t;
    union {
        void* g;
        ItemsList* l;
    } item;
};
 
class ItemsList : public std::vector<ItemsListItem> {
private:
    typedef std::vector<ItemsListItem> base_type;
 
    static void
    delete_item(ItemsListItem& item)
    {
        if(ItemsListItem::item_is_list == item.t) {
            delete item.item.l;
        }
    }
 
public:
    ~ItemsList()
    {
        std::for_each(begin(), end(), &ItemsList::delete_item);
    }
 
    // lists of items need to be deleted in the end
    void
    push_back(void* item)
    {
        this->base_type::push_back(ItemsListItem(item));
    }
 
    // lists of items need to be deleted in the end
    void
    push_back_owned(ItemsList* itemList)
    {
        this->base_type::push_back(ItemsListItem(itemList));
    }
};
 
class GEOS_DLL AbstractSTRtree {
 
private:
    bool built;
    BoundableList* itemBoundables;
 
    virtual AbstractNode* createHigherLevels(
        BoundableList* boundablesOfALevel,
        int level);
 
    virtual std::unique_ptr<BoundableList> sortBoundables(const BoundableList* input) = 0;
 
    bool remove(const void* searchBounds, AbstractNode& node, void* item);
    bool removeItem(AbstractNode& node, void* item);
 
    ItemsList* itemsTree(AbstractNode* node);
 
protected:
 
    class GEOS_DLL IntersectsOp {
    public:
        virtual bool intersects(const void* aBounds,
                                const void* bBounds) = 0;
 
        virtual
        ~IntersectsOp() {}
    };
 
    AbstractNode* root;
 
    std::vector <AbstractNode*>* nodes;
 
    // Ownership to caller (TODO: return by unique_ptr)
    virtual AbstractNode* createNode(int level) = 0;
 
    virtual std::unique_ptr<BoundableList> createParentBoundables(
        BoundableList* childBoundables, int newLevel);
 
    virtual AbstractNode*
    lastNode(BoundableList* nodeList)
    {
        assert(!nodeList->empty());
        // Cast from Boundable to AbstractNode
        return static_cast<AbstractNode*>(nodeList->back());
    }
 
    virtual AbstractNode*
    getRoot()
    {
        assert(built);
        return root;
    }
 
    virtual void insert(const void* bounds, void* item);
 
    void query(const void* searchBounds, std::vector<void*>& foundItems);
 
    void query(const void* searchBounds, ItemVisitor& visitor);
 
    void query(const void* searchBounds, const AbstractNode& node, ItemVisitor& visitor);
 
    bool remove(const void* itemEnv, void* item);
 
    std::unique_ptr<BoundableList> boundablesAtLevel(int level);
 
    // @@ should be size_t, probably
    std::size_t nodeCapacity;
 
    virtual IntersectsOp* getIntersectsOp() = 0;
 
 
public:
 
    AbstractSTRtree(std::size_t newNodeCapacity)
        :
        built(false),
        itemBoundables(new BoundableList()),
        nodes(new std::vector<AbstractNode *>()),
        nodeCapacity(newNodeCapacity)
    {
        assert(newNodeCapacity > 1);
    }
 
    static bool
    compareDoubles(double a, double b)
    {
        // NOTE - strk:
        // Ternary operation is a workaround for
        // a probable MingW bug, see
        // http://trac.osgeo.org/geos/ticket/293
        return (a < b) ? true : false;
    }
 
    virtual ~AbstractSTRtree();
 
    virtual void build();
 
    virtual std::size_t
    getNodeCapacity()
    {
        return nodeCapacity;
    }
 
    virtual void query(const void* searchBounds, const AbstractNode* node, std::vector<void*>* matches);
 
    void iterate(ItemVisitor& visitor);
 
 
    virtual void boundablesAtLevel(int level, AbstractNode* top,
                                   BoundableList* boundables);
 
    ItemsList* itemsTree();
};
 
 
} // namespace geos::index::strtree
} // namespace geos::index
} // namespace geos
 
#endif // GEOS_INDEX_STRTREE_ABSTRACTSTRTREE_H