92 changes: 43 additions & 49 deletions src/core/spatialindex/include/Point.h
View file
Original file line number Diff line number Diff line change
@@ -1,4 +1,4 @@
// Tools Library
// Spatial Index Library
//
// Copyright (C) 2004 Navel Ltd.
//
Expand All @@ -19,65 +19,59 @@
// Email:
// mhadji@gmail.com

#ifndef __tools_geometry_point_h
#define __tools_geometry_point_h
#pragma once

namespace Tools
namespace SpatialIndex
{
namespace Geometry
class SIDX_DLL Point : public Tools::IObject, public virtual IShape
{
class Point : public IObject, public virtual IShape
{
public:
Point();
Point( const double* pCoords, unsigned long dimension );
Point( const Point& p );
virtual ~Point();
public:
Point();
Point( const double* pCoords, uint32_t dimension );
Point( const Point& p );
virtual ~Point();

virtual Point& operator=( const Point& p );
virtual bool operator==( const Point& p ) const;
virtual Point& operator=( const Point& p );
virtual bool operator==( const Point& p ) const;

//
// IObject interface
//
virtual Point* clone();
//
// IObject interface
//
virtual Point* clone();

//
// ISerializable interface
//
virtual unsigned long getByteArraySize();
virtual void loadFromByteArray( const byte* data );
virtual void storeToByteArray( byte** data, unsigned long& length );
//
// ISerializable interface
//
virtual uint32_t getByteArraySize();
virtual void loadFromByteArray( const byte* data );
virtual void storeToByteArray( byte** data, uint32_t& length );

//
// IShape interface
//
virtual bool intersectsShape( const IShape& in ) const;
virtual bool containsShape( const IShape& in ) const;
virtual bool touchesShape( const IShape& in ) const;
virtual void getCenter( Point& out ) const;
virtual unsigned long getDimension() const;
virtual void getMBR( Region& out ) const;
virtual double getArea() const;
virtual double getMinimumDistance( const IShape& in ) const;
//
// IShape interface
//
virtual bool intersectsShape( const IShape& in ) const;
virtual bool containsShape( const IShape& in ) const;
virtual bool touchesShape( const IShape& in ) const;
virtual void getCenter( Point& out ) const;
virtual uint32_t getDimension() const;
virtual void getMBR( Region& out ) const;
virtual double getArea() const;
virtual double getMinimumDistance( const IShape& in ) const;

virtual double getMinimumDistance( const Point& p ) const;
virtual double getMinimumDistance( const Point& p ) const;

virtual double getCoordinate( unsigned long index ) const;
virtual double getCoordinate( uint32_t index ) const;

virtual void makeInfinite( unsigned long dimension );
virtual void makeDimension( unsigned long dimension );
virtual void makeInfinite( uint32_t dimension );
virtual void makeDimension( uint32_t dimension );

public:
unsigned long m_dimension;
double* m_pCoords;
public:
uint32_t m_dimension;
double* m_pCoords;

friend class Region;
friend std::ostream& operator<<( std::ostream& os, const Point& pt );
}; // Point
friend class Region;
friend SIDX_DLL std::ostream& operator<<( std::ostream& os, const Point& pt );
}; // Point

std::ostream& operator<<( std::ostream& os, const Point& pt );
}
SIDX_DLL std::ostream& operator<<( std::ostream& os, const Point& pt );
}

#endif /*__tools_geometry_point_h*/
88 changes: 43 additions & 45 deletions src/core/spatialindex/include/RTree.h
View file
Original file line number Diff line number Diff line change
Expand Up @@ -19,86 +19,84 @@
// Email:
// mhadji@gmail.com

#ifndef __spatialindex_rtree_h
#define __spatialindex_rtree_h
#pragma once

namespace SpatialIndex
{
namespace RTree
{
enum RTreeVariant
SIDX_DLL enum RTreeVariant
{
RV_LINEAR = 0x0,
RV_QUADRATIC,
RV_RSTAR
};

enum BulkLoadMethod
SIDX_DLL enum BulkLoadMethod
{
BLM_STR = 0x0
};

enum PersistenObjectIdentifier
SIDX_DLL enum PersistenObjectIdentifier
{
PersistentIndex = 0x1,
PersistentLeaf = 0x2
};

enum RangeQueryType
SIDX_DLL enum RangeQueryType
{
ContainmentQuery = 0x1,
IntersectionQuery = 0x2
};

class Data : public IData, public Tools::ISerializable
class SIDX_DLL Data : public IData, public Tools::ISerializable
{
public:
Data( unsigned long len, byte* pData, Tools::Geometry::Region& r, long id );
Data( uint32_t len, byte* pData, Region& r, id_type id );
virtual ~Data();

virtual Data* clone();
virtual long getIdentifier() const;
virtual id_type getIdentifier() const;
virtual void getShape( IShape** out ) const;
virtual void getData( unsigned long& len, byte** data ) const;
virtual unsigned long getByteArraySize();
virtual void getData( uint32_t& len, byte** data ) const;
virtual uint32_t getByteArraySize();
virtual void loadFromByteArray( const byte* data );
virtual void storeToByteArray( byte** data, unsigned long& len );
virtual void storeToByteArray( byte** data, uint32_t& len );

long m_id;
Tools::Geometry::Region m_region;
id_type m_id;
Region m_region;
byte* m_pData;
unsigned long m_dataLength;
uint32_t m_dataLength;
}; // Data

#ifdef _MSC_VER
// MSVC didn't like the difference in parameter names between declaration
// definition
extern ISpatialIndex* returnRTree( IStorageManager& sm, Tools::PropertySet& ps );
#else
extern ISpatialIndex* returnRTree( IStorageManager& in0, Tools::PropertySet& in1 );
#endif//_MSC_VER
extern ISpatialIndex* createNewRTree(
IStorageManager& sm,
double fillFactor,
unsigned long indexCapacity,
unsigned long leafCapacity,
unsigned long dimension,
RTreeVariant rv,
long& indexIdentifier
);
extern ISpatialIndex* createAndBulkLoadNewRTree(
BulkLoadMethod m,
IDataStream& stream,
IStorageManager& sm,
double fillFactor,
unsigned long indexCapacity,
unsigned long leafCapacity,
unsigned long dimension,
RTreeVariant rv,
long& indexIdentifier
);
extern ISpatialIndex* loadRTree( IStorageManager& in, long indexIdentifier );
SIDX_DLL ISpatialIndex* returnRTree( IStorageManager& ind, Tools::PropertySet& in );
SIDX_DLL ISpatialIndex* createNewRTree(
IStorageManager& sm,
double fillFactor,
uint32_t indexCapacity,
uint32_t leafCapacity,
uint32_t dimension,
RTreeVariant rv,
id_type& indexIdentifier
);
SIDX_DLL ISpatialIndex* createAndBulkLoadNewRTree(
BulkLoadMethod m,
IDataStream& stream,
IStorageManager& sm,
double fillFactor,
uint32_t indexCapacity,
uint32_t leafCapacity,
uint32_t dimension,
RTreeVariant rv,
id_type& indexIdentifier
);
SIDX_DLL ISpatialIndex* createAndBulkLoadNewRTree(
BulkLoadMethod m,
IDataStream& stream,
IStorageManager& sm,
Tools::PropertySet& ps,
id_type& indexIdentifier
);
SIDX_DLL ISpatialIndex* loadRTree( IStorageManager& in, id_type indexIdentifier );
}
}

#endif /* __spatialindex_rtree_h */
152 changes: 73 additions & 79 deletions src/core/spatialindex/include/Region.h
View file
Original file line number Diff line number Diff line change
@@ -1,4 +1,4 @@
// Tools Library
// Spatial Index Library
//
// Copyright (C) 2004 Navel Ltd.
//
Expand All @@ -19,85 +19,79 @@
// Email:
// mhadji@gmail.com

#ifndef __tools_geometry_region_h
#define __tools_geometry_region_h
#pragma once

namespace Tools
namespace SpatialIndex
{
namespace Geometry
class SIDX_DLL Region : public Tools::IObject, public virtual IShape
{
class Region : public IObject, public virtual IShape
{
public:
Region();
Region( const double* pLow, const double* pHigh, unsigned long dimension );
Region( const Point& low, const Point& high );
Region( const Region& in );
virtual ~Region();

virtual Region& operator=( const Region& r );
virtual bool operator==( const Region& ) const;

//
// IObject interface
//
virtual Region* clone();

//
// ISerializable interface
//
virtual unsigned long getByteArraySize();
virtual void loadFromByteArray( const byte* data );
virtual void storeToByteArray( byte** data, unsigned long& length );

//
// IShape interface
//
virtual bool intersectsShape( const IShape& in ) const;
virtual bool containsShape( const IShape& in ) const;
virtual bool touchesShape( const IShape& in ) const;
virtual void getCenter( Point& out ) const;
virtual unsigned long getDimension() const;
virtual void getMBR( Region& out ) const;
virtual double getArea() const;
virtual double getMinimumDistance( const IShape& in ) const;

virtual bool intersectsRegion( const Region& in ) const;
virtual bool containsRegion( const Region& in ) const;
virtual bool touchesRegion( const Region& in ) const;
virtual double getMinimumDistance( const Region& in ) const;

virtual bool containsPoint( const Point& in ) const;
virtual bool touchesPoint( const Point& in ) const;
virtual double getMinimumDistance( const Point& in ) const;

virtual Region getIntersectingRegion( const Region& r ) const;
virtual double getIntersectingArea( const Region& in ) const;
virtual double getMargin() const;

virtual void combineRegion( const Region& in );
virtual void combinePoint( const Point& in );
virtual void getCombinedRegion( Region& out, const Region& in ) const;

virtual double getLow( unsigned long index ) const;
virtual double getHigh( unsigned long index ) const;

virtual void makeInfinite( unsigned long dimension );
virtual void makeDimension( unsigned long dimension );

private:
void initialize( const double* pLow, const double* pHigh, unsigned long dimension );

public:
unsigned long m_dimension;
double* m_pLow;
double* m_pHigh;

friend std::ostream& operator<<( std::ostream& os, const Region& r );
}; // Region

std::ostream& operator<<( std::ostream& os, const Region& r );
}
public:
Region();
Region( const double* pLow, const double* pHigh, uint32_t dimension );
Region( const Point& low, const Point& high );
Region( const Region& in );
virtual ~Region();

virtual Region& operator=( const Region& r );
virtual bool operator==( const Region& ) const;

//
// IObject interface
//
virtual Region* clone();

//
// ISerializable interface
//
virtual uint32_t getByteArraySize();
virtual void loadFromByteArray( const byte* data );
virtual void storeToByteArray( byte** data, uint32_t& length );

//
// IShape interface
//
virtual bool intersectsShape( const IShape& in ) const;
virtual bool containsShape( const IShape& in ) const;
virtual bool touchesShape( const IShape& in ) const;
virtual void getCenter( Point& out ) const;
virtual uint32_t getDimension() const;
virtual void getMBR( Region& out ) const;
virtual double getArea() const;
virtual double getMinimumDistance( const IShape& in ) const;

virtual bool intersectsRegion( const Region& in ) const;
virtual bool containsRegion( const Region& in ) const;
virtual bool touchesRegion( const Region& in ) const;
virtual double getMinimumDistance( const Region& in ) const;

virtual bool containsPoint( const Point& in ) const;
virtual bool touchesPoint( const Point& in ) const;
virtual double getMinimumDistance( const Point& in ) const;

virtual Region getIntersectingRegion( const Region& r ) const;
virtual double getIntersectingArea( const Region& in ) const;
virtual double getMargin() const;

virtual void combineRegion( const Region& in );
virtual void combinePoint( const Point& in );
virtual void getCombinedRegion( Region& out, const Region& in ) const;

virtual double getLow( uint32_t index ) const;
virtual double getHigh( uint32_t index ) const;

virtual void makeInfinite( uint32_t dimension );
virtual void makeDimension( uint32_t dimension );

private:
void initialize( const double* pLow, const double* pHigh, uint32_t dimension );

public:
uint32_t m_dimension;
double* m_pLow;
double* m_pHigh;

friend SIDX_DLL std::ostream& operator<<( std::ostream& os, const Region& r );
}; // Region

