I started to write this range indexing class, based on a RBTree implementation that I lifted from the web somewhere. However it's a bit buggy, and large ranges null pointer. Anyone want to work on making these stable? Once done we can start using them with not/exists nodes. Standard joins will take a bit more work, due to some integration issues of the tuple structures. The two classes can be found in this commit, just try removing the @Ignore to see the issues, and feel free to add more range tests. https://github.com/droolsjbpm/drools/commit/c789459c431763581db02653fb7bf... drools-core/src/main/java/org/drools/core/util/RBTree.java drools-core/src/test/java/org/drools/core/util/RBTreeTest.java Mark _______________________________________________ rules-dev mailing list rules-dev(a)lists.jboss.org https://lists.jboss.org/mailman/listinfo/rules-dev

Also, found this is in RBTree.java, where it doesn't belong? import org.junit.Test; -W

On 07/07/2012, Wolfgang Laun <wolfgang.laun(a)gmail.com&gt; wrote: > Removing the line marked with //>>> helps. > > public void recurse() { > > if ( depth == stack.length - 1 ) { > // increase the stack if we have used up all space > //>>> stack = new int[depth * 3 ]; > stack = Arrays.copyOf( stack, stack.length * 3 ); > } > > Cheers > Wolfgang > > > On 07/07/2012, Mark Proctor <mproctor(a)codehaus.org&gt; wrote: >> I started to write this range indexing class, based on a RBTree >> implementation that I lifted from the web somewhere. However it's a bit >> buggy, and large ranges null pointer. Anyone want to work on making >> these stable? Once done we can start using them with not/exists nodes. >> Standard joins will take a bit more work, due to some integration issues >> of the tuple structures. >> >> The two classes can be found in this commit, just try removing the >> @Ignore to see the issues, and feel free to add more range tests. >> https://github.com/droolsjbpm/drools/commit/c789459c431763581db02653fb7bf... >> drools-core/src/main/java/org/drools/core/util/RBTree.java >> drools-core/src/test/java/org/drools/core/util/RBTreeTest.java >> >> Mark >> _______________________________________________ >> rules-dev mailing list >> rules-dev(a)lists.jboss.org >> https://lists.jboss.org/mailman/listinfo/rules-dev >> _______________________________________________ rules-dev mailing list rules-dev(a)lists.jboss.org https://lists.jboss.org/mailman/listinfo/rules-dev

On 08/07/2012 11:55, Mark Proctor wrote: > On 07/07/2012 07:13, Wolfgang Laun wrote: >> Also, found this is in RBTree.java, where it doesn't belong? >> import org.junit.Test; >> -W > It's a rough but of unfinished code, that mostly, but not completely > works. Feel free to run with it how you wish. note the code is not in master and was deleted some time ago, so anyone wishing to use it as a starting point, will need to recover it from the listed commit. Mark > > Mark >> >> >> On 07/07/2012, Wolfgang Laun <wolfgang.laun(a)gmail.com&gt; wrote: >>> Removing the line marked with //>>> helps. >>> >>> public void recurse() { >>> >>> if ( depth == stack.length - 1 ) { >>> // increase the stack if we have used up all space >>> //>>> stack = new int[depth * 3 ]; >>> stack = Arrays.copyOf( stack, stack.length * 3 ); >>> } >>> >>> Cheers >>> Wolfgang >>> >>> >>> On 07/07/2012, Mark Proctor <mproctor(a)codehaus.org&gt; wrote: >>>> I started to write this range indexing class, based on a RBTree >>>> implementation that I lifted from the web somewhere. However it's a >>>> bit >>>> buggy, and large ranges null pointer. Anyone want to work on making >>>> these stable? Once done we can start using them with not/exists nodes. >>>> Standard joins will take a bit more work, due to some integration >>>> issues >>>> of the tuple structures. >>>> >>>> The two classes can be found in this commit, just try removing the >>>> @Ignore to see the issues, and feel free to add more range tests. >>>> https://github.com/droolsjbpm/drools/commit/c789459c431763581db02653fb7bf... >>>> >>>> >>>> drools-core/src/main/java/org/drools/core/util/RBTree.java >>>> drools-core/src/test/java/org/drools/core/util/RBTreeTest.java >>>> >>>> Mark >>>> _______________________________________________ >>>> rules-dev mailing list >>>> rules-dev(a)lists.jboss.org >>>> https://lists.jboss.org/mailman/listinfo/rules-dev >>>> >> _______________________________________________ >> rules-dev mailing list >> rules-dev(a)lists.jboss.org >> https://lists.jboss.org/mailman/listinfo/rules-dev > > _______________________________________________ rules-dev mailing list rules-dev(a)lists.jboss.org https://lists.jboss.org/mailman/listinfo/rules-dev

