| /* |
| * Copyright (c) 2014-2021 by Wen Yu |
| * |
| * This program and the accompanying materials are made available under the |
| * terms of the Eclipse Public License 2.0 which is available at |
| * http://www.eclipse.org/legal/epl-2.0. |
| * |
| * This Source Code may also be made available under the following Secondary |
| * Licenses when the conditions for such availability set forth in the Eclipse |
| * Public License, v. 2.0 are satisfied: GNU General Public License, version 2 |
| * or any later version. |
| * |
| * SPDX-License-Identifier: EPL-2.0 OR GPL-2.0-or-later |
| * |
| * Change History - most recent changes go on top of previous changes |
| * |
| * ArrayUtils.java |
| * |
| * Who Date Description |
| * ==== ========= ====================================================================== |
| * WY 14Jun2015 Bug fix for toNBits() to use long data type internally |
| * WY 04Jun2015 Rewrote all concatenation related methods |
| * WY 02Jun2015 Bug fix for generic concatenate methods |
| * WY 06Apr2015 Added reverse(byte[]) to reverse byte array elements |
| * WY 06Jan2015 Added reverse() to reverse array elements |
| * WY 10Dec2014 Moved reverseBits() from IMGUtils to here along with BIT_REVERSE_TABLE |
| * WY 08Dec2014 Fixed bug for flipEndian() with more than 32 bit sample data |
| * WY 07Dec2014 Changed method names for byte array to other array types conversion |
| * WY 07Dec2014 Added new methods to work with floating point TIFF images |
| * WY 03Dec2014 Added byteArrayToFloatArray() and byteArrayToDoubleArray() |
| * WY 25Nov2014 Added removeDuplicates() to sort and remove duplicates from int arrays |
| * WY 12Nov2014 Changed the argument sequence for flipEndian() |
| * WY 11Nov2014 Changed flipEndian() to include scan line stride to skip bits |
| * WY 11Nov2014 Added toNBits() to convert byte array to nBits data unit |
| * WY 28Oct2014 Added flipEndian() to work with TIFTweaker mergeTiffImagesEx() |
| */ |
| |
| package pixy.util; |
| |
| import java.util.Arrays; |
| import java.util.Comparator; |
| import java.util.HashSet; |
| import java.util.List; |
| import java.util.Set; |
| import java.lang.reflect.Array; |
| import java.nio.ByteOrder; |
| import java.util.AbstractList; |
| import java.nio.ByteBuffer; |
| import java.nio.DoubleBuffer; |
| import java.nio.FloatBuffer; |
| import java.nio.IntBuffer; |
| import java.nio.LongBuffer; |
| import java.nio.ShortBuffer; |
| |
| /** |
| * Array utility class |
| * |
| * @author Wen Yu, yuwen_66@yahoo.com |
| * @version 1.0 09/18/2012 |
| */ |
| public class ArrayUtils |
| { |
| // Bit mask 0 - 32 bits (inclusive) |
| private static final int[] MASK = { 0x000, |
| 0x1, 0x3, 0x7, 0xf, |
| 0x1f, 0x3f, 0x7f, 0xff, |
| 0x1ff, 0x3ff, 0x7ff, 0xfff, |
| 0x1fff, 0x3fff, 0x7fff, 0xffff, |
| 0x1ffff, 0x3ffff, 0x7ffff, 0xfffff, |
| 0x1fffff, 0x3fffff, 0x7fffff, 0xffffff, |
| 0x1ffffff, 0x3ffffff, 0x7ffffff, 0xfffffff, |
| 0x1fffffff, 0x3fffffff, 0x7fffffff, 0xffffffff // 32 bits |
| }; |
| |
| // Bit reverse table to work with TIFF FillOrder field. |
| private static final byte[] BIT_REVERSE_TABLE = { |
| (byte)0x00, (byte)0x80, (byte)0x40, (byte)0xc0, (byte)0x20, (byte)0xa0, (byte)0x60, (byte)0xe0, |
| (byte)0x10, (byte)0x90, (byte)0x50, (byte)0xd0, (byte)0x30, (byte)0xb0, (byte)0x70, (byte)0xf0, |
| (byte)0x08, (byte)0x88, (byte)0x48, (byte)0xc8, (byte)0x28, (byte)0xa8, (byte)0x68, (byte)0xe8, |
| (byte)0x18, (byte)0x98, (byte)0x58, (byte)0xd8, (byte)0x38, (byte)0xb8, (byte)0x78, (byte)0xf8, |
| (byte)0x04, (byte)0x84, (byte)0x44, (byte)0xc4, (byte)0x24, (byte)0xa4, (byte)0x64, (byte)0xe4, |
| (byte)0x14, (byte)0x94, (byte)0x54, (byte)0xd4, (byte)0x34, (byte)0xb4, (byte)0x74, (byte)0xf4, |
| (byte)0x0c, (byte)0x8c, (byte)0x4c, (byte)0xcc, (byte)0x2c, (byte)0xac, (byte)0x6c, (byte)0xec, |
| (byte)0x1c, (byte)0x9c, (byte)0x5c, (byte)0xdc, (byte)0x3c, (byte)0xbc, (byte)0x7c, (byte)0xfc, |
| (byte)0x02, (byte)0x82, (byte)0x42, (byte)0xc2, (byte)0x22, (byte)0xa2, (byte)0x62, (byte)0xe2, |
| (byte)0x12, (byte)0x92, (byte)0x52, (byte)0xd2, (byte)0x32, (byte)0xb2, (byte)0x72, (byte)0xf2, |
| (byte)0x0a, (byte)0x8a, (byte)0x4a, (byte)0xca, (byte)0x2a, (byte)0xaa, (byte)0x6a, (byte)0xea, |
| (byte)0x1a, (byte)0x9a, (byte)0x5a, (byte)0xda, (byte)0x3a, (byte)0xba, (byte)0x7a, (byte)0xfa, |
| (byte)0x06, (byte)0x86, (byte)0x46, (byte)0xc6, (byte)0x26, (byte)0xa6, (byte)0x66, (byte)0xe6, |
| (byte)0x16, (byte)0x96, (byte)0x56, (byte)0xd6, (byte)0x36, (byte)0xb6, (byte)0x76, (byte)0xf6, |
| (byte)0x0e, (byte)0x8e, (byte)0x4e, (byte)0xce, (byte)0x2e, (byte)0xae, (byte)0x6e, (byte)0xee, |
| (byte)0x1e, (byte)0x9e, (byte)0x5e, (byte)0xde, (byte)0x3e, (byte)0xbe, (byte)0x7e, (byte)0xfe, |
| (byte)0x01, (byte)0x81, (byte)0x41, (byte)0xc1, (byte)0x21, (byte)0xa1, (byte)0x61, (byte)0xe1, |
| (byte)0x11, (byte)0x91, (byte)0x51, (byte)0xd1, (byte)0x31, (byte)0xb1, (byte)0x71, (byte)0xf1, |
| (byte)0x09, (byte)0x89, (byte)0x49, (byte)0xc9, (byte)0x29, (byte)0xa9, (byte)0x69, (byte)0xe9, |
| (byte)0x19, (byte)0x99, (byte)0x59, (byte)0xd9, (byte)0x39, (byte)0xb9, (byte)0x79, (byte)0xf9, |
| (byte)0x05, (byte)0x85, (byte)0x45, (byte)0xc5, (byte)0x25, (byte)0xa5, (byte)0x65, (byte)0xe5, |
| (byte)0x15, (byte)0x95, (byte)0x55, (byte)0xd5, (byte)0x35, (byte)0xb5, (byte)0x75, (byte)0xf5, |
| (byte)0x0d, (byte)0x8d, (byte)0x4d, (byte)0xcd, (byte)0x2d, (byte)0xad, (byte)0x6d, (byte)0xed, |
| (byte)0x1d, (byte)0x9d, (byte)0x5d, (byte)0xdd, (byte)0x3d, (byte)0xbd, (byte)0x7d, (byte)0xfd, |
| (byte)0x03, (byte)0x83, (byte)0x43, (byte)0xc3, (byte)0x23, (byte)0xa3, (byte)0x63, (byte)0xe3, |
| (byte)0x13, (byte)0x93, (byte)0x53, (byte)0xd3, (byte)0x33, (byte)0xb3, (byte)0x73, (byte)0xf3, |
| (byte)0x0b, (byte)0x8b, (byte)0x4b, (byte)0xcb, (byte)0x2b, (byte)0xab, (byte)0x6b, (byte)0xeb, |
| (byte)0x1b, (byte)0x9b, (byte)0x5b, (byte)0xdb, (byte)0x3b, (byte)0xbb, (byte)0x7b, (byte)0xfb, |
| (byte)0x07, (byte)0x87, (byte)0x47, (byte)0xc7, (byte)0x27, (byte)0xa7, (byte)0x67, (byte)0xe7, |
| (byte)0x17, (byte)0x97, (byte)0x57, (byte)0xd7, (byte)0x37, (byte)0xb7, (byte)0x77, (byte)0xf7, |
| (byte)0x0f, (byte)0x8f, (byte)0x4f, (byte)0xcf, (byte)0x2f, (byte)0xaf, (byte)0x6f, (byte)0xef, |
| (byte)0x1f, (byte)0x9f, (byte)0x5f, (byte)0xdf, (byte)0x3f, (byte)0xbf, (byte)0x7f, (byte)0xff |
| }; |
| |
| // From Effective Java 2nd Edition. |
| public static List<Integer> asList(final int[] a) |
| { |
| if (a == null) |
| throw new NullPointerException(); |
| return new AbstractList<Integer>() {// Concrete implementation built atop skeletal implementation |
| public Integer get(int i) { |
| return a[i]; |
| } |
| |
| @Override public Integer set(int i, Integer val) { |
| int oldVal = a[i]; |
| a[i] = val; |
| return oldVal; |
| } |
| public int size() { |
| return a.length; |
| } |
| }; |
| } |
| |
| public static void bubbleSort(int[] array) { |
| int n = array.length; |
| boolean doMore = true; |
| |
| while (doMore) { |
| n--; |
| doMore = false; // assume this is our last pass over the array |
| |
| for (int i=0; i < n; i++) { |
| if (array[i] > array[i+1]) { |
| // exchange elements |
| int temp = array[i]; |
| array[i] = array[i+1]; |
| array[i+1] = temp; |
| doMore = true; // after an exchange, must look again |
| } |
| } |
| } |
| } |
| |
| public static <T extends Comparable<? super T>> void bubbleSort(T[] array) { |
| int n = array.length; |
| boolean doMore = true; |
| |
| while (doMore) { |
| n--; |
| doMore = false; // assume this is our last pass over the array |
| |
| for (int i = 0; i < n; i++) { |
| if (array[i].compareTo(array[i+1]) > 0) { |
| // exchange elements |
| T temp = array[i]; |
| array[i] = array[i+1]; |
| array[i+1] = temp; |
| doMore = true; // after an exchange, must look again |
| } |
| } |
| } |
| } |
| |
| /** |
| * Since Set doesn't allow duplicates add() return false |
| * if we try to add duplicates into Set and this property |
| * can be used to check if array contains duplicates. |
| * |
| * @param input input array |
| * @return true if input array contains duplicates, otherwise false. |
| */ |
| public static <T> boolean checkDuplicate(T[] input) { |
| Set<T> tempSet = new HashSet<T>(); |
| |
| for (T str : input) { |
| if (!tempSet.add(str)) { |
| return true; |
| } |
| } |
| |
| return false; |
| } |
| |
| public static byte[] concat(byte[] first, byte[]... rest) { |
| if(first == null) { |
| throw new IllegalArgumentException("Firt element is null"); |
| } |
| if(rest.length == 0) return first; |
| // Now the real stuff |
| int totalLength = first.length; |
| |
| for (byte[] array : rest) { |
| totalLength += array.length; |
| } |
| |
| byte[] result = new byte[totalLength]; |
| |
| int offset = first.length; |
| |
| System.arraycopy(first, 0, result, 0, offset); |
| |
| for (byte[] array : rest) { |
| System.arraycopy(array, 0, result, offset, array.length); |
| offset += array.length; |
| } |
| |
| return result; |
| } |
| |
| /** |
| * Type safe concatenation of arrays with upper type bound T |
| * <p> |
| * Note: if type parameter is not explicitly supplied, it will be inferred as the |
| * upper bound for the two parameters. |
| * |
| * @param arrays the arrays to be concatenated |
| * @return a concatenation of the input arrays |
| * @throws NullPointerException if any of the input array is null |
| */ |
| public static <T> T[] concat(T[]... arrays) { |
| if(arrays.length == 0) |
| throw new IllegalArgumentException("Varargs length is zero"); |
| |
| if(arrays.length == 1) return arrays[0]; |
| |
| // Now the real stuff |
| int totalLength = 0; |
| // Taking advantage of the compiler type inference |
| Class<?> returnType = arrays.getClass().getComponentType().getComponentType(); |
| |
| for (T[] array : arrays) |
| totalLength += array.length; |
| |
| @SuppressWarnings("unchecked") |
| T[] result = (T[]) Array.newInstance(returnType, totalLength); |
| |
| int offset = 0; |
| for (T[] array : arrays) { |
| System.arraycopy(array, 0, result, offset, array.length); |
| offset += array.length; |
| } |
| |
| return result; |
| } |
| |
| /** |
| * Type safe concatenation of arrays with upper type bound T |
| * |
| * @param type type bound for the concatenated array |
| * @param arrays arrays to be concatenated |
| * @return a concatenation of the arrays. |
| * @throws NullPointerException if any of the arrays to be |
| * concatenated is null. |
| */ |
| public static <T> T[] concat(Class<T> type, T[]... arrays) { |
| if(type == null) |
| throw new IllegalArgumentException("Input type class is null"); |
| |
| if(arrays.length == 0) { // Return a zero length array instead of null |
| @SuppressWarnings("unchecked") |
| T[] result = (T[]) Array.newInstance(type, 0); |
| |
| return result; |
| } |
| |
| // Make sure we have at least two arrays to concatenate |
| if(arrays.length == 1) return arrays[0]; |
| |
| int totalLength = 0; |
| for (T[] array : arrays) |
| totalLength += array.length; |
| |
| @SuppressWarnings("unchecked") |
| T[] result = (T[]) Array.newInstance(type, totalLength); |
| |
| int offset = 0; |
| for (T[] array : arrays) { |
| System.arraycopy(array, 0, result, offset, array.length); |
| offset += array.length; |
| } |
| |
| return result; |
| } |
| |
| public static int findEqualOrLess(int[] a, int key) { |
| return findEqualOrLess(a, 0, a.length, key); |
| } |
| |
| /** |
| * Find the index of the element which is equal or less than the key. |
| * The array must be sorted in ascending order. |
| * |
| * @param a the array to be searched |
| * @param key the value to be searched for |
| * @return index of the search key or index of the element which is closest to but less than the search key or |
| * -1 is the search key is less than the first element of the array. |
| */ |
| |
| public static int findEqualOrLess(int[] a, int fromIndex, int toIndex, int key) { |
| int index = Arrays.binarySearch(a, fromIndex, toIndex, key); |
| |
| // -index - 1 is the insertion point if not found, so -index - 1 -1 is the less position |
| if(index < 0) { |
| index = -index - 1 - 1; |
| } |
| |
| // The index of the element which is either equal or less than the key |
| return index; |
| } |
| |
| public static <T> int findEqualOrLess(T[] a, int fromIndex, int toIndex, T key, Comparator<? super T> c) { |
| int index = Arrays.binarySearch(a, fromIndex, toIndex, key, c); |
| |
| // -index - 1 is the insertion point if not found |
| if(index < 0) { |
| index = -index - 1 - 1; |
| } |
| |
| return index; |
| } |
| |
| public static <T> int findEqualOrLess(T[] a, T key, Comparator<? super T> c) { |
| return findEqualOrLess(a, 0, a.length, key, c); |
| } |
| |
| /** |
| * Flip the endian of the input byte-compacted array |
| * |
| * @param input the input byte array which is byte compacted |
| * @param offset the offset to start the reading input |
| * @param len number of bytes to read |
| * @param bits number of bits for the data before compaction |
| * @param scanLineStride scan line stride to skip bits |
| * @param bigEndian whether or not the input data is in big endian order |
| * |
| * @return a byte array with the endian flipped |
| */ |
| public static byte[] flipEndian(byte[] input, int offset, int len, int bits, int scanLineStride, boolean bigEndian) { |
| long value = 0; |
| int bits_remain = 0; |
| long temp_byte = 0; // Must make this long, otherwise will give wrong result for bits > 32 |
| int empty_bits = 8; |
| |
| byte[] output = new byte[input.length]; |
| |
| int strideCounter = 0; |
| |
| int end = offset + len; |
| int bufIndex = 0; |
| |
| int temp = bits; |
| boolean bigEndianOut = !bigEndian; |
| |
| loop: |
| while(true) { |
| |
| if(!bigEndian) |
| value = (temp_byte >> (8-bits_remain)); |
| else |
| value = (temp_byte & MASK[bits_remain]); |
| |
| while (bits > bits_remain) |
| { |
| if(offset >= end) { |
| break loop; |
| } |
| |
| temp_byte = input[offset++]&0xff; |
| |
| if(bigEndian) |
| value = ((value<<8)|temp_byte); |
| else |
| value |= (temp_byte<<bits_remain); |
| |
| bits_remain += 8; |
| } |
| |
| bits_remain -= bits; |
| |
| if(bigEndian) |
| value = (value>>bits_remain); |
| |
| // Write bits bit length value in opposite endian |
| if(bigEndianOut) { |
| temp = bits-empty_bits; |
| output[bufIndex] |= ((value>>temp)&MASK[empty_bits]); |
| |
| while(temp > 8) |
| { |
| output[++bufIndex] |= ((value>>(temp-8))&MASK[8]); |
| temp -= 8; |
| } |
| |
| if(temp > 0) { |
| output[++bufIndex] |= ((value&MASK[temp])<<(8-temp)); |
| temp -= 8; |
| } |
| } else { // Little endian |
| temp = bits; |
| output[bufIndex] |= ((value&MASK[empty_bits])<<(8-empty_bits)); |
| value >>= empty_bits; |
| temp -= empty_bits; |
| // If the code is longer than the empty_bits |
| while(temp > 8) { |
| output[++bufIndex] |= (value&0xff); |
| value >>= 8; |
| temp -= 8; |
| } |
| |
| if(temp > 0) |
| { |
| output[++bufIndex] |= (value&MASK[temp]); |
| temp -= 8; |
| } |
| } |
| |
| empty_bits = -temp; |
| |
| if(++strideCounter%scanLineStride == 0) { |
| empty_bits = 0; |
| bits_remain = 0; |
| } |
| } |
| |
| return output; |
| } |
| |
| // From http://stackoverflow.com/questions/6162651/half-precision-floating-point-in-java |
| // returns all higher 16 bits as 0 for all results |
| public static int fromFloat(float fval) |
| { |
| int fbits = Float.floatToIntBits(fval); |
| int sign = fbits >>> 16 & 0x8000; // sign only |
| int val = (fbits & 0x7fffffff) + 0x1000; // rounded value |
| |
| if(val >= 0x47800000) // might be or become NaN/Inf |
| { // avoid Inf due to rounding |
| if( (fbits & 0x7fffffff) >= 0x47800000) |
| { // is or must become NaN/Inf |
| if(val < 0x7f800000) // was value but too large |
| return sign | 0x7c00; // make it +/-Inf |
| return sign | 0x7c00 | // remains +/-Inf or NaN |
| (fbits & 0x007fffff) >>> 13; // keep NaN (and Inf) bits |
| } |
| return sign | 0x7bff; // unrounded not quite Inf |
| } |
| if(val >= 0x38800000) // remains normalized value |
| return sign | val - 0x38000000 >>> 13; // exp - 127 + 15 |
| if(val < 0x33000000) // too small for subnormal |
| return sign; // becomes +/-0 |
| val = (fbits & 0x7fffffff) >>> 23; // tmp exp for subnormal calc |
| return sign | ((fbits & 0x7fffff | 0x800000) // add subnormal bit |
| + (0x800000 >>> val - 102) // round depending on cut off |
| >>> 126 - val); // div by 2^(1-(exp-127+15)) and >> 13 | exp=0 |
| } |
| |
| /** |
| * Since nonzero-length array is always mutable, we should return |
| * a clone of the underlying array as BIT_REVERSE_TABLE.clone(). |
| * |
| * @return the byte reverse table. |
| */ |
| public static byte[] getBitReverseTable() { |
| return BIT_REVERSE_TABLE.clone(); |
| } |
| |
| // Insertion sort |
| public static void insertionsort(int[] array) { |
| insertionsort(array, 0, array.length - 1); |
| } |
| |
| public static void insertionsort(int[] array, int start, int end) { |
| int j; |
| |
| for (int i = start + 1; i < end + 1; i++) |
| { |
| |
| int temp = array[i]; |
| for ( j = i; j > start && temp <= array[j-1]; j-- ) |
| array[j] = array[j-1]; |
| // Move temp to the right place |
| array[j] = temp; |
| } |
| } |
| |
| // Insertion sort |
| public static <T extends Comparable<? super T>> void insertionsort(T[] array) { |
| insertionsort(array, 0, array.length - 1); |
| } |
| |
| // Insertion sort |
| public static <T extends Comparable<? super T>> void insertionsort(T[] array, int start, int end) { |
| int j; |
| |
| for (int i = start + 1; i < end + 1; i++) |
| { |
| T temp = array[i]; |
| for ( j = i; j > start && temp.compareTo(array[j-1]) <= 0; j-- ) |
| array[j] = array[j-1]; |
| // Move temp to the right place |
| array[j] = temp; |
| } |
| } |
| |
| // Merge sort |
| public static void mergesort(int[] array) { |
| mergesort(array, new int[array.length], 0, array.length - 1); |
| } |
| |
| public static void mergesort(int[] array, int left, int right) { |
| if(left < 0 || right > array.length - 1) throw new IllegalArgumentException("Array index out of bounds"); |
| mergesort(array, new int[array.length], left, right); |
| } |
| |
| private static void mergesort(int[] array, int[] temp, int left, int right) { |
| // check the base case |
| if (left < right) { |
| // Get the index of the element which is in the middle |
| int middle = left + (right - left) / 2; |
| // Sort the left side of the array |
| mergesort(array, temp, left, middle); |
| // Sort the right side of the array |
| mergesort(array, temp, middle + 1, right); |
| // Merge the left and the right |
| merge(array, temp, left, middle, right); |
| } |
| } |
| |
| public static <T extends Comparable<? super T>> void mergesort(T[] array) { |
| mergesort(array, 0, array.length - 1); |
| } |
| |
| public static <T extends Comparable<? super T>> void mergesort(T[] array, int left, int right) { |
| if(left < 0 || right > array.length - 1) throw new IllegalArgumentException("Array index out of bounds"); |
| @SuppressWarnings("unchecked") |
| T[] temp = (T[]) Array.newInstance(array.getClass().getComponentType(), array.length); |
| mergesort(array, temp, left, right); |
| } |
| |
| // Merge sort |
| private static <T extends Comparable<? super T>> void mergesort(T[] array, T[] temp, int left, int right) { |
| // check the base case |
| if (left < right) { |
| // Get the index of the element which is in the middle |
| int middle = left + (right - left) / 2; |
| // Sort the left side of the array |
| mergesort(array, temp, left, middle); |
| // Sort the right side of the array |
| mergesort(array, temp, middle + 1, right); |
| // Merge the left and the right |
| merge(array, temp, left, middle, right); |
| } |
| } |
| |
| private static <T extends Comparable<? super T>> void merge(T[] array, T[] temp, int left, int middle, int right) { |
| // Copy both parts into the temporary array |
| for (int i = left; i <= right; i++) { |
| temp[i] = array[i]; |
| } |
| int i = left; |
| int j = middle + 1; |
| int k = left; |
| while (i <= middle && j <= right) { |
| if (temp[i].compareTo(temp[j]) <= 0) { |
| array[k] = temp[i]; |
| i++; |
| } else { |
| array[k] = temp[j]; |
| j++; |
| } |
| k++; |
| } |
| while (i <= middle) { |
| array[k] = temp[i]; |
| k++; |
| i++; |
| } |
| } |
| |
| private static void merge(int[] array, int[] temp, int left, int middle, int right) { |
| // Copy both parts into the temporary array |
| for (int i = left; i <= right; i++) { |
| temp[i] = array[i]; |
| } |
| int i = left; |
| int j = middle + 1; |
| int k = left; |
| while (i <= middle && j <= right) { |
| if (temp[i] <= temp[j]) { |
| array[k] = temp[i]; |
| i++; |
| } else { |
| array[k] = temp[j]; |
| j++; |
| } |
| k++; |
| } |
| while (i <= middle) { |
| array[k] = temp[i]; |
| k++; |
| i++; |
| } |
| } |
| |
| /** |
| * Packs all or part of the input byte array which uses "bits" bits to use all 8 bits. |
| * |
| * @param input input byte array |
| * @param start offset of the input array to start packing |
| * @param bits number of bits used by the input array |
| * @param len number of bytes from the input to be packed |
| * @return the packed byte array |
| */ |
| public static byte[] packByteArray(byte[] input, int start, int bits, int len) { |
| // |
| if(bits == 8) return ArrayUtils.subArray(input, start, len); |
| if(bits > 8 || bits <= 0) throw new IllegalArgumentException("Invalid value of bits: " + bits); |
| |
| byte[] packedBytes = new byte[(bits*len + 7)>>3]; |
| short mask[] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff}; |
| |
| int index = 0; |
| int empty_bits = 8; |
| int end = start + len; |
| |
| for(int i = start; i < end; i++) { |
| // If we have enough space for input byte, one step operation |
| if(empty_bits >= bits) { |
| packedBytes[index] |= ((input[i]&mask[bits])<<(empty_bits-bits)); |
| empty_bits -= bits; |
| if(empty_bits == 0) { |
| index++; |
| empty_bits = 8; |
| } |
| } else { // Otherwise two step operation |
| packedBytes[index++] |= ((input[i]>>(bits-empty_bits))&mask[empty_bits]); |
| packedBytes[index] |= ((input[i]&mask[bits-empty_bits])<<(8-bits+empty_bits)); |
| empty_bits += (8-bits); |
| } |
| } |
| |
| return packedBytes; |
| } |
| |
| /** |
| * Packs all or part of the input byte array which uses "bits" bits to use all 8 bits. |
| * <p> |
| * We assume len is a multiplication of stride. The parameter stride controls the packing |
| * unit length and different units <b>DO NOT</b> share same byte. This happens when packing |
| * image data where each scan line <b>MUST</b> start at byte boundary like TIFF. |
| * |
| * @param input input byte array to be packed |
| * @param stride length of packing unit |
| * @param start offset of the input array to start packing |
| * @param bits number of bits used in each byte of the input |
| * @param len number of input bytes to be packed |
| * @return the packed byte array |
| */ |
| public static byte[] packByteArray(byte[] input, int stride, int start, int bits, int len) { |
| // |
| if(bits == 8) return ArrayUtils.subArray(input, start, len); |
| if(bits > 8 || bits <= 0) throw new IllegalArgumentException("Invalid value of bits: " + bits); |
| |
| int bitsPerStride = bits*stride; |
| int numOfStrides = len/stride; |
| byte[] packedBytes = new byte[((bitsPerStride + 7)>>3)*numOfStrides]; |
| short mask[] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff}; |
| |
| int index = 0; |
| int empty_bits = 8; |
| int end = start + len; |
| int strideCounter = 0; |
| |
| for(int i = start; i < end; i++) { |
| // If we have enough space for input byte, one step operation |
| if(empty_bits >= bits) { |
| packedBytes[index] |= ((input[i]&mask[bits])<<(empty_bits-bits)); |
| empty_bits -= bits; |
| } else { // Otherwise, split the pixel between two bytes. |
| //This will never happen for 1, 2, 4, 8 bits color depth image |
| packedBytes[index++] |= ((input[i]>>(bits-empty_bits))&mask[empty_bits]); |
| packedBytes[index] |= ((input[i]&mask[bits-empty_bits])<<(8-bits+empty_bits)); |
| empty_bits += (8-bits); |
| } |
| // Check to see if we need to move to next byte |
| if(++strideCounter%stride == 0 || empty_bits == 0) { |
| index++; |
| empty_bits = 8; |
| } |
| } |
| |
| return packedBytes; |
| } |
| |
| // Quick sort |
| public static void quicksort(int[] array) { |
| quicksort (array, 0, array.length - 1); |
| } |
| |
| public static void quicksort (int[] array, int start, int end) { |
| int inner = start; |
| int outer = end; |
| int mid = (start + end) / 2; |
| |
| do { |
| // work in from the start until we find a swap to the |
| // other partition is needed |
| while ((inner < mid) && (array[inner] <= array[mid])) |
| inner++; |
| |
| // work in from the end until we find a swap to the |
| // other partition is needed |
| |
| while ((outer > mid) && (array[outer] >= array[mid])) |
| outer--; |
| |
| // if inner index <= outer index, swap elements |
| if (inner < mid && outer > mid) { |
| swap(array, inner, outer); |
| inner++; |
| outer--; |
| } else if (inner < mid) { |
| swap(array, inner, mid - 1); |
| swap(array, mid, mid - 1); |
| mid--; |
| } else if (outer >mid) { |
| swap(array, outer, mid + 1); |
| swap(array, mid, mid + 1); |
| mid++; |
| } |
| } while (inner !=outer); |
| |
| // recursion |
| if ((mid - 1) > start) quicksort(array, start, mid - 1); |
| if (end > (mid + 1)) quicksort(array, mid + 1, end); |
| } |
| |
| // Quick sort |
| public static <T extends Comparable<? super T>> void quicksort (T[] array) { |
| quicksort(array, 0, array.length - 1); |
| } |
| |
| // Quick sort |
| public static <T extends Comparable<? super T>> void quicksort (T[] array, int low, int high) { |
| int i = low, j = high; |
| // Get the pivot element from the middle of the list |
| T pivot = array[low + (high-low)/2]; |
| |
| // Divide into two lists |
| while (i <= j) { |
| // If the current value from the left list is smaller then the pivot |
| // element then get the next element from the left list |
| while (array[i].compareTo(pivot) < 0) { |
| i++; |
| } |
| // If the current value from the right list is larger then the pivot |
| // element then get the next element from the right list |
| while (array[j].compareTo(pivot) > 0) { |
| j--; |
| } |
| |
| // If we have found a values in the left list which is larger then |
| // the pivot element and if we have found a value in the right list |
| // which is smaller then the pivot element then we exchange the |
| // values. |
| // As we are done we can increase i and j |
| if (i <= j) { |
| swap(array, i, j); |
| i++; |
| j--; |
| } |
| } |
| // Recursion |
| if (low < j) |
| quicksort(array, low, j); |
| if (i < high) |
| quicksort(array, i, high); |
| } |
| |
| // Based on java2novice.com example |
| /** |
| * Remove duplicate elements from an int array |
| * |
| * @param input input unsorted int array |
| * @return a sorted int array with unique elements |
| */ |
| public static int[] removeDuplicates(int[] input) { |
| //return if the array length is less than 2 |
| if(input.length < 2){ |
| return input; |
| } |
| |
| // Sort the array first |
| Arrays.sort(input); |
| |
| int j = 0; |
| int i = 1; |
| |
| while(i < input.length){ |
| if(input[i] == input[j]){ |
| i++; |
| } else{ |
| input[++j] = input[i++]; |
| } |
| } |
| |
| int[] output = new int[j + 1]; |
| |
| System.arraycopy(input, 0, output, 0, j + 1); |
| |
| return output; |
| } |
| |
| // Reverse the bit order (bit sex) of a byte array |
| public static void reverseBits(byte[] input) { |
| for(int i = input.length - 1; i >= 0; i--) |
| input[i] = BIT_REVERSE_TABLE[input[i]&0xff]; |
| } |
| |
| public static byte[] reverse(byte[] array) { |
| if (array == null) |
| throw new IllegalArgumentException("Input array is null"); |
| int left = 0; |
| int right = array.length - 1; |
| byte tmp; |
| while (left < right) { |
| tmp = array[right]; |
| array[right] = array[left]; |
| array[left] = tmp; |
| left++; |
| right--; |
| } |
| |
| return array; |
| } |
| |
| // Reverse the array |
| public static <T> void reverse(T[] data) { |
| for (int left = 0, right = data.length - 1; left < right; left++, right--) { |
| T temp = data[left]; |
| data[left] = data[right]; |
| data[right] = temp; |
| } |
| } |
| |
| // Shell sort |
| public static void shellsort(int[] array) { |
| shellsort(array, 0, array.length - 1); |
| } |
| |
| public static void shellsort(int[] array, int start, int end) { |
| if(start < 0 || end < 0 || start > end || end > array.length -1) throw new IllegalArgumentException("Array index out of bounds"); |
| int gap = 1; |
| int len = end - start + 1; |
| // Generate Knuth sequence 1, 4, 13, 40, 121, 364,1093, 3280, 9841 ... |
| while(gap < len) gap = 3*gap + 1; |
| while ( gap > 0 ) |
| { |
| int begin = start + gap; |
| for (int i = begin; i <= end; i++) |
| { |
| int temp = array[i]; |
| int j = i; |
| while ( j >= begin && temp <= array[j - gap]) |
| { |
| array[j] = array[j - gap]; |
| j -= gap; |
| } |
| array[j] = temp; |
| } |
| gap /= 3; |
| } |
| } |
| |
| // Shell sort |
| public static <T extends Comparable<? super T>> void shellsort(T[] array) { |
| shellsort(array, 0, array.length - 1); |
| } |
| |
| // Shell sort |
| public static <T extends Comparable<? super T>> void shellsort(T[] array, int start, int end) { |
| if(start < 0 || end < 0 || start > end || end > array.length - 1) throw new IllegalArgumentException("Array index out of bounds"); |
| int gap = 1; |
| int len = end - start + 1; |
| // Generate Knuth sequence 1, 4, 13, 40, 121, 364,1093, 3280, 9841 ... |
| while(gap < len) gap = 3*gap + 1; |
| while ( gap > 0 ) |
| { |
| int begin = start + gap; |
| for (int i = begin; i <= end; i++) |
| { |
| T temp = array[i]; |
| int j = i; |
| while ( j >= begin && temp.compareTo(array[j - gap]) <= 0) |
| { |
| array[j] = array[j - gap]; |
| j -= gap; |
| } |
| array[j] = temp; |
| } |
| gap /= 3; |
| } |
| } |
| |
| public static byte[] subArray(byte[] src, int offset, int len) { |
| if(offset == 0 && len == src.length) return src; |
| if((offset < 0 || offset >= src.length) || (offset + len > src.length)) |
| throw new IllegalArgumentException("Copy range out of array bounds"); |
| byte[] dest = new byte[len]; |
| System.arraycopy(src, offset, dest, 0, len); |
| |
| return dest; |
| } |
| |
| private static final void swap(int[] array, int a, int b) { |
| int temp = array[a]; |
| array[a] = array[b]; |
| array[b] = temp; |
| } |
| |
| private static final <T> void swap(T[] array, int a, int b) { |
| T temp = array[a]; |
| array[a] = array[b]; |
| array[b] = temp; |
| } |
| |
| public static float[] to16BitFloatArray(byte[] data, boolean bigEndian) { |
| short[] shorts = (short[])toNBits(16, data, Integer.MAX_VALUE, bigEndian); |
| float[] floats = new float[shorts.length]; |
| |
| for(int i = 0; i < floats.length; i++) { |
| floats[i] = toFloat(shorts[i]); |
| } |
| |
| return floats; |
| } |
| |
| /* |
| * Tries to convert 24 bit floating point sample to 32 bit float data. |
| * Up to now, there has been no way to do it correctly and there might be no |
| * correct way to do this because 24 bit is not an IEEE floating point type. |
| * 24 bit floating point images appear too dark using this conversion. |
| */ |
| public static float[] to24BitFloatArray(byte[] data, boolean bigEndian) { |
| int[] ints = (int[])toNBits(24, data, Integer.MAX_VALUE, bigEndian); |
| float[] floats = new float[ints.length]; |
| |
| for(int i = 0; i < floats.length; i++) { |
| /** |
| int bits = ints[i]<<8; |
| int sign = ((bits & 0x80000000) == 0) ? 1 : -1; |
| int exponent = ((bits & 0x7f800000) >> 23); |
| int mantissa = (bits & 0x007fffff); |
| |
| mantissa |= 0x00800000; |
| |
| floats[i] = (float)(sign * mantissa * Math.pow(2, exponent-150)); |
| */ |
| floats[i] = Float.intBitsToFloat(ints[i]<<8); |
| } |
| |
| return floats; |
| } |
| |
| // Convert byte array to long array, then to integer array discarding the higher bits |
| public static int[] to32BitsLongArray(byte[] data, boolean bigEndian) { |
| ByteBuffer byteBuffer = ByteBuffer.wrap(data); |
| |
| if (bigEndian) { |
| byteBuffer.order(ByteOrder.BIG_ENDIAN); |
| } else { |
| byteBuffer.order(ByteOrder.LITTLE_ENDIAN); |
| } |
| |
| LongBuffer longBuf = byteBuffer.asLongBuffer(); |
| long[] array = new long[longBuf.remaining()]; |
| longBuf.get(array); |
| |
| int[] iArray = new int[array.length]; |
| |
| int i = 0; |
| |
| for(long l : array) { |
| iArray[i++] = (int)l; |
| } |
| |
| return iArray; |
| } |
| |
| public static byte[] toByteArray(int value) { |
| return new byte[] { |
| (byte)value, |
| (byte)(value >>> 8), |
| (byte)(value >>> 16), |
| (byte)(value >>> 24) |
| }; |
| } |
| |
| public static byte[] toByteArray(int[] data, boolean bigEndian) { |
| |
| ByteBuffer byteBuffer = ByteBuffer.allocate(data.length * 4); |
| |
| if (bigEndian) { |
| byteBuffer.order(ByteOrder.BIG_ENDIAN); |
| } else { |
| byteBuffer.order(ByteOrder.LITTLE_ENDIAN); |
| } |
| |
| IntBuffer intBuffer = byteBuffer.asIntBuffer(); |
| intBuffer.put(data); |
| |
| byte[] array = byteBuffer.array(); |
| |
| return array; |
| } |
| |
| public static byte[] toByteArray(long[] data, boolean bigEndian) { |
| |
| ByteBuffer byteBuffer = ByteBuffer.allocate(data.length * 8); |
| |
| if (bigEndian) { |
| byteBuffer.order(ByteOrder.BIG_ENDIAN); |
| } else { |
| byteBuffer.order(ByteOrder.LITTLE_ENDIAN); |
| } |
| |
| LongBuffer longBuffer = byteBuffer.asLongBuffer(); |
| longBuffer.put(data); |
| |
| byte[] array = byteBuffer.array(); |
| |
| return array; |
| } |
| |
| public static byte[] toByteArray(short value) { |
| return new byte[] { |
| (byte)value, (byte)(value >>> 8)}; |
| } |
| |
| public static byte[] toByteArray(short[] data, boolean bigEndian) { |
| |
| ByteBuffer byteBuffer = ByteBuffer.allocate(data.length * 2); |
| |
| if (bigEndian) { |
| byteBuffer.order(ByteOrder.BIG_ENDIAN); |
| } else { |
| byteBuffer.order(ByteOrder.LITTLE_ENDIAN); |
| } |
| |
| ShortBuffer shortBuffer = byteBuffer.asShortBuffer(); |
| shortBuffer.put(data); |
| |
| byte[] array = byteBuffer.array(); |
| |
| return array; |
| } |
| |
| public static byte[] toByteArrayMM(int value) { |
| return new byte[] { |
| (byte)(value >>> 24), |
| (byte)(value >>> 16), |
| (byte)(value >>> 8), |
| (byte)value}; |
| } |
| |
| public static byte[] toByteArrayMM(short value) { |
| return new byte[] { |
| (byte)(value >>> 8), (byte)value}; |
| } |
| |
| public static double[] toDoubleArray(byte[] data, boolean bigEndian) { |
| return toDoubleArray(data, 0, data.length, bigEndian); |
| } |
| |
| public static double[] toDoubleArray(byte[] data, int offset, int len, boolean bigEndian) { |
| |
| ByteBuffer byteBuffer = ByteBuffer.wrap(data, offset, len); |
| |
| if (bigEndian) { |
| byteBuffer.order(ByteOrder.BIG_ENDIAN); |
| } else { |
| byteBuffer.order(ByteOrder.LITTLE_ENDIAN); |
| } |
| |
| DoubleBuffer doubleBuf = byteBuffer.asDoubleBuffer(); |
| double[] array = new double[doubleBuf.remaining()]; |
| doubleBuf.get(array); |
| |
| return array; |
| } |
| |
| // From http://stackoverflow.com/questions/6162651/half-precision-floating-point-in-java |
| // Converts integer to float ignores the higher 16 bits |
| public static float toFloat(int lbits) { |
| // ignores the higher 16 bits |
| int mant = lbits & 0x03ff; // 10 bits mantissa |
| int exp = lbits & 0x7c00; // 5 bits exponent |
| |
| if(exp == 0x7c00 ) { // NaN/Inf |
| exp = 0x3fc00; // -> NaN/Inf |
| } else if(exp != 0) { // normalized value |
| exp += 0x1c000; // exp - 15 + 127 |
| if( mant == 0 && exp > 0x1c400) // smooth transition |
| return Float.intBitsToFloat( |
| ( lbits & 0x8000) << 16 |
| | exp << 13 | 0x3ff); |
| } else if(mant != 0) { // && exp==0 -> subnormal |
| exp = 0x1c400; // make it normal |
| do { |
| mant <<= 1; // mantissa * 2 |
| exp -= 0x400; // decrease exp by 1 |
| } while((mant & 0x400) == 0); // while not normal |
| mant &= 0x3ff; // discard subnormal bit |
| } // else +/-0 -> +/-0 |
| |
| return Float.intBitsToFloat( // combine all parts |
| ( lbits & 0x8000 ) << 16 // sign << ( 31 - 15 ) |
| | ( exp | mant ) << 13 ); // value << ( 23 - 10 ) |
| } |
| |
| public static float[] toFloatArray(byte[] data, boolean bigEndian) { |
| return toFloatArray(data, 0, data.length, bigEndian); |
| } |
| |
| public static float[] toFloatArray(byte[] data, int offset, int len, boolean bigEndian) { |
| |
| ByteBuffer byteBuffer = ByteBuffer.wrap(data, offset, len); |
| |
| if (bigEndian) { |
| byteBuffer.order(ByteOrder.BIG_ENDIAN); |
| } else { |
| byteBuffer.order(ByteOrder.LITTLE_ENDIAN); |
| } |
| |
| FloatBuffer floatBuf = byteBuffer.asFloatBuffer(); |
| float[] array = new float[floatBuf.remaining()]; |
| floatBuf.get(array); |
| |
| return array; |
| } |
| |
| public static int[] toIntArray(byte[] data, boolean bigEndian) { |
| return toIntArray(data, 0, data.length, bigEndian); |
| } |
| |
| public static int[] toIntArray(byte[] data, int offset, int len, boolean bigEndian) { |
| |
| ByteBuffer byteBuffer = ByteBuffer.wrap(data, offset, len); |
| |
| if (bigEndian) { |
| byteBuffer.order(ByteOrder.BIG_ENDIAN); |
| } else { |
| byteBuffer.order(ByteOrder.LITTLE_ENDIAN); |
| } |
| |
| IntBuffer intBuf = byteBuffer.asIntBuffer(); |
| int[] array = new int[intBuf.remaining()]; |
| intBuf.get(array); |
| |
| return array; |
| } |
| |
| public static long[] toLongArray(byte[] data, boolean bigEndian) { |
| return toLongArray(data, 0, data.length, bigEndian); |
| } |
| |
| public static long[] toLongArray(byte[] data, int offset, int len, boolean bigEndian) { |
| |
| ByteBuffer byteBuffer = ByteBuffer.wrap(data, offset, len); |
| |
| if (bigEndian) { |
| byteBuffer.order(ByteOrder.BIG_ENDIAN); |
| } else { |
| byteBuffer.order(ByteOrder.LITTLE_ENDIAN); |
| } |
| |
| LongBuffer longBuf = byteBuffer.asLongBuffer(); |
| long[] array = new long[longBuf.remaining()]; |
| longBuf.get(array); |
| |
| return array; |
| } |
| |
| /** |
| * Converts an input byte array to nBits data array using the smallest data type which |
| * can hold the nBits data. Each data type contains only one data element. |
| * |
| * @param nBits number of bits for the data element |
| * @param input the input array for the data elements |
| * @param stride scan line stride used to discard remaining bits |
| * @param bigEndian the packing order of the bits. True if bigEndian, otherwise false. |
| * |
| * @return an array of the smallest data type which can hold the nBits data |
| */ |
| public static Object toNBits(int nBits, byte[] input, int stride, boolean bigEndian) { |
| int value = 0; |
| int bits_remain = 0; |
| int temp_byte = 0; |
| |
| byte[] byteOutput = null; |
| short[] shortOutput = null; |
| int[] intOutput = null; |
| Object output = null; |
| |
| int outLen = (int)((input.length*8L + nBits - 1)/nBits); |
| |
| if(nBits <= 8) { |
| byteOutput = new byte[outLen]; |
| output = byteOutput; |
| } else if(nBits <= 16) { |
| shortOutput = new short[outLen]; |
| output = shortOutput; |
| } else if(nBits <= 32){ |
| intOutput = new int[outLen]; |
| output = intOutput; |
| } else { |
| throw new IllegalArgumentException("nBits exceeds limit - maximum 32"); |
| } |
| |
| int offset = 0; |
| int index = 0; |
| |
| int strideCounter = 0; |
| |
| loop: |
| while(true) { |
| |
| if(!bigEndian) |
| value = (temp_byte >> (8-bits_remain)); |
| else |
| value = (temp_byte & MASK[bits_remain]); |
| |
| while (nBits > bits_remain) |
| { |
| if(offset >= input.length) { |
| break loop; |
| } |
| |
| temp_byte = input[offset++]&0xff; |
| |
| if(bigEndian) |
| value = ((value<<8)|temp_byte); |
| else |
| value |= (temp_byte<<bits_remain); |
| |
| bits_remain += 8; |
| } |
| |
| bits_remain -= nBits; |
| |
| if(bigEndian) |
| value = (value>>(bits_remain)); |
| |
| value &= MASK[nBits]; |
| |
| if(++strideCounter%stride == 0) { |
| bits_remain = 0; // Discard the remaining bits |
| } |
| |
| if(nBits <= 8) byteOutput[index++] = (byte)value; |
| else if(nBits <= 16) shortOutput[index++] = (short)value; |
| else intOutput[index++] = value; |
| } |
| |
| return output; |
| } |
| |
| public static double[] toPrimitive(Double[] doubles) { |
| double[] dArray = new double[doubles.length]; |
| int i = 0; |
| |
| for (double d : doubles) { |
| dArray[i++] = d; |
| } |
| |
| return dArray; |
| } |
| |
| public static float[] toPrimitive(Float[] floats) { |
| float[] fArray = new float[floats.length]; |
| int i = 0; |
| |
| for (float f : floats) { |
| fArray[i++] = f; |
| } |
| |
| return fArray; |
| } |
| |
| public static int[] toPrimitive(Integer[] integers) { |
| int[] ints = new int[integers.length]; |
| int i = 0; |
| |
| for (int n : integers) { |
| ints[i++] = n; |
| } |
| |
| return ints; |
| } |
| |
| public static long[] toPrimitive(Long[] longs) { |
| long[] lArray = new long[longs.length]; |
| int i = 0; |
| |
| for (long l : longs) { |
| lArray[i++] = l; |
| } |
| |
| return lArray; |
| } |
| |
| public static short[] toPrimitive(Short[] shorts) { |
| short[] sArray = new short[shorts.length]; |
| int i = 0; |
| |
| for (short s : shorts) { |
| sArray[i++] = s; |
| } |
| |
| return sArray; |
| } |
| |
| public static short[] toShortArray(byte[] data, boolean bigEndian) { |
| return toShortArray(data, 0, data.length, bigEndian); |
| } |
| |
| public static short[] toShortArray(byte[] data, int offset, int len, boolean bigEndian) { |
| |
| ByteBuffer byteBuffer = ByteBuffer.wrap(data, offset, len); |
| |
| if (bigEndian) { |
| byteBuffer.order(ByteOrder.BIG_ENDIAN); |
| } else { |
| byteBuffer.order(ByteOrder.LITTLE_ENDIAN); |
| } |
| |
| ShortBuffer shortBuf = byteBuffer.asShortBuffer(); |
| short[] array = new short[shortBuf.remaining()]; |
| shortBuf.get(array); |
| |
| return array; |
| } |
| |
| private ArrayUtils(){} // Prevents instantiation |
| } |