SIDX_DLL std::ostream& operator<<( std::ostream& os, const Region& r );
}

#endif /*__tools_geometry_region_h*/
279 changes: 154 additions & 125 deletions src/core/spatialindex/include/SpatialIndex.h
View file
Original file line number Diff line number Diff line change
Expand Up @@ -19,193 +19,222 @@
// Email:
// mhadji@gmail.com

#ifndef __spatialindex_h
#define __spatialindex_h
#pragma once

#include <assert.h>
#include <iostream>
#include <vector>
#include <map>
#include <limits>
#include <stack>
#include <queue>
#include <set>
#include <cmath>
#include <cstring>
#include <sstream>
#include "tools/Tools.h"

#include "Tools.h"

using namespace Tools::Geometry;

# if !HAVE_BZERO
# define bzero(d, n) memset((d), 0, (n))
# endif
#ifndef M_PI_2
#define M_PI_2 1.57079632679489661922
#endif

namespace SpatialIndex
{
//const std::string VERSION;
//const std::string DATE;
class Point;
class Region;

enum CommandType
typedef int64_t id_type;

SIDX_DLL enum CommandType
{
CT_NODEREAD = 0x0,
CT_NODEDELETE,
CT_NODEWRITE
};

class SIDX_DLL InvalidPageException : public Tools::Exception
{
public:
InvalidPageException( id_type id );
virtual ~InvalidPageException() {}
virtual std::string what();

private:
std::string m_error;
}; // InvalidPageException

//
// Interfaces
//
interface IEntry : public Tools::IObject

class SIDX_DLL IShape : public Tools::ISerializable
{
public:
virtual long getIdentifier() const = 0;
virtual void getShape( IShape** out ) const = 0;
virtual ~IEntry() {}
public:
virtual bool intersectsShape( const IShape& in ) const = 0;
virtual bool containsShape( const IShape& in ) const = 0;
virtual bool touchesShape( const IShape& in ) const = 0;
virtual void getCenter( Point& out ) const = 0;
virtual uint32_t getDimension() const = 0;
virtual void getMBR( Region& out ) const = 0;
virtual double getArea() const = 0;
virtual double getMinimumDistance( const IShape& in ) const = 0;
virtual ~IShape() {}
}; // IShape

class SIDX_DLL ITimeShape : public Tools::IInterval
{
public:
virtual bool intersectsShapeInTime( const ITimeShape& in ) const = 0;
virtual bool intersectsShapeInTime( const Tools::IInterval& ivI, const ITimeShape& in ) const = 0;
virtual bool containsShapeInTime( const ITimeShape& in ) const = 0;
virtual bool containsShapeInTime( const Tools::IInterval& ivI, const ITimeShape& in ) const = 0;
virtual bool touchesShapeInTime( const ITimeShape& in ) const = 0;
virtual bool touchesShapeInTime( const Tools::IInterval& ivI, const ITimeShape& in ) const = 0;
virtual double getAreaInTime() const = 0;
virtual double getAreaInTime( const Tools::IInterval& ivI ) const = 0;
virtual double getIntersectingAreaInTime( const ITimeShape& r ) const = 0;
virtual double getIntersectingAreaInTime( const Tools::IInterval& ivI, const ITimeShape& r ) const = 0;
virtual ~ITimeShape() {}
}; // ITimeShape

class SIDX_DLL IEvolvingShape
{
public:
virtual void getVMBR( Region& out ) const = 0;
virtual void getMBRAtTime( double t, Region& out ) const = 0;
virtual ~IEvolvingShape() {}
}; // IEvolvingShape

class SIDX_DLL IEntry : public Tools::IObject
{
public:
virtual id_type getIdentifier() const = 0;
virtual void getShape( IShape** out ) const = 0;
virtual ~IEntry() {}
}; // IEntry

interface INode : public IEntry, public Tools::ISerializable
class SIDX_DLL INode : public IEntry, public Tools::ISerializable
{
public:
virtual unsigned long getChildrenCount() const = 0;
virtual long getChildIdentifier( unsigned long index ) const = 0;
virtual void getChildShape( unsigned long index, IShape** out ) const = 0;
virtual unsigned long getLevel() const = 0;
virtual bool isIndex() const = 0;
virtual bool isLeaf() const = 0;
virtual ~INode() {}
public:
virtual uint32_t getChildrenCount() const = 0;
virtual id_type getChildIdentifier( uint32_t index ) const = 0;
virtual void getChildData( uint32_t index, uint32_t& len, byte** data ) const = 0;
virtual void getChildShape( uint32_t index, IShape** out ) const = 0;
virtual uint32_t getLevel() const = 0;
virtual bool isIndex() const = 0;
virtual bool isLeaf() const = 0;
virtual ~INode() {}
}; // INode

interface IData : public IEntry
class SIDX_DLL IData : public IEntry
{
public:
virtual void getData( unsigned long& len, byte** data ) const = 0;
virtual ~IData() {}
public:
virtual void getData( uint32_t& len, byte** data ) const = 0;
virtual ~IData() {}
}; // IData

interface IDataStream : public Tools::IObjectStream
class SIDX_DLL IDataStream : public Tools::IObjectStream
{
public:
virtual IData* getNext() = 0;
virtual ~IDataStream() {}
public:
virtual IData* getNext() = 0;
virtual ~IDataStream() {}
}; // IDataStream

interface ICommand
class SIDX_DLL ICommand
{
public:
virtual void execute( const INode& in ) = 0;
virtual ~ICommand() {}
public:
virtual void execute( const INode& in ) = 0;
virtual ~ICommand() {}
}; // ICommand

interface INearestNeighborComparator
class SIDX_DLL INearestNeighborComparator
{
public:
virtual double getMinimumDistance( const IShape& query, const IShape& entry ) = 0;
virtual double getMinimumDistance( const IShape& query, const IData& data ) = 0;
virtual ~INearestNeighborComparator() {}
public:
virtual double getMinimumDistance( const IShape& query, const IShape& entry ) = 0;
virtual double getMinimumDistance( const IShape& query, const IData& data ) = 0;
virtual ~INearestNeighborComparator() {}
}; // INearestNeighborComparator

interface IStorageManager
class SIDX_DLL IStorageManager
{
public:
virtual void loadByteArray( const long id, unsigned long& len, byte** data ) = 0;
virtual void storeByteArray( long& id, const unsigned long len, const byte* const data ) = 0;
virtual void deleteByteArray( const long id ) = 0;
virtual ~IStorageManager() {}
public:
virtual void loadByteArray( const id_type id, uint32_t& len, byte** data ) = 0;
virtual void storeByteArray( id_type& id, const uint32_t len, const byte* const data ) = 0;
virtual void deleteByteArray( const id_type id ) = 0;
virtual ~IStorageManager() {}
}; // IStorageManager

interface IVisitor
class SIDX_DLL IVisitor
{
public:
virtual void visitNode( const INode& in ) = 0;
virtual void visitData( const IData& in ) = 0;
virtual void visitData( std::vector<const IData*>& v ) = 0;
virtual ~IVisitor() {}
public:
virtual void visitNode( const INode& in ) = 0;
virtual void visitData( const IData& in ) = 0;
virtual void visitData( std::vector<const IData*>& v ) = 0;
virtual ~IVisitor() {}
}; // IVisitor

interface IQueryStrategy
class SIDX_DLL IQueryStrategy
{
public:
virtual void getNextEntry( const IEntry& previouslyFetched, long& nextEntryToFetch, bool& bFetchNextEntry ) = 0;
virtual ~IQueryStrategy() {}
public:
virtual void getNextEntry( const IEntry& previouslyFetched, id_type& nextEntryToFetch, bool& bFetchNextEntry ) = 0;
virtual ~IQueryStrategy() {}
}; // IQueryStrategy

interface IStatistics
class SIDX_DLL IStatistics
{
public:
virtual unsigned long getReads() const = 0;
virtual unsigned long getWrites() const = 0;
virtual unsigned long getNumberOfNodes() const = 0;
virtual unsigned long getNumberOfData() const = 0;
virtual ~IStatistics() {}
public:
virtual uint64_t getReads() const = 0;
virtual uint64_t getWrites() const = 0;
virtual uint32_t getNumberOfNodes() const = 0;
virtual uint64_t getNumberOfData() const = 0;
virtual ~IStatistics() {}
}; // IStatistics

interface ISpatialIndex
{
public:
virtual void insertData( unsigned long len, const byte* pData, const IShape& shape, long shapeIdentifier ) = 0;
virtual bool deleteData( const IShape& shape, long shapeIdentifier ) = 0;
virtual void containsWhatQuery( const IShape& query, IVisitor& v ) = 0;
virtual void intersectsWithQuery( const IShape& query, IVisitor& v ) = 0;
virtual void pointLocationQuery( const Tools::Geometry::Point& query, IVisitor& v ) = 0;
virtual void nearestNeighborQuery( long k, const IShape& query, IVisitor& v, INearestNeighborComparator& nnc ) = 0;
virtual void nearestNeighborQuery( long k, const IShape& query, IVisitor& v ) = 0;
virtual void selfJoinQuery( const IShape& s, IVisitor& v ) = 0;
virtual void queryStrategy( IQueryStrategy& qs ) = 0;
virtual void getIndexProperties( Tools::PropertySet& out ) const = 0;
virtual void addCommand( ICommand* in, CommandType ct ) = 0;
virtual bool isIndexValid() = 0;
virtual void getStatistics( IStatistics** out ) const = 0;
virtual ~ISpatialIndex() {}
class SIDX_DLL ISpatialIndex
{
public:
virtual void insertData( uint32_t len, const byte* pData, const IShape& shape, id_type shapeIdentifier ) = 0;
virtual bool deleteData( const IShape& shape, id_type shapeIdentifier ) = 0;
virtual void containsWhatQuery( const IShape& query, IVisitor& v ) = 0;
virtual void intersectsWithQuery( const IShape& query, IVisitor& v ) = 0;
virtual void pointLocationQuery( const Point& query, IVisitor& v ) = 0;
virtual void nearestNeighborQuery( uint32_t k, const IShape& query, IVisitor& v, INearestNeighborComparator& nnc ) = 0;
virtual void nearestNeighborQuery( uint32_t k, const IShape& query, IVisitor& v ) = 0;
virtual void selfJoinQuery( const IShape& s, IVisitor& v ) = 0;
virtual void queryStrategy( IQueryStrategy& qs ) = 0;
virtual void getIndexProperties( Tools::PropertySet& out ) const = 0;
virtual void addCommand( ICommand* in, CommandType ct ) = 0;
virtual bool isIndexValid() = 0;
virtual void getStatistics( IStatistics** out ) const = 0;
virtual ~ISpatialIndex() {}

}; // ISpatialIndex

namespace StorageManager
{
enum StorageManagerConstants
SIDX_DLL enum StorageManagerConstants
{
EmptyPage = -0x1,
NewPage = -0x1
};

interface IBuffer : public IStorageManager
class SIDX_DLL IBuffer : public IStorageManager
{
public:
virtual unsigned long getHits() = 0;
virtual void clear() = 0;
virtual ~IBuffer() {}
public:
virtual uint64_t getHits() = 0;
virtual void clear() = 0;
virtual ~IBuffer() {}
}; // IBuffer

extern IStorageManager* returnMemoryStorageManager( Tools::PropertySet& in );
extern IStorageManager* createNewMemoryStorageManager();

extern IStorageManager* returnDiskStorageManager( Tools::PropertySet& in );
extern IStorageManager* createNewDiskStorageManager( std::string& baseName, unsigned long pageSize );
extern IStorageManager* loadDiskStorageManager( std::string& baseName );

#ifdef _MSC_VER
// MSVC didn't like the difference in parameter names between declaration
// definition
extern IBuffer* returnRandomEvictionsBuffer( IStorageManager& sm, Tools::PropertySet& ps );
#else
extern IBuffer* returnRandomEvictionsBuffer( IStorageManager& in0, Tools::PropertySet& in1 );
#endif//_MSC_VER
extern IBuffer* createNewRandomEvictionsBuffer( IStorageManager& in, unsigned int capacity, bool bWriteThrough );
SIDX_DLL IStorageManager* returnMemoryStorageManager( Tools::PropertySet& in );
SIDX_DLL IStorageManager* createNewMemoryStorageManager();

SIDX_DLL IStorageManager* returnDiskStorageManager( Tools::PropertySet& in );
SIDX_DLL IStorageManager* createNewDiskStorageManager( std::string& baseName, uint32_t pageSize );
SIDX_DLL IStorageManager* loadDiskStorageManager( std::string& baseName );

SIDX_DLL IBuffer* returnRandomEvictionsBuffer( IStorageManager& ind, Tools::PropertySet& in );
SIDX_DLL IBuffer* createNewRandomEvictionsBuffer( IStorageManager& in, uint32_t capacity, bool bWriteThrough );
}

//
// Global functions
//
extern std::ostream& operator<<( std::ostream&, const ISpatialIndex& );
extern std::ostream& operator<<( std::ostream&, const IStatistics& );
SIDX_DLL std::ostream& operator<<( std::ostream&, const ISpatialIndex& );
SIDX_DLL std::ostream& operator<<( std::ostream&, const IStatistics& );
}

//#include "TimePoint.h"
//#include "TimeRegion.h"
//#include "MovingPoint.h"
//#include "MovingRegion.h"
#include "Point.h"
#include "Region.h"
#include "LineSegment.h"
#include "RTree.h"
//#include "MVRTree.h"
//#include "TPRTree.h"

#endif /*__spatialindex_h*/
#include "Version.h"
789 changes: 0 additions & 789 deletions src/core/spatialindex/include/Tools.h
View file

This file was deleted.

45 changes: 18 additions & 27 deletions ...core/spatialindex/include/TemporaryFile.h → src/core/spatialindex/include/Version.h
View file
Original file line number Diff line number Diff line change
@@ -1,6 +1,6 @@
// Tools Library
// Spatial Index Library
//
// Copyright (C) 2004 Navel Ltd.
// Copyright (C) 2003 Navel Ltd.
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
Expand All @@ -19,33 +19,24 @@
// Email:
// mhadji@gmail.com

#ifndef __tools_temporary_file_h
#define __tools_temporary_file_h
#pragma once

namespace Tools
{
class TemporaryFile
{
public:
TemporaryFile();
virtual ~TemporaryFile();
#ifndef SIDX_VERSION_MAJOR
#define SIDX_VERSION_MAJOR 1
#define SIDX_VERSION_MINOR 6
#define SIDX_VERSION_REV 1
#define SIDX_VERSION_BUILD 0
#endif

void storeNextObject( ISerializable* r );
void storeNextObject( unsigned long len, const byte* const data );
void loadNextObject( ISerializable* r );
void loadNextObject( byte** data, unsigned long& len );
#ifndef SIDX_VERSION_NUM
#define SIDX_VERSION_NUM (SIDX_VERSION_MAJOR*1000+SIDX_VERSION_MINOR*100+SIDX_VERSION_REV*10+SIDX_VERSION_BUILD)
#endif

void rewindForReading();
void rewindForWriting();
#ifndef SIDX_RELEASE_DATE
#define SIDX_RELEASE_DATE 20101204
#endif

private:
std::fstream m_file;
std::vector<std::string> m_strFileName;
unsigned long m_currentFile;
unsigned long m_fileSize;
bool m_bEOF;
}; // TemporaryFile
}

#endif /* __tools_temporary_file_h */
#ifndef SIDX_RELEASE_NAME
#define SIDX_RELEASE_NAME "1.6.1"
#endif

31 changes: 12 additions & 19 deletions src/core/spatialindex/include/PointerPool.h → .../spatialindex/include/tools/PointerPool.h
View file
Original file line number Diff line number Diff line change
@@ -1,5 +1,4 @@
#include "qgslogger.h"
// Tools Library
// Spatial Index Library
//
// Copyright (C) 2004 Navel Ltd.
//
Expand All @@ -20,21 +19,16 @@
// Email:
// mhadji@gmail.com

#ifndef __tools_pointer_pool_h
#define __tools_pointer_pool_h
#pragma once

#include "PoolPointer.h"

#define NDEBUG 1

namespace Tools
{
template <class X> class PointerPool
{
// class PoolPointer<X>;

public:
explicit PointerPool( unsigned long capacity ) : m_capacity( capacity )
explicit PointerPool( uint32_t capacity ) : m_capacity( capacity )
{
#ifndef NDEBUG
m_hits = 0;
Expand All @@ -51,13 +45,13 @@ namespace Tools
{
X* x = m_pool.top(); m_pool.pop();
#ifndef NDEBUG
m_pointerCount--;
--m_pointerCount;
#endif
delete x;
}

#ifndef NDEBUG
QgsDebugMsg( QString( "Lost pointers: %1" ).arg( m_pointerCount ) );
std::cerr << "Lost pointers: " << m_pointerCount << std::endl;
#endif
}

Expand Down Expand Up @@ -93,31 +87,30 @@ namespace Tools
else
{
#ifndef NDEBUG
m_pointerCount--;
--m_pointerCount;
#endif
delete p;
}

assert( m_pool.size() <= m_capacity );
}

unsigned long getCapacity() const { return m_capacity; }
void setCapacity( unsigned long c )
uint32_t getCapacity() const { return m_capacity; }
void setCapacity( uint32_t c )
{
m_capacity = c;
}

private:
unsigned long m_capacity;
uint32_t m_capacity;
std::stack<X*> m_pool;

#ifndef NDEBUG
public:
unsigned long m_hits;
unsigned long m_misses;
long m_pointerCount;
uint64_t m_hits;
uint64_t m_misses;
uint64_t m_pointerCount;
#endif
};
}

