How to build an undo storage with limit?

Question

Dear All,

I want build a data structure to store limited undo buffer, take store 6 dict data for example with below pseudocode:

rawdict1 = {1}
buffer = [{1}]

rawdict1 = {2}
buffer = [{2}{1}]      # {1} stored on the postion

rawdict1 = {3}
buffer = [{3}{2}{1}]      
...
rawdict1 = {5}
buffer = [{5}{4}{3}{2}{1}]      # max length limited to 5

rawdict1 = {6}
buffer = [{6}{5}{4}{3}{2}]      # {1} has been deleted because exceed the limit

when I want to restore the rawdict1 later, I can use something looks like:

rawdict1 = buffer[5]                 # restore the 5th dict.

My question is, can existing buildin data type or standard library type can be used for such a purpose?

And is it possible such a structure can store multi-types in one structure instance, say, if I want to store dict and self-defined class in one go?

Thanks!

Rgs,

KC

Answer 1

Rockford Lhotka's CSLA.NET framework contains an Undo architecture. Perhaps you could study it and figure out what he did, or even use it out of the box.

Answer 2

Perhaps use something like this:

import collections

class UndoBuffer(object):
    def __init__(self,value,max_length=5):
        self.max_length=max_length
        self._buffer=collections.deque([value],max_length)
    @property
    def data(self):
        return self._buffer[-1]
    @data.setter
    def data(self,value):
        self._buffer.append(value)
    def restore(self,index):
        self.data=self._buffer[index]

Make an UndoBuffer object

rawdict=UndoBuffer('{1}')      

Setting the data attribute automatically stores the value in _buffer:

print(rawdict._buffer)
# deque(['{1}'], maxlen=5)
print(rawdict.data)
# {1}

Changing the value of rawdict.data appends the value to rawdict._buffer:

rawdict.data = '{2}'
print(rawdict._buffer)
# deque(['{1}', '{2}'], maxlen=5)

Buf if you access rawdict.data you just get the most recent value:

print(rawdict.data)
# {2}

Change the value a few more times. '{1}' gets dropped when the buffer is filled to its maximum length:

rawdict.data = '{3}'
rawdict.data = '{4}'
rawdict.data = '{5}'
print(rawdict._buffer)
# deque(['{1}', '{2}', '{3}', '{4}', '{5}'], maxlen=5)
rawdict.data = '{6}'
print(rawdict._buffer)
# deque(['{2}', '{3}', '{4}', '{5}', '{6}'], maxlen=5)

Restoring the value from rawdict._buffer:

rawdict.restore(0)   # set rawdict.data to rawdict._buffer[0]
print(rawdict.data)
# {2}
print(rawdict._buffer)
# deque(['{3}', '{4}', '{5}', '{6}', '{2}'], maxlen=5)

Answer 3

You cannot do it on a barename (such as rawdict1) because there is no way for you to intercept assignments to a barename and make them do sometime "on the side" such as saving the previous value. It's easy to do on a decorated name, e.g.:

undoable.rawdict1 = {1}

and the like, by making undoable an instance of a class with an appropriate __setitem__ which appends the previous value (if any) to a list, and pops the 0th item if the list is getting too long. But that would not suffice for other "undoable" actions besides assignment, such as undoable.rawdict1.update(whatever) -- you sure you don't need that?

Answer 4

You can quickly subclass the list to only allow limited storage.

class LimitedStack(list):
 def __init__(self,limit=6):
    list.__init__(self)
    self.limit = limit

 def append(self,obj):
    if len(self) == self.limit:
        list.pop(self,0)
    list.append(self,obj)

Python lists do not have to be of a certain type like the generic lists in C#. They will store any object you append to them.

Answer 5

The collections module, as of python 2.6, contains the "deque" collection. It behaves as you need:

>>> import collections
>>> buffer = collections.deque([],6)
>>> buffer.extend(range(6))
>>> buffer
deque([0, 1, 2, 3, 4, 5], maxlen=6)
>>> buffer.append(6)
>>> buffer
deque([1, 2, 3, 4, 5, 6], maxlen=6)
>>> buffer[-1]
6