bump version to 12.2.2-pve1

[ceph.git] / ceph / src / boost / libs / geometry / doc / index / rtree / creation.qbk

[/============================================================================
  Boost.Geometry Index

  Copyright (c) 2011-2012 Adam Wulkiewicz.

  Use, modification and distribution is subject to the Boost Software License,
  Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  http://www.boost.org/LICENSE_1_0.txt)
=============================================================================/]

[section Creation and Modification]

[h4 Template parameters]

__rtree__ has 5 parameters but only 2 are required:

 rtree<Value,
       Parameters,
       IndexableGetter = index::indexable<Value>,
       EqualTo = index::equal_to<Value>,
       Allocator = std::allocator<Value> >

* `__value__` - type of object which will be stored in the container,
* `Parameters` - parameters type, inserting/splitting algorithm,
* `IndexableGetter` - function object translating `__value__` to `__indexable__` (`__point__` or `__box__`) which __rtree__ can handle,
* `EqualTo` - function object comparing `__value__`s,
* `Allocator` - `Value`s allocator, all allocators needed by the container are created from it.

[h4 Values and Indexables]

__rtree__ may store `__value__`s of any type as long as passed function objects know how to interpret those `__value__`s, that is
extract an `__indexable__` that the __rtree__ can handle and compare `__value__`s.
The `__indexable__` is a type adapted to Point, Box or Segment concept.
The examples of rtrees storing `__value__`s translatable to various `__indexable__`s are presented below.

[table
[[rtree<Point, ...>] [rtree<Box, ...>] [rtree<Segment, ...>]]
[[[$img/index/rtree/rtree_pt.png]] [[$img/index/rtree/rstar.png]] [[$img/index/rtree/rtree_seg.png]]]
]

By default function objects `index::indexable<Value>` and `index::equal_to<Value>` are defined for some typically used `__value__`
types which may be stored without defining any additional classes. By default the rtree may store pure `__indexable__`s, pairs
and tuples. In the case of those two collection types, the `__indexable__` must be the first stored type.

* `__indexable__ = __point__ | __box__ | Segment`
* `__value__ = Indexable | std::pair<__indexable__, T> | boost::tuple<__indexable__, ...> [ | std::tuple<__indexable__, ...> ]`

By default `boost::tuple<...>` is supported on all compilers. If the compiler supports C++11 tuples and variadic templates
then `std::tuple<...>` may be used "out of the box" as well.

Examples of default `__value__` types:

 geometry::model::point<...>
 geometry::model::point_xy<...>
 geometry::model::box<...>
 geometry::model::segment<...>
 std::pair<geometry::model::box<...>, unsigned>
 boost::tuple<geometry::model::point<...>, int, float>

The predefined `index::indexable<Value>` returns const reference to the `__indexable__` stored in the `__value__`.

[important The translation is done quite frequently inside the container - each time the rtree needs it. ]

The predefined `index::equal_to<Value>`:

* for `__point__`, `__box__` and `Segment` - compares `__value__`s with geometry::equals().
* for `std::pair<...>` - compares both components of the `__value__`. The first value stored in the pair is compared before the second one.
  If the value stored in the pair is a Geometry, `geometry::equals()` is used. For other types it uses `operator==()`.
* for `tuple<...>` - compares all components of the `__value__`. If the component is a `Geometry`, `geometry::equals()`
  function is used. For other types it uses `operator==()`.

[h4 Balancing algorithms compile-time parameters]

`__value__`s may be inserted to the __rtree__ in many various ways. Final internal structure
of the __rtree__ depends on algorithms used in the insertion process and parameters. The most important is
nodes' balancing algorithm. Currently, three well-known types of R-trees may be created.

Linear - classic __rtree__ using balancing algorithm of linear complexity

 index::rtree< __value__, index::linear<16> > rt;

Quadratic - classic __rtree__ using balancing algorithm of quadratic complexity

 index::rtree< __value__, index::quadratic<16> > rt;

R*-tree - balancing algorithm minimizing nodes' overlap with forced reinsertions
 
 index::rtree< __value__, index::rstar<16> > rt;

[h4 Balancing algorithms run-time parameters]