#endif /* __tools_pointer_pool_h */
8 changes: 4 additions & 4 deletions src/core/spatialindex/include/PoolPointer.h → .../spatialindex/include/tools/PoolPointer.h
View file
Original file line number Diff line number Diff line change
@@ -1,4 +1,4 @@
// Tools Library
// Spatial Index Library
//
// Copyright (C) 2004 Navel Ltd.
//
Expand All @@ -19,8 +19,9 @@
// Email:
// mhadji@gmail.com

#ifndef __tools_pool_pointer_h
#define __tools_pool_pointer_h
#pragma once

#include "PointerPool.h"

namespace Tools
{
Expand Down Expand Up @@ -93,4 +94,3 @@ namespace Tools
};
}

#endif /* __tools_pool_pointer_h */
6 changes: 2 additions & 4 deletions src/core/spatialindex/include/SmartPointer.h → ...spatialindex/include/tools/SmartPointer.h
View file
Original file line number Diff line number Diff line change
@@ -1,4 +1,4 @@
// Tools Library
// Spatial Index Library
//
// Copyright (C) 2004 Navel Ltd.
//
Expand All @@ -19,8 +19,7 @@
// Email:
// mhadji@gmail.com

#ifndef __tools_smart_pointer_h
#define __tools_smart_pointer_h
#pragma once

