from __future__ import division
import types, random, heapq

def accumulation(acc, f, it):
    """Iterate x over it, accumulating f(x) into acc, and return result."""
    if isinstance(acc, (types.ClassType, types.TypeType)): 
        a = acc()                                          
    else:                                                  
        a = acc                                            
    for x in it:
        if a.add(f(x), x):
            break         
    return a.result()

class Sum:
    "Accumulate the sum of a sequence of numbers"
    def __init__(self): self.total = 0

    def add(self, exp, _): self.total += exp

    def result(self): return self.total

class Product:
    "Accumulate the product of a sequence of numbers"
    def __init__(self): self.prod = 1

    def add(self, exp, _): 
        self.prod *= exp
        if exp == 0: 
            return True

    def result(self): return self.prod

class Max:
    "Accumulate the maximum value of a sequence"
    def __init__(self): self.seen = False

    def add(self, exp, _): 
        if self.seen:
            self.max = max(self.max, exp)
        else:
            self.seen, self.max = True, exp

    def result(self):
        if not self.seen: 
            raise ValueError("No values given to Max")
        return self.max

class Min:
    "Accumulate the minimum value of a sequence"
    def __init__(self): self.seen = False

    def add(self, exp, _): 
        if self.seen:
            self.min = min(self.min, exp)
        else:
            self.seen, self.min = True, exp

    def result(self):
        if not self.seen: 
            raise ValueError("No values given to Min")
        return self.min

class Argmax:
    "Accumulate the element of a sequence that has the maximum value"
    def __init__(self): self.seen = False

    def add(self, exp, x): 
        if self.seen:
            if exp > self.max:
                self.max, self.x = exp, x
        else:
            self.seen, self.max, self.x = True, exp, x

    def result(self):
        if not self.seen: 
            raise ValueError("No values given to Argmax")
        return self.x

class Argmin:
    "Accumulate the element of a sequence that has the minimum value"
    def __init__(self): self.seen = False

    def add(self, exp, x): 
        if self.seen:
            if exp < self.min:
                self.min, self.x = exp, x
        else:
            self.seen, self.min, self.x = True, exp, x

    def result(self):
        if not self.seen: 
            raise ValueError("No values given to Argmin")
        return self.x

class Mean:
    "Accumulate the average of a sequence of numbers"
    def __init__(self):
        self.total, self.n = 0, 0

    def add(self, exp, _):
        self.total, self.n = self.total+exp, self.n+1

    def result(self):
        return self.total / self.n

class Median:
    """Accumulate the number that is in the middle: half above, half below.
    If there is an even number, try to average the middle two, or else just
    choose randomly from them if they can't be averaged."""
    def __init__(self): self.values = []

    def add(self, exp, _): self.values.append(exp)

    def result(self):
        ## There are faster algorithms, but for now just use sort
        values = self.values
        n = len(values)
        values.sort()
        if n % 2 == 1:
            return values[n//2]
        else:
            (m, n) = values[(n//2)-1:(n//2)+1]
            try:
                return (m + n) / 2
            except TypeError:
                return random.choice((m, n))

class Mode:
    "Accumulate the most popular element of a sequence"
    def __init__(self): self.map = {}

    def add(self, exp, _): self.map[exp] = self.map.get(exp, 0) + 1

    def result(self):
        map = self.map
        return accumulation(Argmax, lambda exp: map[exp], map)

class Some:
    "An accumulator: If some exp is true, return it; otherwise return False"
    def __init__(self): self.value = False

    def add(self, exp, _):
        if exp:
            self.value = True
            return StopIteration

    def result(self): return self.value

class Every:
    "An accumulator: If every exp is true, return True; otherwise return False"
    def __init__(self): self.value = True

    def add(self, exp, _):
        if not exp:
            self.value = False
            return StopIteration

    def result(self): return self.value

class Top:
    def __init__(self, k):
        self.k = k
        self.heap = []

    def add(self, exp, _):
        heap = self.heap
        if len(heap) < self.k:
            heapq.heappush(heap, exp)
        elif exp > heap[0]:
            heapq.heapreplace(heap, exp)

    def result(self):
        self.heap.sort()
        self.heap.reverse()
        return self.heap

class RandomChoice:
    "An accumulator: choose a random item, with uniform distribution."
    def __init__(self):
            self.n, self.choice = 0, None

    def add(self, exp, _):
        self.n += 1
        if random.randrange(self.n) == 0:
            self.choice = exp

    def result(self):
        if self.n == 0:
            raise ValueError, "No elements for RandomChoice"
        return self.choice

class Join:
    "An accumulator: convert items to strings and join them."
    def __init__(self, joiner=''):
        self.joiner = joiner
        self.items = []

    def add(self, exp, _):
        self.items.append(str(exp))

    def result(self):
        return self.joiner.join(self.items)

class SortBy:
    """An accumulator that sorts items using a key.
    [SortBy: abs(x) for x in (-2,-4,3,1)] yields (1, -2, 3, -4)]"""
    def __init__(self, reverse=False):
        self.items = []
        self.reverse = reverse

    def add(self, exp, x):
        self.items.append((exp, len(self.items), x))

    def result(self):
        self.items.sort()
        if self.reverse:
            self.items.reverse()
        return [x for (_, _, x) in self.items]