Collection of static methods for operations on arrays
// // (C) Copyright 2009 Irantha Suwandarathna (irantha@gmail.com) // All rights reserved. // /* Copyright (c) 2001-2008, The HSQL Development Group * All rights reserved. * * Redistribution and use _in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: * * Redistributions of source code must retain the above copyright notice, this * list of conditions and the following disclaimer. * * Redistributions _in binary form must reproduce the above copyright notice, * this list of conditions and the following disclaimer _in the documentation * and/or other materials provided with the distribution. * * Neither the name of the HSQL Development Group nor the names of its * contributors may be used to endorse or promote products derived from this * software without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG, * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ using System; namespace EffiProz.Core.Lib { /** * Collection of static methods for operations on arrays * * @author fredt@users * @version 1.7.2 * @since 1.7.2 */ public class ArrayUtil { public const int CLASS_CODE_BYTE = 'B'; public const int CLASS_CODE_CHAR = 'C'; public const int CLASS_CODE_DOUBLE = 'D'; public const int CLASS_CODE_FLOAT = 'F'; public const int CLASS_CODE_INT = 'I'; public const int CLASS_CODE_LONG = 'J'; public const int CLASS_CODE_OBJECT = 'L'; public const int CLASS_CODE_SHORT = 'S'; public const int CLASS_CODE_bool = 'Z'; //private static IntValueHashMap classCodeMap = new IntValueHashMap(); //static ArrayUtil() //{ // classCodeMap.put(typeof(byte), ArrayUtil.CLASS_CODE_BYTE); // classCodeMap.put(typeof(char), ArrayUtil.CLASS_CODE_SHORT); // classCodeMap.put(typeof(short), ArrayUtil.CLASS_CODE_SHORT); // classCodeMap.put(typeof(int), ArrayUtil.CLASS_CODE_INT); // classCodeMap.put(typeof(long), ArrayUtil.CLASS_CODE_LONG); // classCodeMap.put(typeof(float), ArrayUtil.CLASS_CODE_FLOAT); // classCodeMap.put(typeof(double), ArrayUtil.CLASS_CODE_DOUBLE); // classCodeMap.put(typeof(bool), ArrayUtil.CLASS_CODE_bool); // classCodeMap.put(typeof(Object), ArrayUtil.CLASS_CODE_OBJECT); //} ///** // * Returns a distinct int code for each primitive type and for all Object types. // */ //static int getClassCode(Type cla) //{ // if (!cla.IsPrimitive) // { // return ArrayUtil.CLASS_CODE_OBJECT; // } // return classCodeMap.get(cla, -1); //} /** * Returns true if arra and the first bcount elements of arrb share any * element. <p> * * Used for checks for any overlap between two arrays of column indexes. */ public static bool haveCommonElement(int[] arra, int[] arrb, int bcount) { for (int i = 0; i < arra.Length; i++) { int c = arra[i]; for (int j = 0; j < bcount; j++) { if (c == arrb[j]) { return true; } } } return false; } public static bool areIntIndexesInBooleanArray(int[] arra, bool[] arrb) { for (int i = 0; i < arra.Length; i++) { if (arrb[arra[i]]) { continue; } return false; } return true; } /** * Return count of true elements in array */ /** * As above but copies in reverse direction. <p> * * @param row the target array * @param columnMap the list of indexes into row * @param newRow the source array */ public static void projectRowReverse(Object[] row, int[] columnMap, Object[] newRow) { for (int i = 0; i < columnMap.Length; i++) { row[columnMap[i]] = newRow[i]; } } public static void orBooleanArray(bool[] source, bool[] dest) { for (int i = 0; i < dest.Length; i++) { dest[i] |= source[i]; } } /** * Returns a duplicates of an array. */ public static Object duplicateArray(Object source) { int size = ((Array)source).Length; Array newarray = Array.CreateInstance(source.GetType().GetElementType(), size); Array.Copy((Array)source, 0, newarray, 0, size); return newarray; } public static int countTrueElements(bool[] arra) { int count = 0; for (int i = 0; i < arra.Length; i++) { if (arra[i]) { count++; } } return count; } public static int find(short[] array, int value) { for (int i = 0; i < array.Length; i++) { if (array[i] == value) { return i; } } return -1; } public static int find(short[] array, int value, int offset, int count) { for (int i = offset; i < offset + count; i++) { if (array[i] == value) { return i; } } return -1; } /** * Finds the first element of the array that is not equal to the given value. */ public static int findNot(int[] array, int value) { for (int i = 0; i < array.Length; i++) { if (array[i] != value) { return i; } } return -1; } /** * Determines if the array has a null column for any of the positions given * in the rowColMap array. */ public static bool hasNull(Object[] array, int[] columnMap) { int count = columnMap.Length; for (int i = 0; i < count; i++) { if (array[columnMap[i]] == null) { return true; } } return false; } public static bool hasAllNull(Object[] array, int[] columnMap) { int count = columnMap.Length; for (int i = 0; i < count; i++) { if (array[columnMap[i]] != null) { return false; } } return true; } /** * Clears an area of the given array of the given type. */ public static void clearArray(int type, Object data, int from, int to) { switch (type) { case ArrayUtil.CLASS_CODE_BYTE: { byte[] array = (byte[])data; while (--to >= from) { array[to] = 0; } return; } case ArrayUtil.CLASS_CODE_CHAR: { byte[] array = (byte[])data; while (--to >= from) { array[to] = 0; } return; } case ArrayUtil.CLASS_CODE_SHORT: { short[] array = (short[])data; while (--to >= from) { array[to] = 0; } return; } case ArrayUtil.CLASS_CODE_INT: { int[] array = (int[])data; while (--to >= from) { array[to] = 0; } return; } case ArrayUtil.CLASS_CODE_LONG: { long[] array = (long[])data; while (--to >= from) { array[to] = 0; } return; } case ArrayUtil.CLASS_CODE_FLOAT: { float[] array = (float[])data; while (--to >= from) { array[to] = 0; } return; } case ArrayUtil.CLASS_CODE_DOUBLE: { double[] array = (double[])data; while (--to >= from) { array[to] = 0; } return; } case ArrayUtil.CLASS_CODE_bool: { bool[] array = (bool[])data; while (--to >= from) { array[to] = false; } return; } default: { Object[] array = (Object[])data; while (--to >= from) { array[to] = null; } return; } } } /** * Basic sort for small arrays of int. */ public static void sortArray(int[] array) { bool swapped; do { swapped = false; for (int i = 0; i < array.Length - 1; i++) { if (array[i] > array[i + 1]) { int temp = array[i + 1]; array[i + 1] = array[i]; array[i] = temp; swapped = true; } } } while (swapped); } /** * Basic find for small arrays of Object. */ public static int find(Object[] array, Object _object) { for (int i = 0; i < array.Length; i++) { if (array[i] == _object) { // hadles both nulls return i; } if (_object != null && _object.Equals(array[i])) { return i; } } return -1; } /** * Returns the index of the first occurence of arrb in arra. Or -1 if not found. */ public static int find(byte[] arra, int start, int limit, byte[] arrb) { int k = start; limit = limit - arrb.Length + 1; int value = arrb[0]; for (; k < limit; k++) { if (arra[k] == value) { if (arrb.Length == 1) { return k; } if (containsAt(arra, k, arrb)) { return k; } } } return -1; } /** * Basic find for small arrays of int. */ public static int find(int[] array, int value) { for (int i = 0; i < array.Length; i++) { if (array[i] == value) { return i; } } return -1; } /** * Returns true if arra and arrb contain the same set of integers, not * necessarily _in the same order. This implies the arrays are of the same * length. */ public static bool areEqualSets(int[] arra, int[] arrb) { return arra.Length == arrb.Length && ArrayUtil.haveEqualSets(arra, arrb, arra.Length); } /** * For full == true returns true if arra and arrb are identical (have the * same length and contain the same integers _in the same sequence). * * For full == false returns the result * of haveEqualArrays(arra,arrb,count) * * For full == true, the array lengths must be the same as count * */ public static bool areEqual(int[] arra, int[] arrb, int count, bool full) { if (ArrayUtil.haveEqualArrays(arra, arrb, count)) { if (full) { return arra.Length == arrb.Length && count == arra.Length; } return true; } return false; } /** * Returns true if the first count elements of arra and arrb are identical * sets of integers (not necessarily _in the same order). * */ public static bool haveEqualSets(int[] arra, int[] arrb, int count) { if (count > arra.Length || count > arrb.Length) { return false; } if (count == 1) { return arra[0] == arrb[0]; } int[] tempa = (int[])resizeArray(arra, count); int[] tempb = (int[])resizeArray(arrb, count); sortArray(tempa); sortArray(tempb); for (int j = 0; j < count; j++) { if (tempa[j] != tempb[j]) { return false; } } return true; } /** * Returns true if the first count elements of arra and arrb are identical * subarrays of integers * */ public static bool haveEqualArrays(int[] arra, int[] arrb, int count) { if (count > arra.Length || count > arrb.Length) { return false; } for (int j = 0; j < count; j++) { if (arra[j] != arrb[j]) { return false; } } return true; } /** * Returns an int[] containing elements shared between the two arrays * arra and arrb. The arrays contain sets (no value is repeated). * * Used to find the overlap between two arrays of column indexes. * Ordering of the result arrays will be the same as _in array * a. The method assumes that each index is only listed * once _in the two input arrays. * <p> * e.g. * </p> * <code> * <table width="90%" bgcolor="lightblue"> * <tr><td colspane="3">The arrays</td></tr> * <tr><td>int []arra</td><td>=</td><td>{2,11,5,8}</td></tr> * <tr><td>int []arrb</td><td>=</td><td>{20,8,10,11,28,12}</td></tr> * <tr><td colspane="3">will result in:</td></tr> * <tr><td>int []arrc</td><td>=</td><td>{11,8}</td></tr> * </table> * * @param arra int[]; first column indexes * * @param arrb int[]; second column indexes * * @return int[] common indexes or <code>null</code> if there is no overlap. * * @short Return the overlap between two arrays of column indexes. */ public static int[] commonElements(int[] arra, int[] arrb) { int[] c = null; int n = countCommonElements(arra, arrb); if (n > 0) { c = new int[n]; int k = 0; for (int i = 0; i < arra.Length; i++) { for (int j = 0; j < arrb.Length; j++) { if (arra[i] == arrb[j]) { c[k++] = arra[i]; } } } } return c; } /** * Returns the number of elements shared between the two arrays containing * sets.<p> * * Return the number of elements shared by two column index arrays. * This method assumes that each of these arrays contains a set (each * element index is listed only once _in each index array). Otherwise the * returned number will NOT represent the number of unique column indexes * shared by both index array. * * @param arra int[]; first array of column indexes. * * @param arrb int[]; second array of column indexes * * @return int; number of elements shared by <code>a</code> and <code>b</code> */ public static int countCommonElements(int[] arra, int[] arrb) { int k = 0; for (int i = 0; i < arra.Length; i++) { for (int j = 0; j < arrb.Length; j++) { if (arra[i] == arrb[j]) { k++; } } } return k; } /** * Returns the count of elements _in arra from position start that are * sequentially equal to the elements of arrb. */ public static int countSameElements(byte[] arra, int start, byte[] arrb) { int k = 0; int limit = arra.Length - start; if (limit > arrb.Length) { limit = arrb.Length; } for (int i = 0; i < limit; i++) { if (arra[i + start] == arrb[i]) { k++; } else { break; } } return k; } /** * Returns the count of elements in arra from position start that are * among the elements of arrb. Stops at any element not in arrb. */ public static int countStartElementsAt(byte[] arra, int start, byte[] arrb) { int k = 0; for (int i = start; i < arra.Length; i++) { for (int j = 0; j < arrb.Length; j++) { if (arra[i] == arrb[j]) { k++; goto mainloop; } } break; mainloop: continue; } return k; } /** * Returns the count of elements in arra from position start that are not * among the elements of arrb. * */ public static int countNonStartElementsAt(byte[] arra, int start, byte[] arrb) { int k = 0; for (int i = start; i < arra.Length; i++) { for (int j = 0; j < arrb.Length; j++) { if (arra[i] == arrb[j]) { goto outmainloop; } } k++; } outmainloop: return k; } ///** // * Returns the index of the first occurence of arrb _in arra. Or -1 if not found. // */ //public static int find(byte[] arra, int start, int limit, byte[] arrb) //{ // int k = 0; // limit = limit - arrb.Length + 1; // int value = arrb[0]; // for (; k < limit; k++) // { // if (arra[k] == value) // { // if (arrb.Length == 1) // { // return k; // } // if (containsAt(arra, k, arrb)) // { // return k; // } // } // } // return -1; //} ///** // * Returns an index into arra (or -1) where the character is not _in the // * charset byte array. // */ //public static int findNotIn(byte[] arra, int start, int limit, // byte[] charset) //{ // int k = 0; // for (; k < limit; k++) // { // for (int i = 0; i < charset.Length; i++) // { // if (arra[k] == charset[i]) // { // continue; // } // } // return k; // } // return -1; //} ///** // * Returns an index into arra (or -1) where the character is _in the // * charset byte array. // */ //public static int findIn(byte[] arra, int start, int limit, // byte[] charset) //{ // int k = 0; // for (; k < limit; k++) // { // for (int i = 0; i < charset.Length; i++) // { // if (arra[k] == charset[i]) // { // return k; // } // } // } // return -1; //} ///** // * Returns the index of b or c _in arra. Or -1 if not found. // */ //public static int find(byte[] arra, int start, int limit, int b, int c) //{ // int k = 0; // for (; k < limit; k++) // { // if (arra[k] == b || arra[k] == c) // { // return k; // } // } // return -1; //} /** * Set elements of arrb true if their indexes appear _in arrb. */ public static void intIndexesToboolArray(int[] arra, bool[] arrb) { for (int i = 0; i < arra.Length; i++) { if (arra[i] < arrb.Length) { arrb[arra[i]] = true; } } } /** * Return true if for each true element _in arrb, the corresponding * element _in arra is true */ public static bool containsAllTrueElements(bool[] arra, bool[] arrb) { for (int i = 0; i < arra.Length; i++) { if (arrb[i] && !arra[i]) { return false; } } return true; } /** * Returns true if arra from position start contains all elements of arrb * _in sequential order. */ public static bool containsAt(byte[] arra, int start, byte[] arrb) { return countSameElements(arra, start, arrb) == arrb.Length; } ///** // * Returns the count of elements _in arra from position start that are // * among the elements of arrb. Stops at any element not _in arrb. // */ //public static int countStartElementsAt(byte[] arra, int start, // byte[] arrb) //{ // int k = 0; // for (int i = start; i < arra.Length; i++) // { // for (int j = 0; j < arrb.Length; j++) // { // if (arra[i] == arrb[j]) // { // k++; // goto mainloop; // } // } // break; // mainloop: { } // } // return k; //} ///** // * Returns the count of elements _in arra from position start that are not // * among the elements of arrb. // * // */ //public static int countNonStartElementsAt(byte[] arra, int start, // byte[] arrb) //{ // int k = 0; // for (int i = start; i < arra.Length; i++) // { // for (int j = 0; j < arrb.Length; j++) // { // if (arra[i] == arrb[j]) // { // goto mainloop; // } // } // k++; // } //mainloop: { } // return k; //} ///** // * Convenience wrapper for Array.Copy(). // */ //public static void copyArray(Object source, Object dest, int count) //{ // Array.Copy((Array)source, 0, (Array)dest, 0, count); //} /** * Returns a range of elements of source from start to end of the array. */ public static int[] arraySlice(int[] source, int start, int count) { int[] slice = new int[count]; Array.Copy(source, start, slice, 0, count); return slice; } /** * Fills the array with a value. */ public static void fillArray(Object[] array, Object value) { int to = array.Length; while (--to >= 0) { array[to] = value; } } /** * Fills part of the array with a value. */ public static void fillArray(char[] array, int offset, char value) { int to = array.Length; while (--to >= offset) { array[to] = value; } } /** * Fills the int array with a value */ public static void fillArray(int[] array, int value) { int to = array.Length; while (--to >= 0) { array[to] = value; } } ///** // * Returns a duplicates of an array. // */ //public static Object duplicateArray(Object source) //{ // int size = ((Array)source).Length; // Object newarray = // Array.CreateInstance(source.GetType(), size); // Array.Copy((Array)source, 0, (Array)newarray, 0, size); // return newarray; //} /** * Returns the given array if newsize is the same as existing. * Returns a new array of given size, containing as many elements of * the original array as it can hold. */ public static Object resizeArrayIfDifferent(Object source, int newsize) { int oldsize = ((Array)source).Length; if (oldsize == newsize) { return source; } Object newarray = Array.CreateInstance(source.GetType().GetElementType(), newsize); if (oldsize < newsize) { newsize = oldsize; } Array.Copy((Array)source, 0, (Array)newarray, 0, newsize); return newarray; } /** * Returns a new array of given size, containing as many elements of * the original array as it can hold. N.B. Always returns a new array * even if newsize parameter is the same as the old size. */ public static Object resizeArray(Object source, int newsize) { Object newarray = Array.CreateInstance(source.GetType().GetElementType(), newsize); int oldsize = ((Array)source).Length; if (oldsize < newsize) { newsize = oldsize; } Array.Copy((Array)source, 0, (Array)newarray, 0, newsize); return newarray; } /** * Returns an array containing the elements of parameter source, with one * element removed or added. Parameter adjust {-1, +1} indicates the * operation. Parameter colindex indicates the position at which an element * is removed or added. Parameter addition is an Object to add when * adjust is +1. */ public static Object toAdjustedArray(Array source, Object addition, int colindex, int adjust) { int newsize = ((Array)source).Length + adjust; Object newarray = Array.CreateInstance(source.GetType().GetElementType(), newsize); copyAdjustArray(source, newarray, addition, colindex, adjust); return newarray; } /** * Copies elements of source to dest. If adjust is -1 the element at * colindex is not copied. If adjust is +1 that element is filled with * the Object addition. All the rest of the elements _in source are * shifted left or right accordingly when they are copied. If adjust is 0 * the addition is copied over the element at colindex. * * No checks are perfomed on array sizes and an exception is thrown * if they are not consistent with the other arguments. */ public static void copyAdjustArray(Object source, Object dest, Object addition, int colindex, int adjust) { int length = ((Array)source).Length; if (colindex < 0) { Array.Copy((Array)source, 0, (Array)dest, 0, length); return; } Array.Copy((Array)source, 0, (Array)dest, 0, colindex); if (adjust == 0) { int endcount = length - colindex - 1; ((Array)dest).SetValue(addition, colindex); if (endcount > 0) { Array.Copy((Array)source, colindex + 1, (Array)dest, colindex + 1, endcount); } } else if (adjust < 0) { int endcount = length - colindex - 1; if (endcount > 0) { Array.Copy((Array)source, colindex + 1, (Array)dest, colindex, endcount); } } else { int endcount = length - colindex; ((Array)dest).SetValue(addition, colindex); if (endcount > 0) { Array.Copy((Array)source, colindex, (Array)dest, colindex + 1, endcount); } } } /** * Returns a new array with the elements _in collar adjusted to reflect * changes at colindex. <p> * * Each element _in collarr represents an index into another array * otherarr. <p> * * colindex is the index at which an element is added or removed. * Each element _in the result array represents the new, * adjusted index. <p> * * For each element of collarr that represents an index equal to * colindex and adjust is -1, the result will not contain that element * and will be shorter than collar by one element. * * @param colarr the source array * @param colindex index at which to perform adjustement * @param adjust +1, 0 or -1 * @return new, adjusted array */ public static int[] toAdjustedColumnArray(int[] colarr, int colindex, int adjust) { if (colarr == null) { return null; } int[] intarr = new int[colarr.Length]; int j = 0; for (int i = 0; i < colarr.Length; i++) { if (colarr[i] > colindex) { intarr[j] = colarr[i] + adjust; j++; } else if (colarr[i] == colindex) { if (adjust < 0) { // skip an element from colarr } else { intarr[j] = colarr[i] + adjust; j++; } } else { intarr[j] = colarr[i]; j++; } } if (colarr.Length != j) { int[] newarr = new int[j]; Array.Copy(intarr, newarr, j); return newarr; } return intarr; } /** * Copies some elements of row into colobject by using colindex as * the list of indexes into row. <p> * * colindex and colobject are of equal length and are normally * shorter than row. <p> * * @param row the source array * @param colindex the list of indexes into row * @param colobject the destination array */ public static void copyColumnValues(Object[] row, int[] colindex, Object[] colobject) { for (int i = 0; i < colindex.Length; i++) { colobject[i] = row[colindex[i]]; } } public static void copyColumnValues(int[] row, int[] colindex, int[] colobject) { for (int i = 0; i < colindex.Length; i++) { colobject[i] = row[colindex[i]]; } } public static void fillSequence(int[] colindex) { for (int i = 0; i < colindex.Length; i++) { colindex[i] = i; } } /** * Copies some elements of row into newRow by using columnMap as * the list of indexes into row. <p> * * columnMap and newRow are of equal length and are normally * shorter than row. <p> * * @param row the source array * @param columnMap the list of indexes into row * @param newRow the destination array */ public static void projectRow(Object[] row, int[] columnMap, Object[] newRow) { for (int i = 0; i < columnMap.Length; i++) { newRow[i] = row[columnMap[i]]; } } public static void projectRow(int[] row, int[] columnMap, int[] newRow) { for (int i = 0; i < columnMap.Length; i++) { newRow[i] = row[columnMap[i]]; } } /* public static void main(String[] args) { int[] a = new int[] { 23, 11, 37, 7, 1, 5 }; int[] b = new int[] { 1, 3, 7, 11, 13, 17, 19, 3, 1 }; int[] c = toAdjustedColumnArray(a, 7, -1); int[] d = toAdjustedColumnArray(b, 11, 1); int[] e = new int[a.Length]; copyArray(a, e, a.Length); sortArray(e); int[] f = new int[b.Length]; copyArray(b, f, b.Length); sortArray(f); bool x = haveEqualSets(a, e, a.Length); bool y = haveEqualSets(b, f, b.Length); Console.Write("test passed: "); Console.Write(x == true && y == true && c.Length == a.Length - 1 && d.Length == b.Length); } */ } }