Skip to main content
RSS feed Subscribe to feed

 

Undoable Keyed Collections

Undoable Keyed Collections combine features from lists and a dictionarys. The elements are primarily ordered as a list, but may also be indexed by a property of the elements.

Overview

The framework provides one class for undoable sets:

TKey
The key has to be an undoable property held by the nodes in the collection.
TNode
The type of the nodes in the collection.

The undoable keyed collection data structure is implemented by two balanced binary search trees. The first is ordered by list position, the other by specified property. Indexing, adding, removing, looking up or checking for containment takes logarithmic time.

When the property of a node that is stored in an undoable keyed collection is changed the second search tree structure is automatically updated so that the element can be found quickly. This takes logarithmic time.

Data table columns can profit from being stored in an undoable keyed collection: First each column is assigned a position in the list based on the order of import from the data source. Then a column can be located based on a property, like its name.

Implementation Pattern

Refer to Undoable Lists.