/* ====================================================================
Licensed to the Apache Software Foundation (ASF) under one or more
contributor license agreements. See the NOTICE file distributed with
this work for additional information regarding copyright ownership.
The ASF licenses this file to You under the Apache License, Version 2.0
(the "License"); you may not use this file except in compliance with
the License. You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
==================================================================== */
package org.apache.poi.ss.formula.functions;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import org.apache.poi.ss.formula.TwoDEval;
import org.apache.poi.ss.formula.eval.BlankEval;
import org.apache.poi.ss.formula.eval.BoolEval;
import org.apache.poi.ss.formula.eval.ErrorEval;
import org.apache.poi.ss.formula.eval.EvaluationException;
import org.apache.poi.ss.formula.eval.NumberEval;
import org.apache.poi.ss.formula.eval.NumericValueEval;
import org.apache.poi.ss.formula.eval.OperandResolver;
import org.apache.poi.ss.formula.eval.RefEval;
import org.apache.poi.ss.formula.eval.StringEval;
import org.apache.poi.ss.formula.eval.ValueEval;
/**
* Common functionality used by VLOOKUP, HLOOKUP, LOOKUP and MATCH
*/
final class LookupUtils {
/**
* Represents a single row or column within an AreaEval.
*/
public interface ValueVector {
ValueEval getItem(int index);
int getSize();
}
private static final class RowVector implements ValueVector {
private final TwoDEval _tableArray;
private final int _size;
private final int _rowIndex;
public RowVector(TwoDEval tableArray, int rowIndex) {
_rowIndex = rowIndex;
int lastRowIx = tableArray.getHeight() - 1;
if(rowIndex < 0 || rowIndex > lastRowIx) {
throw new IllegalArgumentException("Specified row index (" + rowIndex
+ ") is outside the allowed range (0.." + lastRowIx + ")");
}
_tableArray = tableArray;
_size = tableArray.getWidth();
}
public ValueEval getItem(int index) {
if(index > _size) {
throw new ArrayIndexOutOfBoundsException("Specified index (" + index
+ ") is outside the allowed range (0.." + (_size-1) + ")");
}
return _tableArray.getValue(_rowIndex, index);
}
public int getSize() {
return _size;
}
}
private static final class ColumnVector implements ValueVector {
private final TwoDEval _tableArray;
private final int _size;
private final int _columnIndex;
public ColumnVector(TwoDEval tableArray, int columnIndex) {
_columnIndex = columnIndex;
int lastColIx = tableArray.getWidth()-1;
if(columnIndex < 0 || columnIndex > lastColIx) {
throw new IllegalArgumentException("Specified column index (" + columnIndex
+ ") is outside the allowed range (0.." + lastColIx + ")");
}
_tableArray = tableArray;
_size = _tableArray.getHeight();
}
public ValueEval getItem(int index) {
if(index > _size) {
throw new ArrayIndexOutOfBoundsException("Specified index (" + index
+ ") is outside the allowed range (0.." + (_size-1) + ")");
}
return _tableArray.getValue(index, _columnIndex);
}
public int getSize() {
return _size;
}
}
private static final class SheetVector implements ValueVector {
private final RefEval _re;
private final int _size;
public SheetVector(RefEval re) {
_size = re.getNumberOfSheets();
_re = re;
}
public ValueEval getItem(int index) {
if(index >= _size) {
throw new ArrayIndexOutOfBoundsException("Specified index (" + index
+ ") is outside the allowed range (0.." + (_size-1) + ")");
}
int sheetIndex = _re.getFirstSheetIndex() + index;
return _re.getInnerValueEval(sheetIndex);
}
public int getSize() {
return _size;
}
}
public static ValueVector createRowVector(TwoDEval tableArray, int relativeRowIndex) {
return new RowVector(tableArray, relativeRowIndex);
}
public static ValueVector createColumnVector(TwoDEval tableArray, int relativeColumnIndex) {
return new ColumnVector(tableArray, relativeColumnIndex);
}
/**
* @return null
if the supplied area is neither a single row nor a single colum
*/
public static ValueVector createVector(TwoDEval ae) {
if (ae.isColumn()) {
return createColumnVector(ae, 0);
}
if (ae.isRow()) {
return createRowVector(ae, 0);
}
return null;
}
public static ValueVector createVector(RefEval re) {
return new SheetVector(re);
}
/**
* Enumeration to support 4 valued comparison results.
Input Return | Value | Thrown Error |
---|---|---|
5 | 4 | |
2.9 | 2 | |
"5" | 4 | |
"2.18e1" | 21 | |
"-$2" | -3 | * |
FALSE | -1 | * |
TRUE | 0 | |
"TRUE" | #REF! | |
"abc" | #REF! | |
"" | #REF! | |
<blank> | #VALUE! |
null
*/
public static boolean resolveRangeLookupArg(ValueEval rangeLookupArg, int srcCellRow, int srcCellCol) throws EvaluationException {
ValueEval valEval = OperandResolver.getSingleValue(rangeLookupArg, srcCellRow, srcCellCol);
if(valEval instanceof BlankEval) {
// Tricky:
// fourth arg supplied but evaluates to blank
// this does not get the default value
return false;
}
if(valEval instanceof BoolEval) {
// Happy day flow
BoolEval boolEval = (BoolEval) valEval;
return boolEval.getBooleanValue();
}
if (valEval instanceof StringEval) {
String stringValue = ((StringEval) valEval).getStringValue();
if(stringValue.length() < 1) {
// More trickiness:
// Empty string is not the same as BlankEval. It causes #VALUE! error
throw EvaluationException.invalidValue();
}
// TODO move parseBoolean to OperandResolver
Boolean b = Countif.parseBoolean(stringValue);
if(b != null) {
// string converted to boolean OK
return b.booleanValue();
}
// Even more trickiness:
// Note - even if the StringEval represents a number value (for example "1"),
// Excel does not resolve it to a boolean.
throw EvaluationException.invalidValue();
// This is in contrast to the code below,, where NumberEvals values (for
// example 0.01) *do* resolve to equivalent boolean values.
}
if (valEval instanceof NumericValueEval) {
NumericValueEval nve = (NumericValueEval) valEval;
// zero is FALSE, everything else is TRUE
return 0.0 != nve.getNumberValue();
}
throw new RuntimeException("Unexpected eval type (" + valEval.getClass().getName() + ")");
}
public static int lookupIndexOfValue(ValueEval lookupValue, ValueVector vector, boolean isRangeLookup) throws EvaluationException {
LookupValueComparer lookupComparer = createLookupComparer(lookupValue, isRangeLookup, false);
int result;
if(isRangeLookup) {
result = performBinarySearch(vector, lookupComparer);
} else {
result = lookupIndexOfExactValue(lookupComparer, vector);
}
if(result < 0) {
throw new EvaluationException(ErrorEval.NA);
}
return result;
}
/**
* Finds first (lowest index) exact occurrence of specified value.
* @param lookupComparer the value to be found in column or row vector
* @param vector the values to be searched. For VLOOKUP this is the first column of the
* tableArray. For HLOOKUP this is the first row of the tableArray.
* @return zero based index into the vector, -1 if value cannot be found
*/
private static int lookupIndexOfExactValue(LookupValueComparer lookupComparer, ValueVector vector) {
// find first occurrence of lookup value
int size = vector.getSize();
for (int i = 0; i < size; i++) {
if(lookupComparer.compareTo(vector.getItem(i)).isEqual()) {
return i;
}
}
return -1;
}
/**
* Encapsulates some standard binary search functionality so the unusual Excel behaviour can
* be clearly distinguished.
*/
private static final class BinarySearchIndexes {
private int _lowIx;
private int _highIx;
public BinarySearchIndexes(int highIx) {
_lowIx = -1;
_highIx = highIx;
}
/**
* @return -1 if the search range is empty
*/
public int getMidIx() {
int ixDiff = _highIx - _lowIx;
if(ixDiff < 2) {
return -1;
}
return _lowIx + (ixDiff / 2);
}
public int getLowIx() {
return _lowIx;
}
public int getHighIx() {
return _highIx;
}
public void narrowSearch(int midIx, boolean isLessThan) {
if(isLessThan) {
_highIx = midIx;
} else {
_lowIx = midIx;
}
}
}
/**
* Excel has funny behaviour when the some elements in the search vector are the wrong type.
*
*/
private static int performBinarySearch(ValueVector vector, LookupValueComparer lookupComparer) {
// both low and high indexes point to values assumed too low and too high.
BinarySearchIndexes bsi = new BinarySearchIndexes(vector.getSize());
while(true) {
int midIx = bsi.getMidIx();
if(midIx < 0) {
return bsi.getLowIx();
}
CompareResult cr = lookupComparer.compareTo(vector.getItem(midIx));
if(cr.isTypeMismatch()) {
int newMidIx = handleMidValueTypeMismatch(lookupComparer, vector, bsi, midIx);
if(newMidIx < 0) {
continue;
}
midIx = newMidIx;
cr = lookupComparer.compareTo(vector.getItem(midIx));
}
if(cr.isEqual()) {
return findLastIndexInRunOfEqualValues(lookupComparer, vector, midIx, bsi.getHighIx());
}
bsi.narrowSearch(midIx, cr.isLessThan());
}
}
/**
* Excel seems to handle mismatched types initially by just stepping 'mid' ix forward to the
* first compatible value.
* @param midIx 'mid' index (value which has the wrong type)
* @return usually -1, signifying that the BinarySearchIndex has been narrowed to the new mid
* index. Zero or greater signifies that an exact match for the lookup value was found
*/
private static int handleMidValueTypeMismatch(LookupValueComparer lookupComparer, ValueVector vector,
BinarySearchIndexes bsi, int midIx) {
int newMid = midIx;
int highIx = bsi.getHighIx();
while(true) {
newMid++;
if(newMid == highIx) {
// every element from midIx to highIx was the wrong type
// move highIx down to the low end of the mid values
bsi.narrowSearch(midIx, true);
return -1;
}
CompareResult cr = lookupComparer.compareTo(vector.getItem(newMid));
if(cr.isLessThan() && newMid == highIx-1) {
// move highIx down to the low end of the mid values
bsi.narrowSearch(midIx, true);
return -1;
// but only when "newMid == highIx-1"? slightly weird.
// It would seem more efficient to always do this.
}
if(cr.isTypeMismatch()) {
// keep stepping over values until the right type is found
continue;
}
if(cr.isEqual()) {
return newMid;
}
// Note - if moving highIx down (due to lookup