lookuputils.java

来自「EXCEL read and write」· Java 代码 · 共 617 行 · 第 1/2 页

	 *    <table border="0" cellpadding="1" cellspacing="2" summary="Sample behaviour">
	 *      <tr><th>Input&nbsp;&nbsp;&nbsp;Return</th><th>Value&nbsp;&nbsp;</th><th>Thrown Error</th></tr>
	 *      <tr><td>5</td><td>4</td><td>&nbsp;</td></tr>
	 *      <tr><td>2.9</td><td>2</td><td>&nbsp;</td></tr>
	 *      <tr><td>"5"</td><td>4</td><td>&nbsp;</td></tr>
	 *      <tr><td>"2.18e1"</td><td>21</td><td>&nbsp;</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>&nbsp;</td></tr>
	 *      <tr><td>"TRUE"</td><td>&nbsp;</td><td>#REF!</td></tr>
	 *      <tr><td>"abc"</td><td>&nbsp;</td><td>#REF!</td></tr>
	 *      <tr><td>""</td><td>&nbsp;</td><td>#REF!</td></tr>
	 *      <tr><td>&lt;blank&gt;</td><td>&nbsp;</td><td>#VALUE!</td></tr>
	 *    </table><br/>
	 *
	 * Note - out of range errors (result index too high) are handled by the caller.
	 * @return column or row index as a zero-based value, never negative.
	 * @throws EvaluationException when the specified arg cannot be coerced to a non-negative integer
	 */
	public static int resolveRowOrColIndexArg(Eval rowColIndexArg, int srcCellRow, int srcCellCol) throws EvaluationException {
		if(rowColIndexArg == null) {
			throw new IllegalArgumentException("argument must not be null");
		}
		
		ValueEval veRowColIndexArg;
		try {
			veRowColIndexArg = OperandResolver.getSingleValue(rowColIndexArg, srcCellRow, (short)srcCellCol);
		} catch (EvaluationException e) {
			// All errors get translated to #REF!
			throw EvaluationException.invalidRef();
		}
		int oneBasedIndex;
		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 #REF! 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
		oneBasedIndex = OperandResolver.coerceValueToInt(veRowColIndexArg);
		if (oneBasedIndex < 1) {
			// note this is asymmetric with the errors when the index is too large (#REF!)  
			throw EvaluationException.invalidValue();
		}
		return oneBasedIndex - 1; // convert to zero based
	}



	/**
	 * 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.
			return refEval.offset(0, 0, 0, 0);
		}
		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) {

		if (lookupValue == BlankEval.INSTANCE) {
			// blank eval translates to zero
			// Note - a blank eval in the lookup column/row never matches anything
			// empty string in the lookup column/row can only be matched by explicit emtpty string
			return new NumberLookupComparer(NumberEval.ZERO);
		}
		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() + ")");
	}
}