Source code

001/**
002 * Java Web Archive Toolkit - Software to read and validate ARC, WARC
003 * and GZip files. (http://jwat.org/)
004 * Copyright 2011-2012 Netarkivet.dk (http://netarkivet.dk/)
005 *
006 * Licensed under the Apache License, Version 2.0 (the "License");
007 * you may not use this file except in compliance with the License.
008 * You may obtain a copy of the License at
009 *
010 * http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018package org.jwat.common;
019
020import java.util.LinkedList;
021import java.util.List;
022
023/**
024 * Common byte array helper methods.
025 *
026 * @author nicl
027 */
028public class ArrayUtils {
029
030    /** Case sensitive array where [i] == i. */
031    protected static final byte[] CASE_SENSITIVE = new byte[256];
032    /** Case insensitive array where [i] == toLowerCase(i). */
033    protected static final byte[] CASE_INSENSITIVE = new byte[256];
034
035    /** Array where the character equal to the index is 1 only for whitespace characters. **/
036    public static final byte[] SKIP_WHITESPACE = new byte[256];
037    /** Array where the character equal to the index is 1 only for non whitespace characters. **/
038    public static final byte[] SKIP_NONWHITESPACE = new byte[256];
039
040    /** Zero length byte array. */
041    protected static final byte[] zeroArr = new byte[0];
042
043    /**
044     * Initialize static arrays.
045     */
046    static {
047        for (int i=0; i<256; ++i) {
048            CASE_SENSITIVE[i] = (byte)i;
049            CASE_INSENSITIVE[i] = (byte)Character.toLowerCase(i);
050            SKIP_WHITESPACE[i] = 0;
051            SKIP_NONWHITESPACE[i] = 1;
052        }
053        SKIP_WHITESPACE[' '] = 1;
054        SKIP_WHITESPACE['\t'] = 1;
055        SKIP_WHITESPACE['\r'] = 1;
056        SKIP_WHITESPACE['\n'] = 1;
057        SKIP_NONWHITESPACE[' '] = 0;
058        SKIP_NONWHITESPACE['\t'] = 0;
059        SKIP_NONWHITESPACE['\r'] = 0;
060        SKIP_NONWHITESPACE['\n'] = 0;
061    }
062
063    /**
064     * Purely for unit testing.
065     */
066    protected ArrayUtils() {
067    }
068
069    /**
070     * Move index forward according to the values in the byte array and the skip byte array which decides which byte values must be skipped.
071     * @param skip byte array deciding which byte values must be skipped
072     * @param arr byte array to skip in
073     * @param fIdx byte array index
074     * @return updated index depending of how many bytes where skipped
075     */
076    public static int skip(byte[] skip, byte[] arr, int fIdx) {
077        int arrLen = arr.length;
078        while (fIdx < arrLen && skip[arr[fIdx] & 255] == 1) {
079            ++fIdx;
080        }
081        return fIdx;
082    }
083
084    /**
085     * Check if a byte array starts with a specified case sensitive sub byte array.
086     * @param subArr case sensitive sub byte array to compare for
087     * @param arr byte array to look in
088     * @return boolean indicating if there was a match
089     */
090    public static boolean startsWith(byte[] subArr, byte[] arr) {
091        boolean bRes = false;
092        int lIdx = subArr.length - 1;
093        if (lIdx < arr.length) {
094            if (subArr[0] == arr[0]) {
095                while (lIdx > 0 && subArr[lIdx] == arr[lIdx]) {
096                    --lIdx;
097                }
098                bRes = (lIdx == 0);
099            }
100        }
101        return bRes;
102    }
103
104    /**
105     * Check if a byte array starts with a specified case insensitive sub byte array.
106     * @param subArr case insensitive sub byte array to compare for
107     * @param arr byte array to look in
108     * @return boolean indicating if there was a match
109     */
110    public static boolean startsWithIgnoreCase(byte[] subArr, byte[] arr) {
111        boolean bRes = false;
112        int lIdx = subArr.length - 1;
113        if (lIdx < arr.length) {
114            if (CASE_INSENSITIVE[subArr[0]] == CASE_INSENSITIVE[arr[0]]) {
115                while (lIdx > 0 && CASE_INSENSITIVE[subArr[lIdx]] == CASE_INSENSITIVE[arr[lIdx]]) {
116                    --lIdx;
117                }
118                bRes = (lIdx == 0);
119            }
120        }
121        return bRes;
122    }
123
124    /**
125     * Check if a byte array matches a specified case sensitive sub byte array at a certain index.
126     * @param subArr case sensitive sub byte array to compare against
127     * @param arr byte array to look in
128     * @param fIdx index to start looking from in <code>arr</code>
129     * @return boolean indicating if there was a match
130     */
131    public static boolean equalsAt(byte[] subArr, byte[] arr, int fIdx) {
132        boolean bRes = false;
133        int lIdx = subArr.length - 1;
134        int tIdx = fIdx + lIdx;
135        if (tIdx < arr.length) {
136            if (subArr[0] == arr[fIdx]) {
137                while (lIdx > 0 && subArr[lIdx] == arr[tIdx]) {
138                    --lIdx;
139                    --tIdx;
140                }
141                bRes = (lIdx == 0);
142            }
143        }
144        return bRes;
145    }
146
147    /**
148     * Check if a byte array matches a specified case insensitive sub byte array at a certain index.
149     * @param subArr case sensitive sub byte array to compare against
150     * @param arr byte array to look in
151     * @param fIdx index to start looking from in <code>arr</code>
152     * @return boolean indicating if there was a match
153     */
154    public static boolean equalsAtIgnoreCase(byte[] subArr, byte[] arr, int fIdx) {
155        boolean bRes = false;
156        int lIdx = subArr.length - 1;
157        int tIdx = fIdx + lIdx;
158        if (tIdx < arr.length) {
159            if (CASE_INSENSITIVE[subArr[0] & 255] == CASE_INSENSITIVE[arr[fIdx] & 255]) {
160                while (lIdx > 0 && CASE_INSENSITIVE[subArr[lIdx] & 255] == CASE_INSENSITIVE[arr[tIdx] & 255]) {
161                    --lIdx;
162                    --tIdx;
163                }
164                bRes = (lIdx == 0);
165            }
166        }
167        return bRes;
168    }
169
170    /**
171     * Find the next case sensitive occurrence of a byte sub array in a larger byte array beginning from a specific index.
172     * @param subArr case sensitive byte sub array to compare against
173     * @param arr byte array to look in
174     * @param fIdx index to starting looking from
175     * @return next occurrence or -1, if none was found
176     */
177    public static int indexOf(byte[] subArr, byte[] arr, int fIdx) {
178        int csIdx;
179        int caIdx;
180        int idx = -1;
181        int subArrLast = subArr.length - 1;
182        int arrLen = arr.length;
183        int lIdx = fIdx + subArrLast;
184        if (subArrLast > 0) {
185            while (lIdx < arrLen && idx == -1) {
186                if (subArr[0] == arr[fIdx]) {
187                    csIdx = subArrLast;
188                    caIdx = lIdx;
189                    while (csIdx > 0 && subArr[csIdx] == arr[caIdx]) {
190                        --csIdx;
191                        --caIdx;
192                    }
193                    if (csIdx == 0) {
194                        idx = fIdx;
195                    }
196                }
197                ++fIdx;
198                ++lIdx;
199            }
200        }
201        else if (subArrLast == 0) {
202            while (fIdx < arrLen && idx == -1) {
203                if (subArr[0] == arr[fIdx]) {
204                    idx = fIdx;
205                }
206                ++fIdx;
207            }
208        }
209        return idx;
210    }
211
212    /**
213     * Find the next case insensitive occurrence of a byte sub array in a larger byte array beginning from a specific index.
214     * @param subArr case insensitive byte sub array to compare against
215     * @param arr byte array to look in
216     * @param fIdx index to starting looking from
217     * @return next occurrence or -1, if none was found
218     */
219    public static int indexOfIgnoreCase(byte[] subArr, byte[] arr, int fIdx) {
220        int csIdx;
221        int caIdx;
222        int idx = -1;
223        int subArrLast = subArr.length - 1;
224        int arrLen = arr.length;
225        int lIdx = fIdx + subArrLast;
226        if (subArrLast > 0) {
227            while (lIdx < arrLen && idx == -1) {
228                if (CASE_INSENSITIVE[subArr[0]] == CASE_INSENSITIVE[arr[fIdx]]) {
229                    csIdx = subArrLast;
230                    caIdx = lIdx;
231                    while (csIdx > 0 && CASE_INSENSITIVE[subArr[csIdx]] == CASE_INSENSITIVE[arr[caIdx]]) {
232                        --csIdx;
233                        --caIdx;
234                    }
235                    if (csIdx == 0) {
236                        idx = fIdx;
237                    }
238                }
239                ++fIdx;
240                ++lIdx;
241            }
242        }
243        else if (subArrLast == 0) {
244            while (fIdx < arrLen && idx == -1) {
245                if (CASE_INSENSITIVE[subArr[0]] == CASE_INSENSITIVE[arr[fIdx]]) {
246                    idx = fIdx;
247                }
248                ++fIdx;
249            }
250        }
251        return idx;
252    }
253
254    /**
255     * Case sensitive split a byte array into a list of byte arrays.
256     * @param arr byte array to split
257     * @param subArr case sensitive byte sub array to split around
258     * @param fIdx from index to start from when splitting
259     * @param tIdx to index to end splitting
260     * @return a list of byte arrays
261     */
262    public static List<byte[]> split(byte[] arr, byte[] subArr, int fIdx, int tIdx) {
263        List<byte[]> list = new LinkedList<byte[]>();
264        byte[] tmpArr;
265        int csIdx;
266        int caIdx;
267        int subArrLen = subArr.length;
268        int subArrLast = subArrLen - 1;
269        if (arr.length < tIdx) {
270            tIdx = arr.length;
271        }
272        if (fIdx > tIdx) {
273            throw new IllegalArgumentException("Reverse interval!");
274        }
275        int lIdx = fIdx + subArrLast;
276        int pIdx = fIdx;
277        if (subArrLast > 0) {
278            while (lIdx < tIdx) {
279                if (subArr[0] == arr[fIdx]) {
280                    csIdx = subArrLast;
281                    caIdx = lIdx;
282                    while (csIdx > 0 && subArr[csIdx] == arr[caIdx]) {
283                        --csIdx;
284                        --caIdx;
285                    }
286                    if (csIdx == 0) {
287                        tmpArr = new byte[fIdx - pIdx];
288                        System.arraycopy(arr, pIdx, tmpArr, 0, tmpArr.length);
289                        list.add(tmpArr);
290                        fIdx += subArrLen;
291                        lIdx += subArrLen;
292                        pIdx = fIdx;
293                    }
294                    else {
295                        ++fIdx;
296                        ++lIdx;
297                    }
298                }
299                else {
300                    ++fIdx;
301                    ++lIdx;
302                }
303            }
304            if (pIdx < tIdx) {
305                tmpArr = new byte[tIdx - pIdx];
306                System.arraycopy(arr, pIdx, tmpArr, 0, tmpArr.length);
307                list.add(tmpArr);
308            }
309        }
310        else {
311            while (fIdx < tIdx) {
312                if (subArr[0] == arr[fIdx]) {
313                    tmpArr = new byte[fIdx - pIdx];
314                    System.arraycopy(arr, pIdx, tmpArr, 0, tmpArr.length);
315                    list.add(tmpArr);
316                    pIdx = ++fIdx;
317                }
318                else {
319                    ++fIdx;
320                }
321            }
322            if (pIdx < tIdx) {
323                tmpArr = new byte[tIdx - pIdx];
324                System.arraycopy(arr, pIdx, tmpArr, 0, tmpArr.length);
325                list.add(tmpArr);
326            }
327        }
328        if (pIdx == fIdx) {
329            list.add(zeroArr);
330        }
331        return list;
332    }
333
334}