MOAL.data_structures package¶

Subpackages¶

Submodules¶

MOAL.data_structures.persistent module¶

class MOAL.data_structures.persistent.ConfluentlyPersistentFatNode[source]¶

Bases: MOAL.data_structures.persistent.ConfluentlyPersistentNode

From Wikipedia:

“Fat node method is to record all changes made to node fields in the nodes themselves, without erasing old values of the fields. This requires that we allow nodes to become arbitrarily ‘fat’.

Each extra field value has an associated field name and a version stamp which indicates the version in which the named field was changed to have the specified value.

Besides, each fat node has its own version stamp, indicating the version in which the node was created. In order to navigate through the structure, each original field value in a node has a version stamp of zero.”

__getitem__(key)[source]¶

__setitem__(key, data)[source]¶

class MOAL.data_structures.persistent.ConfluentlyPersistentNode[source]¶

Bases: MOAL.data_structures.persistent.FullyPersistentNode

From Wikipedia: “If there is also a meld or merge operation that can create a new version from two previous versions, the data structure is called confluently persistent.”

meld(key, versions=[])[source]¶

class MOAL.data_structures.persistent.ConfluentlyPersistentPathCopyingFatNode[source]¶

Bases: MOAL.data_structures.persistent.ConfluentlyPersistentFatNode, MOAL.data_structures.persistent.ConfluentlyPersistentPathCopyingNode

TODO

class MOAL.data_structures.persistent.ConfluentlyPersistentPathCopyingNode[source]¶

Bases: MOAL.data_structures.persistent.ConfluentlyPersistentNode

TODO

class MOAL.data_structures.persistent.FullyPersistentNode[source]¶

Bases: MOAL.data_structures.persistent.PartiallyPersistentNode

From Wikipedia: “The data structure is fully persistent if every version can be both accessed and modified.”

__getitem__(key)[source]¶

__setitem__(key, data)[source]¶

get_current()[source]¶

class MOAL.data_structures.persistent.MutableAccessException[source]¶

class MOAL.data_structures.persistent.PartiallyPersistentNode[source]¶

Bases: MOAL.data_structures.persistent.PersistentDataStructure

From Wikipedia:

“In computing, a persistent data structure is a data structure that always preserves the previous version of itself when it is modified. Such data structures are effectively immutable, as their operations do not (visibly) update the structure in-place, but instead always yield a new updated structure.

A data structure is partially persistent if all versions can be accessed but only the newest version can be modified.”

__delitem__(key)[source]¶

Deleting an item is not allowed, as the data structure should be immutable.

__init__()[source]¶

__setattr__(name, value)[source]¶

__setitem__(key, data)[source]¶

__str__()[source]¶

get_all()[source]¶

get_current()[source]¶

view_all()[source]¶

class MOAL.data_structures.persistent.PersistentDataStructure[source]¶

Bases: object

MOAL.data_structures.retroactive module¶

class MOAL.data_structures.retroactive.FullyRetroactiveNode[source]¶

Bases: MOAL.data_structures.retroactive.RetroactiveNode, MOAL.data_structures.persistent.ConfluentlyPersistentFatNode

_update_retroactive(key)¶

class MOAL.data_structures.retroactive.PartiallyRetroactiveNode[source]¶

Bases: MOAL.data_structures.retroactive.RetroactiveNode

From Wikipedia:

“In computer science a retroactive data structure is data structure which supports efficient modifications to a sequence of operations that have been performed on the structure. These modifications can take the form of retroactive insertion, deletion or updating an operation that was performed at some time in the past.”

The notion of temporal updates is probably intuitive, especially the idea of cascading changes, but what is probably confusing (at least was for me) is how this translates into something real.

For example, if one element changes, and the rest are also supposed to change as a result, what exactly should these other elements change to? It’s one thing to say “update node X[0]’s value with y”, but how does that translate for X[1], X[2], etc...? I think the point here is that it depends on your own personal use-case and context.

For example, if you are using something like git, and you need to update the references when something changes, you can implement your own method of temporal updates on the data structure.

Or, let’s say you are maintaining some numerical values that have special properties, you can go back and recalculate each one.

Or apply a hash function, or some other modifier for each element. Or just update the time-stamp.

Hopefully that makes sense!

_update_retroactive(key)[source]¶

class MOAL.data_structures.retroactive.RetroactiveNode[source]¶

Bases: MOAL.data_structures.persistent.FullyPersistentNode

Piggybacking on the existing classes from previous examples, we just use the Partial/Full persistent classes for each of these. The only difference is the addition of temporal updates across all nodes.

__setitem__(key, value)[source]¶

_handlenode(nodeval)[source]¶

Handle updating individual node values - throws in gibberish for each type, just for debugging/visualizing.