Balancing algorithm parameters may be passed to the __rtree__ in run-time.
To use run-time versions of the __rtree__ one may pass parameters which
names start with `dynamic_`.

 // linear
 index::rtree<__value__, index::dynamic_linear> rt(index::dynamic_linear(16));

 // quadratic
 index::rtree<__value__, index::dynamic_quadratic> rt(index::dynamic_quadratic(16));

 // rstar
 index::rtree<__value__, index::dynamic_rstar> rt(index::dynamic_rstar(16));

The obvious drawback is a slightly slower __rtree__.

[h4 Non-default parameters]

Non-default R-tree parameters are described in the reference.

[h4 Copying, moving and swapping]

The __rtree__ is copyable and movable container. Move semantics is implemented using Boost.Move library
so it's possible to move the container on a compilers without rvalue references support.

 // default constructor
 index::rtree< __value__, index::rstar<8> > rt1;

 // copy constructor
 index::rtree< __value__, index::rstar<8> > rt2(r1);

 // copy assignment
 rt2 = r1;

 // move constructor
 index::rtree< __value__, index::rstar<8> > rt3(boost::move(rt1));

 // move assignment
 rt3 = boost::move(rt2);

 // swap
 rt3.swap(rt2);

[h4 Inserting and removing Values]

The following code creates an __rtree__ using quadratic balancing algorithm.

 using namespace boost::geometry;
 typedef std::pair<Box, int> __value__;
 index::rtree< __value__, index::quadratic<16> > rt;

To insert or remove a `__value__' by method call one may use the following
code.

 __value__ v = std::make_pair(__box__(...), 0);

 rt.insert(v);

 rt.remove(v);

To insert or remove a `__value__' by function call one may use the following
code.

 __value__ v = std::make_pair(__box__(...), 0);

 index::insert(rt, v);

 index::remove(rt, v);

Typically you will perform those operations in a loop in order to e.g. insert
some number of `__value__`s corresponding to geometrical objects (e.g. `Polygons`)
stored in another container.

[h4 Additional interface]

The __rtree__ allows creation, inserting and removing of Values from a range. The range may be passed as
`[first, last)` Iterators pair or as a Range adapted to one of the Boost.Range Concepts.

 namespace bgi = boost::geometry::index;
 typedef std::pair<Box, int> __value__;
 typedef bgi::rtree< __value__, bgi::linear<32> > RTree;

 std::vector<__value__> values;
 /* vector filling code, here */

 // create R-tree with default constructor and insert values with insert(Value const&)
 RTree rt1;
 BOOST_FOREACH(__value__ const& v, values)
    rt1.insert(v);

 // create R-tree with default constructor and insert values with insert(Iter, Iter)
 RTree rt2;
 rt2.insert(values.begin(), values.end());

 // create R-tree with default constructor and insert values with insert(Range)
 RTree rt3;
 rt3.insert(values_range);

 // create R-tree with constructor taking Iterators
 RTree rt4(values.begin(), values.end());

 // create R-tree with constructor taking Range
 RTree rt5(values_range);

 // remove values with remove(Value const&)
 BOOST_FOREACH(__value__ const& v, values)
    rt1.remove(v);

 // remove values with remove(Iter, Iter)
 rt2.remove(values.begin(), values.end());

 // remove values with remove(Range)
 rt3.remove(values_range);

Furthermore, it's possible to pass a Range adapted by one of the Boost.Range adaptors into the rtree (more complete example can be found in the *Examples* section).

 // create Rtree containing `std::pair<Box, int>` from a container of Boxes on the fly.
 RTree rt6(boxes | boost::adaptors::indexed()
                 | boost::adaptors::transformed(pair_maker()));

[h4 Insert iterator]

There are functions like `std::copy()`, or __rtree__'s queries that copy values to an output iterator.
In order to insert values to a container in this kind of function insert iterators may be used.
Geometry.Index provide its own `bgi::insert_iterator<Container>` which is generated by
`bgi::inserter()` function.

 namespace bgi = boost::geometry::index;
 typedef std::pair<Box, int> __value__;
 typedef bgi::rtree< __value__, bgi::linear<32> > RTree;

 std::vector<__value__> values;
 /* vector filling code, here */

 // create R-tree and insert values from the vector
 RTree rt1;
 std::copy(values.begin(), values.end(), bgi::inserter(rt1));
 
 // create R-tree and insert values returned by a query
 RTree rt2;
 rt1.spatial_query(Box(/*...*/), bgi::inserter(rt2));

[endsect] [/ Creation and Modification /]