12d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert// © 2016 and later: Unicode, Inc. and others. 22d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert// License & terms of use: http://www.unicode.org/copyright.html#License 37935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert/* 47935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert ****************************************************************************** 57935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Copyright (C) 1996-2011, International Business Machines Corporation and * 67935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * others. All Rights Reserved. * 77935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert ****************************************************************************** 87935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 97935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 107935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert/** 117935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Store bits (Unicode character properties) in bit set vectors. 122d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 137935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * This is a port of the C++ class UPropsVectors from ICU4C 142d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 157935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @author Shaopeng Jia 167935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @internal 177935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 187935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 197935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubertpackage com.ibm.icu.impl; 207935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 217935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubertimport java.util.Arrays; 227935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubertimport java.util.Comparator; 237935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 247935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert/** 257935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Unicode Properties Vectors associated with code point ranges. 262d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 277935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Rows of primitive integers in a contiguous array store the range limits and 287935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * the properties vectors. 292d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 307935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * In each row, row[0] contains the start code point and row[1] contains the 317935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * limit code point, which is the start of the next range. 322d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 337935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Initially, there is only one range [0..0x110000] with values 0. 342d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 357935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * It would be possible to store only one range boundary per row, but 367935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * self-contained rows allow to later sort them by contents. 377935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 387935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubertpublic class PropsVectors { 397935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private int v[]; 407935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private int columns; // number of columns, plus two for start 417935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // and limit values 427935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private int maxRows; 437935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private int rows; 447935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private int prevRow; // search optimization: remember last row seen 457935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private boolean isCompacted; 467935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 477935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // internal function to compare elements in v and target. Return true iff 482d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert // elements in v starting from index1 to index1 + length - 1 497935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // are exactly the same as elements in target 507935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // starting from index2 to index2 + length - 1 512d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert private boolean areElementsSame(int index1, int[] target, int index2, 527935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int length) { 537935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert for (int i = 0; i < length; ++i) { 547935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (v[index1 + i] != target[index2 + i]) { 557935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return false; 567935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 577935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 587935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return true; 597935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 602d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 617935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // internal function which given rangeStart, returns 627935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // index where v[index]<=rangeStart<v[index+1]. 637935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // The returned index is a multiple of columns, and therefore 647935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // points to the start of a row. 657935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private int findRow(int rangeStart) { 667935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int index = 0; 677935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 687935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // check the vicinity of the last-seen row (start 697935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // searching with an unrolled loop) 707935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 717935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert index = prevRow * columns; 727935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (rangeStart >= v[index]) { 737935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (rangeStart < v[index + 1]) { 747935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // same row as last seen 757935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return index; 767935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } else { 777935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert index += columns; 787935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (rangeStart < v[index + 1]) { 797935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert ++prevRow; 807935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return index; 817935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } else { 827935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert index += columns; 837935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (rangeStart < v[index + 1]) { 847935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert prevRow += 2; 857935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return index; 867935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } else if ((rangeStart - v[index + 1]) < 10) { 877935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // we are close, continue looping 887935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert prevRow += 2; 897935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert do { 907935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert ++prevRow; 917935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert index += columns; 927935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } while (rangeStart >= v[index + 1]); 937935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return index; 947935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 957935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 967935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 977935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } else if (rangeStart < v[1]) { 987935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // the very first row 997935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert prevRow = 0; 1007935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return 0; 1017935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1027935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1037935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // do a binary search for the start of the range 1047935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int start = 0; 1057935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int mid = 0; 1067935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int limit = rows; 1077935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert while (start < limit - 1) { 1087935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert mid = (start + limit) / 2; 1097935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert index = columns * mid; 1107935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (rangeStart < v[index]) { 1117935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert limit = mid; 1127935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } else if (rangeStart < v[index + 1]) { 1137935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert prevRow = mid; 1147935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return index; 1157935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } else { 1167935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert start = mid; 1177935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1187935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1197935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1207935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // must be found because all ranges together always cover 1217935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // all of Unicode 1227935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert prevRow = start; 1237935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert index = start * columns; 1247935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return index; 1257935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1267935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1277935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* 1287935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Special pseudo code points for storing the initialValue and the 1297935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * errorValue which are used to initialize a Trie or similar. 1307935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 1317935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public final static int FIRST_SPECIAL_CP = 0x110000; 1327935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public final static int INITIAL_VALUE_CP = 0x110000; 1337935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public final static int ERROR_VALUE_CP = 0x110001; 1347935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public final static int MAX_CP = 0x110001; 1357935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1367935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public final static int INITIAL_ROWS = 1 << 12; 1377935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public final static int MEDIUM_ROWS = 1 << 16; 1387935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public final static int MAX_ROWS = MAX_CP + 1; 1397935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1407935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* 1417935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Constructor. 1427935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @param numOfColumns Number of value integers (32-bit int) per row. 1437935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 1447935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public PropsVectors(int numOfColumns) { 1457935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (numOfColumns < 1) { 1467935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert throw new IllegalArgumentException("numOfColumns need to be no " 1477935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert + "less than 1; but it is " + numOfColumns); 1487935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1497935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert columns = numOfColumns + 2; // count range start and limit columns 1507935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert v = new int[INITIAL_ROWS * columns]; 1517935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert maxRows = INITIAL_ROWS; 1527935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert rows = 2 + (MAX_CP - FIRST_SPECIAL_CP); 1537935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert prevRow = 0; 1547935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert isCompacted = false; 1557935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert v[0] = 0; 1567935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert v[1] = 0x110000; 1577935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int index = columns; 1587935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert for (int cp = FIRST_SPECIAL_CP; cp <= MAX_CP; ++cp) { 1597935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert v[index] = cp; 1607935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert v[index + 1] = cp + 1; 1617935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert index += columns; 1627935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1637935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1647935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1657935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* 1667935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * In rows for code points [start..end], select the column, reset the mask 1677935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * bits and set the value bits (ANDed with the mask). 1682d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 1697935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @throws IllegalArgumentException 1702d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 1717935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @throws IllegalStateException 1722d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 1737935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @throws IndexOutOfBoundsException 1747935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 1757935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public void setValue(int start, int end, int column, int value, int mask) { 1767935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (start < 0 || start > end || end > MAX_CP || column < 0 1777935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert || column >= (columns - 2)) { 1787935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert throw new IllegalArgumentException(); 1797935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1807935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (isCompacted) { 1817935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert throw new IllegalStateException("Shouldn't be called after" 1827935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert + "compact()!"); 1837935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1847935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1857935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int firstRow, lastRow; 1867935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int limit = end + 1; 1877935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert boolean splitFirstRow, splitLastRow; 1887935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // skip range start and limit columns 1897935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert column += 2; 1907935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert value &= mask; 1917935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1927935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // find the rows whose ranges overlap with the input range 1937935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // find the first and last row, always successful 1947935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert firstRow = findRow(start); 1957935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert lastRow = findRow(end); 1967935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1977935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* 1987935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Rows need to be split if they partially overlap with the input range 1997935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * (only possible for the first and last rows) and if their value 2007935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * differs from the input value. 2017935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 2027935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert splitFirstRow = (start != v[firstRow] && value != (v[firstRow + column] & mask)); 2037935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert splitLastRow = (limit != v[lastRow + 1] && value != (v[lastRow + column] & mask)); 2047935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 2057935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // split first/last rows if necessary 2067935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (splitFirstRow || splitLastRow) { 2077935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int rowsToExpand = 0; 2087935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (splitFirstRow) { 2097935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert ++rowsToExpand; 2107935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2117935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (splitLastRow) { 2127935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert ++rowsToExpand; 2137935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2147935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int newMaxRows = 0; 2157935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if ((rows + rowsToExpand) > maxRows) { 2167935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (maxRows < MEDIUM_ROWS) { 2177935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert newMaxRows = MEDIUM_ROWS; 2187935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } else if (maxRows < MAX_ROWS) { 2197935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert newMaxRows = MAX_ROWS; 2207935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } else { 2217935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert throw new IndexOutOfBoundsException( 2227935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert "MAX_ROWS exceeded! Increase it to a higher value" + 2237935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert "in the implementation"); 2247935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2257935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int[] temp = new int[newMaxRows * columns]; 2267935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert System.arraycopy(v, 0, temp, 0, rows * columns); 2277935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert v = temp; 2287935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert maxRows = newMaxRows; 2297935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2307935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 2317935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // count the number of row cells to move after the last row, 2327935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // and move them 2337935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int count = (rows * columns) - (lastRow + columns); 2347935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (count > 0) { 2357935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert System.arraycopy(v, lastRow + columns, v, lastRow 2367935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert + (1 + rowsToExpand) * columns, count); 2377935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2387935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert rows += rowsToExpand; 2397935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 2407935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // split the first row, and move the firstRow pointer 2417935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // to the second part 2427935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (splitFirstRow) { 2437935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // copy all affected rows up one and move the lastRow pointer 2447935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert count = lastRow - firstRow + columns; 2457935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert System.arraycopy(v, firstRow, v, firstRow + columns, count); 2467935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert lastRow += columns; 2477935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 2487935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // split the range and move the firstRow pointer 2497935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert v[firstRow + 1] = v[firstRow + columns] = start; 2507935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert firstRow += columns; 2517935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2527935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 2537935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // split the last row 2547935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (splitLastRow) { 2557935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // copy the last row data 2567935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert System.arraycopy(v, lastRow, v, lastRow + columns, columns); 2577935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 2587935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // split the range and move the firstRow pointer 2597935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert v[lastRow + 1] = v[lastRow + columns] = limit; 2607935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2617935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2627935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 2637935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // set the "row last seen" to the last row for the range 2647935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert prevRow = lastRow / columns; 2657935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 2667935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // set the input value in all remaining rows 2677935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert firstRow += column; 2687935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert lastRow += column; 2697935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert mask = ~mask; 2707935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert for (;;) { 2717935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert v[firstRow] = (v[firstRow] & mask) | value; 2727935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (firstRow == lastRow) { 2737935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert break; 2747935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2757935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert firstRow += columns; 2767935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2777935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2787935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 2797935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* 2807935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Always returns 0 if called after compact(). 2817935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 2827935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public int getValue(int c, int column) { 2837935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (isCompacted || c < 0 || c > MAX_CP || column < 0 2847935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert || column >= (columns - 2)) { 2857935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return 0; 2867935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2877935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int index = findRow(c); 2887935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return v[index + 2 + column]; 2897935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2907935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 2917935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* 2927935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Returns an array which contains value elements 2932d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * in row rowIndex. 2947935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * 2957935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @throws IllegalStateException 2967935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @throws IllegalArgumentException 2977935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 2987935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public int[] getRow(int rowIndex) { 2997935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (isCompacted) { 3007935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert throw new IllegalStateException( 3017935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert "Illegal Invocation of the method after compact()"); 3027935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3037935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (rowIndex < 0 || rowIndex > rows) { 3047935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert throw new IllegalArgumentException("rowIndex out of bound!"); 3057935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3067935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int[] rowToReturn = new int[columns - 2]; 3077935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert System.arraycopy(v, rowIndex * columns + 2, rowToReturn, 0, 3087935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert columns - 2); 3097935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return rowToReturn; 3107935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3117935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 3127935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* 3137935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Returns an int which is the start codepoint 3147935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * in row rowIndex. 3152d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 3167935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @throws IllegalStateException 3172d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 3187935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @throws IllegalArgumentException 3197935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 3207935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public int getRowStart(int rowIndex) { 3217935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (isCompacted) { 3227935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert throw new IllegalStateException( 3237935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert "Illegal Invocation of the method after compact()"); 3247935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3257935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (rowIndex < 0 || rowIndex > rows) { 3267935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert throw new IllegalArgumentException("rowIndex out of bound!"); 3277935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3287935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return v[rowIndex * columns]; 3297935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3307935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 3317935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* 3322d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * Returns an int which is the limit codepoint 3337935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * minus 1 in row rowIndex. 3342d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 3357935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @throws IllegalStateException 3362d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 3377935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @throws IllegalArgumentException 3387935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 3397935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public int getRowEnd(int rowIndex) { 3407935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (isCompacted) { 3417935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert throw new IllegalStateException( 3427935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert "Illegal Invocation of the method after compact()"); 3437935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3447935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (rowIndex < 0 || rowIndex > rows) { 3457935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert throw new IllegalArgumentException("rowIndex out of bound!"); 3467935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3477935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return v[rowIndex * columns + 1] - 1; 3487935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3492d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 3507935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* 3517935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Compact the vectors: 3527935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * - modify the memory 3537935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * - keep only unique vectors 3547935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * - store them contiguously from the beginning of the memory 3552d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * - for each (non-unique) row, call the respective function in 3567935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * CompactHandler 3577935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * 3587935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * The handler's rowIndex is the index of the row in the compacted 3592d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * memory block. Therefore, it starts at 0 increases in increments of the 3607935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * columns value. 3617935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * 3627935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * In a first phase, only special values are delivered (each exactly once). 3637935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Then CompactHandler::startRealValues() is called 3647935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * where rowIndex is the length of the compacted array. 3652d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * Then, in the second phase, the CompactHandler::setRowIndexForRange() is 3667935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * called for each row of real values. 3677935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 3687935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public void compact(CompactHandler compactor) { 3697935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (isCompacted) { 3707935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return; 3717935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3727935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 3737935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Set the flag now: Sorting and compacting destroys the builder 3747935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // data structure. 3757935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert isCompacted = true; 3767935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int valueColumns = columns - 2; // not counting start & limit 3777935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 3787935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // sort the properties vectors to find unique vector values 3797935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert Integer[] indexArray = new Integer[rows]; 3807935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert for (int i = 0; i < rows; ++i) { 3817935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert indexArray[i] = Integer.valueOf(columns * i); 3827935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3837935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 3847935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert Arrays.sort(indexArray, new Comparator<Integer>() { 3852d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert @Override 3867935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public int compare(Integer o1, Integer o2) { 3877935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int indexOfRow1 = o1.intValue(); 3887935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int indexOfRow2 = o2.intValue(); 3897935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int count = columns; // includes start/limit columns 3907935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 3917935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // start comparing after start/limit 3927935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // but wrap around to them 3937935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int index = 2; 3947935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert do { 3957935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (v[indexOfRow1 + index] != v[indexOfRow2 + index]) { 3967935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return v[indexOfRow1 + index] < v[indexOfRow2 + index] ? -1 3977935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert : 1; 3987935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3997935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (++index == columns) { 4007935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert index = 0; 4017935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4027935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } while (--count > 0); 4037935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 4047935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return 0; 4057935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4067935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert }); 4077935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 4087935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* 4097935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Find and set the special values. This has to do almost the same work 4107935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * as the compaction below, to find the indexes where the special-value 4117935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * rows will move. 4127935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 4137935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int count = -valueColumns; 4147935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert for (int i = 0; i < rows; ++i) { 4157935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int start = v[indexArray[i].intValue()]; 4167935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 4177935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // count a new values vector if it is different 4187935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // from the current one 4197935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (count < 0 || !areElementsSame(indexArray[i].intValue() + 2, v, 4207935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert indexArray[i-1].intValue() + 2, valueColumns)) { 4217935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert count += valueColumns; 4227935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4237935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 4247935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (start == INITIAL_VALUE_CP) { 4257935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert compactor.setRowIndexForInitialValue(count); 4267935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } else if (start == ERROR_VALUE_CP) { 4277935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert compactor.setRowIndexForErrorValue(count); 4287935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4297935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4307935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 4317935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // count is at the beginning of the last vector, 4327935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // add valueColumns to include that last vector 4337935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert count += valueColumns; 4347935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 4357935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Call the handler once more to signal the start of 4367935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // delivering real values. 4377935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert compactor.startRealValues(count); 4387935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 4397935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* 4402d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * Move vector contents up to a contiguous array with only unique 4417935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * vector values, and call the handler function for each vector. 4422d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 4432d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * This destroys the Properties Vector structure and replaces it 4447935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * with an array of just vector values. 4457935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 4467935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int[] temp = new int[count]; 4477935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert count = -valueColumns; 4487935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert for (int i = 0; i < rows; ++i) { 4497935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int start = v[indexArray[i].intValue()]; 4507935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int limit = v[indexArray[i].intValue() + 1]; 4517935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 4527935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // count a new values vector if it is different 4537935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // from the current one 4542d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert if (count < 0 || !areElementsSame(indexArray[i].intValue() + 2, 4557935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert temp, count, valueColumns)) { 4567935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert count += valueColumns; 4577935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert System.arraycopy(v, indexArray[i].intValue() + 2, temp, count, 4587935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert valueColumns); 4597935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4607935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 4617935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (start < FIRST_SPECIAL_CP) { 4627935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert compactor.setRowIndexForRange(start, limit - 1, count); 4637935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4647935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4657935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert v = temp; 4662d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 4677935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // count is at the beginning of the last vector, 4687935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // add one to include that last vector 4697935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert rows = count / valueColumns + 1; 4707935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4717935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 4727935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* 4737935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Get the vectors array after calling compact(). 4742d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 4757935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @throws IllegalStateException 4767935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 4777935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public int[] getCompactedArray() { 4787935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (!isCompacted) { 4797935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert throw new IllegalStateException( 4807935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert "Illegal Invocation of the method before compact()"); 4817935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4827935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return v; 4837935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4847935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 4857935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* 4867935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Get the number of rows for the compacted array. 4872d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 4887935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @throws IllegalStateException 4897935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 4907935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public int getCompactedRows() { 4917935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (!isCompacted) { 4927935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert throw new IllegalStateException( 4937935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert "Illegal Invocation of the method before compact()"); 4947935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4957935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return rows; 4967935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4977935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 4987935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* 4997935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Get the number of columns for the compacted array. 5002d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 5017935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @throws IllegalStateException 5027935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 5037935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public int getCompactedColumns() { 5047935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (!isCompacted) { 5057935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert throw new IllegalStateException( 5067935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert "Illegal Invocation of the method before compact()"); 5077935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 5087935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return columns - 2; 5097935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 5107935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 5117935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* 5127935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Call compact(), create a IntTrie with indexes into the compacted 5137935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * vectors array. 5147935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 5157935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public IntTrie compactToTrieWithRowIndexes() { 5167935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert PVecToTrieCompactHandler compactor = new PVecToTrieCompactHandler(); 5177935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert compact(compactor); 5187935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return compactor.builder.serialize(new DefaultGetFoldedValue( 5197935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert compactor.builder), new DefaultGetFoldingOffset()); 5207935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 5217935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 5227935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // inner class implementation of Trie.DataManipulate 5237935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private static class DefaultGetFoldingOffset implements Trie.DataManipulate { 5242d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert @Override 5257935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public int getFoldingOffset(int value) { 5267935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return value; 5277935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 5287935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 5297935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 5307935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // inner class implementation of TrieBuilder.DataManipulate 5317935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private static class DefaultGetFoldedValue implements 5327935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert TrieBuilder.DataManipulate { 5337935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private IntTrieBuilder builder; 5347935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 5357935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public DefaultGetFoldedValue(IntTrieBuilder inBuilder) { 5367935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert builder = inBuilder; 5377935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 5387935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 5392d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert @Override 5407935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public int getFoldedValue(int start, int offset) { 5412d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert int initialValue = builder.m_initialValue_; 5427935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int limit = start + 0x400; 5437935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert while (start < limit) { 5447935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert boolean[] inBlockZero = new boolean[1]; 5457935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int value = builder.getValue(start, inBlockZero); 5467935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (inBlockZero[0]) { 5477935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert start += TrieBuilder.DATA_BLOCK_LENGTH; 5487935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } else if (value != initialValue) { 5497935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return offset; 5507935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } else { 5517935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert ++start; 5527935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 5537935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 5547935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return 0; 5557935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 5567935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 5572d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 5587935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public static interface CompactHandler { 5597935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public void setRowIndexForRange(int start, int end, int rowIndex); 5607935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public void setRowIndexForInitialValue(int rowIndex); 5617935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public void setRowIndexForErrorValue(int rowIndex); 5627935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public void startRealValues(int rowIndex); 5637935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 5647935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert}