/**
 * Generic utility functions for <code>MyNumber</code>s.
 *
 * @author   CS211 Staff
 * @version  0.9.2, 09/14/2000
 */

class MyNumbers {
  /**
   * Returns <code>true</code> if <code>n</code> is zero.
   *
   * @param   n  the number to test
   * @return  <code>true</code> if <code>n</code> is zero;
   *          <code>false</code> otherwise
   */
  public static boolean isZero    (MyNumber n)
    { return false;  /* ... */ }

  /**
   * Returns <code>true</code> if <code>n</code> is negative.
   *
   * @param   n  the number to test
   * @return  <code>true</code> if <code>n</code> is less than zero;
   *          <code>false</code> otherwise
   */
  public static boolean isNegative(MyNumber n)
    { return false;  /* ... */ }

  /**
   * Returns a new <code>MyNumber</code> object that initially holds
   * the absolute value of <code>n</code>.
   * <p>
   * [The returned object is guaranteed to be an instance of
   * <code>n</code>'s class.]
   *
   * @param   n  the number whose is magnitude is to be taken
   * @return  a new <code>MyNumber</code> object whose initial value
   *          is the magnitude of <code>n</code>
   */
  public static MyNumber abs(MyNumber n)
    { return null;  /* ... */ }

  /**
   * Returns <code>true</code> if <code>m</code> divides <code>n</code>
   * evenly.  When <code>n</code> and <code>m</code> are both positive,
   * this is equivalent to saying that <code>true</code> is returned iff
   *
   * <pre>  n = m + m + m + ... + m + m + m</pre>
   *
   * where <code>m</code> may be repeated zero or more times on the
   * right-hand side.
   * <p>
   * [For consistency with <code>MyInteger</code>, the <code>divides</code>
   * method's behavior is undefined when <code>m</code> is zero.]
   *
   * @param   m  the number to divide by
   * @param   n  the number to divide into
   * @return  <code>true</code> if <code>m</code> divides <code>n</code>
   *          evenly; <code>false</code> otherwise
   */
  public static boolean divides(MyNumber m0, MyNumber n0) {
    // exploit the fact that m0 divides n0 if and only if
    //  abs(m0) divides abs(n0)...
    MyNumber  m = abs(m0);  // ...invariant:  m is always >= 0
    MyNumber  r = abs(n0);  // ...invariant:  r is always >= 0

    // catch the m = 0 special case...
    if (isZero(m)) {
      warn("division by zero in MyNumbers.divides.");
      return isZero(n0);
    }

    // the naive algorithm is to repeatedly subtract m from r
    // until r < m, at which point r = abs(n0) % abs(m0).  but
    // consider the case m = 7 and r = 11111111111111111111111;
    // how many subtractions would be required?  ouch!
    //
    // we can improve that overly naive strategy by simply taking
    // larger steps, i.e., by subtracting larger multiples of m...
    //
    //   11111111111111111111111
    // -  7000000000000000000000  <--  subtract 1E21 * m =  7E21
    //   -----------------------
    //    4111111111111111111111
    //  - 3500000000000000000000  <--  subtract 5E20 * m = 35E20
    //    ----------------------
    //     611111111111111111111
    //   - 560000000000000000000  <--  subtract 8E19 * m = 56E19
    //     ---------------------
    //      51111111111111111111
    //    - 49000000000000000000  <--  subtract 7E18 * m = 49E18
    //      --------------------
    //       2111111111111111111
    //     - 2100000000000000000  <--  subtract 3E17 * m = 21E17
    //       -------------------
    //         11111111111111111
    //                      etc.
    //
    // ...note how each of our large-multiple subtractions shaves off
    // at least one digit from r; instead of ~10^22 steps, we only need
    // ~22!
    //
    // [of course, in actual code, it's more natural to use
    // steps of size "2^i * m", rather than using steps of size
    // "c * 10^i * m", as was done above.]

    // (m has been initialized to abs(m0), and r has been
    //  initialized to abs(n0).)

    // subtract multiples of m from r, until r < m...
    while (! r.lessThan(m)) {
      // ...invariant:  r % m = abs(n0) % abs(m0)

      // want a _large_ multiple of m that is <= r...
      MyNumber  km = largeMultipleBelow(m, r);

      // r -= km
      km.minus();  r.plus(km);

      // [we're exploiting the fact that (r - k * m) % m = r % m
      //  whenever k is an integer such that k * m <= r]
    }

    // since r < m, r = r % m; 
    //  thus r = r % m = abs(n0) % abs(m0)...
    return isZero(r);

    // ...of course, this could be improved further, but it's
    // adequate for our current factorization needs, :).
  }

  /**
   * Returns the largest integer of the form <code>2^i * m</code> that
   * does not exceed <code>n</code>.
   * <p>
   * [<code>m</code> is assumed to be positive, <code>n</code> is
   * assumed to be nonnegative, and <code>m</code> is assumed to be
   * <code>&lt;= n</code>.]
   */
  private static MyNumber largeMultipleBelow(MyNumber m, MyNumber n) {
    MyNumber  km = (MyNumber) m.clone();
      // ...invariant:  km <= n

    MyNumber  kmMultiplier = km.createCompatible(2);
      // ...invariant:  km = kmMultiplier^i * m  (for some i >= 0)

    // km = km * kmMultiplier, until km * kmMultiplier > n...
    MyNumber  kmNext = (MyNumber) km.clone();  kmNext.times(kmMultiplier);
      // ...invariant:  kmNext = km * kmMultiplier > km
    while (! n.lessThan(kmNext))
      { km.times(kmMultiplier);  kmNext.times(kmMultiplier); }

    // km <= n < km * kmMultiplier...
    return km;
  }

  /**
   * Reports a warning.
   */
  private static void warn(String message)
    { System.err.println("**** warning:  " + message); }

  // MyNumbers is entirely static, so we should "hide" the constructor.
  private MyNumbers()  { }
}