A dynamic list that automatically expands

Question

How can I make Python pdtolist equivalent from Pop-11?

Suppose I have a generator named g that returns (say) integers one at a time. I would like to build a list a that grows automatically as I request values ​​outside the current end of the list. For instance:

print a # => [ 0, 1, 2, g] print a[0] # => 0 print a[1] # => 1 print a[2] # => 2 # (obvious enough up to here) print a[6] # => 6 print a # => [ 0, 1, 2, 3, 4, 5, 6, g] # list has automatically expanded a = a[4:] # discard some previous values print a # => [ 4, 5, 6, g] print a[0] # => 4 

The terminology is to anticipate a possible misunderstanding: a list is a "dynamic array", but this is not what I mean; I would like a "dynamic list" in a more abstract sense.

To better explain motivation, suppose you have 999999999 elements to process. Trying to collect all this into memory (in a regular list) will immediately become a problem. The generator solves this part of the problem by presenting them one at a time; each of which is created on demand or read separately from the disk. But suppose during processing you want to refer to some recent values, not just the current? You could recall the last (say) ten values ​​in a separate list. But a dynamic list is better because it remembers them automatically.

Answer 1

Many thanks to everyone who contributed ideas! Here is what I gathered from all the answers. This retains a lot of functionality from the regular list class, adding extra behavior when necessary to meet additional requirements.

 class DynamicList(list): def __init__(self, gen): self.gen = gen def __getitem__(self, index): while index >= len(self): self.append(next(self.gen)) return super(DynamicList, self).__getitem__(index) def __getslice__(self, start, stop): # treat request for "last" item as "most recently fetched" if stop == 2147483647: stop = len(self) while stop > len(self): self.append(next(self.gen)) return super(DynamicList, self).__getslice__(start, stop) def __iter__(self): return self def next(self): n = next(self.gen) self.append(n) return n a = DynamicList(iter(xrange(10))) 

Previously created values ​​can be obtained individually as elements or slices. The recorded history is expanded as necessary if the requested item is outside the current end of the list. You can access the entire recorded history at a time using print a or assigned to a regular list using b = a[:] . A slice of recorded history can be deleted with del a[0:4] . You can iterate over the entire list using for , deleting along the way or when it suits. If you reach the end of the generated values, StopIteration will be raised.

Some awkwardness remains. Assignments such as a = a[0:4] successfully truncate the history, but the resulting list is no longer auto-expanded. Instead, use del a[0:4] to maintain automatic growth properties. In addition, I am not entirely satisfied with the recognition of the magic value 2147483647 , representing the very last element.

Answer 2

This may help you:

 class DynamicList(list): def __init__(self, gen): self._gen = gen def __getitem__(self, index): while index >= len(self): self.append(next(self._gen)) return super(DynamicList, self).__getitem__(index) 

You will need to add special handling for slices (currently they just return a regular list, so you lose dynamic behavior). Also, if you want the generator itself to be a list item, this will add a bit of complexity.

Answer 3

Just answered another similar question and decided to update your answer for you?

 class dynamic_list(list): def __init__(self,num_gen): self._num_gen = num_gen def __getitem__(self,index): if isinstance(index, int): self.expandfor(index) return super(dynamic_list,self).__getitem__(index) elif isinstance(index, slice): if index.stop<index.start: return super(dynamic_list,self).__getitem__(index) else: self.expandfor(index.stop if abs(index.stop)>abs(index.start) else index.start) return super(dynamic_list,self).__getitem__(index) def __setitem__(self,index,value): if isinstance(index, int): self.expandfor(index) return super(dynamic_list,self).__setitem__(index,value) elif isinstance(index, slice): if index.stop<index.start: return super(dynamic_list,self).__setitem__(index,value) else: self.expandfor(index.stop if abs(index.stop)>abs(index.start) else index.start) return super(dynamic_list,self).__setitem__(index,value) def expandfor(self,index): rng = [] if abs(index)>len(self)-1: if index<0: rng = xrange(abs(index)-len(self)) else: rng = xrange(abs(index)-len(self)+1) for i in rng: self.append(self._num_gen.next())