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

How big are the lists? Fairly short (a hundred) or fairly long (millions)? How big is a TTEvt? Do you control all the code that accesses this object, or do you need to keep it a TTEvt? — Dean J, Feb 07 '13 at 03:24
Possible duplicate: http://stackoverflow.com/questions/10070345/undo-changes-in-an-arraylist — Dean J, Feb 07 '13 at 03:28
i'm not sure i understand that post, the Runnable thing in particular. TTEvt is about 10 ints and i control it. my list is typically about 5000 elements long for a 3 minute song. i don't think saving each add and remove will work, too complex, better to save the whole thing — steveh, Feb 07 '13 at 03:52
i think basically i'm looking for a way to serialize and possibly compress ArrayList to memory. but like i said, i don't want to assume that is the best way in case there is something better. — steveh, Feb 07 '13 at 03:54

score 1 · Answer 1 · answered Feb 07 '13 at 07:48

1

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

answered Feb 07 '13 at 07:48

Michał Z.

4,119
1
22
32

score 0 · Answer 2 · answered Feb 07 '13 at 07:45

0

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.

answered Feb 07 '13 at 07:45

Lumis

21,517
8
63
67

objects can be added, removed or changed in the arraylist. trying to keep track of changes only would be very complicated. – steveh Feb 07 '13 at 09:00
I think in order to make it fast, I would create two additional arrays. One would keep the clones of last 20 objects (for example), while another would record the action type i.e. wheather it was added, removed or changed as well other functions that the app can do with references to the objects both current and cloned when required. So two histories: actions and objects. – Lumis Feb 07 '13 at 14:37

steveh · Answer 3 · 2013-02-07T08:58:08.393

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

steveh · Accepted Answer · 2013-02-07T12:05:21.230

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.

i did work out a speed optimization but its not a general thing so i don't need to show it here. basically, my data is divided into logical units, bars of music in my case. i can just save the only the bar i've changed in addUndoCheckpoint which is fast. so basically i divide the data into smaller units and only save/undo on those. — steveh, Feb 07 '13 at 11:08

android best way to implement undo/redo on ArrayList

4 Answers4