Wolfgang, Not sure what you mean, I just checked the src, line 150: https://github.com/droolsjbpm/drools/blob/c00d45712f1cf2027ebda9e7df41567... public void recurse() { if ( depth == stack.length - 1 ) { // increase the stack if we have used up all space stack = new int[depth * 3 ]; stack = Arrays.copyOf( stack, stack.length * 3 ); } The comment doesn't exist there to remove. Mark On 07/07/2012 07:05, Wolfgang Laun wrote: > Removing the line marked with //>>> helps. > > public void recurse() { > > if ( depth == stack.length - 1 ) { > // increase the stack if we have used up all space > //>>> stack = new int[depth * 3 ]; > stack = Arrays.copyOf( stack, stack.length * 3 ); > } > > Cheers > Wolfgang On 07/07/2012, Mark Proctor <mproctor(a)codehaus.org&gt; wrote: >> I started to write this range indexing class, based on a RBTree >> implementation that I lifted from the web somewhere. However it's a bit >> buggy, and large ranges null pointer. Anyone want to work on making >> these stable? Once done we can start using them with not/exists nodes. >> Standard joins will take a bit more work, due to some integration >> issues >> of the tuple structures. >> >> The two classes can be found in this commit, just try removing the >> @Ignore to see the issues, and feel free to add more range tests. >> https://github.com/droolsjbpm/drools/commit/c789459c431763581db02653fb7bf... >> >> drools-core/src/main/java/org/drools/core/util/RBTree.java >> drools-core/src/test/java/org/drools/core/util/RBTreeTest.java >> >> Mark >> _______________________________________________ >> rules-dev mailing list >> rules-dev(a)lists.jboss.org >> https://lists.jboss.org/mailman/listinfo/rules-dev >> > _______________________________________________ > rules-dev mailing list > rules-dev(a)lists.jboss.org > https://lists.jboss.org/mailman/listinfo/rules-dev

