9

I need a list-like object that will "autogrow" whenever a slot number greater or equal to its length is accessed, filling up all the newly created slots with some pre-specified default value. E.g.:

# hypothetical DefaultList class
x = DefaultList(list('abc'), default='*')
x[6] = 'g'
print x[2], x[4], x[6], x[8]  # should print 'c * g *'

Thanks!

PS. I know it is not hard to implement a class like this, but I avoid wheel-reinvention as much as possible, especially if a particularly efficient/well-designed wheel already exists.

PS2. A dict (or a collections.defaultdict) is not an acceptable implementation of the desired data structure. For why, see here: http://groups.google.com/group/comp.lang.python/msg/bcf360dfe8e868d1?hl=en

4
  • so if someone makes a new collection, places something in slot 1 then in slot 1,000,000 you end up with 999,998 useless objects taking up memory? sounds like a bad idea to me.
    – Scott M.
    Feb 28, 2011 at 19:18
  • 1
    maybe it would suffice, if you keep your added items in dict, and to keep the default value - members not changed won't have to be kept in memory at all.
    – ajuc
    Feb 28, 2011 at 19:23
  • correct me if I am wrong, but given your link isn't your issue more with the interface of collections.defaultdict rather then using one as an implementation? Feb 28, 2011 at 19:56
  • I don't see an argument against using dicts as the backend in the link -- as long as the interface is list() compatible, why does it matter? Sep 9, 2011 at 21:32

5 Answers 5

3
class DefaultList(list):
    def __init__(self,*args,**kwargs):
        list.__init__(self,*args)
        self.default=kwargs.get('default',None)
    def __getitem__(self,key):
        # retrieving an item does not expand the list
        if isinstance(key,slice):
            return [self[elt] for elt in range(key.start,key.stop,key.step)]
        else:
            try:
                return list.__getitem__(self,key)
            except IndexError:
                return self.default
    def __setitem__(self,key,value):
        # setting an item may expand the list
        try:
            list.__setitem__(self,key,value)
        except IndexError:
            self.extend([self.default]*(key-len(self)))
            self.append(value)

