libkdtree-devel — Developer discussion list

tarball contents

[martin f k. <ma...@ma...>]

Hi,

The directory in the tarball is named libkdtree++_0.6.2 but should
be named libkdtree++-0.6.2 by convention.

Cheers,

-- 
martin | http://madduck.net/ | http://two.sentenc.es/
 
"i can stand brute force, but brute reason is quite unbearable. there
 is something unfair about its use. it is hitting below the
 intellect."
                                                        -- oscar wilde
 
spamtraps: mad...@ma...

libkdtree moved to git.debian.org

[martin f k. <ma...@ma...>]

Hello,

this is to let you know that we moved the libkdtree code from
sourceforge to alioth.debian.org. It is now maintained in git.

Please see http://libkdtree.alioth.debian.org for more info. I will
automatically move over your -devel and -cvs list memberships to the
new list, but *not* -announce, as there is no longer an announcement
list. I suppose we can use freshmeat for that:
  http://freshmeat.net/projects/libkdtree/ [updates pending]

The sourceforge project will soon be deleted.

Cheers,

--=20
martin;              (greetings from the heart of the sun.)
  \____ echo mailto: !#^."<*>"|tr "<*> mailto:" net@madduck
=20
apt-get source --compile gentoo
=20
spamtraps: mad...@ma...

Re: changes fix #2

[martin f k. <ma...@ma...>]

also sprach Paul <ele...@ya...> [2004.11.05.0320 +0100]:
> Thought I'd better run the changes past you before I checked them in.=20

Ah, lovely fucking sourceforge crap. Sorry for my French there, but
they are highly annoying. I shall move this library to
alioth.debian.org soon.

> Looked at std::set and std::list, and the stl documentation for
> stuff on associative container concepts, sequence concepts etc.
> Not sure exactly what applies here, but I just added support for
> what looked ok.

Cool.

> always disregarded (at least at this stage).  It might in the
> future be helpful for insertion hints (like in set), but that is
> Future with a capital F. Not now.

I checked out insertion hints, but they are impossible to manage, as
the tree itself is not sorted across the contained elements, only
down a single root->leaf walk.

> I also removed the requirement for types to have
> default-construction. Previously for a type to work with kdtree++,
> it required a Type() style constructor.  This is unnecessary 	as
> demonstrated by set's constructor.

Could you elaborate on this, please?

> I readded the 'iterator' type.  set uses iterator instead of
> const_iterator in all of its definitions except for find() etc.
> Both are defined as the same type.  Scott Meyers (i think?)
> recommended not using const_iterator too much, as its a pain if
> you want to use it in some algorithms (which require iterators for
> whatever reason)... whatever, we should try and follow what others
> do - everything except find() uses iterator.

Mh, I would be interested in the reference. Scott Meyers says many
things, and I surely don't approve of all. If algorithms use
iterators without modifying the element pointed to, then it's a bug
in the algorithm, not in kdtree.

I also think that following the others is the way to go... unless
I have to implement all the whacko bugs and hacks the STL contains.

> I removed 'inline' declarations in front of method calls.  They
> are not required...

True, but I always like to make things explicit. In this case,
however, I am willing to go along without further discussion.

> I added a count_within_range() method for simply counting the
> number of items inside a range.  This is more efficient than doing
> a find if you just want a count, since the values aren't written
> to an output iterator.

Yeah, nice!

> I added this-> to some of the method calls. The STL does this,
> presumably to avoid confusing the calls with free-function calls.
> This is also probably why the STL 'reserves'
> function/method/variable names starting with __

Yes, precisely. Thanks for catching these.

> I am torn between american-ising the spelling, and not.=20

As I said, let's do both. I don't want the API to change right now.
Let's add optimize() to call optimise() and add some snide comment
in there about how British English is superior :)

> I renamed _M_meta to _M_header because they call it that in set<>.

Fine.

> I noticed rend() returned reverse_iterator(end()).  It should
> return begin().

Oops.

> - Improve operator=3D() and copy-constructor... theres a faster way
> of copying the tree across.

Certainly.

> - I looked at erase(), It would be nice to have a fast rebalancer
> like set, but right now thats asking too much.

Ha! Have a ball. I tore out my hair for two days on this. I may well
simply have overlooked it though.

If you figure something out, you know it's worth an ACM or IEEE
paper!

Again, Paul, thanks for your help.

--=20
martin;              (greetings from the heart of the sun.)
  \____ echo mailto: !#^."<*>"|tr "<*> mailto:" net@madduck
