Debian Codegraph @

ChangeLog

raw
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.