Mailing List Archive

Python list insert iterators
Hi Python community,

I have a got an example list like

1, 2, 3, 4, 5, 6, 7, 8, 9, 10
T T

and i eventually want to insert items in the given locations
(A shall go between 2 and 3, B shall go between 6 and 7)

Right now i just use index numbers to define the place:

A shall insert in position 2
B shall insert in position 6

However when i insert A in position 2, the index for successful insertion
of B gets wrong
(should now be 7 instead of 6)

No, it's not an option to sort the indexes and start inserting from the
back.
The most elegant option is not to store indexes, but list iterators, which
attach to the list element
and would automatically move, especially if an element is inserted before.

I could not find such functionality in python lists of [ 1,2,3 ]

Does python have such functionality ?
if yes, where can i find it ?
--
https://mail.python.org/mailman/listinfo/python-list
Re: Python list insert iterators [ In reply to ]
On 3/3/2023 3:22 AM, Guenther Sohler wrote:
> Hi Python community,
>
> I have a got an example list like
>
> 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
> T T
>
> and i eventually want to insert items in the given locations
> (A shall go between 2 and 3, B shall go between 6 and 7)
>
> Right now i just use index numbers to define the place:
>
> A shall insert in position 2
> B shall insert in position 6
>
> However when i insert A in position 2, the index for successful insertion
> of B gets wrong
> (should now be 7 instead of 6)
>
> No, it's not an option to sort the indexes and start inserting from the
> back.
> The most elegant option is not to store indexes, but list iterators, which
> attach to the list element
> and would automatically move, especially if an element is inserted before.
>
> I could not find such functionality in python lists of [ 1,2,3 ]
>
> Does python have such functionality ?
> if yes, where can i find it ?

You should be more clear about how to establish the desired insertion
point. In your example, you first say that the insertion of B should be
between 6 and 7. But after A gets inserted, you say that B's insertion
point should change. How is anyone able to know what the correct
insertion point should be at any time?

If the rule is that B should get inserted after a particular known
element, you can find out the index of that element with list.index()
and insert just after that. If the rule is "There is an imaginary
location that starts out after index 6 but moves depending on previous
insertions", then you will probably need to capture a record of those
insertions and use it to adjust the invisible insertion point. But this
synchronization could be tricky to keep correct depending on what you
want to do to this list.

So you need to specify clearly what the rules are going to be.
--
https://mail.python.org/mailman/listinfo/python-list
RE: Python list insert iterators [ In reply to ]
Thomas is correct that this is a bit of an odd request unless explained
better.

There are a number of implicit assumptions that need to be revisited here.
Python Lists are what they are. They are not in any way tagged. They are not
linked lists or binary trees or dictionaries or whatever you are looking
for.

They are a mutable object with an order at any given time and no memory or
history of an earlier status.

They support not just insertion but also deletion and replacement and other
things.

But generally, if your time span between deciding on additions and
implementing them will contain no deletions, then one simple solution is to
re-order your insertion to always do the last one first. The indices will
only change at and above an insertion point. Your remaining insertions will
always be at an untouched region where the indices remain the same, for now.

A second choice as Thomas points out is to adjust your indices. An example
might be if you have a collection of proposed insertions and each contains
an index number and payload. Each time you insert the next payload at the
insertion point, you invoke a function that goes through your remaining
Collection and finds any with an index that is higher and increments it.

Obviously there are issues if dealing with adding multiple times to the same
index or adding multiple items at once.

The above could be encapsulated in some kind of VIEW in some languages
including of course some that use pointers.

I will add by pointing out a way to do a multi-insertion at once if you know
all the insertions at the same time.

Take your list that you want to change by adding at say positions 9, 3 and
6.

Now DON"T insert anything. Forget the concept.

Instead, and this is drastic, make a NEW list.

The new list is loosely old[0:2] + new_at_3 + old[3:5] + new_at_6 + old[6:8]
+new_at_9 + old[9:]

Something carefully written like that using concatenation means you do not
lose track of indices and end up with a new extended list you can feel free
to save under the old name and let the prior one be garbage collected.

Maybe one of the above hints at what could work for you, or others may
supply a better answer, or maybe you reevaluate what you are doing or
explain it some more.

-----Original Message-----
From: Python-list <python-list-bounces+avi.e.gross=gmail.com@python.org> On
Behalf Of Thomas Passin
Sent: Friday, March 3, 2023 1:04 PM
To: python-list@python.org
Subject: Re: Python list insert iterators

