fix original list order

TennyZhuang commented 8 years ago

When I use kdtree.create

import random
import kdtree

a = []
for i in range(1000):
  a.append([random.randint() for _ in range(100)])
b = list(a)
kdtree.create(a)
a == b # False

I think this method shouldn't change the order in original list.

stefankoegl commented 8 years ago

Good catch! I've added an inline comment to the change.

TennyZhuang commented 8 years ago

I do this type check because if data == None, then list(data) will cause an error.

TypeError: 'NoneType' object is not iterable

and if I only

if data:
    data = list(data)

then the test will failed with

FAIL: test_add (__main__.AddTest)
Tests random additions to a tree, multiple times
----------------------------------------------------------------------
Traceback (most recent call last):
  File "test.py", line 92, in test_add
    self.do_random_add()
  File "test.py", line 105, in do_random_add
    self.assertTrue(point in [node.data for node in tree.inorder()])
AssertionError: False is not true

======================================================================
FAIL: test_search_nn_dist (__main__.NearestNeighbor)
tests search_nn_dist() according to bug #8
----------------------------------------------------------------------
Traceback (most recent call last):
  File "test.py", line 258, in test_search_nn_dist
    self.assertTrue( (6,6) in nn)
AssertionError: False is not true

======================================================================
FAIL: test_remove (__main__.RemoveTest)
Tests random removal from a tree, multiple times
----------------------------------------------------------------------
Traceback (most recent call last):
  File "test.py", line 53, in test_remove
    self.do_random_remove()
  File "test.py", line 78, in do_random_remove
    self.assertEqual(nodes_in_tree, remaining_points)
AssertionError: 20 != 19

======================================================================
FAIL: test_remove_duplicates (__main__.RemoveTest)
creates a tree with only duplicate points, and removes them all
----------------------------------------------------------------------
Traceback (most recent call last):
  File "test.py", line 46, in test_remove_duplicates
    self.assertEqual(nodes_in_tree, remaining_points)
AssertionError: 100 != 99

I don't know the reason why failed.

stefankoegl commented 8 years ago

OK, I see - I did not consider that :)

stefankoegl commented 8 years ago

I have moved the preserving of the order into kdtree.create(), see cd4cad2d7f90f5ea939d6f005498db09f00f2884

stefankoegl commented 8 years ago

I've just released version 0.14 with this change included. Thanks for your contribution :)

TennyZhuang commented 8 years ago

A more problem is that this copy is unnecessary while create recursively. (because Python list slice have copied it). Is there an elegant way to avoid this cost? Sent using CloudMagic Email [https://cloudmagic.com/k/d/mailapp?ct=pi&cv=7.6.23&pv=9.2.1&source=email_footer_2] On Sun, Jun 26, 2016 at 01:50, Stefan Kögl notifications@github.com wrote: I've just released version 0.14 with this change included. Thanks for your contribution :)

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub [https://github.com/stefankoegl/kdtree/pull/28#issuecomment-228561859] , or mute the thread [https://github.com/notifications/unsubscribe/AIvK3qWR6hkz6g2nKO-deMUY8DgB0f2nks5qPWpQgaJpZM4IumAo] .

stefankoegl / kdtree

fix original list order #28