x = DefaultList(list('abc'), default='*')
print(x)
# ['a', 'b', 'c']
x[6] = 'g'
print(x)
# ['a', 'b', 'c', '*', '*', '*', 'g']
print x[2], x[4], x[6], x[8]  # should print 'c * g *'
# c * g *
print(x[2:9:2])
# ['c', '*', 'g', '*']
14
  • 1
    This is reasonable; a couple notes. You should use super rather than addressing the parent class directly. None is probably a more sensible fillvalue default than '*'. You should pass kwargs to list.__init__, so keyword arguments work, eg. DefaultList(sequence=[1,2,3]). Feb 28, 2011 at 20:15
  • @Glenn Maynard: I think using super here would actually lead to a subtle pitfall. Since DefaultList's __init__ signature is different than list's __init__, I can't use super. super(DefaultList,self).__init__(*args,**kwargs) would raise a TypeError since list.__init__ expects at most 1 argument. I like the idea of using None as the default.
    – unutbu
    Feb 28, 2011 at 20:29
  • (That's not related to super.) You want to make a copy of kwargs (kwargs=dict(kwargs)), and remove "default" if it exists after pulling the value out. This way it's as transparent as possible with arguments, so things don't go wrong if this class is used with more complex inheritance. (It's simpler to just make default a regular keyword argument, but that can only be done correctly in Python3 which supports keyword-only arguments via PEP 3102.) Feb 28, 2011 at 21:13
  • @Glenn Maynard: In a more complex inheritance scheme, if another class expects the default keyword, removing it in DefaultList would be wrong. Since we don't know what class's __init__ is going to be called by super(DefaultList,self).__init__, the only safe option is to demand all __init__ signatures match exactly. So the only safe option is to either (have a default keyword and use list.__init__) or (remove the default keyword and use super if you so choose).
    – unutbu
    Feb 28, 2011 at 21:44
  • If you're inheriting from two classes that both have their own default keyword to __init__, all is lost; it's not going to work. Your code will always break if another inherited class needs kwargs. The correct thing to do is to take the parameters specific to your function and remove them from kwargs, and pass the rest on. (I don't know why you keep saying super; super.__init__(...) and list.__init__(self, ...) in your code are equivalent, except the former will behave in complex MI scenarios where the latter will break.) Feb 28, 2011 at 22:00
1

I would use a sparse data structure (1xn matrix).

3
1

You could always make a function that handles this:

def fillList(item, slot, myList):
    length = len(myList)
    if slot > length:
        augmentation = [item for x in range(slot-length)]
        myList.extend(augmentation)
    else:
        myList[slot] = item

Which while not a data structure, does accomplish what you want.

0

Using the idea of wheaties's solution and making a prettier interface:

You could inherit from list and overwrite the list 'getitem(index)' method which maps to [index] in your class. It should be something like this:

class GrowingList(list):
    def __getitem__(self, index):
        length = len(self)
        # list is 0 indexed 
        if index >= length:
            tail = [ self.default_value for x in range(index - length + 1)]
            self.extend(tail)


        return super(self.__class__, self).__getitem__(index)

This same code can be used if you don't extend the list, but just return some default value on invalid index

This preserves the whole list interface.

1
  • Not sure if it is any more efficient, but your list comprehension could be rewritten as tail = [self.default_value] * (index-length+1). Feb 28, 2011 at 20:07
0

(This isn't a new answer; just a comment on unutbu's. It should really be possible to post stuff like this in comments; it isn't, so I have to post it as an answer.)

CombineListClasses and CombineListClasses2 inherit from two classes that both inherit from list. The behavior and doctests are straightforward, but break badly in the original version.

This is all standard practice in Python's data model; you almost never should be calling a base class method directly rather than via super.

class DefaultList(list):
    """
    >>> x = DefaultList('abc', default='*')
    >>> x
    ['a', 'b', 'c']
    >>> x[6] = 'g'
    >>> x
    ['a', 'b', 'c', '*', '*', '*', 'g']
    >>> x[2], x[4], x[6], x[8]  # should print 'c * g *'
    ('c', '*', 'g', '*')
    >>> x[2:9:2]
    ['c', '*', 'g', '*']

    >>> x = DefaultList()
    >>> x[1] = 'a'
    >>> x
    [None, 'a']

    >>> x = DefaultList(sequence=[1,2,3], default=5)
    >>> x
    [1, 2, 3]
    >>> x[10]
    5
    """
    def __init__(self, *args, **kwargs):
        if 'default' in kwargs:
            self.default = kwargs['default']
            del kwargs['default']
        else:
            self.default = None
        super(DefaultList, self).__init__(*args, **kwargs)

    def __getitem__(self, key):
        # retrieving an item does not expand the list
        if isinstance(key, slice):
            return [self[elt] for elt in range(key.start, key.stop, key.step)]
        else:
            try:
                return super(DefaultList, self).__getitem__(key)
            except IndexError:
                return self.default

    def __setitem__(self, key, value):
        # setting an item may expand the list
        try:
            super(DefaultList, self).__setitem__(key, value)
        except IndexError:
            self.extend([self.default]*(key-len(self)))
            self.append(value)

# Another class that derives from list:
class AddMethodToList(list):
    def __init__(self, *args, **kwargs):
        self.value = kwargs['value']
        del kwargs['value']
        super(AddMethodToList, self).__init__(*args, **kwargs)

    def new_method(self):
        return self.value

# Derive from both classes.
class CombineListClasses(AddMethodToList, DefaultList):
    """
    >>> a = CombineListClasses(default=10, sequence=[1,2,3], value=3)
    >>> a.new_method()
    3
    >>> a[5] = 1
    >>> a
    [1, 2, 3, 10, 10, 1]
    """
    pass

# Derive from both classes in reverse, reversing the call chain order.
class CombineListClasses2(DefaultList, AddMethodToList):
    """
    >>> a = CombineListClasses2(default=10, sequence=[1,2,3], value=3)
    >>> a.new_method()
    3
    >>> a[5] = 1
    >>> a
    [1, 2, 3, 10, 10, 1]
    """
    pass

if __name__ == '__main__':
    import doctest
    print doctest.testmod()

Note that in Python 3, this is supported by the language directly:

class DefaultList(list):
    def __init__(self, *args, default=None, **kwargs):
        self.default = default
        super(self).__init__(*args, **kwargs)

but that's not supported in Python 2. http://www.python.org/dev/peps/pep-3102

2
  • This post is old enough I may not get an answer here, but is there any reason not to approach default handling like so: self.default = kwargs.pop('default', None)? I believe that accomplishes the same as your conditional statement with 4 fewer lines of code, but I'm interested more in the proper practice than line count. If there's a reason not to use .pop(<idx>, <dflt>) I'd be interested in knowing.
    – g.d.d.c
    May 11, 2011 at 22:14
  • @g.d.d.c. Using kwargs.pop(keyword, None) is fine, and is the more pythonic solution Sep 9, 2011 at 20:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.