Lists may fail if the change event indicies are out of order

[hbrands]

Lists that evaluate the values such as SortedList and FilteredList may break if the change event has
indicies that arrive out of order.

There should be a test for this added to the unit tests and a fix should be made if the problem is
legitimate.

[GLAZEDLISTS-28] created by jessewilson

[hbrands]

I have created a JUnit test that confirms the presense of this bug. That test has been added to CVS.

The solution as I see it is to add a method in the ListChangeSequence that is called from
commitAtomicChanges(). Such a method would examine the list change events and re-order them into
order of increasing index.

The reordering could potentially also merge adjacent list change blocks but this is not totally necessary.

by jessewilson

[hbrands]

The ListChangeSequence now bubble-sorts change blocks when the change is commited.

BubbleSort was used because it only swaps adjacent entries. When two change blocks are swapped,
their indicies must be modified relative to one another. Therefore bubble sort is the simplest sort to
implement.

by jessewilson

[hbrands]

This bug appears to remain broken:

[junit] Testcase: testIndexOutOfOrder(com.odellengineeringltd.glazedlists.test.IndexOrderTest):
FAILED
[junit] expected:<[[I@c05d3b, [I@28f6ee, [I@6bade9, [I@66afb3, [I@9945ce, [I@b5dac4, [I@2d96f2,
[I@110003, [I@17e4ca, [I@adb1d4, [I@75d6ab, [I@60a26f, [I@484a05, [I@f39b3a, [I@542a75,
[I@af993e, [I@75e4fc, [I@c62c8, [I@2940b3, [I@56b6b9, [I@f66cff, [I@6de49c, [I@bbf1ca, [I@ff0dde,
[I@e78fc6, [I@901437, [I@1f6226, [I@64ea66, [I@58f9d3, [I@79a2e7, [I@b60280, [I@5e55ab,
[I@4a55f2, [I@5093f1, [I@20bf2c, [I@e6f7d2, [I@9836ed, [I@3e0ebb, [I@39443f, [I@afae45, [I@da4b71,
[I@8f1d7e, [I@d9660d, [I@bb0d0d, [I@55e55f, [I@45c859, [I@64883c, [I@2c1e6b, [I@811c88,
[I@785d65, [I@3bc257, [I@53f67e, [I@5bdc50, [I@dd3812, [I@8c436b, [I@9e5c73, [I@c791b9,
[I@3020ad, [I@b15692, [I@aa9f99, [I@d42d08, [I@d86fd3, [I@958bb8, [I@7f4ec, [I@60e128,
[I@5e1077, [I@8b3364, [I@db05b2, [I@530cf2, [I@76fba0, [I@81ed9e, [I@175422, [I@949f69,
[I@6dadf9, [I@b8d6f7, [I@290fbc, [I@c80b01, [I@4aa0ce, [I@833eca, [I@8f5824, [I@e3cd51, [I@bc8e1e,
[I@1671b2, [I@82764b, [I@2452e8, [I@bf3d87, [I@60991f, [I@e4f7c2, [I@45f0e3, [I@c9d92c, [I@d0fafc,
[I@dc6b5, [I@70bea5, [I@f47396, [I@d0af9b, [I@b8f8eb, [I@de17f4, [I@f6ba0f, [I@313906, [I@96cf11,
[I@f47bf5, [I@f6438d, [I@cd0888]> but was:<[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43,
44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69,
70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95,
96, 97, 98, 99, 100, 101]>
[junit] junit.framework.AssertionFailedError: expected:<[[I@c05d3b, [I@28f6ee, [I@6bade9,
[I@66afb3, [I@9945ce, [I@b5dac4, [I@2d96f2, [I@110003, [I@17e4ca, [I@adb1d4, [I@75d6ab,
[I@60a26f, [I@484a05, [I@f39b3a, [I@542a75, [I@af993e, [I@75e4fc, [I@c62c8, [I@2940b3, [I@56b6b9,
[I@f66cff, [I@6de49c, [I@bbf1ca, [I@ff0dde, [I@e78fc6, [I@901437, [I@1f6226, [I@64ea66, [I@58f9d3,
[I@79a2e7, [I@b60280, [I@5e55ab, [I@4a55f2, [I@5093f1, [I@20bf2c, [I@e6f7d2, [I@9836ed,
[I@3e0ebb, [I@39443f, [I@afae45, [I@da4b71, [I@8f1d7e, [I@d9660d, [I@bb0d0d, [I@55e55f,
[I@45c859, [I@64883c, [I@2c1e6b, [I@811c88, [I@785d65, [I@3bc257, [I@53f67e, [I@5bdc50,
[I@dd3812, [I@8c436b, [I@9e5c73, [I@c791b9, [I@3020ad, [I@b15692, [I@aa9f99, [I@d42d08,
[I@d86fd3, [I@958bb8, [I@7f4ec, [I@60e128, [I@5e1077, [I@8b3364, [I@db05b2, [I@530cf2, [I@76fba0,
[I@81ed9e, [I@175422, [I@949f69, [I@6dadf9, [I@b8d6f7, [I@290fbc, [I@c80b01, [I@4aa0ce, [I@833eca,
[I@8f5824, [I@e3cd51, [I@bc8e1e, [I@1671b2, [I@82764b, [I@2452e8, [I@bf3d87, [I@60991f,
[I@e4f7c2, [I@45f0e3, [I@c9d92c, [I@d0fafc, [I@dc6b5, [I@70bea5, [I@f47396, [I@d0af9b, [I@b8f8eb,
[I@de17f4, [I@f6ba0f, [I@313906, [I@96cf11, [I@f47bf5, [I@f6438d, [I@cd0888]> but was:<[0, 1, 2, 3,
4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57,
58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83,
84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101]>
[junit] at
com.odellengineeringltd.glazedlists.test.IndexOrderTest.testIndexOutOfOrder(IndexOrderTest.java:85)
[junit] at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
[junit] at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
[junit] at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:
25)

by jessewilson

[hbrands]

The current ordering of events appears to be inverted and thus events appear in
decreasing order.

by kevinmaltby

[hbrands]

Fixed! Again! This bug has haunted me all day.

The solution sorts and combines properly, but not necessarily too efficiently. If this proves to be a
problem, I'll send the optimization police onto it!

Here's an example of the (poor) runtime. Changes are measured in loop executions.
[junit] Changed! blocks before: 142, after: 142, changes: 141
[junit] Changed! blocks before: 204, after: 1, changes: 405
[junit] Changed! blocks before: 203, after: 88, changes: 9890
[junit] Changed! blocks before: 306, after: 253, changes: 647
[junit] Changed! blocks before: 541, after: 40, changes: 5257
[junit] Changed! blocks before: 514, after: 73, changes: 27433
[junit] Changed! blocks before: 212, after: 158, changes: 439
[junit] Changed! blocks before: 626, after: 9, changes: 46633
[junit] Changed! blocks before: 548, after: 67, changes: 22004
[junit] Changed! blocks before: 141, after: 141, changes: 140
[junit] Changed! blocks before: 411, after: 91, changes: 20767
[junit] Changed! blocks before: 119, after: 119, changes: 118
[junit] Changed! blocks before: 490, after: 2, changes: 32108
[junit] Changed! blocks before: 460, after: 81, changes: 24387
[junit] Changed! blocks before: 121, after: 121, changes: 120
[junit] Changed! blocks before: 551, after: 81, changes: 24285
[junit] Changed! blocks before: 219, after: 176, changes: 447
[junit] Changed! blocks before: 623, after: 68, changes: 53634
[junit] Changed! blocks before: 572, after: 23, changes: 23838
[junit] Changed! blocks before: 34, after: 34, changes: 33
[junit] Changed! blocks before: 41, after: 29, changes: 919
[junit] Changed! blocks before: 55, after: 55, changes: 54
[junit] Changed! blocks before: 77, after: 50, changes: 2964
[junit] Changed! blocks before: 65, after: 1, changes: 127
[junit] Changed! blocks before: 46, after: 46, changes: 45

by jessewilson

[hbrands]

This bug has been fixed for two weeks with no problems. I am marking it closed.

by jessewilson