=20
invalid/expired pgp subkeys? use subkeys.pgp.net as keyserver!
spamtraps: mad...@ma...
=20
"if i am occasionally a little overdressed, i make up for it by being
 always immensely over-educated."
                                                        -- oscar wilde

Re: Fixing problems

[martin f k. <ma...@ma...>]

also sprach Paul <ele...@ya...> [2004.11.04.1040 +0100]:
> Why do you need to follow an erase() with an optimise() call?  Is
> it possible to keep the tree correct when erasing?  Is this a bug
> or by design?

It is not necessary to call it after every erase, but since an erase
must do a search, subsequent erases are going to be increasingly
slower.

I don't think it is a bug, nor did I make this a design choice. The
KDTree algorithm does not provide for maintaining a balanced tree
(e.g. like a red-black tree). In addition, I have been unable to
come up with an efficient means to keep the tree balanced.

> Is optimise() always required, even after an insert() ?

No, but before the first search. I usually insert thousands of items
and then optimise once before using the tree.

> This is a huge problem if you want to remove a bunch of items...

I know. I would be happy to discuss possible solutions, but I don't
think it's going to be trivial. The algorithm exists since 1975 and
so far, no solution has been found.

--=20
martin;              (greetings from the heart of the sun.)
  \____ echo mailto: !#^."<*>"|tr "<*> mailto:" net@madduck
=20
invalid/expired pgp subkeys? use subkeys.pgp.net as keyserver!
spamtraps: mad...@ma...
=20
"montag, why do you burn books?"
"it's a job like any other, pay is good and there is a lot of variety."
                                                -- ray bradbury (f451)

Re: [cvs] libkdtree++ ChangeLog,1.6,1.7 NEWS,1.2,1.3 README,1.6,1.7 TODO,1.1,1.2

[Martin F K. <kr...@ai...>]

Paul,

Thanks for your changes! Here are some comments and questions:

also sprach Paul Harris (krafft),,, <ph...@cv...> [2004.11.05.0938=
 +0100]:
> +++ README	5 Nov 2004 08:38:09 -0000	1.7
> +It is ok to call insert(value) many times and optimize() at the end, but=
=20
> +every erase() call should be followed with optimize().

Well, not necessarily, but erases could take longer since searches
are involved.

> +++ TODO	5 Nov 2004 08:38:09 -0000	1.2
> +- keep tree balanced in insert() and erase().

this is a nice TODO, but i banged my head over it for a day or two
with no real success. The only way is to optimise after each insert
and erase, but that's going to cost a lot. I prefer to batch-load
the tree, optimise it once, then use it. Furthermore, erasing is
probably not needed IME.

> +++ ChangeLog	5 Nov 2004 08:38:09 -0000	1.7
> +	- Renamed optimise() to optimize().

You want to fight over this? :)

Mh, I would prefer to have this changed back, not because British is
the way to go, but because you are making an API change.

For all I care, let's provide a second inline method optimise which
just calls the other.

> +	- Some code cleanup=20
> removed inlines,

why?

> switched from const_iterator to iterator

why? I make it an effort always to use const unless it's not needed.

I am not sure I see the reason behind your changing of the
constness of the iterators. Please explain!

> +      void insert(_InputIterator __first, _InputIterator __last) {
> +         for ( ; __first !=3D __last; ++__first )
> +            this->insert(*__first);
> +      }

I would prefer these to be done in while loops, I think...

  while (__first !=3D __last) this->insert(*__first++)

but it does not matter really.

> +      insert(iterator __pos, size_type __n, const value_type& __x)
>        {
> +        for ( ; __n > 0; --__n)

On a side note, you are not very consistent about spaces before and
after parentheses. Sometimes they are there, sometimes not. I prefer
them not to be there. Unless you object, let's keep it that way.
I know, this is pedantic. It's not a big thing...

> -        return (_Link_type&) _M_meta->_M_right;=20
> +        return (_Link_type&) _M_header->_M_right;=20

Why did you change most _M_meta for _M_header?

> -      _Link_type _M_meta;
> +      _Link_type _M_header;

Oh, I see. Is there a reason for this change? Or just your
preference? I chose meta because a tree can be seen as a triangle,
and the header node sort of sits *above* that, with its three pointers
going to the three corners.

Thanks for your work!

--=20
Martin F. Krafft                Artificial Intelligence Laboratory
Ph.D. Student                   Department of Information Technology
Email: kr...@ai...          University of Zurich
Tel: +41.(0)44.63-54323         Andreasstrasse 15, Office 2.18
http://ailab.ch/people/krafft   CH-8050 Zurich, Switzerland
=20
Invalid/expired PGP subkeys? Use subkeys.pgp.net as keyserver!
Spamtraps: kra...@ai... kra...@if...
=20
"a mathematician is a device for turning coffee into theorems."
                                                         -- paul erd=F6s

changes fix #2

[Paul <ele...@ya...>]

Don't think i attached it ...

Hi,

Thought I'd better run the changes past you before I checked them in.
Attached is the diff.  Let me know if you are happy with it, I'd love to
check it in myself.



Lots of changes... to make your old code work with the new library, the
changes you will need to do include:

- find_within_range() doesn't return a size_t anymore (thats a previous
patch)
- its optimize() not optimise()  (read on for more about why)


