View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   * http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing,
13   * software distributed under the License is distributed on an
14   * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   * KIND, either express or implied.  See the License for the
16   * specific language governing permissions and limitations
17   * under the License.
18   */
19  package org.apache.commons.compress.compressors.bzip2;
20  
21  import static org.junit.jupiter.api.Assertions.assertArrayEquals;
22  import static org.junit.jupiter.api.Assertions.assertEquals;
23  
24  import org.junit.jupiter.api.Test;
25  
26  public class BlockSortTest {
27  
28      private static final class DS {
29          private final BZip2CompressorOutputStream.Data data;
30          private final BlockSort s;
31  
32          DS(final BZip2CompressorOutputStream.Data data, final BlockSort s) {
33              this.data = data;
34              this.s = s;
35          }
36      }
37  
38      /*
39       * Burrows-Wheeler transform of fixture the manual way:
40       *
41       * build the matrix
42       *
43       * 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,
44       * 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,
45       * 253, 255, 254, 3, 2
46       *
47       * sort it
48       *
49       * 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,
50       * 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,
51       * 128, 0, 1, 252, 253
52       *
53       * grab last column
54       *
55       * 128, 0, 3, 254, 2, 1, 252, 255, 253
56       *
57       * and the original line has been 0
58       */
59  
60      private static final byte[] FIXTURE = { 0, 1, (byte) 252, (byte) 253, (byte) 255, (byte) 254, 3, 2, (byte) 128 };
61  
62      private static final byte[] FIXTURE_BWT = { (byte) 128, 0, 3, (byte) 254, 2, 1, (byte) 252, (byte) 255, (byte) 253 };
63  
64      private static final int[] FIXTURE_SORTED = { 0, 1, 7, 6, 8, 2, 3, 5, 4 };
65  
66      private static final byte[] FIXTURE2 = { 'C', 'o', 'm', 'm', 'o', 'n', 's', ' ', 'C', 'o', 'm', 'p', 'r', 'e', 's', 's', };
67  
68      private static final byte[] FIXTURE2_BWT = { 's', 's', ' ', 'r', 'o', 'm', 'o', 'o', 'C', 'C', 'm', 'm', 'p', 'n', 's', 'e', };
69  
70      private void assertFixture2Sorted(final BZip2CompressorOutputStream.Data data) {
71          assertFixtureSorted(data, FIXTURE2, FIXTURE2_BWT);
72      }
73  
74      private void assertFixtureSorted(final BZip2CompressorOutputStream.Data data) {
75          assertFixtureSorted(data, FIXTURE, FIXTURE_BWT);
76      }
77  
78      private void assertFixtureSorted(final BZip2CompressorOutputStream.Data data, final byte[] fixture, final byte[] fixtureBwt) {
79          assertEquals(fixture[fixture.length - 1], data.block[0]);
80          for (int i = 0; i < fixture.length; i++) {
81              assertEquals(fixtureBwt[i], data.block[data.fmap[i]]);
82          }
83      }
84  
85      private DS setUpFixture() {
86          return setUpFixture(FIXTURE);
87      }
88  
89      private DS setUpFixture(final byte[] fixture) {
90          final BZip2CompressorOutputStream.Data data = new BZip2CompressorOutputStream.Data(1);
91          System.arraycopy(fixture, 0, data.block, 1, fixture.length);
92          return new DS(data, new BlockSort(data));
93      }
94  
95      private DS setUpFixture2() {
96          return setUpFixture(FIXTURE2);
97      }
98  
99      @Test
100     public void testFallbackSort() {
101         final BZip2CompressorOutputStream.Data data = new BZip2CompressorOutputStream.Data(1);
102         final BlockSort s = new BlockSort(data);
103         final int[] fmap = new int[FIXTURE.length];
104         s.fallbackSort(fmap, FIXTURE, FIXTURE.length);
105         assertArrayEquals(FIXTURE_SORTED, fmap);
106     }
107 
108     @Test
109     public void testSortFixture() {
110         final DS ds = setUpFixture();
111         ds.s.blockSort(ds.data, FIXTURE.length - 1);
112         assertFixtureSorted(ds.data);
113         assertEquals(0, ds.data.origPtr);
114     }
115 
116     @Test
117     public void testSortFixture2() {
118         final DS ds = setUpFixture2();
119         ds.s.blockSort(ds.data, FIXTURE2.length - 1);
120         assertFixture2Sorted(ds.data);
121         assertEquals(1, ds.data.origPtr);
122     }
123 
124     @Test
125     public void testSortFixture2FallbackSort() {
126         final DS ds = setUpFixture2();
127         ds.s.fallbackSort(ds.data, FIXTURE2.length - 1);
128         assertFixture2Sorted(ds.data);
129     }
130 
131     @Test
132     public void testSortFixture2MainSort() {
133         final DS ds = setUpFixture2();
134         ds.s.mainSort(ds.data, FIXTURE2.length - 1);
135         assertFixture2Sorted(ds.data);
136     }
137 
138     @Test
139     public void testSortFixtureFallbackSort() {
140         final DS ds = setUpFixture();
141         ds.s.fallbackSort(ds.data, FIXTURE.length - 1);
142         assertFixtureSorted(ds.data);
143     }
144 
145     @Test
146     public void testSortFixtureMainSort() {
147         final DS ds = setUpFixture();
148         ds.s.mainSort(ds.data, FIXTURE.length - 1);
149         assertFixtureSorted(ds.data);
150     }
151 }