add elements to indexed list locations

[Peter Otten]

levent wrote:

> Thanks for the answers. Enumerating in reverse is indeed quite a smart
> idea.
> 
> The fact is though, I overly simplified the task in the super-hero
> example. In the real case, the dictionary keys are not necessarily the
> indices for inserts; that is to say, the inserts do not necessarily
> take place in some sorted order.
> 
> I think I was thinking more of a linked-list idea, where you do not
> store the indices as integers to some random access array but rather as
> pointers into list's nodes. Then the subsequent inserts would not hurt
> previously stored pointers. For those who know a bit C++/STL here is a
> sketch of the idea:
> 
> name_list  heros;
> heros.push_back("clark");
> // ... add the rest
> indexed_name_list surnames;
> surnames.push_back(
>    make_pair(   find( heros.begin(), heros.end(), "clark"), "kent")   )
>    );  // the find function returns an iterator to appropriate location
> // ... add the rest
> 
> for_each(surnames.begin(), surnames.end(), insert_surnames)
> // insert_surnames is a callback that receives a single indexed surname
> // at a time and does the job, without affecting outer iterators.
> 
> 
> I was wondering how to make indices as *robust* in Python... Any ideas?

Python's list is technically a vector. You can therefore either search for
the insertion point in a timely fashion:

heros = ["super", "clark", "spider", "peter", "bat", "bruce"]
names = [("clark", "kent"), ("peter", "parker"), ("bruce", "wayne")]

for first, last in names:
    heros.insert(heros.index(first)+1, last)
print heros

or you have to snatch a real (linked) list from somewhere. Here's an ad-hoc
implementation:

class Node(object):
    def __init__(self, value, next=None):
        self.value = value
        self.right = next
    def __str__(self):
        return "List(%s)" % ", ".join(repr(n.value) for n in self)
    def __iter__(self):
        item = self
        while item:
            yield item
            item = item.right
    def find(self, value):
        for item in self:
            if item.value == value:
                return item
        raise ValueError("%r not found" % (value,))
    def insert_after(self, value):
        self.right = Node(value, self.right)
    @staticmethod
    def from_list(items):
        items = iter(items)
        try:
            first = items.next()
        except StopIteration:
            raise ValueError("empty lists not supported")
        cur = head = Node(first)
        for value in items:
            node = Node(value)
            cur.right = node
            cur = node
        return head

if __name__ == "__main__":
    heros = ["super", "clark", "spider", "peter", "bat", "bruce"]
    heros = Node.from_list(heros)
    names = [("clark", "kent"), ("peter", "parker"), ("bruce", "wayne")]
    surnames = [(heros.find(f), s) for f, s in names]
    print heros
    for node, value in surnames:
        node.insert_after(value)
    print heros

Peter