The changes:

Looked at std::set and std::list, and the stl documentation for stuff on
associative container concepts, sequence concepts etc.  Not sure exactly
what applies here, but I just added support for what looked ok.

Theres now a full set of constructors, including default and range. You
can also pass an allocator (STL does, I never use the feature... not yet
anyway).  Fill constructors are obviously not appropriate for this one.
Note that this probably is closest to a priority_queue, which is
actually an adapted vector<>.  They don't seem to stick to a single
concept specifically, so I guess we have some room to move.  Range
constructors are great.  Just do Tree tree(begin,end); and its filled
and ready to go... after an optimisation.

Theres also now a full set of inserters.  This allows
inserter(cont,cont.begin()) to work.  Note the 'position' iterator is
always disregarded (at least at this stage).  It might in the future be
helpful for insertion hints (like in set), but that is Future with a
capital F. Not now.

I also removed the requirement for types to have default-construction.
Previously for a type to work with kdtree++, it required a Type() style
constructor.  This is unnecessary 	as demonstrated by set's constructor.
    I also had to slightly change the way it was destroyed.  I just
followed the example in std::set.
This also fixed problems demonstrated by:
KDTree<3,Point> tree;
assert( tree.begin() == tree.end() ); // this would fail !!
tree.optimise();  // segmentation fault!!

I readded the 'iterator' type.  set uses iterator instead of
const_iterator in all of its definitions except for find() etc.  Both
are defined as the same type.  Scott Meyers (i think?) recommended not
using const_iterator too much, as its a pain if you want to use it in
some algorithms (which require iterators for whatever reason)...
whatever, we should try and follow what others do - everything except
find() uses iterator.

I removed 'inline' declarations in front of method calls.  They are not
required... IIRC inline methods are more like hints to the compiler,
'inline' is much more useful for free functions, which will create
multiple implementation instances without the inline (and cause all
sorts of link collisions).   The compiler will figure out if its best to
inline or not, its hard for us to know best.   an example is std::set.
the only inline functions are things like operator==() and in
stl_tree.h: _Rb_tree_rebalance().  These are both free functions and
must be inlined if you want to keep them in a header file.

I added a count_within_range() method for simply counting the number of
items inside a range.  This is more efficient than doing a find if you
just want a count, since the values aren't written to an output iterator.

I added this-> to some of the method calls. The STL does this,
presumably to avoid confusing the calls with free-function calls.  This
is also probably why the STL 'reserves' function/method/variable names
starting with __

I am torn between american-ising the spelling, and not.  As an aussie, i
get a bit pissed off when i have to continuously spell in american, or
mix spellings.  I bet non-english speakers feel the same way.  However,
for the sake of consistency, its best to americanise. americanize.  So i
renamed optimise().  I hate the 'z', so if you insist on the old
spelling, I won't be disappointed, but I bet we would have to switch
back eventually.  Until Australian becomes the world's standard language.

I renamed _M_meta to _M_header because they call it that in set<>.

I noticed rend() returned reverse_iterator(end()).  It should return
begin().

In optimize(), I use a range constructor instead of a copy().  This will
be faster.




Things that could still possibly be done:
- Improve operator=() and copy-constructor... theres a faster way of
copying the tree across.
- I looked at erase(), It would be nice to have a fast rebalancer like
set, but right now thats asking too much.


I was using erase() to average and group points in the tree.  I would
average the first point and erase the items that were averaged,
eventually the tree was empty.  It worked ok, but it was O(nlogn), and a
bad one.  Instead, I wrote some code that 'tagged' each item with an id,
and checked a set<size_t> registry to ignore the points I had ignored.
MUCH much faster, and while there is an O(nlogn) in the set<> find, its
a much smaller hit.