Wolgang, Nice find, with the change below the tests are now working :) What we need to do now is try and develop some more comprehensive tests, we cannot afford to introduce a new beta memory type, if it has "holes" in it's data iterations. If anyone is good at breaking code, please copy the two classes at the bottom of the email, replace line 150 as per below (thanks wolfgang), and try and generate ranges where the iteratator breaks. For anyone that understands BTree iterations, there are many edge cases on how it traverses that could become broken - mostly depending on where you start and where you finish. Generating tests doesn't guarantee we find them all. Mark On 11/07/2012 00:18, Mark Proctor wrote: > ok I think I see what you mean, it's overwriting the array it's > copying from. have updated it, and running tests now: > if ( depth == stack.length - 1 ) { > // increase the stack if we have used up all space > int[] newStack = new int[depth * 3 ]; > System.arraycopy( stack, 0, newStack, 0, > stack.length-1 ); > stack = newStack; > } > > Mark > On 11/07/2012 00:04, Mark Proctor wrote: >> Wolfgang, >> >> Not sure what you mean, I just checked the src, line 150: >> https://github.com/droolsjbpm/drools/blob/c00d45712f1cf2027ebda9e7df41567... >> >> >> >> public void recurse() { >> if ( depth == stack.length - 1 ) { >> // increase the stack if we have used up all space >> stack = new int[depth * 3 ]; >> stack = Arrays.copyOf( stack, stack.length * 3 ); >> } The comment doesn't exist there to remove. Mark >> >> >> >> On 07/07/2012 07:05, Wolfgang Laun wrote: >>> Removing the line marked with //>>> helps. >>> >>> public void recurse() { >>> >>> if ( depth == stack.length - 1 ) { >>> // increase the stack if we have used up all space >>> //>>> stack = new int[depth * 3 ]; >>> stack = Arrays.copyOf( stack, stack.length * 3 ); >>> } >>> >>> Cheers >>> Wolfgang >> On 07/07/2012, Mark Proctor <mproctor(a)codehaus.org&gt; wrote: >>>> I started to write this range indexing class, based on a RBTree >>>> implementation that I lifted from the web somewhere. However it's a >>>> bit >>>> buggy, and large ranges null pointer. Anyone want to work on making >>>> these stable? Once done we can start using them with not/exists nodes. >>>> Standard joins will take a bit more work, due to some integration >>>> issues >>>> of the tuple structures. >>>> >>>> The two classes can be found in this commit, just try removing the >>>> @Ignore to see the issues, and feel free to add more range tests. >>>> https://github.com/droolsjbpm/drools/commit/c789459c431763581db02653fb7bf... >>>> >>>> >>>> drools-core/src/main/java/org/drools/core/util/RBTree.java >>>> drools-core/src/test/java/org/drools/core/util/RBTreeTest.java >>>> >>>> Mark >>>> _______________________________________________ >>>> rules-dev mailing list >>>> rules-dev(a)lists.jboss.org >>>> https://lists.jboss.org/mailman/listinfo/rules-dev >>>> >>> _______________________________________________ >>> rules-dev mailing list >>> rules-dev(a)lists.jboss.org >>> https://lists.jboss.org/mailman/listinfo/rules-dev >> >> > > _______________________________________________ rules-dev mailing list rules-dev(a)lists.jboss.org https://lists.jboss.org/mailman/listinfo/rules-dev

I think instead of generating ranges, each time, and testing. We should pre-generate a larger number of test sets and use those. Ideally those test sets will have random intervals, instead of the regular interval sets my current approach uses. We should probably introduce negative numbers. Once we have a large number of data sets we can also generate start/end points to test against these. Atleast this way the tests are deterministic each time, and we can simply generate more datasets and start/end points if we need to. Mark On 11/07/2012 06:57, Wolfgang Laun wrote: > I have created another test with repeated deletes, checking against > another collection maintained in parallel. I have set this up, > isolated, added cobertura, and see that coverage is already quite > good. I'll analyze this further, to cover all nooks and crannies. > Don't start any work that duplicates my own. > > Note that my original fix is to simply remove this line; Arrays.copyOf > does it all. understood, I used System.arraycopy still as it works in jdk1.5. > > public void recurse() { > > if ( depth == stack.length - 1 ) { > // increase the stack if we have used up all space > // ====> simpl remove this line: stack = new int[depth * 3 ]; > stack = Arrays.copyOf( stack, stack.length * 3 ); > } > > Cheers > Wolfgang > > > On 11/07/2012, Mark Proctor <mproctor(a)codehaus.org&gt; wrote: >> Wolgang, >> >> Nice find, with the change below the tests are now working :) >> >> What we need to do now is try and develop some more comprehensive tests, >> we cannot afford to introduce a new beta memory type, if it has "holes" >> in it's data iterations. >> >> If anyone is good at breaking code, please copy the two classes at the >> bottom of the email, replace line 150 as per below (thanks wolfgang), >> and try and generate ranges where the iteratator breaks. >> >> For anyone that understands BTree iterations, there are many edge cases >> on how it traverses that could become broken - mostly depending on where >> you start and where you finish. Generating tests doesn't guarantee we >> find them all. >> >> Mark >> >> >> On 11/07/2012 00:18, Mark Proctor wrote: >>> ok I think I see what you mean, it's overwriting the array it's >>> copying from. have updated it, and running tests now: >>> if ( depth == stack.length - 1 ) { >>> // increase the stack if we have used up all space >>> int[] newStack = new int[depth * 3 ]; >>> System.arraycopy( stack, 0, newStack, 0, >>> stack.length-1 ); >>> stack = newStack; >>> } >>> >>> Mark >>> On 11/07/2012 00:04, Mark Proctor wrote: >>>> Wolfgang, >>>> >>>> Not sure what you mean, I just checked the src, line 150: >>>> https://github.com/droolsjbpm/drools/blob/c00d45712f1cf2027ebda9e7df41567... >>>> >>>> >>>> >>>> public void recurse() { >>>> if ( depth == stack.length - 1 ) { >>>> // increase the stack if we have used up all space >>>> stack = new int[depth * 3 ]; >>>> stack = Arrays.copyOf( stack, stack.length * 3 ); >>>> } The comment doesn't exist there to remove. Mark >>>> >>>> >>>> >>>> On 07/07/2012 07:05, Wolfgang Laun wrote: >>>>> Removing the line marked with //>>> helps. >>>>> >>>>> public void recurse() { >>>>> >>>>> if ( depth == stack.length - 1 ) { >>>>> // increase the stack if we have used up all space >>>>> //>>> stack = new int[depth * 3 ]; >>>>> stack = Arrays.copyOf( stack, stack.length * 3 ); >>>>> } >>>>> >>>>> Cheers >>>>> Wolfgang >>>> On 07/07/2012, Mark Proctor <mproctor(a)codehaus.org&gt; wrote: >>>>>> I started to write this range indexing class, based on a RBTree >>>>>> implementation that I lifted from the web somewhere. However it's a >>>>>> bit >>>>>> buggy, and large ranges null pointer. Anyone want to work on making >>>>>> these stable? Once done we can start using them with not/exists >>>>>> nodes. >>>>>> Standard joins will take a bit more work, due to some integration >>>>>> issues >>>>>> of the tuple structures. >>>>>> >>>>>> The two classes can be found in this commit, just try removing the >>>>>> @Ignore to see the issues, and feel free to add more range tests. >>>>>> https://github.com/droolsjbpm/drools/commit/c789459c431763581db02653fb7bf... >>>>>> >>>>>> >>>>>> drools-core/src/main/java/org/drools/core/util/RBTree.java >>>>>> drools-core/src/test/java/org/drools/core/util/RBTreeTest.java >>>>>> >>>>>> Mark >>>>>> _______________________________________________ >>>>>> rules-dev mailing list >>>>>> rules-dev(a)lists.jboss.org >>>>>> https://lists.jboss.org/mailman/listinfo/rules-dev >>>>>> >>>>> _______________________________________________ >>>>> rules-dev mailing list >>>>> rules-dev(a)lists.jboss.org >>>>> https://lists.jboss.org/mailman/listinfo/rules-dev >>>> >>> >> >> _______________________________________________ >> rules-dev mailing list >> rules-dev(a)lists.jboss.org >> https://lists.jboss.org/mailman/listinfo/rules-dev >> > _______________________________________________ > rules-dev mailing list > rules-dev(a)lists.jboss.org > https://lists.jboss.org/mailman/listinfo/rules-dev _______________________________________________ rules-dev mailing list rules-dev(a)lists.jboss.org https://lists.jboss.org/mailman/listinfo/rules-dev

my mistake, length should not be zero based: if ( depth == stack.length - 1 ) { // increase the stack if we have used up all space int[] newStack = new int[depth * 3 ]; System.arraycopy( stack, 0, newStack, 0, stack.length); stack = newStack; }

On 11/07/2012 00:18, Mark Proctor wrote: > ok I think I see what you mean, it's overwriting the array it's > copying from. have updated it, and running tests now: > if ( depth == stack.length - 1 ) { > // increase the stack if we have used up all space > int[] newStack = new int[depth * 3 ]; > System.arraycopy( stack, 0, newStack, 0, > stack.length-1 ); > stack = newStack; > } > > Mark > On 11/07/2012 00:04, Mark Proctor wrote: >> Wolfgang, >> >> Not sure what you mean, I just checked the src, line 150: >> https://github.com/droolsjbpm/drools/blob/c00d45712f1cf2027ebda9e7df41567... >> >> >> >> public void recurse() { >> if ( depth == stack.length - 1 ) { >> // increase the stack if we have used up all space >> stack = new int[depth * 3 ]; >> stack = Arrays.copyOf( stack, stack.length * 3 ); >> } The comment doesn't exist there to remove. Mark >> >> >> >> On 07/07/2012 07:05, Wolfgang Laun wrote: >>> Removing the line marked with //>>> helps. >>> >>> public void recurse() { >>> >>> if ( depth == stack.length - 1 ) { >>> // increase the stack if we have used up all space >>> //>>> stack = new int[depth * 3 ]; >>> stack = Arrays.copyOf( stack, stack.length * 3 ); >>> } >>> >>> Cheers >>> Wolfgang >> On 07/07/2012, Mark Proctor <mproctor(a)codehaus.org&gt; wrote: >>>> I started to write this range indexing class, based on a RBTree >>>> implementation that I lifted from the web somewhere. However it's a >>>> bit >>>> buggy, and large ranges null pointer. Anyone want to work on making >>>> these stable? Once done we can start using them with not/exists nodes. >>>> Standard joins will take a bit more work, due to some integration >>>> issues >>>> of the tuple structures. >>>> >>>> The two classes can be found in this commit, just try removing the >>>> @Ignore to see the issues, and feel free to add more range tests. >>>> https://github.com/droolsjbpm/drools/commit/c789459c431763581db02653fb7bf... >>>> >>>> >>>> drools-core/src/main/java/org/drools/core/util/RBTree.java >>>> drools-core/src/test/java/org/drools/core/util/RBTreeTest.java >>>> >>>> Mark >>>> _______________________________________________ >>>> rules-dev mailing list >>>> rules-dev(a)lists.jboss.org >>>> https://lists.jboss.org/mailman/listinfo/rules-dev >>>> >>> _______________________________________________ >>> rules-dev mailing list >>> rules-dev(a)lists.jboss.org >>> https://lists.jboss.org/mailman/listinfo/rules-dev >> >> > > _______________________________________________ rules-dev mailing list rules-dev(a)lists.jboss.org https://lists.jboss.org/mailman/listinfo/rules-dev