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;
//typedef std::list<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);

#if 0
    std::vector<void*>*
    query(const void* searchBounds)
    {
        vector<void*>* matches = new vector<void*>();
        query(searchBounds, *matches);
        return matches;
    }
#endif
    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