android best way to implement undo/redo on ArrayList

Question

sorry about the general nature of this question but i don't want to start with any assumptions for fear of missing the big picture

i have a document editing kind of app (music notation) and want to implement undo and redo. all the relevant data is held in this

static  ArrayList <TTEvt> mEvList;

in my windows/MFC app, i just serialize the data structure and put it on a stack. it uses lots of memory but easy and foolproof.

so i was wondering what's the bast way to save and restore my ArrayList in android?

thanks

Answer 1

so here is the working multilevel undo/redo code. it works fine but it is sloooow. i took the gzip out which helps a bit but it basically makes my UI unusable. but at least it works, i can try optimize from here.

    static LinkedList<byte[]> undoStack = new LinkedList<byte[]>();
    static LinkedList<byte[]> redoStack = new LinkedList<byte[]>();

    public static void addUndoCheckpoint() {

        long start = System.currentTimeMillis();

        byte[] byteBuf = null;
        try {
            ByteArrayOutputStream baos = new ByteArrayOutputStream();
            // GZIPOutputStream gzipOut = new GZIPOutputStream(baos);
            ObjectOutputStream objectOut = new ObjectOutputStream(baos);
            for (TTEvt ev : Doc.mEvList)
                objectOut.writeObject(ev);
            objectOut.close();
            byteBuf = baos.toByteArray();
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }

        undoStack.push(byteBuf);

        if (undoStack.size() > 10)
            undoStack.removeLast(); // limit size

        redoStack.clear();

        long end = System.currentTimeMillis();
        Log.d("MainView", "addUndoCheckpoint time=" + (end - start) + "mS");
    }

    public static void doUndo() {

        if (undoStack.size() == 0)
            return;

        // push current state onto redo stack first
        byte[] byteBuf = null;
        try {
            ByteArrayOutputStream baos = new ByteArrayOutputStream();
            // GZIPOutputStream gzipOut = new GZIPOutputStream(baos);
            ObjectOutputStream objectOut = new ObjectOutputStream(baos);
            for (TTEvt ev : Doc.mEvList)
                objectOut.writeObject(ev);
            objectOut.close();
            byteBuf = baos.toByteArray();
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        redoStack.push(byteBuf); // push current state onto redo stack
        if (redoStack.size() > 10)
            redoStack.removeLast();

        // now undo
        mEvList.clear();
        byteBuf = undoStack.pop();

        ObjectInputStream objectIn = null;
        try {
            ByteArrayInputStream bais = new ByteArrayInputStream(byteBuf);
            // GZIPInputStream gzipIn;
            // gzipIn = new GZIPInputStream(bais);
            objectIn = new ObjectInputStream(bais);
            while (true) {
                TTEvt ev = (TTEvt) objectIn.readObject();
                if (ev == null)
                    break;
                Doc.mEvList.add(ev);
            }
            objectIn.close();
        } catch (IOException e) {
            // this is the normal exit
            if (objectIn != null) {
                try {
                    objectIn.close();
                } catch (IOException e1) {
                    // TODO Auto-generated catch block
                    e1.printStackTrace();
                }
            }
            // e.printStackTrace();
        } catch (ClassNotFoundException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }

        MainView.forceTotalRedraw();
    }

    public static void doRedo() {

        if (redoStack.size() == 0)
            return;

        // push current state onto undo stack first so we can undo the redo
        byte[] byteBuf = null;
        try {
            ByteArrayOutputStream baos = new ByteArrayOutputStream();
            // GZIPOutputStream gzipOut = new GZIPOutputStream(baos);
            ObjectOutputStream objectOut = new ObjectOutputStream(baos);
            for (TTEvt ev : Doc.mEvList)
                objectOut.writeObject(ev);
            objectOut.close();
            byteBuf = baos.toByteArray();
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        undoStack.push(byteBuf); // push current state onto redo stack
        if (undoStack.size() > 10)
            undoStack.removeLast();

        // now redo
        mEvList.clear();
        byteBuf = redoStack.pop();

        ObjectInputStream objectIn = null;
        try {
            ByteArrayInputStream bais = new ByteArrayInputStream(byteBuf);
            // GZIPInputStream gzipIn;
            // gzipIn = new GZIPInputStream(bais);
            objectIn = new ObjectInputStream(bais);
            while (true) {
                TTEvt ev = (TTEvt) objectIn.readObject();
                if (ev == null)
                    break;
                Doc.mEvList.add(ev);
            }
            objectIn.close();
        } catch (IOException e) {
            // this is the normal exit
            if (objectIn != null) {
                try {
                    objectIn.close();
                } catch (IOException e1) {
                    // TODO Auto-generated catch block
                    e1.printStackTrace();
                }
            }
            // e.printStackTrace();
        } catch (ClassNotFoundException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }

        MainView.forceTotalRedraw();

    }
}

note that your should call addUndoCheckpoint BEFORE you change ArrayList. i'm currently working on a version that you can call after you change ArrayList. this has the advantage that you can do addUndoCheckpoint in the background and not slow down the UI.

Answer 2

You can use Memento Design Pattern: here you have an example undo/redo with this pattern http://www.youtube.com/watch?v=jOnxYT8Iaoo&list=PLF206E906175C7E07&index=25

Answer 3

One way of dealing with this is not to remove items from the array but just to flag them as removed and refresh the view so they disappear. So Redo will just unflag them. On some operations the removed items then should be permanently removed from the array depending on the logic of the app.

Also one can have a separate Array where undo items are, for the array only keeps the references to the objects, so it would not take much memory and it can be limited size.

But if undo/redo needs to survive shutting down of the device, then saving values for each item to a file or database is the only option.

Answer 4

FYI, i have come up with a few options.

the simplest way is to write the ArrayList to a simple array of objects using toArray like this:

static TTEvt evArray[];

    public static void addUndoCheckpoint() {

        long start  = System.currentTimeMillis();

        evArray = Doc.mEvList.toArray(new TTEvt[Doc.mEvList.size()]);

        long end = System.currentTimeMillis();
        Log.d("MainView", "addUndoCheckpoint time="+(end-start)+"mS");
    }
    public static void doUndo() {

        Doc.mEvList.clear();
        for(TTEvt ev : evArray)
            Doc.mEvList.add(ev);

        forceTotalRedraw();
    }

UPDATE: i've just figured out the above code isn't really working because toArray does a new on an array of reference to objects only, NOT the objects them selves. so i would additional need to clone all the objects too which is obviously a lot of memory, and probably time. maybe the answer is the below, the slow option, using serialization but do it in an sync thread so its doesn't slow the UI down.

a more complicated way to go use gzip compression to save space like this

  static byte[] undoBuf;

  public static void addUndoCheckpoint() {

    long start  = System.currentTimeMillis();

    //evArray = Doc.mEvList.toArray(new TTEvt[Doc.mEvList.size()]);

    try {
        ByteArrayOutputStream baos = new ByteArrayOutputStream();
        GZIPOutputStream gzipOut = new GZIPOutputStream(baos);
        ObjectOutputStream objectOut = new ObjectOutputStream(gzipOut);
        for(TTEvt ev: Doc.mEvList)
            objectOut.writeObject(ev);
        objectOut.close();
        undoBuf = baos.toByteArray();
    } catch (IOException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    }

    long end = System.currentTimeMillis();
    Log.d("MainView", "addUndoCheckpoint time="+(end-start)+"mS");
  }

  public static void doUndo() {

    Doc.mEvList.clear();
    //for(TTEvt ev : evArray)
    //  Doc.mEvList.add(ev);

    try {
        ByteArrayInputStream bais = new ByteArrayInputStream(undoBuf);
        GZIPInputStream gzipIn;
        gzipIn = new GZIPInputStream(bais);
        ObjectInputStream objectIn = new ObjectInputStream(gzipIn);
        while(objectIn.available()>0) {
            TTEvt ev = (TTEvt) objectIn.readObject();
            Doc.mEvList.add(ev);
        }
        objectIn.close();
    } catch (IOException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    } catch (ClassNotFoundException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    }


    forceTotalRedraw();
}

the problem with this is its slow, almost 1 second for a data struct with about 5000 entries

this is only a 1 level undo at the moment, currently implementing a stack to keep multiple levels, and looking for a faster in memory compress