namespace Tools
{
Expand Down Expand Up @@ -77,4 +76,3 @@ namespace Tools
};
}

#endif /* __tools_smart_pointer_h */
513 changes: 513 additions & 0 deletions src/core/spatialindex/include/tools/Tools.h
View file

Large diffs are not rendered by default.

390 changes: 0 additions & 390 deletions src/core/spatialindex/rtree/BulkLoader.cc
View file

This file was deleted.

123 changes: 0 additions & 123 deletions src/core/spatialindex/rtree/BulkLoader.h
View file

This file was deleted.

175 changes: 0 additions & 175 deletions src/core/spatialindex/rtree/Statistics.cc
View file

This file was deleted.

461 changes: 461 additions & 0 deletions src/core/spatialindex/src/rtree/BulkLoader.cc
View file

Large diffs are not rendered by default.

131 changes: 131 additions & 0 deletions src/core/spatialindex/src/rtree/BulkLoader.h
View file
Original file line number Diff line number Diff line change
@@ -0,0 +1,131 @@
// Spatial Index Library
//
// Copyright (C) 2002 Navel Ltd.
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
//
// Email:
// mhadji@gmail.com

#pragma once

namespace SpatialIndex
{
namespace RTree
{
class ExternalSorter
{
public:
class Record
{
public:
Record();
Record( const Region& r, id_type id, uint32_t len, byte* pData, uint32_t s );
~Record();

bool operator<( const Record& r ) const;

void storeToFile( Tools::TemporaryFile& f );
void loadFromFile( Tools::TemporaryFile& f );

struct SortAscending : public std::binary_function<Record* const, Record* const, bool>
{
bool operator()( Record* const r1, Record* const r2 )
{
if ( *r1 < *r2 ) return true;
else return false;
}
};

public:
Region m_r;
id_type m_id;
byte* m_pData;
uint32_t m_len;
uint32_t m_s;
};

public:
ExternalSorter( uint32_t u32PageSize, uint32_t u32BufferPages );
virtual ~ExternalSorter();

void insert( Record* r );
void sort();
Record* getNextRecord();
uint64_t getTotalEntries() const;

private:
class PQEntry
{
public:
PQEntry( Record* r, uint32_t u32Index ) : m_r( r ), m_u32Index( u32Index ) {}

struct SortAscending : public std::binary_function<const PQEntry&, const PQEntry&, bool>
{
bool operator()( const PQEntry& e1, const PQEntry& e2 )
{
if ( *( e1.m_r ) < *( e2.m_r ) ) return true;
else return false;
}
};

Record* m_r;
uint32_t m_u32Index;
};

private:
bool m_bInsertionPhase;
uint32_t m_u32PageSize;
uint32_t m_u32BufferPages;
Tools::SmartPointer<Tools::TemporaryFile> m_sortedFile;
std::list<Tools::SmartPointer<Tools::TemporaryFile> > m_runs;
std::vector<Record*> m_buffer;
uint64_t m_u64TotalEntries;
uint32_t m_stI;
};

class BulkLoader
{
public:
void bulkLoadUsingSTR(
RTree* pTree,
IDataStream& stream,
uint32_t bindex,
uint32_t bleaf,
uint32_t pageSize, // The number of node entries per page.
uint32_t numberOfPages // The total number of pages to use.
);

protected:
void createLevel(
RTree* pTree,
Tools::SmartPointer<ExternalSorter> es,
uint32_t dimension,
uint32_t indexSize,
uint32_t leafSize,
uint32_t level,
Tools::SmartPointer<ExternalSorter> es2,
uint32_t pageSize,
uint32_t numberOfPages
);

Node* createNode(
RTree* pTree,
std::vector<ExternalSorter::Record*>& e,
uint32_t level
);
};
}
}
100 changes: 47 additions & 53 deletions src/core/spatialindex/rtree/Index.cc → src/core/spatialindex/src/rtree/Index.cc
View file
Original file line number Diff line number Diff line change
Expand Up @@ -19,38 +19,31 @@
// Email:
// mhadji@gmail.com

#include "../spatialindex/SpatialIndexImpl.h"
#include <limits>

#include "../spatialindex/SpatialIndexImpl.h"
#include "RTree.h"
#include "Node.h"
#include "Leaf.h"

#include "Index.h"

using std::stack;
using std::vector;
using namespace SpatialIndex::RTree;

Index::~Index()
{
}

#ifdef _MSC_VER
// MSVC seems to find RTree* pTree ambiguous
Index::Index( SpatialIndex::RTree::RTree* pTree, long id, unsigned long level ) : Node( pTree, id, level, pTree->m_indexCapacity )
#else
Index::Index( RTree* pTree, long id, unsigned long level ) : Node( pTree, id, level, pTree->m_indexCapacity )
#endif//_MSC_VER
Index::Index( SpatialIndex::RTree::RTree* pTree, id_type id, uint32_t level ) : Node( pTree, id, level, pTree->m_indexCapacity )
{
}

