PoolObject
s can have attributes and properties assigned. Attributes are member variables stored with the object (flattened into the object storage). Properties are stored in property maps, external to the object.
Because they need to be flattened, attributes must be composed of primitive types and must always have the same size in memory. An example would be a double[3]
that stores a coordinate vector. In contrast, properties can have any type, for example a String
to store the name of an object.
Attributes can be assigned in the "constructor" (the init()
method) of a PoolObject
and therefore they can be effectively final. Properties are always initially unset and assigned after the PoolObject
has been constructed.
Properties, in contrast to attributes, can be used for non-PoolObjects
as well. The equivalent of an attribute for non-PoolObjects
is simply a member variable.
TODO: We want to make attributes and properties "feel" as similar as possible in terms of accessing values, recording changes for undo/redo, etc.
Ref
objects can have properties assigned via PropertyMap
s.
There is exactly one PropertyMaps
registry per RefPool
. The PropertyMaps
maintains a list of all existing feature maps for that pool and takes care of updating the maps when objects are deleted or added from/to the pool.
TODO: Not all
Pool
s should need to have this. For some pools, no property maps are required. There are even situations when a pool can have property maps but we want to avoid the cost of automatically updating when objects are deleted or added (because the pool is immutable or we handle add/remove independently).
Model graphs in TrackMate support undo/redo. The framework to do this is built into mastodon-collection and mastodon-graph. Because most graph objects are PoolObjects
this is non-trivial but can be done with a minimum of memory overhead.
For undo/redo to work, objects (edges and vertices) need to retain unique IDs. When an object is removed and then re-added by an undo
action, the re-added object must be identifiable by the unique ID of the removed object. For example, assume the following sequence of state transitions Si -> Sj:
- in S0
addVertex(v1)
-> S1 - in S1
addEdge(v1,v2)
-> S2
In state S2, two undo
actions are executed, leading back to S0. Now, redo
of addVertex(v1)
needs to make sure that v1
is a unique object that can be referred to by addEdge(v1,v2)
.
This requirement is realised by the class UndoIdBimap<O>
. It maps unique IDs ("undoId") to objects O
and vice versa. For convenience, UndoIdBimap.getId(O)
creates a new unique ID if the object does not have a unique ID yet.
UndoIdBimap
is implemented as a property map, meaning that entry (o,i)
is removed when o
is deleted. The undo framework must take care of establishing (o',i)
when o
is added back by undo/redo as o'
. This is done through UndoIdBimap.put(O,int)
.
A undo/redo stack is an expandable array of elements with a top
pointer.
This is not really a stack: top
might point to somewhere in the middle of the array, i.e., elements above the top may be retained. Basically, top
points to where the next action would be recorded, and/or where the next (previously recorded and undone) action for redo
is stored.
There are different implementations, e.g., for properties, graph operations, and undoable actions. The basic principle is always something like this:
interface UndoRedoStack<T> {
void record(T e);
T undo();
T redo();
}
record(e)
records a new element attop
, and then incrementstop
:
stack[top++] := e
undo()
decrementstop
, and then returns/handles the element there:
return stack[--top]
redo()
returns/handles the element attop
, and then incrementstop
:
return stack[top++]
UndoRedoStack
is an undo/redo stack that records for each edit
- the type of the edit, and
- whether the edit is an UndoPoint (see below).
UndoRedoStack
also maintains a list of all possible edit types.
Edit types are instances of some subclass of AbstractUndoableEditType
.
The constructor
public AbstractUndoableEditType( final UndoRedoStack undoRedoStack )
takes care of registering the instance with the UndoRedoStack
that it will be recorded on and assigns a unique int
id (unique to this UndoRedoStack
).
The record(...)
methods of subclasses are called when an edit of the respective type should be recorded, with arguments that identify the object that the edit is done to, additional data that should be recorded, etc.
Typically, edit types need to record other information besides of which type the edit was. For this purpose, other independent undo/redo stacks exist onto which information can be pushed. For example, a SetPropertyType
records changes to a specific property map. To do this,
- it needs to record the type of the edit (on the
UndoRedoStack
) which is done by callingAbstractUndoableEditType.recordType()
, - it needs to record the undo id of the object for which the property value is changed, which is done by recording the id on a
ByteArrayUndoRedoStack
(see below), - it needs to record the property value, which is done on a
PropertyUndoRedoStack
(see below).
When undoing such an edit, first the edit type is popped from the UndoRedoStack
and then undo()
is called on the SetPropertyType
(in this case). SetPropertyType.undo()
then knows which values to pop from which stacks to do its job.
As long as there are fewer than 128 edit types, an entry on the UndoRedoStack
is encoded into a single byte: the first bit stores the isUndoPoint
flag, the remaining bits store the id of the edit type.
Undo ids and attributes can be flattened into byte arrays of constant size (however the size can be different between edit type). Therefore, these are all store in continuous flat memory. ByteArrayUndoRedoStack
provides methods for pushing/popping segments of a byte[]
array.
Each edit type knows how much storage from this stack it needs and then pushes or pops a segment of appropriate length. The segment is accessed through ByteArrayUndoRedoStack.ByteArrayRef
, very similar to how a PoolObject
accesses its attribtutes.
In practice, all edit types share the same ByteArrayUndoRedoStack
, but this is not technically necessary.
A PropertyUndoRedoStack
is variation of the UndoRedoStack
interface.
It is used to record changes to a PropertyMap
.
interface PropertyUndoRedoStack<O> {
void record(O obj);
void undo(O obj);
void redo(O obj);
}
Here the method argument obj
is the object with which a property value is associated, not the property value itself. Also, undo
and redo
do not return elements but replace them directly into the provided obj
.
Elements on the UndoRedoStack
can be marked as being UndoPoints. Each high-level undo/redo step triggered by the user proceeds to undo/redo low-level elements until the next UndoPoint is reached.
UndoPoints mark "stable states" in the order elements were recorded. Therefore, undo
will stop immediately before undoing the UndoPoint, and redo
will stop after redoing the UndoPoint.