1 /* 2 * Copyright (C) 2015 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.android.calculator2; 18 19 20 import com.hp.creals.CR; 21 import com.hp.creals.UnaryCRFunction; 22 23 import android.content.Context; 24 import android.text.SpannableString; 25 import android.text.SpannableStringBuilder; 26 import android.text.Spanned; 27 import android.text.style.TtsSpan; 28 import android.text.style.TtsSpan.TextBuilder; 29 import android.util.Log; 30 31 import java.math.BigInteger; 32 import java.io.DataInput; 33 import java.io.DataOutput; 34 import java.io.IOException; 35 import java.util.ArrayList; 36 import java.util.HashMap; 37 import java.util.IdentityHashMap; 38 39 // A mathematical expression represented as a sequence of "tokens". 40 // Many tokes are represented by button ids for the corresponding operator. 41 // Parsed only when we evaluate the expression using the "eval" method. 42 class CalculatorExpr { 43 private ArrayList<Token> mExpr; // The actual representation 44 // as a list of tokens. Constant 45 // tokens are always nonempty. 46 47 private static enum TokenKind { CONSTANT, OPERATOR, PRE_EVAL }; 48 private static TokenKind[] tokenKindValues = TokenKind.values(); 49 private final static BigInteger BIG_MILLION = BigInteger.valueOf(1000000); 50 private final static BigInteger BIG_BILLION = BigInteger.valueOf(1000000000); 51 52 private static abstract class Token { 53 abstract TokenKind kind(); 54 55 /** 56 * Write kind as Byte followed by data needed by subclass constructor. 57 */ 58 abstract void write(DataOutput out) throws IOException; 59 60 /** 61 * Return a textual representation of the token. 62 * The result is suitable for either display as part od the formula or TalkBack use. 63 * It may be a SpannableString that includes added TalkBack information. 64 * @param context context used for converting button ids to strings 65 */ 66 abstract CharSequence toCharSequence(Context context); 67 } 68 69 // An operator token 70 private static class Operator extends Token { 71 final int mId; // We use the button resource id 72 Operator(int resId) { 73 mId = resId; 74 } 75 Operator(DataInput in) throws IOException { 76 mId = in.readInt(); 77 } 78 @Override 79 void write(DataOutput out) throws IOException { 80 out.writeByte(TokenKind.OPERATOR.ordinal()); 81 out.writeInt(mId); 82 } 83 @Override 84 public CharSequence toCharSequence(Context context) { 85 String desc = KeyMaps.toDescriptiveString(context, mId); 86 if (desc != null) { 87 SpannableString result = new SpannableString(KeyMaps.toString(context, mId)); 88 Object descSpan = new TtsSpan.TextBuilder(desc).build(); 89 result.setSpan(descSpan, 0, result.length(), Spanned.SPAN_EXCLUSIVE_EXCLUSIVE); 90 return result; 91 } else { 92 return KeyMaps.toString(context, mId); 93 } 94 } 95 @Override 96 TokenKind kind() { return TokenKind.OPERATOR; } 97 } 98 99 // A (possibly incomplete) numerical constant. 100 // Supports addition and removal of trailing characters; hence mutable. 101 private static class Constant extends Token implements Cloneable { 102 private boolean mSawDecimal; 103 String mWhole; // String preceding decimal point. 104 private String mFraction; // String after decimal point. 105 private int mExponent; // Explicit exponent, only generated through addExponent. 106 107 Constant() { 108 mWhole = ""; 109 mFraction = ""; 110 mSawDecimal = false; 111 mExponent = 0; 112 }; 113 114 Constant(DataInput in) throws IOException { 115 mWhole = in.readUTF(); 116 mSawDecimal = in.readBoolean(); 117 mFraction = in.readUTF(); 118 mExponent = in.readInt(); 119 } 120 121 @Override 122 void write(DataOutput out) throws IOException { 123 out.writeByte(TokenKind.CONSTANT.ordinal()); 124 out.writeUTF(mWhole); 125 out.writeBoolean(mSawDecimal); 126 out.writeUTF(mFraction); 127 out.writeInt(mExponent); 128 } 129 130 // Given a button press, append corresponding digit. 131 // We assume id is a digit or decimal point. 132 // Just return false if this was the second (or later) decimal point 133 // in this constant. 134 // Assumes that this constant does not have an exponent. 135 boolean add(int id) { 136 if (id == R.id.dec_point) { 137 if (mSawDecimal || mExponent != 0) return false; 138 mSawDecimal = true; 139 return true; 140 } 141 int val = KeyMaps.digVal(id); 142 if (mExponent != 0) { 143 if (Math.abs(mExponent) <= 10000) { 144 if (mExponent > 0) { 145 mExponent = 10 * mExponent + val; 146 } else { 147 mExponent = 10 * mExponent - val; 148 } 149 return true; 150 } else { // Too large; refuse 151 return false; 152 } 153 } 154 if (mSawDecimal) { 155 mFraction += val; 156 } else { 157 mWhole += val; 158 } 159 return true; 160 } 161 162 void addExponent(int exp) { 163 // Note that adding a 0 exponent is a no-op. That's OK. 164 mExponent = exp; 165 } 166 167 // Undo the last add. 168 // Assumes the constant is nonempty. 169 void delete() { 170 if (mExponent != 0) { 171 mExponent /= 10; 172 // Once zero, it can only be added back with addExponent. 173 } else if (!mFraction.isEmpty()) { 174 mFraction = mFraction.substring(0, mFraction.length() - 1); 175 } else if (mSawDecimal) { 176 mSawDecimal = false; 177 } else { 178 mWhole = mWhole.substring(0, mWhole.length() - 1); 179 } 180 } 181 182 boolean isEmpty() { 183 return (mSawDecimal == false && mWhole.isEmpty()); 184 } 185 186 // Produces human-readable string, as typed. 187 // Result is internationalized. 188 @Override 189 public String toString() { 190 String result = mWhole; 191 if (mSawDecimal) { 192 result += '.'; 193 result += mFraction; 194 } 195 if (mExponent != 0) { 196 result += "E" + mExponent; 197 } 198 return KeyMaps.translateResult(result); 199 } 200 201 // Return non-null BoundedRational representation. 202 public BoundedRational toRational() { 203 String whole = mWhole; 204 if (whole.isEmpty()) whole = "0"; 205 BigInteger num = new BigInteger(whole + mFraction); 206 BigInteger den = BigInteger.TEN.pow(mFraction.length()); 207 if (mExponent > 0) { 208 num = num.multiply(BigInteger.TEN.pow(mExponent)); 209 } 210 if (mExponent < 0) { 211 den = den.multiply(BigInteger.TEN.pow(-mExponent)); 212 } 213 return new BoundedRational(num, den); 214 } 215 216 @Override 217 CharSequence toCharSequence(Context context) { 218 return toString(); 219 } 220 221 @Override 222 TokenKind kind() { return TokenKind.CONSTANT; } 223 224 // Override clone to make it public 225 @Override 226 public Object clone() { 227 Constant res = new Constant(); 228 res.mWhole = mWhole; 229 res.mFraction = mFraction; 230 res.mSawDecimal = mSawDecimal; 231 res.mExponent = mExponent; 232 return res; 233 } 234 } 235 236 // Hash maps used to detect duplicate subexpressions when 237 // we write out CalculatorExprs and read them back in. 238 private static final ThreadLocal<IdentityHashMap<CR,Integer>>outMap = 239 new ThreadLocal<IdentityHashMap<CR,Integer>>(); 240 // Maps expressions to indices on output 241 private static final ThreadLocal<HashMap<Integer,PreEval>>inMap = 242 new ThreadLocal<HashMap<Integer,PreEval>>(); 243 // Maps expressions to indices on output 244 private static final ThreadLocal<Integer> exprIndex = 245 new ThreadLocal<Integer>(); 246 247 static void initExprOutput() { 248 outMap.set(new IdentityHashMap<CR,Integer>()); 249 exprIndex.set(Integer.valueOf(0)); 250 } 251 252 static void initExprInput() { 253 inMap.set(new HashMap<Integer,PreEval>()); 254 } 255 256 // We treat previously evaluated subexpressions as tokens 257 // These are inserted when either: 258 // - We continue an expression after evaluating some of it. 259 // - TODO: When we copy/paste expressions. 260 // The representation includes three different representations 261 // of the expression: 262 // 1) The CR value for use in computation. 263 // 2) The integer value for use in the computations, 264 // if the expression evaluates to an integer. 265 // 3a) The corresponding CalculatorExpr, together with 266 // 3b) The context (currently just deg/rad mode) used to evaluate 267 // the expression. 268 // 4) A short string representation that is used to 269 // Display the expression. 270 // 271 // (3) is present only so that we can persist the object. 272 // (4) is stored explicitly to avoid waiting for recomputation in the UI 273 // thread. 274 private static class PreEval extends Token { 275 final CR mValue; 276 final BoundedRational mRatValue; 277 private final CalculatorExpr mExpr; 278 private final EvalContext mContext; 279 private final String mShortRep; // Not internationalized. 280 PreEval(CR val, BoundedRational ratVal, CalculatorExpr expr, 281 EvalContext ec, String shortRep) { 282 mValue = val; 283 mRatValue = ratVal; 284 mExpr = expr; 285 mContext = ec; 286 mShortRep = shortRep; 287 } 288 // In writing out PreEvals, we are careful to avoid writing 289 // out duplicates. We assume that two expressions are 290 // duplicates if they have the same mVal. This avoids a 291 // potential exponential blow up in certain off cases and 292 // redundant evaluation after reading them back in. 293 // The parameter hash map maps expressions we've seen 294 // before to their index. 295 @Override 296 void write(DataOutput out) throws IOException { 297 out.writeByte(TokenKind.PRE_EVAL.ordinal()); 298 Integer index = outMap.get().get(mValue); 299 if (index == null) { 300 int nextIndex = exprIndex.get() + 1; 301 exprIndex.set(nextIndex); 302 outMap.get().put(mValue, nextIndex); 303 out.writeInt(nextIndex); 304 mExpr.write(out); 305 mContext.write(out); 306 out.writeUTF(mShortRep); 307 } else { 308 // Just write out the index 309 out.writeInt(index); 310 } 311 } 312 PreEval(DataInput in) throws IOException { 313 int index = in.readInt(); 314 PreEval prev = inMap.get().get(index); 315 if (prev == null) { 316 mExpr = new CalculatorExpr(in); 317 mContext = new EvalContext(in, mExpr.mExpr.size()); 318 // Recompute other fields 319 // We currently do this in the UI thread, but we 320 // only create PreEval expressions that were 321 // previously successfully evaluated, and thus 322 // don't diverge. We also only evaluate to a 323 // constructive real, which involves substantial 324 // work only in fairly contrived circumstances. 325 // TODO: Deal better with slow evaluations. 326 EvalRet res = null; 327 try { 328 res = mExpr.evalExpr(0, mContext); 329 } catch (SyntaxException e) { 330 // Should be impossible, since we only write out 331 // expressions that can be evaluated. 332 Log.e("Calculator", "Unexpected syntax exception" + e); 333 } 334 mValue = res.mVal; 335 mRatValue = res.mRatVal; 336 mShortRep = in.readUTF(); 337 inMap.get().put(index, this); 338 } else { 339 mValue = prev.mValue; 340 mRatValue = prev.mRatValue; 341 mExpr = prev.mExpr; 342 mContext = prev.mContext; 343 mShortRep = prev.mShortRep; 344 } 345 } 346 @Override 347 CharSequence toCharSequence(Context context) { 348 return KeyMaps.translateResult(mShortRep); 349 } 350 @Override 351 TokenKind kind() { 352 return TokenKind.PRE_EVAL; 353 } 354 boolean hasEllipsis() { 355 return mShortRep.lastIndexOf(KeyMaps.ELLIPSIS) != -1; 356 } 357 } 358 359 static Token newToken(DataInput in) throws IOException { 360 TokenKind kind = tokenKindValues[in.readByte()]; 361 switch(kind) { 362 case CONSTANT: 363 return new Constant(in); 364 case OPERATOR: 365 return new Operator(in); 366 case PRE_EVAL: 367 return new PreEval(in); 368 default: throw new IOException("Bad save file format"); 369 } 370 } 371 372 CalculatorExpr() { 373 mExpr = new ArrayList<Token>(); 374 } 375 376 private CalculatorExpr(ArrayList<Token> expr) { 377 mExpr = expr; 378 } 379 380 CalculatorExpr(DataInput in) throws IOException { 381 mExpr = new ArrayList<Token>(); 382 int size = in.readInt(); 383 for (int i = 0; i < size; ++i) { 384 mExpr.add(newToken(in)); 385 } 386 } 387 388 void write(DataOutput out) throws IOException { 389 int size = mExpr.size(); 390 out.writeInt(size); 391 for (int i = 0; i < size; ++i) { 392 mExpr.get(i).write(out); 393 } 394 } 395 396 boolean hasTrailingConstant() { 397 int s = mExpr.size(); 398 if (s == 0) { 399 return false; 400 } 401 Token t = mExpr.get(s-1); 402 return t instanceof Constant; 403 } 404 405 private boolean hasTrailingBinary() { 406 int s = mExpr.size(); 407 if (s == 0) return false; 408 Token t = mExpr.get(s-1); 409 if (!(t instanceof Operator)) return false; 410 Operator o = (Operator)t; 411 return (KeyMaps.isBinary(o.mId)); 412 } 413 414 /** 415 * Append press of button with given id to expression. 416 * If the insertion would clearly result in a syntax error, either just return false 417 * and do nothing, or make an adjustment to avoid the problem. We do the latter only 418 * for unambiguous consecutive binary operators, in which case we delete the first 419 * operator. 420 */ 421 boolean add(int id) { 422 int s = mExpr.size(); 423 int d = KeyMaps.digVal(id); 424 boolean binary = KeyMaps.isBinary(id); 425 Token lastTok = s == 0 ? null : mExpr.get(s-1); 426 int lastOp = lastTok instanceof Operator ? ((Operator) lastTok).mId : 0; 427 // Quietly replace a trailing binary operator with another one, unless the second 428 // operator is minus, in which case we just allow it as a unary minus. 429 if (binary && !KeyMaps.isPrefix(id)) { 430 if (s == 0 || lastOp == R.id.lparen || KeyMaps.isFunc(lastOp) 431 || KeyMaps.isPrefix(lastOp) && lastOp != R.id.op_sub) { 432 return false; 433 } 434 while (hasTrailingBinary()) { 435 delete(); 436 } 437 // s invalid and not used below. 438 } 439 boolean isConstPiece = (d != KeyMaps.NOT_DIGIT || id == R.id.dec_point); 440 if (isConstPiece) { 441 // Since we treat juxtaposition as multiplication, a constant can appear anywhere. 442 if (s == 0) { 443 mExpr.add(new Constant()); 444 s++; 445 } else { 446 Token last = mExpr.get(s-1); 447 if(!(last instanceof Constant)) { 448 if (last instanceof PreEval) { 449 // Add explicit multiplication to avoid confusing display. 450 mExpr.add(new Operator(R.id.op_mul)); 451 s++; 452 } 453 mExpr.add(new Constant()); 454 s++; 455 } 456 } 457 return ((Constant)(mExpr.get(s-1))).add(id); 458 } else { 459 mExpr.add(new Operator(id)); 460 return true; 461 } 462 } 463 464 /** 465 * Add exponent to the constant at the end of the expression. 466 * Assumes there is a constant at the end of the expression. 467 */ 468 void addExponent(int exp) { 469 Token lastTok = mExpr.get(mExpr.size() - 1); 470 ((Constant) lastTok).addExponent(exp); 471 } 472 473 /** 474 * Remove trailing op_add and op_sub operators. 475 */ 476 void removeTrailingAdditiveOperators() { 477 while (true) { 478 int s = mExpr.size(); 479 if (s == 0) break; 480 Token lastTok = mExpr.get(s-1); 481 if (!(lastTok instanceof Operator)) break; 482 int lastOp = ((Operator) lastTok).mId; 483 if (lastOp != R.id.op_add && lastOp != R.id.op_sub) break; 484 delete(); 485 } 486 } 487 488 // Append the contents of the argument expression. 489 // It is assumed that the argument expression will not change, 490 // and thus its pieces can be reused directly. 491 // TODO: We probably only need this for expressions consisting of 492 // a single PreEval "token", and may want to check that. 493 void append(CalculatorExpr expr2) { 494 // Check that we're not concatenating Constant or PreEval 495 // tokens, since the result would look like a single constant 496 int s = mExpr.size(); 497 int s2 = expr2.mExpr.size(); 498 // Check that we're not concatenating Constant or PreEval 499 // tokens, since the result would look like a single constant, 500 // with very mysterious results for the user. 501 if (s != 0 && s2 != 0) { 502 Token last = mExpr.get(s-1); 503 Token first = expr2.mExpr.get(0); 504 if (!(first instanceof Operator) && !(last instanceof Operator)) { 505 // Fudge it by adding an explicit multiplication. 506 // We would have interpreted it as such anyway, and this 507 // makes it recognizable to the user. 508 mExpr.add(new Operator(R.id.op_mul)); 509 } 510 } 511 for (int i = 0; i < s2; ++i) { 512 mExpr.add(expr2.mExpr.get(i)); 513 } 514 } 515 516 // Undo the last key addition, if any. 517 void delete() { 518 int s = mExpr.size(); 519 if (s == 0) return; 520 Token last = mExpr.get(s-1); 521 if (last instanceof Constant) { 522 Constant c = (Constant)last; 523 c.delete(); 524 if (!c.isEmpty()) return; 525 } 526 mExpr.remove(s-1); 527 } 528 529 void clear() { 530 mExpr.clear(); 531 } 532 533 boolean isEmpty() { 534 return mExpr.isEmpty(); 535 } 536 537 // Returns a logical deep copy of the CalculatorExpr. 538 // Operator and PreEval tokens are immutable, and thus 539 // aren't really copied. 540 public Object clone() { 541 CalculatorExpr res = new CalculatorExpr(); 542 for (Token t: mExpr) { 543 if (t instanceof Constant) { 544 res.mExpr.add((Token)(((Constant)t).clone())); 545 } else { 546 res.mExpr.add(t); 547 } 548 } 549 return res; 550 } 551 552 // Am I just a constant? 553 boolean isConstant() { 554 if (mExpr.size() != 1) return false; 555 return mExpr.get(0) instanceof Constant; 556 } 557 558 // Return a new expression consisting of a single PreEval token 559 // representing the current expression. 560 // The caller supplies the value, degree mode, and short 561 // string representation, which must have been previously computed. 562 // Thus this is guaranteed to terminate reasonably quickly. 563 CalculatorExpr abbreviate(CR val, BoundedRational ratVal, 564 boolean dm, String sr) { 565 CalculatorExpr result = new CalculatorExpr(); 566 Token t = new PreEval(val, ratVal, 567 new CalculatorExpr( 568 (ArrayList<Token>)mExpr.clone()), 569 new EvalContext(dm, mExpr.size()), sr); 570 result.mExpr.add(t); 571 return result; 572 } 573 574 // Internal evaluation functions return an EvalRet triple. 575 // We compute rational (BoundedRational) results when possible, both as 576 // a performance optimization, and to detect errors exactly when we can. 577 private class EvalRet { 578 int mPos; // Next position (expression index) to be parsed 579 final CR mVal; // Constructive Real result of evaluating subexpression 580 final BoundedRational mRatVal; // Exact Rational value or null if 581 // irrational or hard to compute. 582 EvalRet(int p, CR v, BoundedRational r) { 583 mPos = p; 584 mVal = v; 585 mRatVal = r; 586 } 587 } 588 589 // And take a context argument: 590 private static class EvalContext { 591 public final int mPrefixLength; // Length of prefix to evaluate. 592 // Not explicitly saved. 593 public final boolean mDegreeMode; 594 // If we add any other kinds of evaluation modes, they go here. 595 EvalContext(boolean degreeMode, int len) { 596 mDegreeMode = degreeMode; 597 mPrefixLength = len; 598 } 599 EvalContext(DataInput in, int len) throws IOException { 600 mDegreeMode = in.readBoolean(); 601 mPrefixLength = len; 602 } 603 void write(DataOutput out) throws IOException { 604 out.writeBoolean(mDegreeMode); 605 } 606 } 607 608 private final CR RADIANS_PER_DEGREE = CR.PI.divide(CR.valueOf(180)); 609 610 private final CR DEGREES_PER_RADIAN = CR.valueOf(180).divide(CR.PI); 611 612 private CR toRadians(CR x, EvalContext ec) { 613 if (ec.mDegreeMode) { 614 return x.multiply(RADIANS_PER_DEGREE); 615 } else { 616 return x; 617 } 618 } 619 620 private CR fromRadians(CR x, EvalContext ec) { 621 if (ec.mDegreeMode) { 622 return x.multiply(DEGREES_PER_RADIAN); 623 } else { 624 return x; 625 } 626 } 627 628 // The following methods can all throw IndexOutOfBoundsException 629 // in the event of a syntax error. We expect that to be caught in 630 // eval below. 631 632 private boolean isOperatorUnchecked(int i, int op) { 633 Token t = mExpr.get(i); 634 if (!(t instanceof Operator)) return false; 635 return ((Operator)(t)).mId == op; 636 } 637 638 private boolean isOperator(int i, int op, EvalContext ec) { 639 if (i >= ec.mPrefixLength) return false; 640 return isOperatorUnchecked(i, op); 641 } 642 643 static class SyntaxException extends Exception { 644 public SyntaxException() { 645 super(); 646 } 647 public SyntaxException(String s) { 648 super(s); 649 } 650 } 651 652 // The following functions all evaluate some kind of expression 653 // starting at position i in mExpr in a specified evaluation context. 654 // They return both the expression value (as constructive real and, 655 // if applicable, as BigInteger) and the position of the next token 656 // that was not used as part of the evaluation. 657 private EvalRet evalUnary(int i, EvalContext ec) throws SyntaxException { 658 Token t = mExpr.get(i); 659 BoundedRational ratVal; 660 CR value; 661 if (t instanceof Constant) { 662 Constant c = (Constant)t; 663 ratVal = c.toRational(); 664 value = ratVal.CRValue(); 665 return new EvalRet(i+1, value, ratVal); 666 } 667 if (t instanceof PreEval) { 668 PreEval p = (PreEval)t; 669 return new EvalRet(i+1, p.mValue, p.mRatValue); 670 } 671 EvalRet argVal; 672 switch(((Operator)(t)).mId) { 673 case R.id.const_pi: 674 return new EvalRet(i+1, CR.PI, null); 675 case R.id.const_e: 676 return new EvalRet(i+1, REAL_E, null); 677 case R.id.op_sqrt: 678 // Seems to have highest precedence. 679 // Does not add implicit paren. 680 // Does seem to accept a leading minus. 681 if (isOperator(i+1, R.id.op_sub, ec)) { 682 argVal = evalUnary(i+2, ec); 683 ratVal = BoundedRational.sqrt( 684 BoundedRational.negate(argVal.mRatVal)); 685 if (ratVal != null) break; 686 return new EvalRet(argVal.mPos, 687 argVal.mVal.negate().sqrt(), null); 688 } else { 689 argVal = evalUnary(i+1, ec); 690 ratVal = BoundedRational.sqrt(argVal.mRatVal); 691 if (ratVal != null) break; 692 return new EvalRet(argVal.mPos, argVal.mVal.sqrt(), null); 693 } 694 case R.id.lparen: 695 argVal = evalExpr(i+1, ec); 696 if (isOperator(argVal.mPos, R.id.rparen, ec)) argVal.mPos++; 697 return new EvalRet(argVal.mPos, argVal.mVal, argVal.mRatVal); 698 case R.id.fun_sin: 699 argVal = evalExpr(i+1, ec); 700 if (isOperator(argVal.mPos, R.id.rparen, ec)) argVal.mPos++; 701 ratVal = ec.mDegreeMode ? BoundedRational.degreeSin(argVal.mRatVal) 702 : BoundedRational.sin(argVal.mRatVal); 703 if (ratVal != null) break; 704 return new EvalRet(argVal.mPos, 705 toRadians(argVal.mVal,ec).sin(), null); 706 case R.id.fun_cos: 707 argVal = evalExpr(i+1, ec); 708 if (isOperator(argVal.mPos, R.id.rparen, ec)) argVal.mPos++; 709 ratVal = ec.mDegreeMode ? BoundedRational.degreeCos(argVal.mRatVal) 710 : BoundedRational.cos(argVal.mRatVal); 711 if (ratVal != null) break; 712 return new EvalRet(argVal.mPos, 713 toRadians(argVal.mVal,ec).cos(), null); 714 case R.id.fun_tan: 715 argVal = evalExpr(i+1, ec); 716 if (isOperator(argVal.mPos, R.id.rparen, ec)) argVal.mPos++; 717 ratVal = ec.mDegreeMode ? BoundedRational.degreeTan(argVal.mRatVal) 718 : BoundedRational.tan(argVal.mRatVal); 719 if (ratVal != null) break; 720 CR argCR = toRadians(argVal.mVal, ec); 721 return new EvalRet(argVal.mPos, 722 argCR.sin().divide(argCR.cos()), null); 723 case R.id.fun_ln: 724 argVal = evalExpr(i+1, ec); 725 if (isOperator(argVal.mPos, R.id.rparen, ec)) argVal.mPos++; 726 ratVal = BoundedRational.ln(argVal.mRatVal); 727 if (ratVal != null) break; 728 return new EvalRet(argVal.mPos, argVal.mVal.ln(), null); 729 case R.id.fun_exp: 730 argVal = evalExpr(i+1, ec); 731 if (isOperator(argVal.mPos, R.id.rparen, ec)) argVal.mPos++; 732 ratVal = BoundedRational.exp(argVal.mRatVal); 733 if (ratVal != null) break; 734 return new EvalRet(argVal.mPos, argVal.mVal.exp(), null); 735 case R.id.fun_log: 736 argVal = evalExpr(i+1, ec); 737 if (isOperator(argVal.mPos, R.id.rparen, ec)) argVal.mPos++; 738 ratVal = BoundedRational.log(argVal.mRatVal); 739 if (ratVal != null) break; 740 return new EvalRet(argVal.mPos, 741 argVal.mVal.ln().divide(CR.valueOf(10).ln()), 742 null); 743 case R.id.fun_arcsin: 744 argVal = evalExpr(i+1, ec); 745 if (isOperator(argVal.mPos, R.id.rparen, ec)) argVal.mPos++; 746 ratVal = ec.mDegreeMode ? BoundedRational.degreeAsin(argVal.mRatVal) 747 : BoundedRational.asin(argVal.mRatVal); 748 if (ratVal != null) break; 749 return new EvalRet(argVal.mPos, 750 fromRadians(UnaryCRFunction 751 .asinFunction.execute(argVal.mVal),ec), 752 null); 753 case R.id.fun_arccos: 754 argVal = evalExpr(i+1, ec); 755 if (isOperator(argVal.mPos, R.id.rparen, ec)) argVal.mPos++; 756 ratVal = ec.mDegreeMode ? BoundedRational.degreeAcos(argVal.mRatVal) 757 : BoundedRational.acos(argVal.mRatVal); 758 if (ratVal != null) break; 759 return new EvalRet(argVal.mPos, 760 fromRadians(UnaryCRFunction 761 .acosFunction.execute(argVal.mVal),ec), 762 null); 763 case R.id.fun_arctan: 764 argVal = evalExpr(i+1, ec); 765 if (isOperator(argVal.mPos, R.id.rparen, ec)) argVal.mPos++; 766 ratVal = ec.mDegreeMode ? BoundedRational.degreeAtan(argVal.mRatVal) 767 : BoundedRational.atan(argVal.mRatVal); 768 if (ratVal != null) break; 769 return new EvalRet(argVal.mPos, 770 fromRadians(UnaryCRFunction 771 .atanFunction.execute(argVal.mVal),ec), 772 null); 773 default: 774 throw new SyntaxException("Unrecognized token in expression"); 775 } 776 // We have a rational value. 777 return new EvalRet(argVal.mPos, ratVal.CRValue(), ratVal); 778 } 779 780 // Compute an integral power of a constructive real. 781 // Unlike the "general" case using logarithms, this handles a negative 782 // base. 783 private static CR pow(CR base, BigInteger exp) { 784 if (exp.compareTo(BigInteger.ZERO) < 0) { 785 return pow(base, exp.negate()).inverse(); 786 } 787 if (exp.equals(BigInteger.ONE)) return base; 788 if (exp.and(BigInteger.ONE).intValue() == 1) { 789 return pow(base, exp.subtract(BigInteger.ONE)).multiply(base); 790 } 791 if (exp.equals(BigInteger.ZERO)) { 792 return CR.valueOf(1); 793 } 794 CR tmp = pow(base, exp.shiftRight(1)); 795 return tmp.multiply(tmp); 796 } 797 798 private static final int TEST_PREC = -100; 799 // Test for integer-ness to 100 bits past binary point. 800 private static final BigInteger MASK = 801 BigInteger.ONE.shiftLeft(-TEST_PREC).subtract(BigInteger.ONE); 802 private static final CR REAL_E = CR.valueOf(1).exp(); 803 private static final CR REAL_ONE_HUNDREDTH = CR.valueOf(100).inverse(); 804 private static final BoundedRational RATIONAL_ONE_HUNDREDTH = 805 new BoundedRational(1,100); 806 private static boolean isApprInt(CR x) { 807 BigInteger appr = x.get_appr(TEST_PREC); 808 return appr.and(MASK).signum() == 0; 809 } 810 811 private EvalRet evalSuffix(int i, EvalContext ec) throws SyntaxException { 812 EvalRet tmp = evalUnary(i, ec); 813 int cpos = tmp.mPos; 814 CR cval = tmp.mVal; 815 BoundedRational ratVal = tmp.mRatVal; 816 boolean isFact; 817 boolean isSquared = false; 818 while ((isFact = isOperator(cpos, R.id.op_fact, ec)) || 819 (isSquared = isOperator(cpos, R.id.op_sqr, ec)) || 820 isOperator(cpos, R.id.op_pct, ec)) { 821 if (isFact) { 822 if (ratVal == null) { 823 // Assume it was an integer, but we 824 // didn't figure it out. 825 // KitKat may have used the Gamma function. 826 if (!isApprInt(cval)) { 827 throw new ArithmeticException("factorial(non-integer)"); 828 } 829 ratVal = new BoundedRational(cval.BigIntegerValue()); 830 } 831 ratVal = BoundedRational.fact(ratVal); 832 cval = ratVal.CRValue(); 833 } else if (isSquared) { 834 ratVal = BoundedRational.multiply(ratVal, ratVal); 835 if (ratVal == null) { 836 cval = cval.multiply(cval); 837 } else { 838 cval = ratVal.CRValue(); 839 } 840 } else /* percent */ { 841 ratVal = BoundedRational.multiply(ratVal, RATIONAL_ONE_HUNDREDTH); 842 if (ratVal == null) { 843 cval = cval.multiply(REAL_ONE_HUNDREDTH); 844 } else { 845 cval = ratVal.CRValue(); 846 } 847 } 848 ++cpos; 849 } 850 return new EvalRet(cpos, cval, ratVal); 851 } 852 853 private EvalRet evalFactor(int i, EvalContext ec) throws SyntaxException { 854 final EvalRet result1 = evalSuffix(i, ec); 855 int cpos = result1.mPos; // current position 856 CR cval = result1.mVal; // value so far 857 BoundedRational ratVal = result1.mRatVal; // int value so far 858 if (isOperator(cpos, R.id.op_pow, ec)) { 859 final EvalRet exp = evalSignedFactor(cpos+1, ec); 860 cpos = exp.mPos; 861 // Try completely rational evaluation first. 862 ratVal = BoundedRational.pow(ratVal, exp.mRatVal); 863 if (ratVal != null) { 864 return new EvalRet(cpos, ratVal.CRValue(), ratVal); 865 } 866 // Power with integer exponent is defined for negative base. 867 // Thus we handle that case separately. 868 // We punt if the exponent is an integer computed from irrational 869 // values. That wouldn't work reliably with floating point either. 870 BigInteger int_exp = BoundedRational.asBigInteger(exp.mRatVal); 871 if (int_exp != null) { 872 cval = pow(cval, int_exp); 873 } else { 874 cval = cval.ln().multiply(exp.mVal).exp(); 875 } 876 ratVal = null; 877 } 878 return new EvalRet(cpos, cval, ratVal); 879 } 880 881 private EvalRet evalSignedFactor(int i, EvalContext ec) throws SyntaxException { 882 final boolean negative = isOperator(i, R.id.op_sub, ec); 883 int cpos = negative ? i + 1 : i; 884 EvalRet tmp = evalFactor(cpos, ec); 885 cpos = tmp.mPos; 886 CR cval = negative ? tmp.mVal.negate() : tmp.mVal; 887 BoundedRational ratVal = negative ? BoundedRational.negate(tmp.mRatVal) 888 : tmp.mRatVal; 889 return new EvalRet(cpos, cval, ratVal); 890 } 891 892 private boolean canStartFactor(int i) { 893 if (i >= mExpr.size()) return false; 894 Token t = mExpr.get(i); 895 if (!(t instanceof Operator)) return true; 896 int id = ((Operator)(t)).mId; 897 if (KeyMaps.isBinary(id)) return false; 898 switch (id) { 899 case R.id.op_fact: 900 case R.id.rparen: 901 return false; 902 default: 903 return true; 904 } 905 } 906 907 private EvalRet evalTerm(int i, EvalContext ec) throws SyntaxException { 908 EvalRet tmp = evalSignedFactor(i, ec); 909 boolean is_mul = false; 910 boolean is_div = false; 911 int cpos = tmp.mPos; // Current position in expression. 912 CR cval = tmp.mVal; // Current value. 913 BoundedRational ratVal = tmp.mRatVal; // Current rational value. 914 while ((is_mul = isOperator(cpos, R.id.op_mul, ec)) 915 || (is_div = isOperator(cpos, R.id.op_div, ec)) 916 || canStartFactor(cpos)) { 917 if (is_mul || is_div) ++cpos; 918 tmp = evalSignedFactor(cpos, ec); 919 if (is_div) { 920 ratVal = BoundedRational.divide(ratVal, tmp.mRatVal); 921 if (ratVal == null) { 922 cval = cval.divide(tmp.mVal); 923 } else { 924 cval = ratVal.CRValue(); 925 } 926 } else { 927 ratVal = BoundedRational.multiply(ratVal, tmp.mRatVal); 928 if (ratVal == null) { 929 cval = cval.multiply(tmp.mVal); 930 } else { 931 cval = ratVal.CRValue(); 932 } 933 } 934 cpos = tmp.mPos; 935 is_mul = is_div = false; 936 } 937 return new EvalRet(cpos, cval, ratVal); 938 } 939 940 private EvalRet evalExpr(int i, EvalContext ec) throws SyntaxException { 941 EvalRet tmp = evalTerm(i, ec); 942 boolean is_plus; 943 int cpos = tmp.mPos; 944 CR cval = tmp.mVal; 945 BoundedRational ratVal = tmp.mRatVal; 946 while ((is_plus = isOperator(cpos, R.id.op_add, ec)) 947 || isOperator(cpos, R.id.op_sub, ec)) { 948 tmp = evalTerm(cpos+1, ec); 949 if (is_plus) { 950 ratVal = BoundedRational.add(ratVal, tmp.mRatVal); 951 if (ratVal == null) { 952 cval = cval.add(tmp.mVal); 953 } else { 954 cval = ratVal.CRValue(); 955 } 956 } else { 957 ratVal = BoundedRational.subtract(ratVal, tmp.mRatVal); 958 if (ratVal == null) { 959 cval = cval.subtract(tmp.mVal); 960 } else { 961 cval = ratVal.CRValue(); 962 } 963 } 964 cpos = tmp.mPos; 965 } 966 return new EvalRet(cpos, cval, ratVal); 967 } 968 969 // Externally visible evaluation result. 970 public class EvalResult { 971 EvalResult (CR val, BoundedRational ratVal) { 972 mVal = val; 973 mRatVal = ratVal; 974 } 975 final CR mVal; 976 final BoundedRational mRatVal; 977 } 978 979 /** 980 * Return the starting position of the sequence of trailing binary operators. 981 */ 982 private int trailingBinaryOpsStart() { 983 int result = mExpr.size(); 984 while (result > 0) { 985 Token last = mExpr.get(result - 1); 986 if (!(last instanceof Operator)) break; 987 Operator o = (Operator)last; 988 if (!KeyMaps.isBinary(o.mId)) break; 989 --result; 990 } 991 return result; 992 } 993 994 // Is the current expression worth evaluating? 995 public boolean hasInterestingOps() { 996 int last = trailingBinaryOpsStart(); 997 int first = 0; 998 if (last > first && isOperatorUnchecked(first, R.id.op_sub)) { 999 // Leading minus is not by itself interesting. 1000 first++; 1001 } 1002 for (int i = first; i < last; ++i) { 1003 Token t1 = mExpr.get(i); 1004 if (t1 instanceof Operator 1005 || t1 instanceof PreEval && ((PreEval)t1).hasEllipsis()) { 1006 return true; 1007 } 1008 } 1009 return false; 1010 } 1011 1012 /** 1013 * Evaluate the expression excluding trailing binary operators. 1014 * Errors result in exceptions, most of which are unchecked. 1015 * Should not be called concurrently with modification of the expression. 1016 * May take a very long time; avoid calling from UI thread. 1017 * 1018 * @param degreeMode use degrees rather than radians 1019 */ 1020 EvalResult eval(boolean degreeMode) throws SyntaxException 1021 // And unchecked exceptions thrown by CR 1022 // and BoundedRational. 1023 { 1024 try { 1025 // We currently never include trailing binary operators, but include 1026 // other trailing operators. 1027 // Thus we usually, but not always, display results for prefixes 1028 // of valid expressions, and don't generate an error where we previously 1029 // displayed an instant result. This reflects the Android L design. 1030 int prefixLen = trailingBinaryOpsStart(); 1031 EvalContext ec = new EvalContext(degreeMode, prefixLen); 1032 EvalRet res = evalExpr(0, ec); 1033 if (res.mPos != prefixLen) { 1034 throw new SyntaxException("Failed to parse full expression"); 1035 } 1036 return new EvalResult(res.mVal, res.mRatVal); 1037 } catch (IndexOutOfBoundsException e) { 1038 throw new SyntaxException("Unexpected expression end"); 1039 } 1040 } 1041 1042 // Produce a string representation of the expression itself 1043 SpannableStringBuilder toSpannableStringBuilder(Context context) { 1044 SpannableStringBuilder ssb = new SpannableStringBuilder(); 1045 for (Token t: mExpr) { 1046 ssb.append(t.toCharSequence(context)); 1047 } 1048 return ssb; 1049 } 1050 } 1051