/* ====================================================================
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.hssf.record.formula.functions;
import org.apache.poi.hssf.record.formula.AreaPtg;
import org.apache.poi.hssf.record.formula.eval.Area2DEval;
import org.apache.poi.hssf.record.formula.eval.AreaEval;
import org.apache.poi.hssf.record.formula.eval.BlankEval;
import org.apache.poi.hssf.record.formula.eval.BoolEval;
import org.apache.poi.hssf.record.formula.eval.ErrorEval;
import org.apache.poi.hssf.record.formula.eval.Eval;
import org.apache.poi.hssf.record.formula.eval.EvaluationException;
import org.apache.poi.hssf.record.formula.eval.NumberEval;
import org.apache.poi.hssf.record.formula.eval.NumericValueEval;
import org.apache.poi.hssf.record.formula.eval.OperandResolver;
import org.apache.poi.hssf.record.formula.eval.RefEval;
import org.apache.poi.hssf.record.formula.eval.StringEval;
import org.apache.poi.hssf.record.formula.eval.ValueEval;
/**
* Common functionality used by VLOOKUP, HLOOKUP, LOOKUP and MATCH
*
* @author Josh Micich
*/
final class LookupUtils {
/**
* Represents a single row or column within an <tt>AreaEval</tt>.
*/
public interface ValueVector {
ValueEval getItem(int index);
int getSize();
}
/**
* Enumeration to support <b>4</b> valued comparison results.<p/>
* Excel lookup functions have complex behaviour in the case where the lookup array has mixed
* types, and/or is unordered. Contrary to suggestions in some Excel documentation, there
* does not appear to be a universal ordering across types. The binary search algorithm used
* changes behaviour when the evaluated 'mid' value has a different type to the lookup value.<p/>
*
* A simple int might have done the same job, but there is risk in confusion with the well
* known <tt>Comparable.compareTo()</tt> and <tt>Comparator.compare()</tt> which both use
* a ubiquitous 3 value result encoding.
*/
public static final class CompareResult {
private final boolean _isTypeMismatch;
private final boolean _isLessThan;
private final boolean _isEqual;
private final boolean _isGreaterThan;
private CompareResult(boolean isTypeMismatch, int simpleCompareResult) {
if(isTypeMismatch) {
_isTypeMismatch = true;
_isLessThan = false;
_isEqual = false;
_isGreaterThan = false;
} else {
_isTypeMismatch = false;
_isLessThan = simpleCompareResult < 0;
_isEqual = simpleCompareResult == 0;
_isGreaterThan = simpleCompareResult > 0;
}
}
public static final CompareResult TYPE_MISMATCH = new CompareResult(true, 0);
public static final CompareResult LESS_THAN = new CompareResult(false, -1);
public static final CompareResult EQUAL = new CompareResult(false, 0);
public static final CompareResult GREATER_THAN = new CompareResult(false, +1);
public static final CompareResult valueOf(int simpleCompareResult) {
if(simpleCompareResult < 0) {
return LESS_THAN;
}
if(simpleCompareResult > 0) {
return GREATER_THAN;
}
return EQUAL;
}
public boolean isTypeMismatch() {
return _isTypeMismatch;
}
public boolean isLessThan() {
return _isLessThan;
}
public boolean isEqual() {
return _isEqual;
}
public boolean isGreaterThan() {
return _isGreaterThan;
}
public String toString() {
StringBuffer sb = new StringBuffer(64);
sb.append(getClass().getName()).append(" [");
sb.append(formatAsString());
sb.append("]");
return sb.toString();
}
private String formatAsString() {
if(_isTypeMismatch) {
return "TYPE_MISMATCH";
}
if(_isLessThan) {
return "LESS_THAN";
}
if(_isEqual) {
return "EQUAL";
}
if(_isGreaterThan) {
return "GREATER_THAN";
}
// toString must be reliable
return "??error??";
}
}
public interface LookupValueComparer {
/**
* @return one of 4 instances or <tt>CompareResult</tt>: <tt>LESS_THAN</tt>, <tt>EQUAL</tt>,
* <tt>GREATER_THAN</tt> or <tt>TYPE_MISMATCH</tt>
*/
CompareResult compareTo(ValueEval other);
}
private static abstract class LookupValueComparerBase implements LookupValueComparer {
private final Class _targetClass;
protected LookupValueComparerBase(ValueEval targetValue) {
if(targetValue == null) {
throw new RuntimeException("targetValue cannot be null");
}
_targetClass = targetValue.getClass();
}
public final CompareResult compareTo(ValueEval other) {
if (other == null) {
throw new RuntimeException("compare to value cannot be null");
}
if (_targetClass != other.getClass()) {
return CompareResult.TYPE_MISMATCH;
}
if (_targetClass == StringEval.class) {
}
return compareSameType(other);
}
public String toString() {
StringBuffer sb = new StringBuffer(64);
sb.append(getClass().getName()).append(" [");
sb.append(getValueAsString());
sb.append("]");
return sb.toString();
}
protected abstract CompareResult compareSameType(ValueEval other);
/** used only for debug purposes */
protected abstract String getValueAsString();
}
private static final class StringLookupComparer extends LookupValueComparerBase {
private String _value;
protected StringLookupComparer(StringEval se) {
super(se);
_value = se.getStringValue();
}
protected CompareResult compareSameType(ValueEval other) {
StringEval se = (StringEval) other;
return CompareResult.valueOf(_value.compareToIgnoreCase(se.getStringValue()));
}
protected String getValueAsString() {
return _value;
}
}
private static final class NumberLookupComparer extends LookupValueComparerBase {
private double _value;
protected NumberLookupComparer(NumberEval ne) {
super(ne);
_value = ne.getNumberValue();
}
protected CompareResult compareSameType(ValueEval other) {
NumberEval ne = (NumberEval) other;
return CompareResult.valueOf(Double.compare(_value, ne.getNumberValue()));
}
protected String getValueAsString() {
return String.valueOf(_value);
}
}
private static final class BooleanLookupComparer extends LookupValueComparerBase {
private boolean _value;
protected BooleanLookupComparer(BoolEval be) {
super(be);
_value = be.getBooleanValue();
}
protected CompareResult compareSameType(ValueEval other) {
BoolEval be = (BoolEval) other;
boolean otherVal = be.getBooleanValue();
if(_value == otherVal) {
return CompareResult.EQUAL;
}
// TRUE > FALSE
if(_value) {
return CompareResult.GREATER_THAN;
}
return CompareResult.LESS_THAN;
}
protected String getValueAsString() {
return String.valueOf(_value);
}
}
/**
* Processes the third argument to VLOOKUP, or HLOOKUP (<b>col_index_num</b>
* or <b>row_index_num</b> respectively).<br>
* Sample behaviour:
* <table border="0" cellpadding="1" cellspacing="2" summary="Sample behaviour">
* <tr><th>Input Return</th><th>Value </th><th>Thrown Error</th></tr>
* <tr><td>5</td><td>4</td><td> </td></tr>
* <tr><td>2.9</td><td>2</td><td> </td></tr>
* <tr><td>"5"</td><td>4</td><td> </td></tr>
* <tr><td>"2.18e1"</td><td>21</td><td> </td></tr>
* <tr><td>"-$2"</td><td>-3</td><td>*</td></tr>
* <tr><td>FALSE</td><td>-1</td><td>*</td></tr>
* <tr><td>TRUE</td><td>0</td><td> </td></tr>
* <tr><td>"TRUE"</td><td> </td><td>#REF!</td></tr>
* <tr><td>"abc"</td><td> </td><td>#REF!</td></tr>
* <tr><td>""</td><td> </td><td>#REF!</td></tr>
* <tr><td><blank></td><td> </td><td>#VALUE!</td></tr>
* </table><br/>
*
* * Note - out of range errors (both too high and too low) are handled by the caller.
* @return column or row index as a zero-based value
*
*/
public static int resolveRowOrColIndexArg(ValueEval veRowColIndexArg) throws EvaluationException {
if(veRowColIndexArg == null) {
throw new IllegalArgumentException("argument must not be null");
}
if(veRowColIndexArg instanceof BlankEval) {
throw EvaluationException.invalidValue();
}
if(veRowColIndexArg instanceof StringEval) {
StringEval se = (StringEval) veRowColIndexArg;
String strVal = se.getStringValue();
Double dVal = OperandResolver.parseDouble(strVal);
if(dVal == null) {
// String does not resolve to a number. Raise #VALUE! error.
throw EvaluationException.invalidRef();
// This includes text booleans "TRUE" and "FALSE". They are not valid.
}
// else - numeric value parses OK
}
// actual BoolEval values get interpreted as FALSE->0 and TRUE->1
return OperandResolver.coerceValueToInt(veRowColIndexArg) - 1;
}
/**
* The second argument (table_array) should be an area ref, but can actually be a cell ref, in
* which case it is interpreted as a 1x1 area ref. Other scalar values cause #VALUE! error.
*/
public static AreaEval resolveTableArrayArg(Eval eval) throws EvaluationException {
if (eval instanceof AreaEval) {
return (AreaEval) eval;
}
if(eval instanceof RefEval) {
RefEval refEval = (RefEval) eval;
// Make this cell ref look like a 1x1 area ref.
// It doesn't matter if eval is a 2D or 3D ref, because that detail is never asked of AreaEval.
// This code only requires the value array item.
// anything would be ok for rowIx and colIx, but may as well get it right.
int rowIx = refEval.getRow();
int colIx = refEval.getColumn();
AreaPtg ap = new AreaPtg(rowIx, rowIx, colIx, colIx, false, false, false, false);
ValueEval value = refEval.getInnerValueEval();
return new Area2DEval(ap, new ValueEval[] { value, });
}
throw EvaluationException.invalidValue();
}
/**
* Resolves the last (optional) parameter (<b>range_lookup</b>) to the VLOOKUP and HLOOKUP functions.
* @param rangeLookupArg
* @param srcCellRow
* @param srcCellCol
* @return
* @throws EvaluationException
*/
public static boolean resolveRangeLookupArg(Eval rangeLookupArg, int srcCellRow, short srcCellCol) throws EvaluationException {
if(rangeLookupArg == null) {
// range_lookup arg not provided
return true; // default is TRUE
}
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);
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 lookupValue 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<vector[newMid]),
// this execution path only moves highIx it down as far as newMid, not midIx,
// which would be more efficient.
bsi.narrowSearch(newMid, cr.isLessThan());
return -1;
}
}
/**
* Once the binary search has found a single match, (V/H)LOOKUP steps one by one over subsequent
* values to choose the last matching item.
*/
private static int findLastIndexInRunOfEqualValues(LookupValueComparer lookupComparer, ValueVector vector,
int firstFoundIndex, int maxIx) {
for(int i=firstFoundIndex+1; i<maxIx; i++) {
if(!lookupComparer.compareTo(vector.getItem(i)).isEqual()) {
return i-1;
}
}
return maxIx - 1;
}
public static LookupValueComparer createLookupComparer(ValueEval lookupValue) throws EvaluationException {
if (lookupValue instanceof BlankEval) {
// blank eval can never be found in a lookup array
throw new EvaluationException(ErrorEval.NA);
}
if (lookupValue instanceof StringEval) {
return new StringLookupComparer((StringEval) lookupValue);
}
if (lookupValue instanceof NumberEval) {
return new NumberLookupComparer((NumberEval) lookupValue);
}
if (lookupValue instanceof BoolEval) {
return new BooleanLookupComparer((BoolEval) lookupValue);
}
throw new IllegalArgumentException("Bad lookup value type (" + lookupValue.getClass().getName() + ")");
}
}