#!/usr/bin/env python
# encoding=utf-8 (pep 0263)
"""Lisp-like linked list data structure"""
Nil = []
class Cons(object):
def __init__(self, x, xs):
self.head = x
self.tail = xs
def reverse(self):
result = Nil
for x in self:
result = Cons(x, result)
return result
def __eq__(self, other):
if isinstance(other, self.__class__):
return self.head == other.head and self.tail == other.tail
else:
return False
def __ne__(self, other):
return not self.__eq__(other)
def __lt__(self, other):
return self.head < other.head or self.tail < other.tail
def __gt__(self, other):
return self.head > other.head or self.tail > other.tail
def __iter__(self):
return _Iterator(self)
def __str__(self):
return str(list(self))
def __repr__(self):
return str(self)
class _Iterator(object):
def __init__(self, linked_list):
self._linked_list = linked_list
def __iter__(self):
return self
def next(self):
if self._linked_list == Nil:
raise StopIteration
else:
head = self._linked_list.head
self._linked_list = self._linked_list.tail
return head
__next__ = next
def LinkedList(lst):
result = Nil
for x in reversed(lst):
result = Cons(x, result)
return result
def member(x, xs):
if xs == Nil:
return False
if x == xs.head:
return True
return member(x, xs.tail)
def member_anyX(xs):
if xs == Nil:
return
yield xs.head
for x in member_anyX(xs.tail):
yield x
def append(xs, ys):
if xs == Nil:
return ys
else:
return Cons(xs.head, append(xs.tail, ys))
def length(xs):
if xs == Nil:
return 0
return 1 + length(xs.tail)