On 3/3/2023 3:22 AM, Guenther Sohler wrote:
> Hi Python community,
>
> I have a got an example list like
>
> 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
> T T
>
> and i eventually want to insert items in the given locations
> (A shall go between 2 and 3, B shall go between 6 and 7)
>
> Right now i just use index numbers to define the place:
>
> A shall insert in position 2
> B shall insert in position 6
>
> However when i insert A in position 2, the index for successful insertion
> of B gets wrong
> (should now be 7 instead of 6)
>
> No, it's not an option to sort the indexes and start inserting from the
> back.
> The most elegant option is not to store indexes, but list iterators, which
> attach to the list element
> and would automatically move, especially if an element is inserted before.
>
> I could not find such functionality in python lists of [ 1,2,3 ]
>
> Does python have such functionality ?
> if yes, where can i find it ?

You should be more clear about how to establish the desired insertion
point. In your example, you first say that the insertion of B should be
between 6 and 7. But after A gets inserted, you say that B's insertion
point should change. How is anyone able to know what the correct
insertion point should be at any time?

If the rule is that B should get inserted after a particular known
element, you can find out the index of that element with list.index()
and insert just after that. If the rule is "There is an imaginary
location that starts out after index 6 but moves depending on previous
insertions", then you will probably need to capture a record of those
insertions and use it to adjust the invisible insertion point. But this
synchronization could be tricky to keep correct depending on what you
want to do to this list.

So you need to specify clearly what the rules are going to be.
--
https://mail.python.org/mailman/listinfo/python-list

--
https://mail.python.org/mailman/listinfo/python-list
Re: Python list insert iterators [ In reply to ]
On 03/03/2023 21.22, Guenther Sohler wrote:
> Hi Python community,
>
> I have a got an example list like
>
> 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
> T T
>
> and i eventually want to insert items in the given locations
> (A shall go between 2 and 3, B shall go between 6 and 7)
>
> Right now i just use index numbers to define the place:
>
> A shall insert in position 2
> B shall insert in position 6
>
> However when i insert A in position 2, the index for successful insertion
> of B gets wrong
> (should now be 7 instead of 6)

The danger here is using the index to have meaning beyond its function
(a position relative to the beginning/end).


> No, it's not an option to sort the indexes and start inserting from the
> back.

Without explaining this criteria (and any others), suggestions can only
be guesses!

> The most elegant option is not to store indexes, but list iterators, which
> attach to the list element
> and would automatically move, especially if an element is inserted before.
>
> I could not find such functionality in python lists of [ 1,2,3 ]

So, if list doesn't float-your-boat, what about moving to something else?

> Does python have such functionality ?
> if yes, where can i find it ?

dict - where the keys indicate relative position

