search

GlenKPeterson / Paguro

Generic, Null-safe, Immutable Collections and Functional Transformations for the JVM
Other
312 stars 24 forks source link

New failing tests for join on two RrbTrees #35

Closed jafingerhut closed 4 years ago

GlenKPeterson commented 4 years ago

Instead of using the magic number "32", please use RrbTree.STRICT_NODE_LENGTH. That's why it's package scope instead of private.

Full disclosure: I barely looked at this. I'm supposed to be staying off the computer for a month (this is the start of week 2). I apologize. Normally I would pounce on accepting help like this at least on the nearest weekend.

jafingerhut commented 4 years ago

Will update the PR as you suggest.

Sorry to pick a bad time to submit these things, and tempt you onto the computer :-) . There is no rush on my account to examine any of these issues. I just wanted to make sure the failing test case was recorded for future examination.

GlenKPeterson commented 4 years ago

I have confirmed that you have found a bug and that this pull request shows it.

GlenKPeterson commented 4 years ago

I set NODE_LENGTH_POW_2 = 2, then added r3.debugValidate(); right after the join (working on the mutable test) and got this:

java.lang.IllegalStateException: Non-last strict node is not full!
Strict4(size=28
        Strict2(size=16
                A[0 1 2 3] A[4 5 6 7] A[8 9 10 11] A[12 13 14 15])
        Strict2(size=4
                A[16 17 18 19])
        Strict2(size=8
                A[20 21 22 23] A[24 25 26 27]))

You can see that the middle node is not full. This is a bug in the join code.

GlenKPeterson commented 2 years ago

@jafingerhut I removed the Strict nodes from the RRB-Tree and your tests seem to pass now. Any interest in trying to break this again? My changes are on the 2021-12-11_fixRrb branch. No idea about speed, but it's not fast if it's not correct.