encoding?

[hsnetzer]

Is it possible to encode or serialize a tree?

[Bersaelor]

hey @hsnetzer, I haven't added this to the code but it wouldn't take long.

Maybe makes sense when we go Swift4 as we can then use the default Serializable protocol. ( https://github.com/apple/swift-evolution/blob/master/proposals/0166-swift-archival-serialization.md )

[Bersaelor]

@hsnetzer working on it: https://github.com/Bersaelor/KDTree/pull/20

(It's a little tricky as conditional conformance is not implemented in Swift4 yet, so I have to use the same workaround they use in the standard library for Arrays/Optionals)

[Bersaelor]

@hsnetzer I finished working on Codable.

The swift 4 branch of KDTree now has the feature you need, please tell me what you think about it :)

To Install:

        pod 'KDTree', :git => 'https://github.com/Quick/Quick', :branch => 'swift4'

usage:

    //saving
    try tree.save(to: filePath)
    //loading
    let tree = try KDTree(contentsOf: filePath) 

Internally it's using Apples plist file format. It's not terrible fast, but thats mostly due to Swift4 Codable and PropertyListDecoder using NSNumber internally.

[Bersaelor]

Swift4 with Codable feature is merged, closing :)

[HTLife]

Hi @Bersaelor, I tried to use the save function and it saved to file successfully. However, when I tried to load the file, I got

2020-12-05 19:32:31.076320+0800[10367:426841] [general] Too many nested arrays or dictionaries

Error info: dataCorrupted(Swift.DecodingError.Context(codingPath: [], debugDescription: "The given data was not a valid property list.", underlyingError: Optional(Error Domain=NSCocoaErrorDomain Code=3840 "Unexpected character b at line 1" UserInfo={NSDebugDescription=Unexpected character b at line 1, kCFPropertyListOldStyleParsingError=Error Domain=NSCocoaErrorDomain Code=3840 "Conversion of string failed." UserInfo={NSDebugDescription=Conversion of string failed.}})))

What might be wrong to generate the unsupported file?

[Bersaelor]

@HTLife Mhmm, the unit tests are succeeding, and they also encode/decode large datasets, so I can't really say what the issue is.

The error says Unexpected character b at line 1 and The given data was not a valid property list. . Can you try opening the property list file manually to see it's contents?

[HTLife]

@Bersaelor Thanks for quick reply. The plist file content is

hexdump -C kdtreebin
00000000  62 70 6c 69 73 74 30 30  d4 00 01 00 02 00 03 00  |bplist00........|
00000010  04 00 05 00 06 02 ee 22  ba 51 64 51 72 51 6c 51  |.......".QdQrQlQ|
00000020  76 10 00 d4 00 01 00 02  00 03 00 04 00 07 00 08  |v...............|
00000030  02 ee 22 ae 10 01 d4 00  01 00 02 00 03 00 04 00  |..".............|
00000040  05 00 09 02 ee 22 a3 d4  00 01 00 02 00 03 00 04  |....."..........|
00000050  00 07 00 0a 02 ee 22 99  d4 00 01 00 02 00 03 00  |......".........|
00000060  04 00 05 00 0b 02 ee 22  8d d4 00 01 00 02 00 03  |......."........|
00000070  00 04 00 07 00 0c 02 ee  22 82 d4 00 01 00 02 00  |........".......|
00000080  03 00 04 00 05 00 0d 02  ee 22 76 d4 00 01 00 02  |........."v.....|
00000090  00 03 00 04 00 07 00 0e  02 ee 22 6b d4 00 01 00  |.........."k....|
000000a0  02 00 03 00 04 00 05 00  0f 02 ee 22 61 d4 00 01  |..........."a...|
000000b0  00 02 00 03 00 04 00 07  00 10 02 ee 22 56 d4 00  |............"V..|
000000c0  01 00 02 00 03 00 04 00  05 00 11 02 ee 22 4b d4  |............."K.|
000000d0  00 01 00 02 00 03 00 04  00 07 00 12 02 ee 22 40  |.............."@|
000000e0  d4 00 01 00 02 00 03 00  04 00 05 00 13 02 ee 22  |..............."|
000000f0  34 d4 00 01 00 02 00 03  00 04 00 07 00 14 02 ee  |4...............|
00000100  22 29 d4 00 01 00 02 00  03 00 04 00 05 00 15 02  |")..............|
00000110  ee 22 1f d4 00 01 00 02  00 03 00 04 00 07 00 16  |."..............|
00000120  02 ee 22 14 d4 00 01 00  02 00 03 00 04 00 05 00  |..".............|
00000130  17 02 ee 22 0a d4 00 01  00 02 00 03 00 04 00 07  |..."............|
...
...

Seems that it didn't accept the starting string bplist....

This is my sample code https://gist.github.com/HTLife/32bff1dce39c484696bfc4d10193247d

[Bersaelor]

I don't see any major issues on a cursory read of your code, but I would recommend to open the plist file just the normal way, and check it's contents. Every mac with Xcode should be able to open plist files since on MacOS the file is encoded as plist here.

So, in the test we save and load a tree too, maybe you can copy+paste the code from the test, make sure that works on your computer and then slowly make changes to it till you have your example, so we can zero down on what causes this issue.

[HTLife]

I just followed the instructions and found that, the KDTree saved in plist format with deeply nested structure. When the depth is too much, the corrupted file shown above is generated. The reproduce method is simple, I just wrote a loop to increase the array size with dummy data.

for index in 1...1000 {
    testp += [GPSPoint(key: "1", key_country: "2", key_region: "3", lat: 4, lon: 5)]
}
let tree = KDTree(values: points)
print("Time build tree: \(Date().timeIntervalSince(startTreeBuilding)),"
        .appending(" complete time: \(Date().timeIntervalSince(startLoading))s"))

let filePath = NSHomeDirectory() + "/Documents/kdtreebin"
do
{
    try tree.save(to: URL(fileURLWithPath: filePath) )
    print(URL(fileURLWithPath: filePath))
    print("save kdtreebin")
}
catch
{
    print("Error info: \(error)")
}

[Bersaelor]

Mhmm, so the test data are 1000 randomly generated points, adding 1000 identical points leads to a rather extreme case of a tree.

That said, might this be a bug in PListencoder?

Would the same thing happen with JSONEncoder? I'm currently very busy working on a different project, if you have a moment, you could try removing the #if os(Linux) block in here:

#if os(Linux)
    let data = try JSONEncoder().encode(self)
#else
    let data = try PropertyListEncoder().encode(self)
#endif

in your locally downloaded version of KDTree and see if that changes things. I'll try adding some more unit tests to see if I can replicate your issue this weekend.

Also, you are free to create a PR with a failing Unit Test, that encapulates the issue, then we have it formally in the project!