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