| 1 |
libkdtree++ ChangeLog |
| 2 |
===================== |
| 3 |
|
| 4 |
2008-11-17 Sylvain Bougerel <[email protected]> |
| 5 |
|
| 6 |
- Added #include<cstdio> in order to compile 'printf' statements in the |
| 7 |
file 'examples/test_find_within_range.cpp'. |
| 8 |
- Added patch from Max Fellermann in order to compile libkdtree++ with |
| 9 |
clang++. |
| 10 |
|
| 11 |
2009-02-10 Paul Harris <[email protected]> |
| 12 |
|
| 13 |
- Bug fix: was incorrectly casting a pointer when the search key type |
| 14 |
was different to the stored type. |
| 15 |
|
| 16 |
2008-12-30 Paul Harris <[email protected]> |
| 17 |
|
| 18 |
- New function: efficient_replace_and_optimise(). |
| 19 |
Yes, its a long name. Sylvain doesn't like it. |
| 20 |
The reason for the long name is that it is a dangerous function, |
| 21 |
and it will resort whatever vector<> of data that you pass it. |
| 22 |
So I wanted the user to really know what they were doing before |
| 23 |
they called this function. |
| 24 |
- Now calls sqrt() when required in order to search for items |
| 25 |
in 'real' distance units... And so it will accept and return distance |
| 26 |
in 'real' units (as opposed to squared units). |
| 27 |
This is not an ideal solution, we have all sorts of ideas to improve |
| 28 |
kdtree which will include less calls to sqrt() for more speed, and |
| 29 |
the ability to change the standard euclidean distance measurements |
| 30 |
for distance-on-a-sphere or whatever the user wants. |
| 31 |
- Changed from using std::sort() to std::nth_element() when optimising |
| 32 |
the tree. Performance boost. |
| 33 |
- Added lots of tests to check that the find functions are working |
| 34 |
correctly when fed edge-cases, including: |
| 35 |
- Items that are exactly 'max' distance away from the target. |
| 36 |
- When there are no value items to find. |
| 37 |
- Templated the find functions so that the target/center point can be |
| 38 |
anything that can be accessed via the Accessor. |
| 39 |
- Fixes to make it compile. |
| 40 |
|
| 41 |
- And, a Python wrapper ! See README.Python |
| 42 |
|
| 43 |
- CMake support now can build the python wrapper and install the headers |
| 44 |
and the python wrapper to a destination folder. Its simple, but neat. |
| 45 |
Does not install python module into the python site packages or anything |
| 46 |
like that. |
| 47 |
|
| 48 |
2008-11-17 Sylvain Bougerel <[email protected]> |
| 49 |
|
| 50 |
- The version number of the library is now part of the headers. |
| 51 |
- Fixed a bug with assignment operator. |
| 52 |
- Fixed uninitialized memory problem with valgrind, when printing the |
| 53 |
content of the tree. Due to the fact the _M_header was a _Link_type |
| 54 |
instead of a _Node_base type and _M_root was a _Base_ptr type instead of |
| 55 |
a _Link_type. |
| 56 |
- Paul Harris fixed find() by ensuring that the correct node is being |
| 57 |
matched during a find(). Thus, fixed a similar problem in erase. Paul |
| 58 |
also added a new test courtesy of Hayne. |
| 59 |
- Paul Harris augmented test_kdtree with various test on copy |
| 60 |
construction, assignment, and formatting operator. |
| 61 |
- Paul Harris added support for CMake, which should suit not only |
| 62 |
MSVC users but others too. |
| 63 |
- Paul Harris fixed bug with compiling with MSVC2005 with the 64bit |
| 64 |
warnings turned on. |
| 65 |
|
| 66 |
2008-11-12 Sylvain Bougerel <[email protected]> |
| 67 |
|
| 68 |
- Fix segfault on the regular iterator when _M_header->_M_right == |
| 69 |
_M_root. Fix segfault on the reverse iterator when _M_header->_M_left == |
| 70 |
_M_root. |
| 71 |
|
| 72 |
Besides, it also change the behavior when iterating past the end() or |
| 73 |
rend(). Previously this would result in segfaults, now it makes the |
| 74 |
iterator points to an undetermined location in the tree, similarly to |
| 75 |
the current implementation of GNU libstdc++. |
| 76 |
|
| 77 |
2008-11-10 Sylvain Bougerel <[email protected]> |
| 78 |
|
| 79 |
- kdtree++/iterator.hpp (KDTree): the decrement iterator was |
| 80 |
ill-written. Its buggy behavior, and the use of non-standard |
| 81 |
reverse_iterator initialiser needed to be fixed. These error were do to |
| 82 |
a previous failed attempt by me at fixing the reverse_iterator. |
| 83 |
|
| 84 |
This time, I believe I got it right, however it needed the kdtree |
| 85 |
structure to be modified. The reason is that without modification it is |
| 86 |
not possible to distinguish the "header" from the "root" within the |
| 87 |
iterator. This is required for the reverse_iterator to work properly. |
| 88 |
|
| 89 |
Now the kdtree has an additional pointer that points directly to the |
| 90 |
root. The parent pointer of the header is permanently null. And |
| 91 |
therefore the header can be distinguished from the root within the |
| 92 |
iterator by checking the parent of the current node: if it is null, we |
| 93 |
are at the header. |
| 94 |
|
| 95 |
|
| 96 |
2008-11-10 Sylvain Bougerel ([email protected]) |
| 97 |
|
| 98 |
- patch from Martin Shreiber to make libkdtree to compile with newer |
| 99 |
version of g++-4.2 and g++4.3. |
| 100 |
|
| 101 |
- patch from Paul Harris to make libkdtree more exception transparent. |
| 102 |
|
| 103 |
2007-12-08 Sylvain Bougerel ([email protected]) |
| 104 |
|
| 105 |
- fix bug where find_nearest() could return the wrong value if a |
| 106 |
maximum distance greater than the root distance to the target value |
| 107 |
was given in argument to the function. |
| 108 |
|
| 109 |
- find_nearest() still returns SQUARED value of the distance. You still |
| 110 |
have to use sqrt() on the second member of the iterator. |
| 111 |
|
| 112 |
- find_nearest() behavior was slightly changed: if many nodes are at |
| 113 |
the same distance from the target value, the node with the lowest |
| 114 |
memory address will be returned. This is to catter for the |
| 115 |
reimplementation of find_exact() coming soon. |
| 116 |
|
| 117 |
2007-12-02 Sylvain Bougerel ([email protected]) |
| 118 |
|
| 119 |
- find_nearest() now returned the SQUARED value of the distance for |
| 120 |
euclidean space calculation (the default). You have to use sqrt() on |
| 121 |
the returned distance (i.e. iterator->second) if you want to read the |
| 122 |
absolute distance returned by find_nearest. My apologies for not |
| 123 |
making highlighting this beforehand. |
| 124 |
|
| 125 |
- Increased the performance of find and find_nearest/find_nearest_if by |
| 126 |
about 50x to 100x depending on your compilation flags. |
| 127 |
|
| 128 |
- KDTree are not defined as: |
| 129 |
KDTree<__K, _Val, _Acc, _Cmp, _Alloc> |
| 130 |
but as: |
| 131 |
KDTree<__K, _Val, _Acc, _Dist, _Cmp, _Alloc> |
| 132 |
So pay attention to the _Dist functor. The distance functor calculate |
| 133 |
the squared difference between 2 elements returned by the accessor. You |
| 134 |
might have to change your code to reflect the new definition, or it wont |
| 135 |
compile if you have set custom accessor and comparison functors. |
| 136 |
|
| 137 |
- The following functors are now accessible in the tree: |
| 138 |
- the comparison functor, accessible by copy only |
| 139 |
- the accessor functor, accessible by copy only |
| 140 |
- the distance functor, accessible read-write, this means that |
| 141 |
you can modify the behavior of find, find_nearest, |
| 142 |
find_nearest_if within the same KDTree object. |
| 143 |
|
| 144 |
- find_exact has not be modified and retained the code of the former, |
| 145 |
slower algorithm. I have to write some more code to do this. Pls wait a |
| 146 |
little more. |
| 147 |
|
| 148 |
- The file accessor.hpp was renamed as function.hpp for it now boast |
| 149 |
more than just the KDTree accessor |
| 150 |
|
| 151 |
2007-11-25 Sylvain Bougerel ([email protected]) |
| 152 |
|
| 153 |
- fixed the reverse_iterator. Now it can be used. |
| 154 |
|
| 155 |
2007-10-24 Sylvain Bougerel ([email protected]) |
| 156 |
|
| 157 |
- Removal of all the warnings that are yield by the compiler when |
| 158 |
using the following flags: |
| 159 |
-Wall -pedantic -ansi |
| 160 |
Do not hesitate to suggest any flags for additional code checking. |
| 161 |
|
| 162 |
This release also feature numerous of enhancements by Paul Harris |
| 163 |
([email protected]): |
| 164 |
- const kdtrees can be searched |
| 165 |
- find_nearest_if() enforce validation of a predicate |
| 166 |
- visit_within_range() walk the tree and calls |
| 167 |
Visitor::operator() on template argument <Visitor> for |
| 168 |
each node within the range |
| 169 |
- find_exact() matches an kdtree::value_type by location and by |
| 170 |
calling kdtree::value_type::operator==() (in case two different |
| 171 |
items have the same location find_exact() will not return the |
| 172 |
wrong item) |
| 173 |
- erase_exact() is to erase() what find_exact() is to find() |
| 174 |
- check_tree() and num_dist_calcs for debugging purpose plus |
| 175 |
additional improvements on erase and region intersection |
| 176 |
|
| 177 |
2004-11-26 Paul Harris ([email protected]) |
| 178 |
|
| 179 |
- New feature: find_nearest() |
| 180 |
- Accessors can now be initialised with the tree, so ptr_fun() |
| 181 |
or functors can be used to access datapoints. |
| 182 |
- Accessors now much more generic, so you can use the same |
| 183 |
accessor to access multiple types. |
| 184 |
- Range-constructors now optimise() automatically, simplifying |
| 185 |
the construction of a filled tree. |
| 186 |
- _Range is now more easy to construct. |
| 187 |
|
| 188 |
2004-11-15 Martin F. Krafft ([email protected]) |
| 189 |
|
| 190 |
- fixed numerous little bugs that led to compilation problems |
| 191 |
- changed code to compile cleanly with GCC 3.4 and GCC 4.0 |
| 192 |
|
| 193 |
2004-11-06 Martin F. Krafft ([email protected]) |
| 194 |
|
| 195 |
- reverted to optimise() to prevent API change, and added an optimize() |
| 196 |
passthrough method with an appropriate comment. |
| 197 |
|
| 198 |
2004-11-05 Paul Harris ([email protected]) |
| 199 |
|
| 200 |
- Renamed optimise() to optimize(). |
| 201 |
- Added a full set of range constructors and insert(range) methods. |
| 202 |
it now works with inserter(tree,tree.begin()) |
| 203 |
- Target type no longer needs a default constructor. This also fixes |
| 204 |
problems with empty trees (would crash if optimized). |
| 205 |
- Some code cleanup (removed inlines, switched from const_iterator to |
| 206 |
iterator, added this-> to ensure the methods are called). |
| 207 |
- Added a new method: count_within_range(). |
| 208 |
- Fixed bug in rend(). |
| 209 |
|
| 210 |
2004-11-04 Martin F. Krafft ([email protected]) |
| 211 |
|
| 212 |
- Integrated patch by Paul Harris to fix a logic error pertaining to |
| 213 |
OutputIterators in find_within_range. find_within_range() now |
| 214 |
returns the output iterator instead of a count. Thanks, Paul! |
| 215 |
- Added another fix by Paul Harris to _M_get_j_max, which would cause |
| 216 |
a dimensional overflow for trees with depths >= K. Thanks (again) Paul! |
| 217 |
- Made some improvements to the autotools files. |
| 218 |
|
| 219 |
2004-05-11 Martin F. Krafft ([email protected]) |
| 220 |
|
| 221 |
- Fixed CFlags and Libs entries in pkgconfig file. |
| 222 |
|
| 223 |
2004-05-11 Martin F. Krafft ([email protected]) |
| 224 |
|
| 225 |
- Initial release. |
| 226 |
|
| 227 |
|
| 228 |
COPYRIGHT -- |
| 229 |
libkdtree++ is (c) 2004-2007 Martin F. Krafft <[email protected]> and |
| 230 |
Sylvain Bougerel <[email protected]> and distributed under the |
| 231 |
terms of the Artistic License 2.0. See the ./COPYING file in the source tree |
| 232 |
root for more information. |
| 233 |
|
| 234 |
THIS PACKAGE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED WARRANTIES, |
| 235 |
INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND |
| 236 |
FITNESS FOR A PARTICULAR PURPOSE. |