Skip to content

Instantly share code, notes, and snippets.

@hrldcpr
Created July 12, 2015 22:08
Show Gist options
  • Save hrldcpr/20688c977d9784088921 to your computer and use it in GitHub Desktop.
Save hrldcpr/20688c977d9784088921 to your computer and use it in GitHub Desktop.
implementation of `itertools.tee()` using one linked list instead of n deques
import collections
class LinkedList:
def __init__(self, value, tail=None):
self.value = value
self.tail = tail
def tee(iterable, n=2):
it = iter(iterable)
empty = LinkedList(None)
positions = [empty] * n
def gen(i):
while True:
if not positions[i].tail: # when local position is at the end of the list
newval = next(it) # fetch a new value and
positions[i].tail = LinkedList(newval) # add it to the list
positions[i] = positions[i].tail # advance local position in the list
yield positions[i].value
return tuple(gen(i) for i in range(n))
@kuritzky
Copy link

kuritzky commented Jul 7, 2016

There is no need to create a list of positions:

def tee(iterable, n=2):
    it = iter(iterable)
    empty = LinkedList(None)
    def gen():
        position = empty
        while True:
            if not position.tail:                   # when local position is at the end of the list
                newval = next(it)                   # fetch a new value and
                position.tail = LinkedList(newval)  # add it to the list
            position = position.tail                # advance local position in the list
            yield position.value
    return tuple(gen() for i in range(n))

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment