########################################
# The contents of this file are subject to the MLX PUBLIC LICENSE version
# 1.0 (the "License"); you may not use this file except in
# compliance with the License.
# 
# Software distributed under the License is distributed on an "AS IS"
# basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.  See
# the License for the specific language governing rights and limitations
# under the License.
# 
# The Original Source Code is "compClust", released 2003 September 03.
# 
# The Original Source Code was developed by the California Institute of
# Technology (Caltech).  Portions created by Caltech are Copyright (C)
# 2002-2003 California Institute of Technology. All Rights Reserved.
########################################

import operator
import copy

def unique(s):
  """Return a list of the elements in s, but without duplicates.
  
  For example, unique([1,2,3,1,2,3]) is some permutation of [1,2,3],
  unique("abcabc") some permutation of ["a", "b", "c"], and
  unique(([1, 2], [2, 3], [1, 2])) some permutation of
  [[2, 3], [1, 2]].
  
  For best speed, all sequence elements should be hashable.  Then
  unique() will usually work in linear time.
  
  If not possible, the sequence elements should enjoy a total
  ordering, and if list(s).sort() doesn't raise TypeError it's
  assumed that they do enjoy a total ordering.  Then unique() will
  usually work in O(N*log2(N)) time.
  
  If that's not possible either, the sequence elements must support
  equality-testing.  Then unique() will usually work in quadratic
  time.
  """
  
  n = len(s)
  if n == 0:
    return []

  # Try using a dict first, as that's the fastest and will usually
  # work.  If it doesn't work, it will usually fail quickly, so it
  # usually doesn't cost much to *try* it.  It requires that all the
  # sequence elements be hashable, and support equality comparison.
  u = {}
  try:
    for x in s:
      u[x] = 1
  except TypeError:
    del u  # move on to the next method
  else:
    return u.keys()

  # We can't hash all the elements.  Second fastest is to sort,
  # which brings the equal elements together; then duplicates are
  # easy to weed out in a single pass.
  # NOTE:  Python's list.sort() was designed to be efficient in the
  # presence of many duplicate elements.  This isn't true of all
  # sort functions in all languages or libraries, so this approach
  # is more effective in Python than it may be elsewhere.
  try:
    t = list(s)
    t.sort()
  except TypeError:
    del t  # move on to the next method
  else:
    assert n > 0
    last = t[0]
    lasti = i = 1
    while i < n:
      if t[i] != last:
        t[lasti] = last = t[i]
        lasti += 1
      i += 1
    return t[:lasti]

  # Brute force is all that's left.
  u = []
  for x in s:
    if x not in u:
      u.append(x)
  return u

def count(a):
  """returns a dictionary of the item:number of occurances for a list
  WARNING : all elements in the list most be hashable
  """

  counts = {}
  for i in a:
    try:
      counts[i] +=1
    except KeyError:
      counts[i] = 1
  return(counts)

def union(a, b):
  """Union of 2 lists"""
  return unique(a + b)

def cartesian(a, b):
  return map(list, [(x,y) for x in a for y in b])
  
def intersection(a, b):
  """Intersection of two lists"""
  x = {}
  map(x.setdefault, a, [1] * len(a))
  return filter(x.has_key, b)

def difference(a,b):
  """Difference of two lists.  items in a which are not in b"""

  x = {}
  map(x.setdefault, b, [None] * len(b))
  diff = []
  diff.extend(map(x.setdefault, a,a ))
  return(filter(None, diff))

def symetricDifference(a,b):
  """Difference of two lists. Items which are in only a or b, but not both (XOR)"""

  x = {}
  y = {}
  map(x.setdefault, a, [None] * len(a))
  map(y.setdefault, b, [None] * len(b))
  diff = []
  diff.extend(map(x.setdefault, b,b ))
  diff.extend(map(y.setdefault, a,a ))
  return(filter(None, diff))

def sort(a, f=cmp):
  """Not inplace sort"""
  b = copy.copy(a)
  b.sort(f)
  return b

def reverse(a):
  """Not inplace revers"""
  b = copy.copy(a)
  b.reverse()
  return b

def unravel(a):
  """Unravel list of lists"""
  return reduce(operator.add, a, [])

def findAll(a, i):
  """Return a list of indices of occurences of an item"""
  n = len(a)
  tmp = map(operator.not_, map(cmp, a, [i]*n))
  tmp = filter(None, map(operator.mul, tmp, range(1, n+1)))
  return map(operator.sub, tmp, [1] * len(tmp))
  
def take(a, i):
  """Takes a subset of elements of a list"""
  return map(operator.getitem, [a] * len(i), i)
  
def transpose(a):
  """Transpose list of lists"""
  return(map(list, apply(zip, a)))

def allTrue(a):
  """ returns 1 if all items are true """
  return reduce(operator.mul, map(operator.truth, a))
  
def someTrue(a):
  """ returns 1 if there is atleast one true element"""
  return reduce(operator.add, map(operator.truth, a)) > 0

def fullCross(listOfLists):
  """
  full cross product of the lists of lists.  
  """

  if len(listOfLists) == 1 :
    return([[i] for i in listOfLists[0]])
  else:
    a = listOfLists[0]
    b = fullCross(listOfLists[1:])
    return( [ [i] + j  for i in a for j in b])