content: /*
   * Copyright (C) 2013 The Android Open Source Project
   *
   * Licensed 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 android.content;
  
  import android.annotation.UnsupportedAppUsage;
  import android.os.Parcel;
  import android.os.Parcelable;
  import android.os.ParcelableParcel;
  import android.text.TextUtils;
  import android.util.ArrayMap;
  
  import java.util.ArrayList;
  
  /**
   * Top-level class for managing and interacting with the global undo state for
   * a document or application.  This class supports both undo and redo and has
   * helpers for merging undoable operations together as they are performed.
   *
   * <p>A single undoable operation is represented by {@link UndoOperation} which
   * apps implement to define their undo/redo behavior.  The UndoManager keeps
   * a stack of undo states; each state can have one or more undo operations
   * inside of it.</p>
   *
   * <p>Updates to the stack must be done inside of a {@link #beginUpdate}/{@link #endUpdate()}
   * pair.  During this time you can add new operations to the stack with
   * {@link #addOperation}, retrieve and modify existing operations with
   * {@link #getLastOperation}, control the label shown to the user for this operation
   * with {@link #setUndoLabel} and {@link #suggestUndoLabel}, etc.</p>
   *
   * <p>Every {link UndoOperation} is associated with an {@link UndoOwner}, which identifies
   * the data it belongs to.  The owner is used to indicate how operations are dependent
   * on each other -- operations with the same owner are dependent on others with the
   * same owner.  For example, you may have a document with multiple embedded objects.  If the
   * document itself and each embedded object use different owners, then you
   * can provide undo semantics appropriate to the user's context: while within
   * an embedded object, only edits to that object are seen and the user can
   * undo/redo them without needing to impact edits in other objects; while
   * within the larger document, all edits can be seen and the user must
   * undo/redo them as a single stream.</p>
   *
   * @hide
   */
  public class UndoManager {
      // The common case is a single undo owner (e.g. for a TextView), so default to that capacity.
      private final ArrayMap<String, UndoOwner> mOwners =
              new ArrayMap<String, UndoOwner>(1 /* capacity */);
      private final ArrayList<UndoState> mUndos = new ArrayList<UndoState>();
      private final ArrayList<UndoState> mRedos = new ArrayList<UndoState>();
      private int mUpdateCount;
      private int mHistorySize = 20;
      private UndoState mWorking;
      private int mCommitId = 1;
      private boolean mInUndo;
      private boolean mMerged;
  
      private int mStateSeq;
      private int mNextSavedIdx;
      private UndoOwner[] mStateOwners;
  
      /**
       * Never merge with the last undo state.
       */
      public static final int MERGE_MODE_NONE = 0;
  
      /**
       * Allow merge with the last undo state only if it contains
       * operations with the caller's owner.
       */
      public static final int MERGE_MODE_UNIQUE = 1;
  
      /**
       * Always allow merge with the last undo state, if possible.
       */
      public static final int MERGE_MODE_ANY = 2;
  
      @UnsupportedAppUsage
      public UndoOwner getOwner(String tag, Object data) {
          if (tag == null) {
              throw new NullPointerException("tag can't be null");
          }
          if (data == null) {
              throw new NullPointerException("data can't be null");
          }
          UndoOwner owner = mOwners.get(tag);
          if (owner != null) {
              if (owner.mData != data) {
                  if (owner.mData != null) {
                      throw new IllegalStateException("Owner " + owner + " already exists with data "
                              + owner.mData + " but giving different data " + data);
                  }
                  owner.mData = data;
              }
              return owner;
          }
  
          owner = new UndoOwner(tag, this);
          owner.mData = data;
          mOwners.put(tag, owner);
          return owner;
      }
  
      void removeOwner(UndoOwner owner) {
          // XXX need to figure out how to prune.
          if (false) {
              mOwners.remove(owner.mTag);
          }
      }
  
      /**
       * Flatten the current undo state into a Parcel object, which can later be restored
       * with {@link #restoreInstanceState(android.os.Parcel, java.lang.ClassLoader)}.
       */
      @UnsupportedAppUsage
      public void saveInstanceState(Parcel p) {
          if (mUpdateCount > 0) {
              throw new IllegalStateException("Can't save state while updating");
          }
          mStateSeq++;
          if (mStateSeq <= 0) {
              mStateSeq = 0;
          }
          mNextSavedIdx = 0;
          p.writeInt(mHistorySize);
          p.writeInt(mOwners.size());
          // XXX eventually we need to be smart here about limiting the
          // number of undo states we write to not exceed X bytes.
          int i = mUndos.size();
          while (i > 0) {
              p.writeInt(1);
              i--;
              mUndos.get(i).writeToParcel(p);
          }
          i = mRedos.size();
          while (i > 0) {
              p.writeInt(2);
              i--;
              mRedos.get(i).writeToParcel(p);
          }
          p.writeInt(0);
      }
  
      void saveOwner(UndoOwner owner, Parcel out) {
          if (owner.mStateSeq == mStateSeq) {
              out.writeInt(owner.mSavedIdx);
          } else {
              owner.mStateSeq = mStateSeq;
              owner.mSavedIdx = mNextSavedIdx;
              out.writeInt(owner.mSavedIdx);
              out.writeString(owner.mTag);
              out.writeInt(owner.mOpCount);
              mNextSavedIdx++;
          }
      }
  
      /**
       * Restore an undo state previously created with {@link #saveInstanceState(Parcel)}.  This
       * will restore the UndoManager's state to almost exactly what it was at the point it had
       * been previously saved; the only information not restored is the data object
       * associated with each {@link UndoOwner}, which requires separate calls to
       * {@link #getOwner(String, Object)} to re-associate the owner with its data.
       */
      @UnsupportedAppUsage
      public void restoreInstanceState(Parcel p, ClassLoader loader) {
          if (mUpdateCount > 0) {
              throw new IllegalStateException("Can't save state while updating");
          }
          forgetUndos(null, -1);
          forgetRedos(null, -1);
          mHistorySize = p.readInt();
          mStateOwners = new UndoOwner[p.readInt()];
  
          int stype;
          while ((stype=p.readInt()) != 0) {
              UndoState ustate = new UndoState(this, p, loader);
              if (stype == 1) {
                  mUndos.add(0, ustate);
              } else {
                  mRedos.add(0, ustate);
              }
          }
      }
  
      UndoOwner restoreOwner(Parcel in) {
          int idx = in.readInt();
          UndoOwner owner = mStateOwners[idx];
          if (owner == null) {
              String tag = in.readString();
              int opCount = in.readInt();
              owner = new UndoOwner(tag, this);
              owner.mOpCount = opCount;
              mStateOwners[idx] = owner;
              mOwners.put(tag, owner);
          }
          return owner;
      }
  
      /**
       * Set the maximum number of undo states that will be retained.
       */
      public void setHistorySize(int size) {
          mHistorySize = size;
          if (mHistorySize >= 0 && countUndos(null) > mHistorySize) {
              forgetUndos(null, countUndos(null) - mHistorySize);
          }
      }
  
      /**
       * Return the current maximum number of undo states.
       */
      public int getHistorySize() {
          return mHistorySize;
      }
  
      /**
       * Perform undo of last/top <var>count</var> undo states.  The states impacted
       * by this can be limited through <var>owners</var>.
       * @param owners Optional set of owners that should be impacted.  If null, all
       * undo states will be visible and available for undo.  If non-null, only those
       * states that contain one of the owners specified here will be visible.
       * @param count Number of undo states to pop.
       * @return Returns the number of undo states that were actually popped.
       */
      @UnsupportedAppUsage
      public int undo(UndoOwner[] owners, int count) {
          if (mWorking != null) {
              throw new IllegalStateException("Can't be called during an update");
          }
  
          int num = 0;
          int i = -1;
  
          mInUndo = true;
  
          UndoState us = getTopUndo(null);
          if (us != null) {
              us.makeExecuted();
          }
  
          while (count > 0 && (i=findPrevState(mUndos, owners, i)) >= 0) {
              UndoState state = mUndos.remove(i);
              state.undo();
              mRedos.add(state);
              count--;
              num++;
          }
  
          mInUndo = false;
  
          return num;
      }
  
      /**
       * Perform redo of last/top <var>count</var> undo states in the transient redo stack.
       * The states impacted by this can be limited through <var>owners</var>.
       * @param owners Optional set of owners that should be impacted.  If null, all
       * undo states will be visible and available for undo.  If non-null, only those
       * states that contain one of the owners specified here will be visible.
       * @param count Number of undo states to pop.
       * @return Returns the number of undo states that were actually redone.
       */
      @UnsupportedAppUsage
      public int redo(UndoOwner[] owners, int count) {
          if (mWorking != null) {
              throw new IllegalStateException("Can't be called during an update");
          }
  
          int num = 0;
          int i = -1;
  
          mInUndo = true;
  
          while (count > 0 && (i=findPrevState(mRedos, owners, i)) >= 0) {
              UndoState state = mRedos.remove(i);
              state.redo();
              mUndos.add(state);
              count--;
              num++;
          }
  
          mInUndo = false;
  
          return num;
      }
  
      /**
       * Returns true if we are currently inside of an undo/redo operation.  This is
       * useful for editors to know whether they should be generating new undo state
       * when they see edit operations happening.
       */
      @UnsupportedAppUsage
      public boolean isInUndo() {
          return mInUndo;
      }
  
      @UnsupportedAppUsage
      public int forgetUndos(UndoOwner[] owners, int count) {
          if (count < 0) {
              count = mUndos.size();
          }
  
          int removed = 0;
          int i = 0;
          while (i < mUndos.size() && removed < count) {
              UndoState state = mUndos.get(i);
              if (count > 0 && matchOwners(state, owners)) {
                  state.destroy();
                  mUndos.remove(i);
                  removed++;
              } else {
                  i++;
              }
          }
  
          return removed;
      }
  
      @UnsupportedAppUsage
      public int forgetRedos(UndoOwner[] owners, int count) {
          if (count < 0) {
              count = mRedos.size();
          }
  
          int removed = 0;
          int i = 0;
          while (i < mRedos.size() && removed < count) {
              UndoState state = mRedos.get(i);
              if (count > 0 && matchOwners(state, owners)) {
                  state.destroy();
                  mRedos.remove(i);
                  removed++;
              } else {
                  i++;
              }
          }
  
          return removed;
      }
  
      /**
       * Return the number of undo states on the undo stack.
       * @param owners If non-null, only those states containing an operation with one of
       * the owners supplied here will be counted.
       */
      @UnsupportedAppUsage
      public int countUndos(UndoOwner[] owners) {
          if (owners == null) {
              return mUndos.size();
          }
  
          int count=0;
          int i=0;
          while ((i=findNextState(mUndos, owners, i)) >= 0) {
              count++;
              i++;
          }
          return count;
      }
  
      /**
       * Return the number of redo states on the undo stack.
       * @param owners If non-null, only those states containing an operation with one of
       * the owners supplied here will be counted.
       */
      @UnsupportedAppUsage
      public int countRedos(UndoOwner[] owners) {
          if (owners == null) {
              return mRedos.size();
          }
  
          int count=0;
          int i=0;
          while ((i=findNextState(mRedos, owners, i)) >= 0) {
              count++;
              i++;
          }
          return count;
      }
  
      /**
       * Return the user-visible label for the top undo state on the stack.
       * @param owners If non-null, will select the top-most undo state containing an
       * operation with one of the owners supplied here.
       */
      public CharSequence getUndoLabel(UndoOwner[] owners) {
          UndoState state = getTopUndo(owners);
          return state != null ? state.getLabel() : null;
      }
  
      /**
       * Return the user-visible label for the top redo state on the stack.
       * @param owners If non-null, will select the top-most undo state containing an
       * operation with one of the owners supplied here.
       */
      public CharSequence getRedoLabel(UndoOwner[] owners) {
          UndoState state = getTopRedo(owners);
          return state != null ? state.getLabel() : null;
      }
  
      /**
       * Start creating a new undo state.  Multiple calls to this function will nest until
       * they are all matched by a later call to {@link #endUpdate}.
       * @param label Optional user-visible label for this new undo state.
       */
      @UnsupportedAppUsage
      public void beginUpdate(CharSequence label) {
          if (mInUndo) {
              throw new IllegalStateException("Can't being update while performing undo/redo");
          }
          if (mUpdateCount <= 0) {
              createWorkingState();
              mMerged = false;
              mUpdateCount = 0;
          }
  
          mWorking.updateLabel(label);
          mUpdateCount++;
      }
  
      private void createWorkingState() {
          mWorking = new UndoState(this, mCommitId++);
          if (mCommitId < 0) {
              mCommitId = 1;
          }
      }
  
      /**
       * Returns true if currently inside of a {@link #beginUpdate}.
       */
      public boolean isInUpdate() {
          return mUpdateCount > 0;
      }
  
      /**
       * Forcibly set a new for the new undo state being built within a {@link #beginUpdate}.
       * Any existing label will be replaced with this one.
       */
      @UnsupportedAppUsage
      public void setUndoLabel(CharSequence label) {
          if (mWorking == null) {
              throw new IllegalStateException("Must be called during an update");
          }
          mWorking.setLabel(label);
      }
  
      /**
       * Set a new for the new undo state being built within a {@link #beginUpdate}, but
       * only if there is not a label currently set for it.
       */
      public void suggestUndoLabel(CharSequence label) {
          if (mWorking == null) {
              throw new IllegalStateException("Must be called during an update");
          }
          mWorking.updateLabel(label);
      }
  
      /**
       * Return the number of times {@link #beginUpdate} has been called without a matching
       * {@link #endUpdate} call.
       */
      public int getUpdateNestingLevel() {
          return mUpdateCount;
      }
  
      /**
       * Check whether there is an {@link UndoOperation} in the current {@link #beginUpdate}
       * undo state.
       * @param owner Optional owner of the operation to look for.  If null, will succeed
       * if there is any operation; if non-null, will only succeed if there is an operation
       * with the given owner.
       * @return Returns true if there is a matching operation in the current undo state.
       */
      public boolean hasOperation(UndoOwner owner) {
          if (mWorking == null) {
              throw new IllegalStateException("Must be called during an update");
          }
          return mWorking.hasOperation(owner);
      }
  
      /**
       * Return the most recent {@link UndoOperation} that was added to the update.
       * @param mergeMode May be either {@link #MERGE_MODE_NONE} or {@link #MERGE_MODE_ANY}.
       */
      public UndoOperation<?> getLastOperation(int mergeMode) {
          return getLastOperation(null, null, mergeMode);
      }
  
      /**
       * Return the most recent {@link UndoOperation} that was added to the update and
       * has the given owner.
       * @param owner Optional owner of last operation to retrieve.  If null, the last
       * operation regardless of owner will be retrieved; if non-null, the last operation
       * matching the given owner will be retrieved.
       * @param mergeMode May be either {@link #MERGE_MODE_NONE}, {@link #MERGE_MODE_UNIQUE},
       * or {@link #MERGE_MODE_ANY}.
       */
      public UndoOperation<?> getLastOperation(UndoOwner owner, int mergeMode) {
          return getLastOperation(null, owner, mergeMode);
      }
  
      /**
       * Return the most recent {@link UndoOperation} that was added to the update and
       * has the given owner.
       * @param clazz Optional class of the last operation to retrieve.  If null, the
       * last operation regardless of class will be retrieved; if non-null, the last
       * operation whose class is the same as the given class will be retrieved.
       * @param owner Optional owner of last operation to retrieve.  If null, the last
       * operation regardless of owner will be retrieved; if non-null, the last operation
       * matching the given owner will be retrieved.
       * @param mergeMode May be either {@link #MERGE_MODE_NONE}, {@link #MERGE_MODE_UNIQUE},
       * or {@link #MERGE_MODE_ANY}.
       */
      @UnsupportedAppUsage
      public <T extends UndoOperation> T getLastOperation(Class<T> clazz, UndoOwner owner,
              int mergeMode) {
          if (mWorking == null) {
              throw new IllegalStateException("Must be called during an update");
          }
          if (mergeMode != MERGE_MODE_NONE && !mMerged && !mWorking.hasData()) {
              UndoState state = getTopUndo(null);
              UndoOperation<?> last;
              if (state != null && (mergeMode == MERGE_MODE_ANY || !state.hasMultipleOwners())
                      && state.canMerge() && (last=state.getLastOperation(clazz, owner)) != null) {
                  if (last.allowMerge()) {
                      mWorking.destroy();
                      mWorking = state;
                      mUndos.remove(state);
                      mMerged = true;
                      return (T)last;
                  }
              }
          }
  
          return mWorking.getLastOperation(clazz, owner);
      }
  
      /**
       * Add a new UndoOperation to the current update.
       * @param op The new operation to add.
       * @param mergeMode May be either {@link #MERGE_MODE_NONE}, {@link #MERGE_MODE_UNIQUE},
       * or {@link #MERGE_MODE_ANY}.
       */
      @UnsupportedAppUsage
      public void addOperation(UndoOperation<?> op, int mergeMode) {
          if (mWorking == null) {
              throw new IllegalStateException("Must be called during an update");
          }
          UndoOwner owner = op.getOwner();
          if (owner.mManager != this) {
              throw new IllegalArgumentException(
                      "Given operation's owner is not in this undo manager.");
          }
          if (mergeMode != MERGE_MODE_NONE && !mMerged && !mWorking.hasData()) {
              UndoState state = getTopUndo(null);
              if (state != null && (mergeMode == MERGE_MODE_ANY || !state.hasMultipleOwners())
                      && state.canMerge() && state.hasOperation(op.getOwner())) {
                  mWorking.destroy();
                  mWorking = state;
                  mUndos.remove(state);
                  mMerged = true;
              }
          }
          mWorking.addOperation(op);
      }
  
      /**
       * Finish the creation of an undo state, matching a previous call to
       * {@link #beginUpdate}.
       */
      @UnsupportedAppUsage
      public void endUpdate() {
          if (mWorking == null) {
              throw new IllegalStateException("Must be called during an update");
          }
          mUpdateCount--;
  
          if (mUpdateCount == 0) {
              pushWorkingState();
          }
      }
  
      private void pushWorkingState() {
          int N = mUndos.size() + 1;
  
          if (mWorking.hasData()) {
              mUndos.add(mWorking);
              forgetRedos(null, -1);
              mWorking.commit();
              if (N >= 2) {
                  // The state before this one can no longer be merged, ever.
                  // The only way to get back to it is for the user to perform
                  // an undo.
                  mUndos.get(N-2).makeExecuted();
              }
          } else {
              mWorking.destroy();
          }
          mWorking = null;
  
          if (mHistorySize >= 0 && N > mHistorySize) {
              forgetUndos(null, N - mHistorySize);
          }
      }
  
      /**
       * Commit the last finished undo state.  This undo state can no longer be
       * modified with further {@link #MERGE_MODE_UNIQUE} or
       * {@link #MERGE_MODE_ANY} merge modes.  If called while inside of an update,
       * this will push any changes in the current update on to the undo stack
       * and result with a fresh undo state, behaving as if {@link #endUpdate()}
       * had been called enough to unwind the current update, then the last state
       * committed, and {@link #beginUpdate} called to restore the update nesting.
       * @param owner The optional owner to determine whether to perform the commit.
       * If this is non-null, the commit will only execute if the current top undo
       * state contains an operation with the given owner.
       * @return Returns an integer identifier for the committed undo state, which
       * can later be used to try to uncommit the state to perform further edits on it.
       */
      @UnsupportedAppUsage
      public int commitState(UndoOwner owner) {
          if (mWorking != null && mWorking.hasData()) {
              if (owner == null || mWorking.hasOperation(owner)) {
                  mWorking.setCanMerge(false);
                  int commitId = mWorking.getCommitId();
                  pushWorkingState();
                  createWorkingState();
                  mMerged = true;
                  return commitId;
              }
          } else {
              UndoState state = getTopUndo(null);
              if (state != null && (owner == null || state.hasOperation(owner))) {
                  state.setCanMerge(false);
                  return state.getCommitId();
              }
          }
          return -1;
      }
  
      /**
       * Attempt to undo a previous call to {@link #commitState}.  This will work
       * if the undo state at the top of the stack has the given id, and has not been
       * involved in an undo operation.  Otherwise false is returned.
       * @param commitId The identifier for the state to be uncommitted, as returned
       * by {@link #commitState}.
       * @param owner Optional owner that must appear in the committed state.
       * @return Returns true if the uncommit is successful, else false.
       */
      public boolean uncommitState(int commitId, UndoOwner owner) {
          if (mWorking != null && mWorking.getCommitId() == commitId) {
              if (owner == null || mWorking.hasOperation(owner)) {
                  return mWorking.setCanMerge(true);
              }
          } else {
              UndoState state = getTopUndo(null);
              if (state != null && (owner == null || state.hasOperation(owner))) {
                  if (state.getCommitId() == commitId) {
                      return state.setCanMerge(true);
                  }
              }
          }
          return false;
      }
  
      UndoState getTopUndo(UndoOwner[] owners) {
          if (mUndos.size() <= 0) {
              return null;
          }
          int i = findPrevState(mUndos, owners, -1);
          return i >= 0 ? mUndos.get(i) : null;
      }
  
      UndoState getTopRedo(UndoOwner[] owners) {
          if (mRedos.size() <= 0) {
              return null;
          }
          int i = findPrevState(mRedos, owners, -1);
          return i >= 0 ? mRedos.get(i) : null;
      }
  
      boolean matchOwners(UndoState state, UndoOwner[] owners) {
          if (owners == null) {
              return true;
          }
          for (int i=0; i<owners.length; i++) {
              if (state.matchOwner(owners[i])) {
                  return true;
              }
          }
          return false;
      }
  
      int findPrevState(ArrayList<UndoState> states, UndoOwner[] owners, int from) {
          final int N = states.size();
  
          if (from == -1) {
              from = N-1;
          }
          if (from >= N) {
              return -1;
          }
          if (owners == null) {
              return from;
          }
  
          while (from >= 0) {
              UndoState state = states.get(from);
              if (matchOwners(state, owners)) {
                  return from;
              }
              from--;
          }
  
          return -1;
      }
  
      int findNextState(ArrayList<UndoState> states, UndoOwner[] owners, int from) {
          final int N = states.size();
  
          if (from < 0) {
              from = 0;
          }
          if (from >= N) {
              return -1;
          }
          if (owners == null) {
              return from;
          }
  
          while (from < N) {
              UndoState state = states.get(from);
              if (matchOwners(state, owners)) {
                  return from;
              }
              from++;
          }
  
          return -1;
      }
  
      final static class UndoState {
          private final UndoManager mManager;
          private final int mCommitId;
          private final ArrayList<UndoOperation<?>> mOperations = new ArrayList<UndoOperation<?>>();
          private ArrayList<UndoOperation<?>> mRecent;
          private CharSequence mLabel;
          private boolean mCanMerge = true;
          private boolean mExecuted;
  
          UndoState(UndoManager manager, int commitId) {
              mManager = manager;
              mCommitId = commitId;
          }
  
          UndoState(UndoManager manager, Parcel p, ClassLoader loader) {
              mManager = manager;
              mCommitId = p.readInt();
              mCanMerge = p.readInt() != 0;
              mExecuted = p.readInt() != 0;
              mLabel = TextUtils.CHAR_SEQUENCE_CREATOR.createFromParcel(p);
              final int N = p.readInt();
              for (int i=0; i<N; i++) {
                  UndoOwner owner = mManager.restoreOwner(p);
                  UndoOperation op = (UndoOperation)p.readParcelable(loader);
                  op.mOwner = owner;
                  mOperations.add(op);
              }
          }
  
          void writeToParcel(Parcel p) {
              if (mRecent != null) {
                  throw new IllegalStateException("Can't save state before committing");
              }
              p.writeInt(mCommitId);
              p.writeInt(mCanMerge ? 1 : 0);
              p.writeInt(mExecuted ? 1 : 0);
              TextUtils.writeToParcel(mLabel, p, 0);
              final int N = mOperations.size();
              p.writeInt(N);
              for (int i=0; i<N; i++) {
                  UndoOperation op = mOperations.get(i);
                  mManager.saveOwner(op.mOwner, p);
                  p.writeParcelable(op, 0);
              }
          }
  
          int getCommitId() {
              return mCommitId;
          }
  
          void setLabel(CharSequence label) {
              mLabel = label;
          }
  
          void updateLabel(CharSequence label) {
              if (mLabel != null) {
                  mLabel = label;
              }
          }
  
          CharSequence getLabel() {
              return mLabel;
          }
  
          boolean setCanMerge(boolean state) {
              // Don't allow re-enabling of merging if state has been executed.
              if (state && mExecuted) {
                  return false;
              }
              mCanMerge = state;
              return true;
          }
  
          void makeExecuted() {
              mExecuted = true;
          }
  
          boolean canMerge() {
              return mCanMerge && !mExecuted;
          }
  
          int countOperations() {
              return mOperations.size();
          }
  
          boolean hasOperation(UndoOwner owner) {
              final int N = mOperations.size();
              if (owner == null) {
                  return N != 0;
              }
              for (int i=0; i<N; i++) {
                  if (mOperations.get(i).getOwner() == owner) {
                      return true;
                  }
              }
              return false;
          }
  
          boolean hasMultipleOwners() {
              final int N = mOperations.size();
              if (N <= 1) {
                  return false;
              }
              UndoOwner owner = mOperations.get(0).getOwner();
              for (int i=1; i<N; i++) {
                  if (mOperations.get(i).getOwner() != owner) {
                      return true;
                  }
              }
              return false;
          }
  
          void addOperation(UndoOperation<?> op) {
              if (mOperations.contains(op)) {
                  throw new IllegalStateException("Already holds " + op);
              }
              mOperations.add(op);
              if (mRecent == null) {
                  mRecent = new ArrayList<UndoOperation<?>>();
                  mRecent.add(op);
              }
              op.mOwner.mOpCount++;
          }
  
          <T extends UndoOperation> T getLastOperation(Class<T> clazz, UndoOwner owner) {
              final int N = mOperations.size();
              if (clazz == null && owner == null) {
                  return N > 0 ? (T)mOperations.get(N-1) : null;
              }
              // First look for the top-most operation with the same owner.
              for (int i=N-1; i>=0; i--) {
                  UndoOperation<?> op = mOperations.get(i);
                  if (owner != null && op.getOwner() != owner) {
                      continue;
                  }
                  // Return this operation if it has the same class that the caller wants.
                  // Note that we don't search deeper for the class, because we don't want
                  // to end up with a different order of operations for the same owner.
                  if (clazz != null && op.getClass() != clazz) {
                      return null;
                  }
                  return (T)op;
              }
  
              return null;
          }
  
          boolean matchOwner(UndoOwner owner) {
              for (int i=mOperations.size()-1; i>=0; i--) {
                  if (mOperations.get(i).matchOwner(owner)) {
                      return true;
                  }
              }
              return false;
          }
  
          boolean hasData() {
              for (int i=mOperations.size()-1; i>=0; i--) {
                  if (mOperations.get(i).hasData()) {
                      return true;
                  }
              }
              return false;
          }
  
          void commit() {
              final int N = mRecent != null ? mRecent.size() : 0;
              for (int i=0; i<N; i++) {
                  mRecent.get(i).commit();
              }
              mRecent = null;
          }
  
          void undo() {
              for (int i=mOperations.size()-1; i>=0; i--) {
                  mOperations.get(i).undo();
              }
          }
  
          void redo() {
              final int N = mOperations.size();
              for (int i=0; i<N; i++) {
                  mOperations.get(i).redo();
              }
          }
  
          void destroy() {
              for (int i=mOperations.size()-1; i>=0; i--) {
                  UndoOwner owner = mOperations.get(i).mOwner;
                  owner.mOpCount--;
                  if (owner.mOpCount <= 0) {
                      if (owner.mOpCount < 0) {
                          throw new IllegalStateException("Underflow of op count on owner " + owner
                                  + " in op " + mOperations.get(i));
                      }
                      mManager.removeOwner(owner);
                  }
              }
          }
      }
  }
  