diff options
Diffstat (limited to 'framework/src/ant/apache-ant-1.9.6/src/tests/junit/org/apache/tools/bzip2/BlockSortTest.java')
| -rw-r--r-- | framework/src/ant/apache-ant-1.9.6/src/tests/junit/org/apache/tools/bzip2/BlockSortTest.java | 171 |
1 files changed, 171 insertions, 0 deletions
diff --git a/framework/src/ant/apache-ant-1.9.6/src/tests/junit/org/apache/tools/bzip2/BlockSortTest.java b/framework/src/ant/apache-ant-1.9.6/src/tests/junit/org/apache/tools/bzip2/BlockSortTest.java new file mode 100644 index 00000000..12b871ed --- /dev/null +++ b/framework/src/ant/apache-ant-1.9.6/src/tests/junit/org/apache/tools/bzip2/BlockSortTest.java @@ -0,0 +1,171 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ +package org.apache.tools.bzip2; + +import org.junit.Test; + +import static org.junit.Assert.assertArrayEquals; +import static org.junit.Assert.assertEquals; + +public class BlockSortTest { + + private static final byte[] FIXTURE = { 0, 1, (byte) 252, (byte) 253, (byte) 255, + (byte) 254, 3, 2, (byte) 128 }; + + /* + Burrows-Wheeler transform of fixture the manual way: + + * build the matrix + + 0, 1, 252, 253, 255, 254, 3, 2, 128 + 1, 252, 253, 255, 254, 3, 2, 128, 0 + 252, 253, 255, 254, 3, 2, 128, 0, 1 + 253, 255, 254, 3, 2, 128, 0, 1, 252 + 255, 254, 3, 2, 128, 0, 1, 252, 253 + 254, 3, 2, 128, 0, 1, 252, 253, 255 + 3, 2, 128, 0, 1, 252, 253, 255, 254 + 2, 128, 0, 1, 252, 253, 255, 254, 3 + 128, 0, 1, 252, 253, 255, 254, 3, 2 + + * sort it + + 0, 1, 252, 253, 255, 254, 3, 2, 128 + 1, 252, 253, 255, 254, 3, 2, 128, 0 + 2, 128, 0, 1, 252, 253, 255, 254, 3 + 3, 2, 128, 0, 1, 252, 253, 255, 254 + 128, 0, 1, 252, 253, 255, 254, 3, 2 + 252, 253, 255, 254, 3, 2, 128, 0, 1 + 253, 255, 254, 3, 2, 128, 0, 1, 252 + 254, 3, 2, 128, 0, 1, 252, 253, 255 + 255, 254, 3, 2, 128, 0, 1, 252, 253 + + * grab last column + + 128, 0, 3, 254, 2, 1, 252, 255, 253 + + and the original line has been 0 + */ + + private static final byte[] FIXTURE_BWT = { (byte) 128, 0, 3, (byte) 254, 2, 1, + (byte) 252, (byte) 255, (byte) 253 }; + + private static final int[] FIXTURE_SORTED = { + 0, 1, 7, 6, 8, 2, 3, 5, 4 + }; + + private static final byte[] FIXTURE2 = { + 'C', 'o', 'm', 'm', 'o', 'n', 's', ' ', 'C', 'o', 'm', 'p', 'r', 'e', 's', 's', + }; + + private static final byte[] FIXTURE2_BWT = { + 's', 's', ' ', 'r', 'o', 'm', 'o', 'o', 'C', 'C', 'm', 'm', 'p', 'n', 's', 'e', + }; + + @Test + public void testSortFixture() { + DS ds = setUpFixture(); + ds.s.blockSort(ds.data, FIXTURE.length - 1); + assertFixtureSorted(ds.data); + assertEquals(0, ds.data.origPtr); + } + + @Test + public void testSortFixtureMainSort() { + DS ds = setUpFixture(); + ds.s.mainSort(ds.data, FIXTURE.length - 1); + assertFixtureSorted(ds.data); + } + + @Test + public void testSortFixtureFallbackSort() { + DS ds = setUpFixture(); + ds.s.fallbackSort(ds.data, FIXTURE.length - 1); + assertFixtureSorted(ds.data); + } + + @Test + public void testSortFixture2() { + DS ds = setUpFixture2(); + ds.s.blockSort(ds.data, FIXTURE2.length - 1); + assertFixture2Sorted(ds.data); + assertEquals(1, ds.data.origPtr); + } + + @Test + public void testSortFixture2MainSort() { + DS ds = setUpFixture2(); + ds.s.mainSort(ds.data, FIXTURE2.length - 1); + assertFixture2Sorted(ds.data); + } + + @Test + public void testSortFixture2FallbackSort() { + DS ds = setUpFixture2(); + ds.s.fallbackSort(ds.data, FIXTURE2.length - 1); + assertFixture2Sorted(ds.data); + } + + @Test + public void testFallbackSort() { + CBZip2OutputStream.Data data = new CBZip2OutputStream.Data(1); + BlockSort s = new BlockSort(data); + int[] fmap = new int[FIXTURE.length]; + s.fallbackSort(fmap, FIXTURE, FIXTURE.length); + assertArrayEquals(FIXTURE_SORTED, fmap); + } + + private DS setUpFixture() { + return setUpFixture(FIXTURE); + } + + private void assertFixtureSorted(CBZip2OutputStream.Data data) { + assertFixtureSorted(data, FIXTURE, FIXTURE_BWT); + } + + private DS setUpFixture2() { + return setUpFixture(FIXTURE2); + } + + private void assertFixture2Sorted(CBZip2OutputStream.Data data) { + assertFixtureSorted(data, FIXTURE2, FIXTURE2_BWT); + } + + private DS setUpFixture(byte[] fixture) { + CBZip2OutputStream.Data data = new CBZip2OutputStream.Data(1); + System.arraycopy(fixture, 0, data.block, 1, fixture.length); + return new DS(data, new BlockSort(data)); + } + + private void assertFixtureSorted(CBZip2OutputStream.Data data, + byte[] fixture, byte[] fixtureBwt) { + assertEquals(fixture[fixture.length - 1], data.block[0]); + for (int i = 0; i < fixture.length; i++) { + assertEquals(fixtureBwt[i], data.block[data.fmap[i]]); + } + } + + private static class DS { + private final CBZip2OutputStream.Data data; + private final BlockSort s; + DS(CBZip2OutputStream.Data data, BlockSort s) { + this.data = data; + this.s = s; + } + } +} |