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 org.junit.Test;
22  
23  import static org.junit.Assert.assertArrayEquals;
24  import static org.junit.Assert.assertEquals;
25  
26  public class BlockSortTest {
27  
28      private static final byte[] FIXTURE = { 0, 1, (byte) 252, (byte) 253, (byte) 255,
29                                              (byte) 254, 3, 2, (byte) 128 };
30  
31      /*
32        Burrows-Wheeler transform of fixture the manual way:
33  
34        * build the matrix
35  
36        0, 1, 252, 253, 255, 254, 3, 2, 128
37        1, 252, 253, 255, 254, 3, 2, 128, 0
38        252, 253, 255, 254, 3, 2, 128, 0, 1
39        253, 255, 254, 3, 2, 128, 0, 1, 252
40        255, 254, 3, 2, 128, 0, 1, 252, 253
41        254, 3, 2, 128, 0, 1, 252, 253, 255
42        3, 2, 128, 0, 1, 252, 253, 255, 254
43        2, 128, 0, 1, 252, 253, 255, 254, 3
44        128, 0, 1, 252, 253, 255, 254, 3, 2
45  
46        * sort it
47  
48        0, 1, 252, 253, 255, 254, 3, 2, 128
49        1, 252, 253, 255, 254, 3, 2, 128, 0
50        2, 128, 0, 1, 252, 253, 255, 254, 3
51        3, 2, 128, 0, 1, 252, 253, 255, 254
52        128, 0, 1, 252, 253, 255, 254, 3, 2
53        252, 253, 255, 254, 3, 2, 128, 0, 1
54        253, 255, 254, 3, 2, 128, 0, 1, 252
55        254, 3, 2, 128, 0, 1, 252, 253, 255
56        255, 254, 3, 2, 128, 0, 1, 252, 253
57  
58        * grab last column
59  
60        128, 0, 3, 254, 2, 1, 252, 255, 253
61  
62          and the original line has been 0
63      */
64  
65      private static final byte[] FIXTURE_BWT = { (byte) 128, 0, 3, (byte) 254, 2, 1, 
66                                                  (byte) 252, (byte) 255, (byte) 253 };
67  
68      private static final int[] FIXTURE_SORTED = {
69          0, 1, 7, 6, 8, 2, 3, 5, 4
70      };
71  
72      private static final byte[] FIXTURE2 = { 
73          'C', 'o', 'm', 'm', 'o', 'n', 's', ' ', 'C', 'o', 'm', 'p', 'r', 'e', 's', 's', 
74      };
75  
76      private static final byte[] FIXTURE2_BWT = {
77          's', 's', ' ', 'r', 'o', 'm', 'o', 'o', 'C', 'C', 'm', 'm', 'p', 'n', 's', 'e', 
78      };
79  
80      @Test
81      public void testSortFixture() {
82          DS ds = setUpFixture();
83          ds.s.blockSort(ds.data, FIXTURE.length - 1);
84          assertFixtureSorted(ds.data);
85          assertEquals(0, ds.data.origPtr);
86      }
87  
88      @Test
89      public void testSortFixtureMainSort() {
90          DS ds = setUpFixture();
91          ds.s.mainSort(ds.data, FIXTURE.length - 1);
92          assertFixtureSorted(ds.data);
93      }
94  
95      @Test
96      public void testSortFixtureFallbackSort() {
97          DS ds = setUpFixture();
98          ds.s.fallbackSort(ds.data, FIXTURE.length - 1);
99          assertFixtureSorted(ds.data);
100     }
101 
102     @Test
103     public void testSortFixture2() {
104         DS ds = setUpFixture2();
105         ds.s.blockSort(ds.data, FIXTURE2.length - 1);
106         assertFixture2Sorted(ds.data);
107         assertEquals(1, ds.data.origPtr);
108     }
109 
110     @Test
111     public void testSortFixture2MainSort() {
112         DS ds = setUpFixture2();
113         ds.s.mainSort(ds.data, FIXTURE2.length - 1);
114         assertFixture2Sorted(ds.data);
115     }
116 
117     @Test
118     public void testSortFixture2FallbackSort() {
119         DS ds = setUpFixture2();
120         ds.s.fallbackSort(ds.data, FIXTURE2.length - 1);
121         assertFixture2Sorted(ds.data);
122     }
123 
124     @Test
125     public void testFallbackSort() {
126         BZip2CompressorOutputStream.Data data = new BZip2CompressorOutputStream.Data(1);
127         BlockSort s = new BlockSort(data);
128         int[] fmap = new int[FIXTURE.length];
129         s.fallbackSort(fmap, FIXTURE, FIXTURE.length);
130         assertArrayEquals(FIXTURE_SORTED, fmap);
131     }
132 
133     private DS setUpFixture() {
134         return setUpFixture(FIXTURE);
135     }
136 
137     private void assertFixtureSorted(BZip2CompressorOutputStream.Data data) {
138         assertFixtureSorted(data, FIXTURE, FIXTURE_BWT);
139     }
140 
141     private DS setUpFixture2() {
142         return setUpFixture(FIXTURE2);
143     }
144 
145     private void assertFixture2Sorted(BZip2CompressorOutputStream.Data data) {
146         assertFixtureSorted(data, FIXTURE2, FIXTURE2_BWT);
147     }
148 
149     private DS setUpFixture(byte[] fixture) {
150         BZip2CompressorOutputStream.Data data = new BZip2CompressorOutputStream.Data(1);
151         System.arraycopy(fixture, 0, data.block, 1, fixture.length);
152         return new DS(data, new BlockSort(data));
153     }
154 
155     private void assertFixtureSorted(BZip2CompressorOutputStream.Data data,
156                                      byte[] fixture, byte[] fixtureBwt) {
157         assertEquals(fixture[fixture.length - 1], data.block[0]);
158         for (int i = 0; i < fixture.length; i++) {
159             assertEquals(fixtureBwt[i], data.block[data.fmap[i]]);
160         }
161     }
162 
163     private static class DS {
164         private final BZip2CompressorOutputStream.Data data;
165         private final BlockSort s;
166         DS(BZip2CompressorOutputStream.Data data, BlockSort s) {
167             this.data = data;
168             this.s = s;
169         }
170     }
171 }