AbstractSTRtree.h

/**********************************************************************
 * $Id: AbstractSTRtree.h 2556 2009-06-06 22:22:28Z strk $
 *
 * GEOS - Geometry Engine Open Source
 * http://geos.refractions.net
 *
 * 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 auto_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 reinterpret_cast<ItemsList*>(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::auto_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 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 auto_ptr)
        virtual AbstractNode* createNode(int level)=0;

        virtual std::auto_ptr<BoundableList> createParentBoundables(
                        BoundableList* childBoundables, int newLevel);

        virtual AbstractNode* lastNode(BoundableList* nodes)
        {
                assert(!nodes->empty());
                // Cast from Boundable to AbstractNode
                return static_cast<AbstractNode*>( nodes->back() );
        }

        virtual AbstractNode* getRoot() {
                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::auto_ptr<BoundableList> boundablesAtLevel(int level);

        // @@ should be size_t, probably
        size_t nodeCapacity;

        virtual IntersectsOp *getIntersectsOp()=0;
 

public:

        AbstractSTRtree(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) {
                return a<b;
        }

        virtual ~AbstractSTRtree();

        virtual void build();

        virtual size_t getNodeCapacity() { return nodeCapacity; }

        virtual void query(const void* searchBounds, const AbstractNode* node, std::vector<void*>* matches);

        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

/**********************************************************************
 * $Log$
 * Revision 1.3  2006/06/12 10:49:43  strk
 * unsigned int => size_t
 *
 * Revision 1.2  2006/06/08 11:20:24  strk
 * Added missing virtual destructor to abstract classes.
 *
 * Revision 1.1  2006/03/21 10:47:34  strk
 * indexStrtree.h split
 *
 **********************************************************************/

---