Create history of states in Java

Question

Hi All,

I need to save a history of states over a few actions in a Java application, which I can later reload in order to restore the state at a certain action. In other words I have a screen which has a state associated with it and I need to store it as well as any changes in a history so that I can restore the state of the screen at any time. This is kind of like 'undo' but not exactly as the difference between two state can be very large and there are no well-defined actions that changes the states.

Let me explain with an example: A very basic screen state might just contain a single Map. In state A this Map contains a reference to "Object1" with key "Key1" and "Object2" with key "Key2". In state B the Map still contains the reference to "Object1", but "Object2" has been modified and an "Object3" has been added. I now need to be able to return to state A, which would involve "dropping" Object3 and restoring Object2 to its previous state. I cannot define any custom "undo actions" as I do not know what changes were made to Object2 or even what the type of Object2 is. Further, because the reference remains the same for Object2 in state A and B, those changes are reflected in state A so Object2 isn't the same as it was.

I realize the best solution is to implement clone methods, but as I need to support all types of Objects (including primitives and standard collections) this isn't feasible. I thought about using serializable, where I would serialize the Map as soon as a state transition happens and then deserialize it when it is needed again, but it seems like a very ugly solution.

Does anybody have any other ideas? Thank you, Ristretto

Answer 1

We do something similar to this with serialization.

We store archived data to the file system in serialized form. The part of the object graph we need to restore is serialized as well as the main object.

Make sure that you version your objects and make sure that your differencing can cope with missing/new fields.

We chose to store to the filesystem because it gives us (effectively) unlimited capacity. The speed isn't an issue for us but the file system method is surprisingly quick, most people don't notice the extra 50-100ms!

Answer 2

You could always use serialization;

ByteArrayOutputStream byteArrayOutputStream = new ByteArrayOutputStream();
ObjectOutputStream objectOutputStream = new ObjectOutputStream(byteArrayOutputStream);
objectOutputStream.writeObject(object);
objectOutputStream.flush();
byteArrayOutputStream.close();
ByteArrayInputStream istream = new ByteArrayInputStream(byteArrayOutputStream.toByteArray());
ObjectInputStream objectInputStream= new ObjectInputStream(istream);
Object deserialized = objectInputStream.readObject();
istream.close();

Slow and clunky, but works.

Answer 3

Have you tried looking into the Memento Design Pattern? It seems particularly well defined for your problem. From Wikipedia:

The memento pattern is a software design pattern that provides the ability to restore an object to its previous state (undo via rollback).

The same page also has a section with a Java implementation since you mentioned this is in Java.

Answer 4

You might want to check out Prevayler

Answer 5

If what you want is in fact a map, you may want to look into persistent data structures; for instance, persistent B trees.

Answer 6

Consider a change of perspective. Instead of mutating the objects that make up the state of the screen, use an immutable state. This might sound like a contradiction in terms, but it's not.

For example, say (for simplicity's sake) that your state consists of a single String. Obviously, since Strings are immutable, you will not have to clone the String in order to save and modify the state. For example:

public List<String> changeTheScreen(List<String> states) {
  return states.cons(states.head() + "x");
}

public void renderTheScreen(String currentState) {
  // TODO: draw the screen given the current state
}

In the above example, List is fj.data.List, an immutable in-memory singly-linked list type from the Functional Java library (the standard libraries don't have an immutable list). The method would take the history of states, with the current state at the front of the list. It manipulates the state of the screen by creating a new state and putting it at the front of a new list of states.

Apply this same principle to any type you want to use as state. Make sure that your state is composed entirely out of immutable objects (Strings and primitives are already immutable). Using immutable objects for state will save you a lot of maintenance headaches down the road, as well as conserve memory, since immutable things can be reused without having to be cloned.

An immutable object will be initialized in its constructor and all of its inner fields will be final.

Functional Java has an immutable map called TreeMap. You would use it in the following manner:

public List<TreeMap<String, Object>>
changeState(List<TreeMap<String, Object>> states) {
  return states.cons(states.head().set("Key1", new Object1("x")));
}

Answer 7

In my project, we achieved something very similar by serializing to XML files. That worked nice for us. All the objects that you want to get back - serialize in a XML file in a well-defined manner so that anytime afterwards you can get back the state from the XML file.