well, thats all for now.

Paul

changes fix #2

[Paul <ele...@ya...>]

Hi,

Thought I'd better run the changes past you before I checked them in. 
Attached is the diff.  Let me know if you are happy with it, I'd love to 
check it in myself.



Lots of changes... to make your old code work with the new library, the
changes you will need to do include:

- find_within_range() doesn't return a size_t anymore (thats a previous
patch)
- its optimize() not optimise()  (read on for more about why)


The changes:

Looked at std::set and std::list, and the stl documentation for stuff on
associative container concepts, sequence concepts etc.  Not sure exactly
what applies here, but I just added support for what looked ok.

Theres now a full set of constructors, including default and range. You
can also pass an allocator (STL does, I never use the feature... not yet
anyway).  Fill constructors are obviously not appropriate for this one.
Note that this probably is closest to a priority_queue, which is
actually an adapted vector<>.  They don't seem to stick to a single
concept specifically, so I guess we have some room to move.  Range
constructors are great.  Just do Tree tree(begin,end); and its filled
and ready to go... after an optimisation.

Theres also now a full set of inserters.  This allows
inserter(cont,cont.begin()) to work.  Note the 'position' iterator is
always disregarded (at least at this stage).  It might in the future be
helpful for insertion hints (like in set), but that is Future with a
capital F. Not now.

I also removed the requirement for types to have default-construction.
Previously for a type to work with kdtree++, it required a Type() style
constructor.  This is unnecessary 	as demonstrated by set's constructor.
   I also had to slightly change the way it was destroyed.  I just
followed the example in std::set.
This also fixed problems demonstrated by:
KDTree<3,Point> tree;
assert( tree.begin() == tree.end() ); // this would fail !!
tree.optimise();  // segmentation fault!!

I readded the 'iterator' type.  set uses iterator instead of
const_iterator in all of its definitions except for find() etc.  Both
are defined as the same type.  Scott Meyers (i think?) recommended not
using const_iterator too much, as its a pain if you want to use it in
some algorithms (which require iterators for whatever reason)...
whatever, we should try and follow what others do - everything except
find() uses iterator.

I removed 'inline' declarations in front of method calls.  They are not
required... IIRC inline methods are more like hints to the compiler,
'inline' is much more useful for free functions, which will create
multiple implementation instances without the inline (and cause all
sorts of link collisions).   The compiler will figure out if its best to
inline or not, its hard for us to know best.   an example is std::set.
the only inline functions are things like operator==() and in
stl_tree.h: _Rb_tree_rebalance().  These are both free functions and
must be inlined if you want to keep them in a header file.

I added a count_within_range() method for simply counting the number of
items inside a range.  This is more efficient than doing a find if you
just want a count, since the values aren't written to an output iterator.

I added this-> to some of the method calls. The STL does this,
presumably to avoid confusing the calls with free-function calls.  This
is also probably why the STL 'reserves' function/method/variable names
starting with __

I am torn between american-ising the spelling, and not.  As an aussie, i
get a bit pissed off when i have to continuously spell in american, or
mix spellings.  I bet non-english speakers feel the same way.  However,
for the sake of consistency, its best to americanise. americanize.  So i
renamed optimise().  I hate the 'z', so if you insist on the old
spelling, I won't be disappointed, but I bet we would have to switch
back eventually.  Until Australian becomes the world's standard language.

I renamed _M_meta to _M_header because they call it that in set<>.

I noticed rend() returned reverse_iterator(end()).  It should return
begin().

In optimize(), I use a range constructor instead of a copy().  This will
be faster.




Things that could still possibly be done:
- Improve operator=() and copy-constructor... theres a faster way of
copying the tree across.
- I looked at erase(), It would be nice to have a fast rebalancer like
set, but right now thats asking too much.


I was using erase() to average and group points in the tree.  I would
average the first point and erase the items that were averaged,
eventually the tree was empty.  It worked ok, but it was O(nlogn), and a
bad one.  Instead, I wrote some code that 'tagged' each item with an id,
and checked a set<size_t> registry to ignore the points I had ignored.
MUCH much faster, and while there is an O(nlogn) in the set<> find, its
a much smaller hit.

well, thats all for now.

Paul

Fixing problems

[Paul <ele...@ya...>]

Hi,

Why do you need to follow an erase() with an optimise() call?  Is it 
possible to keep the tree correct when erasing?  Is this a bug or by design?

Is optimise() always required, even after an insert() ?

This is a huge problem if you want to remove a bunch of items...

Cheers
Paul