import math

class TypecheckError(TypeError): pass

def typechecked(*argtypes):
    """Function decorator for basic run-time argument type checking.

    Use this decorator as in the following example:
    @typechecked(int, str)
    def add(x, y):
        return x + len(y)

    If a type error is encountered in a call to a decorated function,
    this will raise a TypecheckError.

    This decorator understands variable arity functions, but the
    function types must have fixed arity."""

    def advise(func):
        def wrapper(*args):
            # Check number of arguments
            if len(args) != len(argtypes):
                pl = ""
                if len(argtypes) != 1: pl = "s"
                raise TypecheckError, \
                      "%s() takes exactly %d argument%s (%d given)" % \
                      (func.func_name, len(argtypes), pl, len(args))
            # Check argument types
            giventypes = map(type, args)
            for giventype, argtype in zip(giventypes, args):
                if not isinstance(argtype, giventype):
                    raise TypecheckError, \
                          "%s takes %s (%s given)" % \
                          (func.func_name,
                           "*".join([x.__name__ for x in argtypes]),
                           "*".join([x.__name__ for x in giventypes]))
            # Call function
            return func(*args)

        # Make sure number of arguments that func takes matches the
        # number of typechecked arguments
        if func.func_code.co_argcount > len(argtypes) or \
               (~func.func_code.co_flags & 0x04 and \
                func.func_code.co_argcount < len(argtypes)):
            raise TypecheckError, \
                  "Function signature doesn't match type signature"

        wrapper.func_name = func.func_name+"_typechecked"
        return wrapper

    return advise

def genericHash(fields):
    """Generic hash function: hash the values listed in fields. This
    uses the hash function defined on the values and combines the
    results."""
    val = 0
    for x in fields:
        val *= 1000003
        val += hash(x)
    return hash(val)

def printArg(x):
    """Utility function to print and return the argument. A useful
    callback for debugging."""
    print x
    return x

def uniquify(l):
    """Return the unique items in the input list, in the original
    order. If an item appears multiple times, only the first is
    preserved. All objects in the list must be hashable."""
    
    seen = {}; r= []
    for x in l:
        if x in seen:
            continue
        seen[x] = True
        r.append(x)
    return r

class ExpirationQueue:
    """Simple queue for keeping track of expiration times for
    objects. Implemented as a sorted list."""
    
    def __init__(self):
        """Create an empty queue."""
        self.queue = []

    @typechecked(object, object, float)
    def add(self, obj, expire):
        """Add obj to the queue with specified expire time."""
        rec = (expire, obj)
        for i in range(len(self.queue)):
            if self.queue[i] > rec:
                self.queue.insert(i, rec)
                return
        self.queue.append(rec)

    @typechecked(object, object)
    def remove(self, obj):
        """Remove (all entries matching) obj from the queue."""
        self.queue = [x for x in self.queue if x[1] != obj]

    @typechecked(object, object, float)
    def refresh(self, obj, expire):
        """Update the expiration time for obj."""
        self.remove(obj)
        self.add(obj, expire)

    def min(self):
        """Return (expire time, obj) for the earliest-expiring element
        in the queue."""
        if len(self.queue) > 0:
            return self.queue[0]
        else:
            return None

    def __len__(self):
        return len(self.queue)


def If(test, result, alternative=None):
    """If test is true, 'do' result, else alternative. 'Do' means call
    if callable or just return otherwise. Borrowed from Norvig's
    Python IAQ as a replacement for the non-existent ternary
    operator."""
    
    if test:
        if callable(result): result = result()
        return result
    else:
        if callable(alternative): alternative = alternative()
        return alternative
    
def printf(format, *args):
    print format % args,

def prin(x):
    print x,

def mean(x):
    return float(sum(x))/len(x)

def stddev(x):
    xmean = mean(x)
    var = 0
    for i in x:
        var += (i - xmean) ** 2
    var /= len(x)
    return math.sqrt(var)

def percentile(lst, p):
    ind = float(p)/100*len(lst)
    return sorted(lst)[int(ind)]