#!/usr/bin/env python
#
# iter.py
#   iterread(f, n, delim=" ", bufsiz=256)
#   iternread(f, n, chunksize, bufsiz=256)
#   striter(s, delim=" ")
#   strniter(s, chunksize)
#   mergeiters(iterators, cmp=cmp)
#   uniqiter(iter1, n=1, differ=cmp)
#   count(iter)
#


# split verrry long string from files
def iterread(f, n, delim=" ", bufsiz=4096):
  s0 = ""
  loc = f.tell()
  while n:
    f.seek(loc)
    s = f.read(min(n, bufsiz))
    loc = f.tell()
    n -= len(s)
    p = s.split(delim)
    s0 += p[0]
    if 1 < len(p):
      yield s0
      for t in p[1:-1]:
        yield t
      s0 = p[-1]
  yield s0
  return

def iternread(f, n, chunksize, bufsiz=4096):
  s = ""
  loc = f.tell()
  while chunksize <= n:
    f.seek(loc)
    s += f.read(min(n, bufsiz))
    loc = f.tell()
    i = 0
    while i+chunksize <= len(s):
      yield s[i:i+chunksize]
      i += chunksize
      n -= chunksize
    s = s[i:]
  return


# split string into iterators
def striter(s, delim=" "):
  i = 0
  while 1:
    try:
      n = s.index(delim, i)
    except ValueError:
      yield s[i:]
      break
    yield s[i:n]
    i = n + len(delim)
  return

def strniter(s, chunksize):
  i = 0
  while i+chunksize <= len(s):
    yield s[i:i+chunksize]
    i += chunksize
  return


# merge two iters
def mergeiters(iterators, cmp=cmp):
  q = []
  for i in map(iter, iterators):
    try:
      q.append((i.next(), i))
    except StopIteration:
      pass
  q.sort(lambda (p1,x1),(p2,x2): cmp(p2, p1))
  last = None
  while q:
    (n, i) = q.pop()
    yield n
    try:
      x = i.next()
      assert not last or 0 <= cmp(x, last), "not sorted: %r" % x
      q.append((x, i))
      q.sort(lambda (p1,x1),(p2,x2): cmp(p2, p1))
    except StopIteration:
      pass
    last = n
  return


# show elements which appear at least n times
def uniqiter(iter1, n=1, differ=cmp):
  eqv = []
  prev = None
  for x in iter(iter1):
    if prev:
      dif = differ(prev, x)
      if 0 < dif:
        raise "not sorted: %r" % x
      elif dif:
        if n <= len(eqv):
          yield eqv
        eqv = [ x ]
      else:
        eqv.append(x)
    else:
      eqv.append(x)
    prev = x
  if n <= len(eqv):
    yield eqv
  return


# utility functions
def intersection(iterators, cmp=cmp):
  return uniqiter(mergeiters(iterators, cmp), len(iterators), differ=cmp)
def union(iterators, cmp=cmp):
  return uniqiter(mergeiters(iterators, cmp), differ=cmp)



# generate combination 2^n:
#  ex. [1,2,3] -> [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]
def combination_2n(v):
  if not v:
    yield ()
  else:
    for c1 in combination_2n(v[1:]):
      yield c1
      yield (v[0],)+c1
  return

# generate combination n^2:
#  ex. [[1,2,3],[4,5,6]] -> [[1,4], [1,5], [1,6], [2,4], [2,5], [2,6], [3,4], [3,5], [3,6]]
def combination_n2(*v):
  if not v:
    yield ()
  else:
    for i in v[0]:
      for c1 in combination_n2(v[1:]):
        yield (i,)+c1
  return


# zipiter
def zipiter(*iters):
  iters = map(iter, iters)
  try:
    while 1:
      yield tuple( i.next() for i in iters )
  except StopIteration:
    return
izip = zipiter

# icount
def icount(i):
  n = 0
  for x in i:
    n += 1
  return n
ilen = icount
counti = icount

# gmax
def gmax(seq, cmp=cmp, key=lambda x:x, default=object()):
  m = default
  for x in seq:
    k = key(x)
    if m == default or 0 < cmp(k, m): m = x
  return m

# gmin
def gmin(seq, cmp=cmp, key=lambda x:x, default=object()):
  m = default
  for x in seq:
    k = key(x)
    if m == default or cmp(k, m) < 0: m = x
  return m

# find, rfind
def find(f, i):
  for x in iter(i):
    if f(x): return x
  raise ValueError("not found")
def rfind(f, i):
  for x in reversed(i):
    if f(x): return x
  raise ValueError("not found")

# exits
def exists(f, it):
  for i in iter(it):
    if f(i): return True
  return False
# forall
def forall(f, it):
  for i in iter(it):
    if not f(i): return False
  return True

def empty(seq):
  for x in seq:
    return False
  return True

def some(seq):
  for x in seq:
    return True
  return False

def first(seq):
  for x in seq:
    return x
  return ValueError('Empty sequence: %r' % seq)

def last(seq):
  x0 = None
  for x in seq:
    x0 = x
  return x0

def imap(f, it):
  for i in iter(it):
    yield f(i)
  return

def ifilter(f, it):
  for i in iter(it):
    if f(i):
      yield i
  return

def flatten(it):
  for i in iter(it):
    if hasattr(i, '__iter__'):
      for x in flatten(i):
        yield x
    else:
      yield i
  return

def combine(n, it):
  it = iter(it)
  try:
    while 1:
      yield tuple( it.next() for i in xrange(n) )
  except StopIteration:
    pass
  return

# test
if __name__ == "__main__":
  import StringIO
  print "iterread:"
  s = "hoge hogea oeiajrf"
  print list(iterread(StringIO.StringIO(s), len(s)))
  print list(striter(s))
  print "iternread:"
  s = "abcdef"
  print list(iternread(StringIO.StringIO(s), len(s), 2))
  print list(strniter(s, 2))
  print "mergeiters:"
  print list(mergeiters([[1,2,3,4], [2,3,5,6], [3,4,6,7]]))
  print "uniqiter:"
  print list(uniqiter([1,1,1,2,3,3,4,4,4,4,4], 2))
  print "intersection:"
  print list(intersection([[1,2,3,4,5], [1,2,3,5,9], [1,4,5]]))
  print "union:"
  print list(union([[2,3,4,5], [1,3,5,55], [0]]))