NodePtr Index::chooseSubtree( const Region& mbr, unsigned long insertionLevel, std::stack<long>& pathBuffer )
NodePtr Index::chooseSubtree( const Region& mbr, uint32_t insertionLevel, std::stack<id_type>& pathBuffer )
{
if ( m_level == insertionLevel ) return NodePtr( this, &( m_pTree->m_indexPool ) );

pathBuffer.push( m_identifier );

unsigned long child = 0;
uint32_t child = 0;

switch ( m_pTree->m_treeVariant )
{
Expand All @@ -72,20 +65,21 @@ NodePtr Index::chooseSubtree( const Region& mbr, unsigned long insertionLevel, s
default:
throw Tools::NotSupportedException( "Index::chooseSubtree: Tree variant not supported." );
}
assert( child != std::numeric_limits<uint32_t>::max() );

NodePtr n = m_pTree->readNode( m_pIdentifier[child] );
NodePtr ret = n->chooseSubtree( mbr, insertionLevel, pathBuffer );
Q_ASSERT( n.unique() );
assert( n.unique() );
if ( ret.get() == n.get() ) n.relinquish();

return ret;
}

NodePtr Index::findLeaf( const Region& mbr, long id, std::stack<long>& pathBuffer )
NodePtr Index::findLeaf( const Region& mbr, id_type id, std::stack<id_type>& pathBuffer )
{
pathBuffer.push( m_identifier );

for ( unsigned long cChild = 0; cChild < m_children; cChild++ )
for ( uint32_t cChild = 0; cChild < m_children; ++cChild )
{
if ( m_ptrMBR[cChild]->containsRegion( mbr ) )
{
Expand All @@ -101,11 +95,11 @@ NodePtr Index::findLeaf( const Region& mbr, long id, std::stack<long>& pathBuffe
return NodePtr();
}

void Index::split( unsigned long dataLength, byte* pData, Region& mbr, long id, NodePtr& ptrLeft, NodePtr& ptrRight )
void Index::split( uint32_t dataLength, byte* pData, Region& mbr, id_type id, NodePtr& ptrLeft, NodePtr& ptrRight )
{
m_pTree->m_stats.m_splits++;
++( m_pTree->m_stats.m_u64Splits );

vector<long> g1, g2;
std::vector<uint32_t> g1, g2;

switch ( m_pTree->m_treeVariant )
{
Expand All @@ -129,27 +123,27 @@ void Index::split( unsigned long dataLength, byte* pData, Region& mbr, long id,
ptrLeft->m_nodeMBR = m_pTree->m_infiniteRegion;
ptrRight->m_nodeMBR = m_pTree->m_infiniteRegion;

unsigned long cIndex;
uint32_t cIndex;

for ( cIndex = 0; cIndex < g1.size(); cIndex++ )
for ( cIndex = 0; cIndex < g1.size(); ++cIndex )
{
ptrLeft->insertEntry( 0, 0, *( m_ptrMBR[g1[cIndex]] ), m_pIdentifier[g1[cIndex]] );
}

for ( cIndex = 0; cIndex < g2.size(); cIndex++ )
for ( cIndex = 0; cIndex < g2.size(); ++cIndex )
{
ptrRight->insertEntry( 0, 0, *( m_ptrMBR[g2[cIndex]] ), m_pIdentifier[g2[cIndex]] );
}
}

long Index::findLeastEnlargement( const Region& r ) const
uint32_t Index::findLeastEnlargement( const Region& r ) const
{
double area = std::numeric_limits<double>::max();
long best = -1;
uint32_t best = std::numeric_limits<uint32_t>::max();

RegionPtr t = m_pTree->m_regionPool.acquire();

for ( unsigned long cChild = 0; cChild < m_children; cChild++ )
for ( uint32_t cChild = 0; cChild < m_children; ++cChild )
{
m_ptrMBR[cChild]->getCombinedRegion( *t, r );

Expand All @@ -172,7 +166,7 @@ long Index::findLeastEnlargement( const Region& r ) const
return best;
}

long Index::findLeastOverlap( const Region& r ) const
uint32_t Index::findLeastOverlap( const Region& r ) const
{
OverlapEntry** entries = new OverlapEntry*[m_children];

Expand All @@ -181,20 +175,20 @@ long Index::findLeastOverlap( const Region& r ) const
OverlapEntry* best = 0;

// find combined region and enlargement of every entry and store it.
for ( unsigned long cChild = 0; cChild < m_children; cChild++ )
for ( uint32_t cChild = 0; cChild < m_children; ++cChild )
{
try
{
entries[cChild] = new OverlapEntry();
}
catch ( ... )
{
for ( unsigned long i = 0; i < cChild; i++ ) delete entries[i];
for ( uint32_t i = 0; i < cChild; ++i ) delete entries[i];
delete[] entries;
throw;
}

entries[cChild]->m_id = cChild;
entries[cChild]->m_index = cChild;
entries[cChild]->m_original = m_ptrMBR[cChild];
entries[cChild]->m_combined = m_pTree->m_regionPool.acquire();
m_ptrMBR[cChild]->getCombinedRegion( *( entries[cChild]->m_combined ), r );
Expand All @@ -215,15 +209,15 @@ long Index::findLeastOverlap( const Region& r ) const

if ( me < -std::numeric_limits<double>::epsilon() || me > std::numeric_limits<double>::epsilon() )
{
unsigned long cIterations;
uint32_t cIterations;

if ( m_children > m_pTree->m_nearMinimumOverlapFactor )
{
// sort entries in increasing order of enlargement.
::qsort( entries, m_children,
sizeof( OverlapEntry* ),
OverlapEntry::compareEntries );
Q_ASSERT( entries[0]->m_enlargement <= entries[m_children - 1]->m_enlargement );
assert( entries[0]->m_enlargement <= entries[m_children - 1]->m_enlargement );

cIterations = m_pTree->m_nearMinimumOverlapFactor;
}
Expand All @@ -233,14 +227,14 @@ long Index::findLeastOverlap( const Region& r ) const
}

// calculate overlap of most important original entries (near minimum overlap cost).
for ( unsigned long cIndex = 0; cIndex < cIterations; cIndex++ )
for ( uint32_t cIndex = 0; cIndex < cIterations; ++cIndex )
{
double dif = 0.0;
OverlapEntry* e = entries[cIndex];

for ( unsigned long cChild = 0; cChild < m_children; cChild++ )
for ( uint32_t cChild = 0; cChild < m_children; ++cChild )
{
if ( e->m_id != cChild )
if ( e->m_index != cChild )
{
double f = e->m_combined->getIntersectingArea( *( m_ptrMBR[cChild] ) );
if ( f != 0.0 ) dif += f - e->m_original->getIntersectingArea( *( m_ptrMBR[cChild] ) );
Expand Down Expand Up @@ -268,9 +262,9 @@ long Index::findLeastOverlap( const Region& r ) const
} // for (cIndex)
}

long ret = best->m_id;
uint32_t ret = best->m_index;

for ( unsigned long cChild = 0; cChild < m_children; cChild++ )
for ( uint32_t cChild = 0; cChild < m_children; ++cChild )
{
delete entries[cChild];
}
Expand All @@ -279,13 +273,13 @@ long Index::findLeastOverlap( const Region& r ) const
return ret;
}

void Index::adjustTree( Node* n, std::stack<long>& pathBuffer )
void Index::adjustTree( Node* n, std::stack<id_type>& pathBuffer )
{
m_pTree->m_stats.m_adjustments++;
++( m_pTree->m_stats.m_u64Adjustments );

// find entry pointing to old node;
unsigned long child;
for ( child = 0; child < m_children; child++ )
uint32_t child;
for ( child = 0; child < m_children; ++child )
{
if ( m_pIdentifier[child] == n->m_identifier ) break;
}
Expand All @@ -301,15 +295,15 @@ void Index::adjustTree( Node* n, std::stack<long>& pathBuffer )

if ( bRecompute )
{
for ( unsigned long cDim = 0; cDim < m_nodeMBR.m_dimension; cDim++ )
for ( uint32_t cDim = 0; cDim < m_nodeMBR.m_dimension; ++cDim )
{
m_nodeMBR.m_pLow[cDim] = std::numeric_limits<double>::max();
m_nodeMBR.m_pHigh[cDim] = -std::numeric_limits<double>::max();

for ( unsigned long cChild = 0; cChild < m_children; cChild++ )
for ( uint32_t cChild = 0; cChild < m_children; ++cChild )
{
m_nodeMBR.m_pLow[cDim] = qMin( m_nodeMBR.m_pLow[cDim], m_ptrMBR[cChild]->m_pLow[cDim] );
m_nodeMBR.m_pHigh[cDim] = qMax( m_nodeMBR.m_pHigh[cDim], m_ptrMBR[cChild]->m_pHigh[cDim] );
m_nodeMBR.m_pLow[cDim] = std::min( m_nodeMBR.m_pLow[cDim], m_ptrMBR[cChild]->m_pLow[cDim] );
m_nodeMBR.m_pHigh[cDim] = std::max( m_nodeMBR.m_pHigh[cDim], m_ptrMBR[cChild]->m_pHigh[cDim] );
}
}
}
Expand All @@ -318,20 +312,20 @@ void Index::adjustTree( Node* n, std::stack<long>& pathBuffer )

if ( bRecompute && ( ! pathBuffer.empty() ) )
{
long cParent = pathBuffer.top(); pathBuffer.pop();
id_type cParent = pathBuffer.top(); pathBuffer.pop();
NodePtr ptrN = m_pTree->readNode( cParent );
Index* p = static_cast<Index*>( ptrN.get() );
p->adjustTree( this, pathBuffer );
}
}

void Index::adjustTree( Node* n1, Node* n2, std::stack<long>& pathBuffer, byte* overflowTable )
void Index::adjustTree( Node* n1, Node* n2, std::stack<id_type>& pathBuffer, byte* overflowTable )
{
m_pTree->m_stats.m_adjustments++;
++( m_pTree->m_stats.m_u64Adjustments );

// find entry pointing to old node;
unsigned long child;
for ( child = 0; child < m_children; child++ )
uint32_t child;
for ( child = 0; child < m_children; ++child )
{
if ( m_pIdentifier[child] == n1->m_identifier ) break;
}
Expand All @@ -347,15 +341,15 @@ void Index::adjustTree( Node* n1, Node* n2, std::stack<long>& pathBuffer, byte*

if ( bRecompute )
{
for ( unsigned long cDim = 0; cDim < m_nodeMBR.m_dimension; cDim++ )
for ( uint32_t cDim = 0; cDim < m_nodeMBR.m_dimension; ++cDim )
{
m_nodeMBR.m_pLow[cDim] = std::numeric_limits<double>::max();
m_nodeMBR.m_pHigh[cDim] = -std::numeric_limits<double>::max();

for ( unsigned long cChild = 0; cChild < m_children; cChild++ )
for ( uint32_t cChild = 0; cChild < m_children; ++cChild )
{
m_nodeMBR.m_pLow[cDim] = qMin( m_nodeMBR.m_pLow[cDim], m_ptrMBR[cChild]->m_pLow[cDim] );
m_nodeMBR.m_pHigh[cDim] = qMax( m_nodeMBR.m_pHigh[cDim], m_ptrMBR[cChild]->m_pHigh[cDim] );
m_nodeMBR.m_pLow[cDim] = std::min( m_nodeMBR.m_pLow[cDim], m_ptrMBR[cChild]->m_pLow[cDim] );
m_nodeMBR.m_pHigh[cDim] = std::max( m_nodeMBR.m_pHigh[cDim], m_ptrMBR[cChild]->m_pHigh[cDim] );
}
}
}
Expand All @@ -370,7 +364,7 @@ void Index::adjustTree( Node* n1, Node* n2, std::stack<long>& pathBuffer, byte*
// In all other cases insertData above took care of adjustment.
if (( ! bAdjusted ) && bRecompute && ( ! pathBuffer.empty() ) )
{
long cParent = pathBuffer.top(); pathBuffer.pop();
id_type cParent = pathBuffer.top(); pathBuffer.pop();
NodePtr ptrN = m_pTree->readNode( cParent );
Index* p = static_cast<Index*>( ptrN.get() );
p->adjustTree( this, pathBuffer );
Expand Down
26 changes: 11 additions & 15 deletions src/core/spatialindex/rtree/Index.h → src/core/spatialindex/src/rtree/Index.h
View file
Original file line number Diff line number Diff line change
Expand Up @@ -19,8 +19,7 @@
// Email:
// mhadji@gmail.com

#ifndef __spatialindex_rtree_index_h
#define __spatialindex_rtree_index_h
#pragma once

namespace SpatialIndex
{
Expand All @@ -31,24 +30,24 @@ namespace SpatialIndex
public:
virtual ~Index();

private:
Index( RTree* pTree, long id, unsigned long level );
protected:
Index( RTree* pTree, id_type id, uint32_t level );

virtual NodePtr chooseSubtree( const Region& mbr, unsigned long level, std::stack<long>& pathBuffer );
virtual NodePtr findLeaf( const Region& mbr, long id, std::stack<long>& pathBuffer );
virtual NodePtr chooseSubtree( const Region& mbr, uint32_t level, std::stack<id_type>& pathBuffer );
virtual NodePtr findLeaf( const Region& mbr, id_type id, std::stack<id_type>& pathBuffer );

virtual void split( unsigned long dataLength, byte* pData, Region& mbr, long id, NodePtr& left, NodePtr& right );
virtual void split( uint32_t dataLength, byte* pData, Region& mbr, id_type id, NodePtr& left, NodePtr& right );

long findLeastEnlargement( const Region& ) const;
long findLeastOverlap( const Region& ) const;
uint32_t findLeastEnlargement( const Region& ) const;
uint32_t findLeastOverlap( const Region& ) const;

void adjustTree( Node*, std::stack<long>& );
void adjustTree( Node*, Node*, std::stack<long>&, byte* overflowTable );
void adjustTree( Node*, std::stack<id_type>& );
void adjustTree( Node*, Node*, std::stack<id_type>&, byte* overflowTable );

class OverlapEntry
{
public:
unsigned long m_id;
uint32_t m_index;
double m_enlargement;
RegionPtr m_original;
RegionPtr m_combined;
Expand All @@ -72,6 +71,3 @@ namespace SpatialIndex
}; // Index
}
}

#endif /*__spatialindex_rtree_index_h*/

49 changes: 19 additions & 30 deletions src/core/spatialindex/rtree/Leaf.cc → src/core/spatialindex/src/rtree/Leaf.cc
View file
Original file line number Diff line number Diff line change
Expand Up @@ -19,45 +19,34 @@
// Email:
// mhadji@gmail.com

#include "../spatialindex/SpatialIndexImpl.h"
#include <cstring>

#include "../spatialindex/SpatialIndexImpl.h"
#include "RTree.h"
#include "Node.h"
#include "Index.h"

#include "Leaf.h"

using std::stack;
using std::vector;
using namespace SpatialIndex::RTree;

Leaf::~Leaf()
{
}

#ifdef _MSC_VER
// MSVC seems to find RTree* pTree ambiguous
Leaf::Leaf( SpatialIndex::RTree::RTree* pTree, long id ): Node( pTree, id, 0, pTree->m_leafCapacity )
#else
Leaf::Leaf( RTree* pTree, long id ): Node( pTree, id, 0, pTree->m_leafCapacity )
#endif//_MSC_VER
Leaf::Leaf( SpatialIndex::RTree::RTree* pTree, id_type id ): Node( pTree, id, 0, pTree->m_leafCapacity )
{
}

NodePtr Leaf::chooseSubtree( const Region& mbr, unsigned long level, std::stack<long>& pathBuffer )
NodePtr Leaf::chooseSubtree( const Region& , uint32_t , std::stack<id_type>& )
{
Q_UNUSED( mbr );
Q_UNUSED( level );
Q_UNUSED( pathBuffer );
// should make sure to relinquish other PoolPointer lists that might be pointing to the
// same leaf.
return NodePtr( this, &( m_pTree->m_leafPool ) );
}

NodePtr Leaf::findLeaf( const Region& mbr, long id, std::stack<long>& pathBuffer )
NodePtr Leaf::findLeaf( const Region& mbr, id_type id, std::stack<id_type>& )
{
Q_UNUSED( pathBuffer );
for ( unsigned long cChild = 0; cChild < m_children; cChild++ )
for ( uint32_t cChild = 0; cChild < m_children; ++cChild )
{
// should make sure to relinquish other PoolPointer lists that might be pointing to the
// same leaf.
Expand All @@ -67,11 +56,11 @@ NodePtr Leaf::findLeaf( const Region& mbr, long id, std::stack<long>& pathBuffer
return NodePtr();
}

void Leaf::split( unsigned long dataLength, byte* pData, Region& mbr, long id, NodePtr& pLeft, NodePtr& pRight )
void Leaf::split( uint32_t dataLength, byte* pData, Region& mbr, id_type id, NodePtr& pLeft, NodePtr& pRight )
{
m_pTree->m_stats.m_splits++;
++( m_pTree->m_stats.m_u64Splits );

vector<long> g1, g2;
std::vector<uint32_t> g1, g2;

switch ( m_pTree->m_treeVariant )
{
Expand All @@ -95,36 +84,36 @@ void Leaf::split( unsigned long dataLength, byte* pData, Region& mbr, long id, N
pLeft->m_nodeMBR = m_pTree->m_infiniteRegion;
pRight->m_nodeMBR = m_pTree->m_infiniteRegion;

unsigned long cIndex;
uint32_t cIndex;

for ( cIndex = 0; cIndex < g1.size(); cIndex++ )
for ( cIndex = 0; cIndex < g1.size(); ++cIndex )
{
pLeft->insertEntry( m_pDataLength[g1[cIndex]], m_pData[g1[cIndex]], *( m_ptrMBR[g1[cIndex]] ), m_pIdentifier[g1[cIndex]] );
// we don't want to delete the data array from this node's destructor!
m_pData[g1[cIndex]] = 0;
}

for ( cIndex = 0; cIndex < g2.size(); cIndex++ )
for ( cIndex = 0; cIndex < g2.size(); ++cIndex )
{
pRight->insertEntry( m_pDataLength[g2[cIndex]], m_pData[g2[cIndex]], *( m_ptrMBR[g2[cIndex]] ), m_pIdentifier[g2[cIndex]] );
// we don't want to delete the data array from this node's destructor!
m_pData[g2[cIndex]] = 0;
}
}

void Leaf::deleteData( long id, std::stack<long>& pathBuffer )
void Leaf::deleteData( id_type id, std::stack<id_type>& pathBuffer )
{
unsigned long child;
uint32_t child;

for ( child = 0; child < m_children; child++ )
for ( child = 0; child < m_children; ++child )
{
if ( m_pIdentifier[child] == id ) break;
}

deleteEntry( child );
m_pTree->writeNode( this );

stack<NodePtr> toReinsert;
std::stack<NodePtr> toReinsert;
NodePtr ptrThis( this, &( m_pTree->m_leafPool ) );
condenseTree( toReinsert, pathBuffer, ptrThis );
ptrThis.relinquish();
Expand All @@ -135,11 +124,11 @@ void Leaf::deleteData( long id, std::stack<long>& pathBuffer )
NodePtr n = toReinsert.top(); toReinsert.pop();
m_pTree->deleteNode( n.get() );

for ( unsigned long cChild = 0; cChild < n->m_children; cChild++ )
for ( uint32_t cChild = 0; cChild < n->m_children; ++cChild )
{
// keep this in the for loop. The tree height might change after insertions.
byte* overflowTable = new byte[m_pTree->m_stats.m_treeHeight];
memset( overflowTable, 0, m_pTree->m_stats.m_treeHeight );
byte* overflowTable = new byte[m_pTree->m_stats.m_u32TreeHeight];
bzero( overflowTable, m_pTree->m_stats.m_u32TreeHeight );
m_pTree->insertData_impl( n->m_pDataLength[cChild], n->m_pData[cChild], *( n->m_ptrMBR[cChild] ), n->m_pIdentifier[cChild], n->m_level, overflowTable );
n->m_pData[cChild] = 0;
delete[] overflowTable;
Expand Down
37 changes: 17 additions & 20 deletions src/core/spatialindex/rtree/Leaf.h → src/core/spatialindex/src/rtree/Leaf.h
View file
Original file line number Diff line number Diff line change
Expand Up @@ -19,32 +19,29 @@
// Email:
// mhadji@gmail.com

#ifndef __spatialindex_rtree_leaf_h
#define __spatialindex_rtree_leaf_h
#pragma once

namespace SpatialIndex
{
namespace RTree
{
class Leaf : public Node
{
public:
virtual ~Leaf();
namespace RTree
{
class Leaf : public Node
{
public:
virtual ~Leaf();

private:
Leaf( RTree* pTree, long id );
protected:
Leaf(RTree* pTree, id_type id);

virtual NodePtr chooseSubtree( const Region& mbr, unsigned long level, std::stack<long>& pathBuffer );
virtual NodePtr findLeaf( const Region& mbr, long id, std::stack<long>& pathBuffer );
virtual NodePtr chooseSubtree(const Region& mbr, uint32_t level, std::stack<id_type>& pathBuffer);
virtual NodePtr findLeaf(const Region& mbr, id_type id, std::stack<id_type>& pathBuffer);

virtual void split( unsigned long dataLength, byte* pData, Region& mbr, long id, NodePtr& left, NodePtr& right );
virtual void split(uint32_t dataLength, byte* pData, Region& mbr, id_type id, NodePtr& left, NodePtr& right);

virtual void deleteData( long id, std::stack<long>& pathBuffer );
virtual void deleteData(id_type id, std::stack<id_type>& pathBuffer);

friend class RTree;
friend class BulkLoader;
}; // Leaf
}
friend class RTree;
friend class BulkLoader;
}; // Leaf
}
}

#endif /*__spatialindex_rtree_leaf_h*/
423 changes: 216 additions & 207 deletions src/core/spatialindex/rtree/Node.cc → src/core/spatialindex/src/rtree/Node.cc
View file

Large diffs are not rendered by default.

77 changes: 36 additions & 41 deletions src/core/spatialindex/rtree/Node.h → src/core/spatialindex/src/rtree/Node.h
View file
Original file line number Diff line number Diff line change
Expand Up @@ -19,8 +19,7 @@
// Email:
// mhadji@gmail.com

#ifndef __spatialindex_rtree_node_h
#define __spatialindex_rtree_node_h
#pragma once

namespace SpatialIndex
{
Expand All @@ -46,67 +45,65 @@ namespace SpatialIndex
//
// Tools::ISerializable interface
//
virtual unsigned long getByteArraySize();
virtual uint32_t getByteArraySize();
virtual void loadFromByteArray( const byte* data );
virtual void storeToByteArray( byte** data, unsigned long& len );
virtual void storeToByteArray( byte** data, uint32_t& len );

//
// SpatialIndex::IEntry interface
//
virtual long getIdentifier() const;
virtual id_type getIdentifier() const;
virtual void getShape( IShape** out ) const;

//
// SpatialIndex::INode interface
//
virtual unsigned long getChildrenCount() const;
virtual long getChildIdentifier( unsigned long index ) const;
virtual void getChildShape( unsigned long index, IShape** out ) const;
virtual unsigned long getLevel() const;
virtual uint32_t getChildrenCount() const;
virtual id_type getChildIdentifier( uint32_t index ) const;
virtual void getChildShape( uint32_t index, IShape** out ) const;
virtual void getChildData( uint32_t index, uint32_t& length, byte** data ) const;
virtual uint32_t getLevel() const;
virtual bool isIndex() const;
virtual bool isLeaf() const;

private:
Node();
Node( RTree* pTree, long id, unsigned long level, unsigned long capacity );
Node( RTree* pTree, id_type id, uint32_t level, uint32_t capacity );

virtual Node& operator=( const Node& );

virtual void insertEntry( unsigned long dataLength, byte* pData, Region& mbr, long id );
virtual void deleteEntry( unsigned long index );
virtual void insertEntry( uint32_t dataLength, byte* pData, Region& mbr, id_type id );
virtual void deleteEntry( uint32_t index );

virtual bool insertData( unsigned long dataLength, byte* pData, Region& mbr, long id, std::stack<long>& pathBuffer, byte* overflowTable );
virtual void reinsertData( unsigned long dataLength, byte* pData, Region& mbr, long id, std::vector<long>& reinsert, std::vector<long>& keep );
virtual bool insertData( uint32_t dataLength, byte* pData, Region& mbr, id_type id, std::stack<id_type>& pathBuffer, byte* overflowTable );
virtual void reinsertData( uint32_t dataLength, byte* pData, Region& mbr, id_type id, std::vector<uint32_t>& reinsert, std::vector<uint32_t>& keep );

virtual void rtreeSplit( unsigned long dataLength, byte* pData, Region& mbr, long id, std::vector<long>& group1, std::vector<long>& group2 );
virtual void rstarSplit( unsigned long dataLength, byte* pData, Region& mbr, long id, std::vector<long>& group1, std::vector<long>& group2 );
virtual void rtreeSplit( uint32_t dataLength, byte* pData, Region& mbr, id_type id, std::vector<uint32_t>& group1, std::vector<uint32_t>& group2 );
virtual void rstarSplit( uint32_t dataLength, byte* pData, Region& mbr, id_type id, std::vector<uint32_t>& group1, std::vector<uint32_t>& group2 );

virtual void pickSeeds( unsigned long& index1, unsigned long& index2 );
virtual void pickSeeds( uint32_t& index1, uint32_t& index2 );

virtual void condenseTree( std::stack<NodePtr>& toReinsert, std::stack<long>& pathBuffer, NodePtr& ptrThis );
virtual void condenseTree( std::stack<NodePtr>& toReinsert, std::stack<id_type>& pathBuffer, NodePtr& ptrThis );

//virtual void load(unsigned long len, byte* const data);
//virtual void store(unsigned long& len, byte** data);
virtual NodePtr chooseSubtree( const Region& mbr, uint32_t level, std::stack<id_type>& pathBuffer ) = 0;
virtual NodePtr findLeaf( const Region& mbr, id_type id, std::stack<id_type>& pathBuffer ) = 0;

virtual NodePtr chooseSubtree( const Region& mbr, unsigned long level, std::stack<long>& pathBuffer ) = 0;
virtual NodePtr findLeaf( const Region& mbr, long id, std::stack<long>& pathBuffer ) = 0;

virtual void split( unsigned long dataLength, byte* pData, Region& mbr, long id, NodePtr& left, NodePtr& right ) = 0;
virtual void split( uint32_t dataLength, byte* pData, Region& mbr, id_type id, NodePtr& left, NodePtr& right ) = 0;

RTree* m_pTree;
// Parent of all nodes.

unsigned long m_level;
uint32_t m_level;
// The level of the node in the tree.
// Leaves are always at level 0.

long m_identifier;
id_type m_identifier;
// The unique ID of this node.

unsigned long m_children;
uint32_t m_children;
// The number of children pointed by this node.

unsigned long m_capacity;
uint32_t m_capacity;
// Specifies the node capacity.

Region m_nodeMBR;
Expand All @@ -118,29 +115,29 @@ namespace SpatialIndex
RegionPtr* m_ptrMBR;
// The corresponding data MBRs.

long* m_pIdentifier;
id_type* m_pIdentifier;
// The corresponding data identifiers.

unsigned long* m_pDataLength;
uint32_t* m_pDataLength;

unsigned long m_totalDataLength;
uint32_t m_totalDataLength;

class RstarSplitEntry
{
public:
Region* m_pRegion;
long m_id;
unsigned long m_sortDim;
uint32_t m_index;
uint32_t m_sortDim;

RstarSplitEntry( Region* pr, long id, unsigned long dimension ) :
m_pRegion( pr ), m_id( id ), m_sortDim( dimension ) {}
RstarSplitEntry( Region* pr, uint32_t index, uint32_t dimension ) :
m_pRegion( pr ), m_index( index ), m_sortDim( dimension ) {}

static int compareLow( const void* pv1, const void* pv2 )
{
RstarSplitEntry* pe1 = * ( RstarSplitEntry** ) pv1;
RstarSplitEntry* pe2 = * ( RstarSplitEntry** ) pv2;

Q_ASSERT( pe1->m_sortDim == pe2->m_sortDim );
assert( pe1->m_sortDim == pe2->m_sortDim );

if ( pe1->m_pRegion->m_pLow[pe1->m_sortDim] < pe2->m_pRegion->m_pLow[pe2->m_sortDim] ) return -1;
if ( pe1->m_pRegion->m_pLow[pe1->m_sortDim] > pe2->m_pRegion->m_pLow[pe2->m_sortDim] ) return 1;
Expand All @@ -152,7 +149,7 @@ namespace SpatialIndex
RstarSplitEntry* pe1 = * ( RstarSplitEntry** ) pv1;
RstarSplitEntry* pe2 = * ( RstarSplitEntry** ) pv2;

Q_ASSERT( pe1->m_sortDim == pe2->m_sortDim );
assert( pe1->m_sortDim == pe2->m_sortDim );

if ( pe1->m_pRegion->m_pHigh[pe1->m_sortDim] < pe2->m_pRegion->m_pHigh[pe2->m_sortDim] ) return -1;
if ( pe1->m_pRegion->m_pHigh[pe1->m_sortDim] > pe2->m_pRegion->m_pHigh[pe2->m_sortDim] ) return 1;
Expand All @@ -163,10 +160,10 @@ namespace SpatialIndex
class ReinsertEntry
{
public:
long m_id;
uint32_t m_index;
double m_dist;

ReinsertEntry( long id, double dist ) : m_id( id ), m_dist( dist ) {}
ReinsertEntry( uint32_t index, double dist ) : m_index( index ), m_dist( dist ) {}

static int compareReinsertEntry( const void* pv1, const void* pv2 )
{
Expand All @@ -189,5 +186,3 @@ namespace SpatialIndex
}; // Node
}
}

#endif /*__spatialindex_rtree_node_h*/
37 changes: 16 additions & 21 deletions ...core/spatialindex/rtree/PointerPoolNode.h → .../spatialindex/src/rtree/PointerPoolNode.h
View file
Original file line number Diff line number Diff line change
@@ -1,4 +1,3 @@
#include "qgslogger.h"
// Spatial Index Library
//
// Copyright (C) 2002 Navel Ltd.
Expand All @@ -25,16 +24,12 @@

#include "Node.h"

#define NDEBUG 1

using namespace SpatialIndex;

namespace Tools
{
template<> class PointerPool<RTree::Node>
{
public:
explicit PointerPool( unsigned long capacity ) : m_capacity( capacity )
explicit PointerPool( uint32_t capacity ) : m_capacity( capacity )
{
#ifndef NDEBUG
m_hits = 0;
Expand All @@ -45,19 +40,19 @@ namespace Tools

~PointerPool()
{
Q_ASSERT( m_pool.size() <= m_capacity );
assert( m_pool.size() <= m_capacity );

while ( ! m_pool.empty() )
{
RTree::Node* x = m_pool.top(); m_pool.pop();
#ifndef NDEBUG
m_pointerCount--;
--m_pointerCount;
#endif
delete x;
}

#ifndef NDEBUG
QgsDebugMsg( QString( "Lost pointers: %1" ).arg( m_pointerCount ) );
std::cerr << "Lost pointers: " << m_pointerCount << std::endl;
#endif
}

Expand All @@ -67,7 +62,7 @@ namespace Tools
{
RTree::Node* p = m_pool.top(); m_pool.pop();
#ifndef NDEBUG
m_hits++;
++m_hits;
#endif

return PoolPointer<RTree::Node>( p, this );
Expand All @@ -76,8 +71,8 @@ namespace Tools
else
{
// fixme: well sort of...
m_pointerCount++;
m_misses++;
++m_pointerCount;
++m_misses;
}
#endif

Expand All @@ -92,7 +87,7 @@ namespace Tools
{
if ( p->m_pData != 0 )
{
for ( unsigned long cChild = 0; cChild < p->m_children; cChild++ )
for ( uint32_t cChild = 0; cChild < p->m_children; ++cChild )
{
// there is no need to set the pointer to zero, after deleting it,
// since it will be redeleted only if it is actually initialized again,
Expand All @@ -111,30 +106,30 @@ namespace Tools
else
{
#ifndef NDEBUG
m_pointerCount--;
--m_pointerCount;
#endif
delete p;
}

Q_ASSERT( m_pool.size() <= m_capacity );
assert( m_pool.size() <= m_capacity );
}
}

unsigned long getCapacity() const { return m_capacity; }
void setCapacity( unsigned long c )
uint32_t getCapacity() const { return m_capacity; }
void setCapacity( uint32_t c )
{
m_capacity = c;
}

protected:
unsigned long m_capacity;
uint32_t m_capacity;
std::stack<RTree::Node*> m_pool;

#ifndef NDEBUG
public:
unsigned long m_hits;
unsigned long m_misses;
long m_pointerCount;
uint64_t m_hits;
uint64_t m_misses;
uint64_t m_pointerCount;
#endif
};
}
Expand Down
605 changes: 364 additions & 241 deletions src/core/spatialindex/rtree/RTree.cc → src/core/spatialindex/src/rtree/RTree.cc
View file

Large diffs are not rendered by default.

50 changes: 25 additions & 25 deletions src/core/spatialindex/rtree/RTree.h → src/core/spatialindex/src/rtree/RTree.h
View file
Original file line number Diff line number Diff line change
Expand Up @@ -19,8 +19,7 @@
// Email:
// mhadji@gmail.com

#ifndef __spatialindex_rtree_rtree_h
#define __spatialindex_rtree_rtree_h
#pragma once

#include "Statistics.h"
#include "Node.h"
Expand All @@ -32,7 +31,7 @@ namespace SpatialIndex
{
class RTree : public ISpatialIndex
{
class NNEntry;
//class NNEntry;

public:
RTree( IStorageManager&, Tools::PropertySet& );
Expand All @@ -57,16 +56,18 @@ namespace SpatialIndex

virtual ~RTree();



//
// ISpatialIndex interface
//
virtual void insertData( unsigned long len, const byte* pData, const IShape& shape, long shapeIdentifier );
virtual bool deleteData( const IShape& shape, long id );
virtual void insertData( uint32_t len, const byte* pData, const IShape& shape, id_type shapeIdentifier );
virtual bool deleteData( const IShape& shape, id_type id );
virtual void containsWhatQuery( const IShape& query, IVisitor& v );
virtual void intersectsWithQuery( const IShape& query, IVisitor& v );
virtual void pointLocationQuery( const Point& query, IVisitor& v );
virtual void nearestNeighborQuery( long k, const IShape& query, IVisitor& v, INearestNeighborComparator& );
virtual void nearestNeighborQuery( long k, const IShape& query, IVisitor& v );
virtual void nearestNeighborQuery( uint32_t k, const IShape& query, IVisitor& v, INearestNeighborComparator& );
virtual void nearestNeighborQuery( uint32_t k, const IShape& query, IVisitor& v );
virtual void selfJoinQuery( const IShape& s, IVisitor& v );
virtual void queryStrategy( IQueryStrategy& qs );
virtual void getIndexProperties( Tools::PropertySet& out ) const;
Expand All @@ -80,31 +81,30 @@ namespace SpatialIndex
void storeHeader();
void loadHeader();

void insertData_impl( unsigned long dataLength, byte* pData, Region& mbr, long id );
void insertData_impl( unsigned long dataLength, byte* pData, Region& mbr, long id, unsigned long level, byte* overflowTable );
bool deleteData_impl( const Region& mbr, long id );
void insertData_impl( uint32_t dataLength, byte* pData, Region& mbr, id_type id );
void insertData_impl( uint32_t dataLength, byte* pData, Region& mbr, id_type id, uint32_t level, byte* overflowTable );
bool deleteData_impl( const Region& mbr, id_type id );

long writeNode( Node* );
NodePtr readNode( unsigned long );
id_type writeNode( Node* );
NodePtr readNode( id_type page );
void deleteNode( Node* );

void rangeQuery( RangeQueryType type, const IShape& query, IVisitor& v );
void selfJoinQuery( long id1, long id2, const Region& r, IVisitor& vis );
void selfJoinQuery( id_type id1, id_type id2, const Region& r, IVisitor& vis );

IStorageManager* m_pStorageManager;

long m_rootID;
long m_headerID;
id_type m_rootID, m_headerID;

RTreeVariant m_treeVariant;

double m_fillFactor;

unsigned long m_indexCapacity;
uint32_t m_indexCapacity;

unsigned long m_leafCapacity;
uint32_t m_leafCapacity;

unsigned long m_nearMinimumOverlapFactor;
uint32_t m_nearMinimumOverlapFactor;
// The R*-Tree 'p' constant, for calculating nearly minimum overlap cost.
// [Beckmann, Kriegel, Schneider, Seeger 'The R*-tree: An efficient and Robust Access Method
// for Points and Rectangles', Section 4.1]
Expand All @@ -119,7 +119,7 @@ namespace SpatialIndex
// [Beckmann, Kriegel, Schneider, Seeger 'The R*-tree: An efficient and Robust Access Method
// for Points and Rectangles', Section 4.3]

unsigned long m_dimension;
uint32_t m_dimension;

Region m_infiniteRegion;

Expand All @@ -136,20 +136,23 @@ namespace SpatialIndex
std::vector<Tools::SmartPointer<ICommand> > m_readNodeCommands;
std::vector<Tools::SmartPointer<ICommand> > m_deleteNodeCommands;

#ifdef PTHREADS
#ifdef HAVE_PTHREAD_H
pthread_rwlock_t m_rwLock;
#else
bool m_rwLock;
#endif




class NNEntry
{
public:
long m_id;
id_type m_id;
IEntry* m_pEntry;
double m_minDist;

NNEntry( long id, IEntry* e, double f ) : m_id( id ), m_pEntry( e ), m_minDist( f ) {}
NNEntry( id_type id, IEntry* e, double f ) : m_id( id ), m_pEntry( e ), m_minDist( f ) {}
~NNEntry() {}

struct ascending : public std::binary_function<NNEntry*, NNEntry*, bool>
Expand Down Expand Up @@ -196,6 +199,3 @@ namespace SpatialIndex
std::ostream& operator<<( std::ostream& os, const RTree& t );
}
}

#endif /*__spatialindex_rtree_rtree_h*/

172 changes: 172 additions & 0 deletions src/core/spatialindex/src/rtree/Statistics.cc
View file
Original file line number Diff line number Diff line change
@@ -0,0 +1,172 @@
// Spatial Index Library
//
// Copyright (C) 2002 Navel Ltd.
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
//
// Email:
// mhadji@gmail.com

#include "../spatialindex/SpatialIndexImpl.h"

#include "Statistics.h"

using namespace SpatialIndex::RTree;

Statistics::Statistics()
{
reset();
}

Statistics::Statistics( const Statistics& s )
{
m_u64Reads = s.m_u64Reads;
m_u64Writes = s.m_u64Writes;
m_u64Splits = s.m_u64Splits;
m_u64Hits = s.m_u64Hits;
m_u64Misses = s.m_u64Misses;
m_u32Nodes = s.m_u32Nodes;
m_u64Adjustments = s.m_u64Adjustments;
m_u64QueryResults = s.m_u64QueryResults;
m_u64Data = s.m_u64Data;
m_u32TreeHeight = s.m_u32TreeHeight;
m_nodesInLevel = s.m_nodesInLevel;
}

Statistics::~Statistics()
{
}

Statistics& Statistics::operator=( const Statistics & s )
{
if ( this != &s )
{
m_u64Reads = s.m_u64Reads;
m_u64Writes = s.m_u64Writes;
m_u64Splits = s.m_u64Splits;
m_u64Hits = s.m_u64Hits;
m_u64Misses = s.m_u64Misses;
m_u32Nodes = s.m_u32Nodes;
m_u64Adjustments = s.m_u64Adjustments;
m_u64QueryResults = s.m_u64QueryResults;
m_u64Data = s.m_u64Data;
m_u32TreeHeight = s.m_u32TreeHeight;
m_nodesInLevel = s.m_nodesInLevel;
}

return *this;
}

uint64_t Statistics::getReads() const
{
return m_u64Reads;
}

uint64_t Statistics::getWrites() const
{
return m_u64Writes;
}

uint32_t Statistics::getNumberOfNodes() const
{
return m_u32Nodes;
}

uint64_t Statistics::getNumberOfData() const
{
return m_u64Data;
}

uint64_t Statistics::getSplits() const
{
return m_u64Splits;
}

uint64_t Statistics::getHits() const
{
return m_u64Hits;
}

uint64_t Statistics::getMisses() const
{
return m_u64Misses;
}

uint64_t Statistics::getAdjustments() const
{
return m_u64Adjustments;
}

uint64_t Statistics::getQueryResults() const
{
return m_u64QueryResults;
}

uint32_t Statistics::getTreeHeight() const
{
return m_u32TreeHeight;
}

uint32_t Statistics::getNumberOfNodesInLevel( uint32_t l ) const
{
uint32_t u32Nodes;
try
{
u32Nodes = m_nodesInLevel.at( l );
}
catch ( ... )
{
throw Tools::IndexOutOfBoundsException( l );
}

return u32Nodes;
}

void Statistics::reset()
{
m_u64Reads = 0;
m_u64Writes = 0;
m_u64Splits = 0;
m_u64Hits = 0;
m_u64Misses = 0;
m_u32Nodes = 0;
m_u64Adjustments = 0;
m_u64QueryResults = 0;
m_u64Data = 0;
m_u32TreeHeight = 0;
m_nodesInLevel.clear();
}

std::ostream& SpatialIndex::RTree::operator<<( std::ostream& os, const Statistics& s )
{
os << "Reads: " << s.m_u64Reads << std::endl
<< "Writes: " << s.m_u64Writes << std::endl
<< "Hits: " << s.m_u64Hits << std::endl
<< "Misses: " << s.m_u64Misses << std::endl
<< "Tree height: " << s.m_u32TreeHeight << std::endl
<< "Number of data: " << s.m_u64Data << std::endl
<< "Number of nodes: " << s.m_u32Nodes << std::endl;

for ( uint32_t u32Level = 0; u32Level < s.m_u32TreeHeight; ++u32Level )
{
os << "Level " << u32Level << " pages: " << s.m_nodesInLevel[u32Level] << std::endl;
}

os << "Splits: " << s.m_u64Splits << std::endl
<< "Adjustments: " << s.m_u64Adjustments << std::endl
<< "Query results: " << s.m_u64QueryResults << std::endl;

return os;
}
52 changes: 24 additions & 28 deletions src/core/spatialindex/rtree/Statistics.h → src/core/spatialindex/src/rtree/Statistics.h
View file
Original file line number Diff line number Diff line change
Expand Up @@ -19,8 +19,7 @@
// Email:
// mhadji@gmail.com

#ifndef __spatialindex_rtree_statistics_h
#define __spatialindex_rtree_statistics_h
#pragma once

namespace SpatialIndex
{
Expand All @@ -42,43 +41,43 @@ namespace SpatialIndex
//
// IStatistics interface
//
virtual unsigned long getReads() const;
virtual unsigned long getWrites() const;
virtual unsigned long getNumberOfNodes() const;
virtual unsigned long getNumberOfData() const;

virtual unsigned long getSplits() const;
virtual unsigned long getHits() const;
virtual unsigned long getMisses() const;
virtual unsigned long getAdjustments() const;
virtual unsigned long getQueryResults() const;
virtual unsigned long getTreeHeight() const;
virtual unsigned long getNumberOfNodesInLevel( unsigned long l ) const;
virtual uint64_t getReads() const;
virtual uint64_t getWrites() const;
virtual uint32_t getNumberOfNodes() const;
virtual uint64_t getNumberOfData() const;

virtual uint64_t getSplits() const;
virtual uint64_t getHits() const;
virtual uint64_t getMisses() const;
virtual uint64_t getAdjustments() const;
virtual uint64_t getQueryResults() const;
virtual uint32_t getTreeHeight() const;
virtual uint32_t getNumberOfNodesInLevel( uint32_t l ) const;

private:
void reset();

unsigned long m_reads;
uint64_t m_u64Reads;

unsigned long m_writes;
uint64_t m_u64Writes;

unsigned long m_splits;
uint64_t m_u64Splits;

unsigned long m_hits;
uint64_t m_u64Hits;

unsigned long m_misses;
uint64_t m_u64Misses;

unsigned long m_nodes;
uint32_t m_u32Nodes;

unsigned long m_adjustments;
uint64_t m_u64Adjustments;

unsigned long m_queryResults;
uint64_t m_u64QueryResults;

unsigned long m_data;
uint64_t m_u64Data;

unsigned long m_treeHeight;
uint32_t m_u32TreeHeight;

std::vector<unsigned long> m_nodesInLevel;
std::vector<uint32_t> m_nodesInLevel;

friend class RTree;
friend class Node;
Expand All @@ -92,6 +91,3 @@ namespace SpatialIndex
std::ostream& operator<<( std::ostream& os, const Statistics& s );
}
}

#endif /*__spatialindex_rtree_statistics_h*/

Loading