/usr/include/geos/index/bintree/Bintree.h is in libgeos-dev 3.2.2-3ubuntu1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 | /**********************************************************************
* $Id: Bintree.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_IDX_BINTREE_BINTREE_H
#define GEOS_IDX_BINTREE_BINTREE_H
#include <geos/export.h>
#include <vector>
// Forward declarations
namespace geos {
namespace index {
namespace bintree {
class Interval;
class Root;
}
}
}
namespace geos {
namespace index { // geos::index
namespace bintree { // geos::index::bintree
/** \brief
* An BinTree (or "Binary Interval Tree")
* is a 1-dimensional version of a quadtree.
*
* It indexes 1-dimensional intervals (which of course may
* be the projection of 2-D objects on an axis).
* It supports range searching
* (where the range may be a single point).
*
* This implementation does not require specifying the extent of the inserted
* items beforehand. It will automatically expand to accomodate any extent
* of dataset.
*
* This index is different to the Interval Tree of Edelsbrunner
* or the Segment Tree of Bentley.
*/
class GEOS_DLL Bintree {
public:
/**
* Ensure that the Interval for the inserted item has non-zero extents.
* Use the current minExtent to pad it, if necessary
*
* NOTE: in GEOS this function always return a newly allocated object
* with ownership transferred to caller. TODO: change this ?
*
* @param itemInterval
* Source interval, ownership left to caller, no references hold.
*/
static Interval* ensureExtent(const Interval *itemInterval,
double minExtent);
Bintree();
~Bintree();
int depth();
int size();
int nodeSize();
/// @param itemInterval
/// Ownership left to caller, NO reference hold by this class.
///
/// @param item
/// Ownership left to caller, reference kept by this class.
///
void insert(Interval *itemInterval, void* item);
std::vector<void*>* iterator();
std::vector<void*>* query(double x);
std::vector<void*>* query(Interval *interval);
void query(Interval *interval,
std::vector<void*> *foundItems);
private:
std::vector<Interval *>newIntervals;
Root *root;
/**
* Statistics
*
* minExtent is the minimum extent of all items
* inserted into the tree so far. It is used as a heuristic value
* to construct non-zero extents for features with zero extent.
* Start with a non-zero extent, in case the first feature inserted has
* a zero extent in both directions. This value may be non-optimal, but
* only one feature will be inserted with this value.
*/
double minExtent;
void collectStats(Interval *interval);
};
} // namespace geos::index::bintree
} // namespace geos::index
} // namespace geos
#endif // GEOS_IDX_BINTREE_BINTREE_H
/**********************************************************************
* $Log$
* Revision 1.1 2006/03/22 16:01:33 strk
* indexBintree.h header split, classes renamed to match JTS
*
**********************************************************************/
|