linked-list (https://en.wikipedia.org/wiki/Linked_list) where each value
is accompanied by a "pointer" which addresses the next value by-index;
and insertion/deletion is possible by exchanging pointers.
--
Regards,
=dn
--
https://mail.python.org/mailman/listinfo/python-list
Re: Python list insert iterators [ In reply to ]
Guenther Sohler <guenther.sohler@gmail.com> writes:

Hi Python community,

I have a got an example list like

1, 2, 3, 4, 5, 6, 7, 8, 9, 10
T T

and i eventually want to insert items in the given locations
(A shall go between 2 and 3, B shall go between 6 and 7)

Right now i just use index numbers to define the place:

A shall insert in position 2
B shall insert in position 6

However when i insert A in position 2, the index for successful insertion
of B gets wrong
(should now be 7 instead of 6)

No, it's not an option to sort the indexes and start inserting from the
back.

If you are definitely inserting from the front, then you can use
negative indexes, since the positions relative to the end of the list
won't be changing.

If you must insert in a random order, that won't help, but you haven't
told us what your real constraints are.
--
https://mail.python.org/mailman/listinfo/python-list
Re: Python list insert iterators [ In reply to ]
Python lists are arrays in other languages. You?ll have to roll your own or find something in https://pypi.org, etc. I think this incomplete implementation does the trick.

#
# MIT licensed
#
from dataclasses import dataclass
from typing import TypeVar, Generic

T = TypeVar("T")


@dataclass
class ListNode(Generic[T]):
_value: T
_next: "ListNode" = None


# noinspection PyProtectedMember
class ListIter(Generic[T]):

def __init__(self, list_: 'LinkedList', node: ListNode[T]):
self._list = list_
self._node: ListNode[T] = node

def __next__(self) -> T:
if self._node != None:
v = self._node._value
self._node = self._node._next
return v
raise StopIteration()

@property
def value(self) -> T:
return self._node._value

def insert_after(self, value: T) -> None:
self._list._insert_after(self._node, value)


# noinspection PyProtectedMember
class LinkedList(Generic[T]):
"""Singly linked List"""

# noinspection PyTypeChecker
def __init__(self):
self._head: ListNode[T] = None
self._tail: ListNode[T] = None

def __iter__(self):
return ListIter(self, self._head)

def _insert_after(self, node: ListNode[T], value: T):
if node != self._head:
if node != self._tail:
node._next = ListNode(value, node._next)

def append(self, value: T) -> None:
"""Add to end of list"""
if self._head != None:
self._tail._next = (n := ListNode(value))
self._tail = n
return
self._head = self._tail = ListNode(value)

def appendleft(self, value: T) -> None:
"""Add to beginning of list"""
if self._head != None:
single = self._head == self._tail
self._head = (n := ListNode(value, self._head))
if single:
self._tail = n
return
self._head = self._tail = ListNode(value)

def index(self, nth: int) -> ListIter[T]:
"""Return iterator at nth position"""
n = self._head
for i in range(nth):
n = n._next
if n == None:
raise IndexError('list index out of range')
return ListIter(self, n)


#
# TODO: add search for value, deletion of elements, et. al.
#


def unit_test():
"""Test basics"""
linked_list = LinkedList()
for i in range(1, 11):
linked_list.append(i)

# iteration matching equivalent list
for item in zip(linked_list, [i for i in range(1, 11)]):
assert (item[0] == item[1])

# verify index() method
assert linked_list.index(0).value == 1
assert linked_list.index(1).value == 2
try:
print(linked_list.index(11).value)
assert False
except IndexError:
pass
# test append left
linked_list.appendleft(0)
for item in zip(linked_list, [i for i in range(0, 12)]):
assert (item[0] == item[1])


def python_mailing_list_example():
"""Example from mailing list"""
linked_list = LinkedList()
for i in range(1, 11):
linked_list.append(i)
a = linked_list.index(1)
print(a.value)
b = linked_list.index(5)
print(b.value)
a.insert_after(27)
b.insert_after(45)
print(','.join(str(x) for x in linked_list))


unit_test()
python_mailing_list_example()

From: Python-list <python-list-bounces+gweatherby=uchc.edu@python.org> on behalf of Guenther Sohler <guenther.sohler@gmail.com>
Date: Friday, March 3, 2023 at 12:28 PM
To: python-list@python.org <python-list@python.org>
Subject: Python list insert iterators
*** Attention: This is an external email. Use caution responding, opening attachments or clicking on links. ***

Hi Python community,

I have a got an example list like

1, 2, 3, 4, 5, 6, 7, 8, 9, 10
T T

and i eventually want to insert items in the given locations
(A shall go between 2 and 3, B shall go between 6 and 7)

Right now i just use index numbers to define the place:

A shall insert in position 2
B shall insert in position 6

However when i insert A in position 2, the index for successful insertion
of B gets wrong
(should now be 7 instead of 6)

No, it's not an option to sort the indexes and start inserting from the
back.
The most elegant option is not to store indexes, but list iterators, which
attach to the list element
and would automatically move, especially if an element is inserted before.

I could not find such functionality in python lists of [ 1,2,3 ]

Does python have such functionality ?
if yes, where can i find it ?
--
https://urldefense.com/v3/__https://mail.python.org/mailman/listinfo/python-list__;!!Cn_UX_p3!gMAiBffu8h9N-YxV4nxLjapnR3InnNHeAbrHchQ-QoKfCHpF68yr8MKpEvXNdW1uJI3pFEXPiSvDRy9BpXAPfbP0k-Mn$<https://urldefense.com/v3/__https:/mail.python.org/mailman/listinfo/python-list__;!!Cn_UX_p3!gMAiBffu8h9N-YxV4nxLjapnR3InnNHeAbrHchQ-QoKfCHpF68yr8MKpEvXNdW1uJI3pFEXPiSvDRy9BpXAPfbP0k-Mn$>
--
https://mail.python.org/mailman/listinfo/python-list