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     * @return boolean indicating if there was a match
129     */
130    public static boolean equalsAt(byte[] subArr, byte[] arr, int fIdx) {
131        boolean bRes = false;
132        int lIdx = subArr.length - 1;
133        int tIdx = fIdx + lIdx;
134        if (tIdx < arr.length) {
135            if (subArr[0] == arr[fIdx]) {
136                while (lIdx > 0 && subArr[lIdx] == arr[tIdx]) {
137                    --lIdx;
138                    --tIdx;
139                }
140                bRes = (lIdx == 0);
141            }
142        }
143        return bRes;
144    }
145
146    /**
147     * Check if a byte array matches a specified case insensitive sub byte array at a certain index.
148     * @param subArr case sensitive sub byte array to compare against
149     * @param arr byte array to look in
150     * @return boolean indicating if there was a match
151     */
152    public static boolean equalsAtIgnoreCase(byte[] subArr, byte[] arr, int fIdx) {
153        boolean bRes = false;
154        int lIdx = subArr.length - 1;
155        int tIdx = fIdx + lIdx;
156        if (tIdx < arr.length) {
157            if (CASE_INSENSITIVE[subArr[0] & 255] == CASE_INSENSITIVE[arr[fIdx] & 255]) {
158                while (lIdx > 0 && CASE_INSENSITIVE[subArr[lIdx] & 255] == CASE_INSENSITIVE[arr[tIdx] & 255]) {
159                    --lIdx;
160                    --tIdx;
161                }
162                bRes = (lIdx == 0);
163            }
164        }
165        return bRes;
166    }
167
168    /**
169     * Find the next case sensitive occurrence of a byte sub array in a larger byte array beginning from a specific index.
170     * @param subArr case sensitive byte sub array to compare against
171     * @param arr byte array to look in
172     * @param fIdx index to starting looking from
173     * @return next occurrence or -1, if none was found
174     */
175    public static int indexOf(byte[] subArr, byte[] arr, int fIdx) {
176        int csIdx;
177        int caIdx;
178        int idx = -1;
179        int subArrLast = subArr.length - 1;
180        int arrLen = arr.length;
181        int lIdx = fIdx + subArrLast;
182        if (subArrLast > 0) {
183            while (lIdx < arrLen && idx == -1) {
184                if (subArr[0] == arr[fIdx]) {
185                    csIdx = subArrLast;
186                    caIdx = lIdx;
187                    while (csIdx > 0 && subArr[csIdx] == arr[caIdx]) {
188                        --csIdx;
189                        --caIdx;
190                    }
191                    if (csIdx == 0) {
192                        idx = fIdx;
193                    }
194                }
195                ++fIdx;
196                ++lIdx;
197            }
198        }
199        else if (subArrLast == 0) {
200            while (fIdx < arrLen && idx == -1) {
201                if (subArr[0] == arr[fIdx]) {
202                    idx = fIdx;
203                }
204                ++fIdx;
205            }
206        }
207        return idx;
208    }
209
210    /**
211     * Find the next case insensitive occurrence of a byte sub array in a larger byte array beginning from a specific index.
212     * @param subArr case insensitive byte sub array to compare against
213     * @param arr byte array to look in
214     * @param fIdx index to starting looking from
215     * @return next occurrence or -1, if none was found
216     */
217    public static int indexOfIgnoreCase(byte[] subArr, byte[] arr, int fIdx) {
218        int csIdx;
219        int caIdx;
220        int idx = -1;
221        int subArrLast = subArr.length - 1;
222        int arrLen = arr.length;
223        int lIdx = fIdx + subArrLast;
224        if (subArrLast > 0) {
225            while (lIdx < arrLen && idx == -1) {
226                if (CASE_INSENSITIVE[subArr[0]] == CASE_INSENSITIVE[arr[fIdx]]) {
227                    csIdx = subArrLast;
228                    caIdx = lIdx;
229                    while (csIdx > 0 && CASE_INSENSITIVE[subArr[csIdx]] == CASE_INSENSITIVE[arr[caIdx]]) {
230                        --csIdx;
231                        --caIdx;
232                    }
233                    if (csIdx == 0) {
234                        idx = fIdx;
235                    }
236                }
237                ++fIdx;
238                ++lIdx;
239            }
240        }
241        else if (subArrLast == 0) {
242            while (fIdx < arrLen && idx == -1) {
243                if (CASE_INSENSITIVE[subArr[0]] == CASE_INSENSITIVE[arr[fIdx]]) {
244                    idx = fIdx;
245                }
246                ++fIdx;
247            }
248        }
249        return idx;
250    }
251
252    /**
253     * Case sensitive split a byte array into a list of byte arrays.
254     * @param arr byte array to split
255     * @param subArr case sensitive byte sub array to split around
256     * @param fIdx from index to start from when splitting
257     * @param tIdx to index to end splitting
258     * @return a list of byte arrays
259     */
260    public static List<byte[]> split(byte[] arr, byte[] subArr, int fIdx, int tIdx) {
261        List<byte[]> list = new LinkedList<byte[]>();
262        byte[] tmpArr;
263        int csIdx;
264        int caIdx;
265        int subArrLen = subArr.length;
266        int subArrLast = subArrLen - 1;
267        if (arr.length < tIdx) {
268            tIdx = arr.length;
269        }
270        if (fIdx > tIdx) {
271            throw new IllegalArgumentException("Reverse interval!");
272        }
273        int lIdx = fIdx + subArrLast;
274        int pIdx = fIdx;
275        if (subArrLast > 0) {
276            while (lIdx < tIdx) {
277                if (subArr[0] == arr[fIdx]) {
278                    csIdx = subArrLast;
279                    caIdx = lIdx;
280                    while (csIdx > 0 && subArr[csIdx] == arr[caIdx]) {
281                        --csIdx;
282                        --caIdx;
283                    }
284                    if (csIdx == 0) {
285                        tmpArr = new byte[fIdx - pIdx];
286                        System.arraycopy(arr, pIdx, tmpArr, 0, tmpArr.length);
287                        list.add(tmpArr);
288                        fIdx += subArrLen;
289                        lIdx += subArrLen;
290                        pIdx = fIdx;
291                    }
292                    else {
293                        ++fIdx;
294                        ++lIdx;
295                    }
296                }
297                else {
298                    ++fIdx;
299                    ++lIdx;
300                }
301            }
302            if (pIdx < tIdx) {
303                tmpArr = new byte[tIdx - pIdx];
304                System.arraycopy(arr, pIdx, tmpArr, 0, tmpArr.length);
305                list.add(tmpArr);
306            }
307        }
308        else {
309            while (fIdx < tIdx) {
310                if (subArr[0] == arr[fIdx]) {
311                    tmpArr = new byte[fIdx - pIdx];
312                    System.arraycopy(arr, pIdx, tmpArr, 0, tmpArr.length);
313                    list.add(tmpArr);
314                    pIdx = ++fIdx;
315                }
316                else {
317                    ++fIdx;
318                }
319            }
320            if (pIdx < tIdx) {
321                tmpArr = new byte[tIdx - pIdx];
322                System.arraycopy(arr, pIdx, tmpArr, 0, tmpArr.length);
323                list.add(tmpArr);
324            }
325        }
326        if (pIdx == fIdx) {
327            list.add(zeroArr);
328        }
329        return list;
330    }
331
332}