#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# UPMC - c.durr - 2015 
# Conception et Pratique de l'Algorithmique
# TME 7 - déterminer les éléments distincts

from heapq     import *
from random    import *
from sys       import *
from math      import *
from ipaddress import *

def streamIP(filename):
    '''lit un flux d'un log de serveur web, avec pour chaque 
       ligne un numéro IP suivi evt. d'espace et d'autres informations
       ignorées. Ce numéro IP est converti en entiers 32 bits
       pour former un flux d'entiers. 
    '''
    global linenb
    with open(filename) as fp:
        for line in fp:
            yield int(IPv4Address(line.split()[0]))

BITS = 32

def zerosGauche(v):
    '''déterminer le nombre max de zéros le plus à droite de l'expansion binaire de v
    '''
    zeros = BITS
    while v>0:
        zeros -= 1
        v >>= 1
    return zeros

def zerosDroite(v):
    '''déterminer le nombre max de zéros le plus à droite de l'expansion binaire de v
    '''
    if v<=0:
        return BITS
    zeros = 0
    while v & 1 == 0:
        zeros += 1
        v >>= 1
    return zeros


def mult(a,b):
    ''' multiplication dans le corps GF[2^{32}]
        http://web.eecs.utk.edu/~plank/plank/papers/CS-07-593/primitive-polynomial-table.txt
    '''
    assert BITS==32
    v = 0
    for _ in range(BITS):
        if b&1:
            v ^= a
        carry = a & (1<<(BITS-1))
        a <<= 1
        if carry:
            a ^= 0o40020000007
        b >>= 1
    return v

class HashfunctionRijndael:
    ''' Carter Wegman appliqué au corps de Galois GF[2^32]
        aussi appelé corps de Rijndael
    '''
    def __init__(self):
        self.a = getrandbits(BITS)
        self.b = getrandbits(BITS)

    def __call__(self, val):
        return mult(self.a, val) ^ self.b

class HashfunctionCarterWegman:
    ''' Carter and Wegman
        p = next prime after 2**32 = 2**32 + 15
        http://www.wolframalpha.com/input/?i=next+prime+after+2**32
        rapide, mais pas exactement 2-universelle
    '''
    p = 4294967311

    def __init__(self):
        self.a = randint(0,Hashfunction.p-1)
        self.b = randint(0,Hashfunction.p-1)

    def __call__(self, val):
        # assert type(val) == int and 0 <= val and val < 1<<BITS
        return ((self.a*val + self.b) % Hashfunction.p )% (1<<BITS)

class HashfunctionMatrice:
    ''' Matrice binaire
        http://www.cs.cmu.edu/~avrim/Randalgs97/lect0127
    '''

    def __init__(self):
        self.H = [getrandbits(BITS) for _ in range(BITS)]

    def __call__(self, val):
        # assert type(val) == int and 0 <= val and val < 1<<BITS
        v = 0
        for hi in self.H:
            if val & 1 == 1:
                v ^= hi
            val >>= 1 
        return v

# ici on choisit la famille de fonctions de Hashage
class Hashfunction(HashfunctionCarterWegman):
    pass

class F0Naive:
    ''' cette implémentation utilise une qté linéaire de mémoire
        mais est exacte.  Peut donc échouer sur de très grandes données.
    '''
    def __init__(self):
        self.seen = set()

    def update(self, token):
        if token not in self.seen:
            self.seen.add(token)

    def val(self):
        return len(self.seen)


class F0AMS:
    '''Algorithme d'Alon, Matias et Szegedy.
    '''
    def __init__(self):
        self.h = Hashfunction()
        self.min = 1<<32 # infini

    def update(self, token):
        hj =  self.h(token)
        if hj < self.min:
            self.min = hj

    def val(self):
        return int(pow(2, zerosGauche(self.min) + 0.5))

class F0BJKST:
    '''Algorithme de Bar-Yossef, Jayram, Kumar, Sivakumar et Trevisan
    '''

    epsilon = 0.1 

    def __init__(self):
        self.h = Hashfunction()
        e = F0BJKST.epsilon
        self.limit = 1+int(12*24/e/e)
        self.B = [set() for _ in range(BITS)]
        self.lenB = 0
        self.z = 0

    def update(self, token):
        hj = self.h(token)
        zj = zerosDroite(hj)
        if zj >= self.z:
            if hj in self.B[zj]:
                return
            self.B[zj].add(hj)
            self.lenB += 1
            if self.lenB > self.limit:
                self.lenB -= len(self.B[self.z])
                self.B[self.z] = set()
                self.z += 1

    def val(self):
        return self.lenB << self.z


class MedianTrick:
    '''Réduit la probabilité d'erreur d'un algorithme donnée
       qui retourne une valeur trop grande avec probabilité failProb
       et une valeur trop petite avec probabilité failProb.
       Cette classe réduite cette probabilité d'erreur à delta donnée.
    '''
    def __init__(self, algo, failProb, delta):
        k = int(1 + log(2/delta)/log(1/failProb))  # arrondir vers le haut
        self.L = [algo() for _ in range(k)]

    def update(self, token):
        for e in self.L:
            e.update(token)

    def val(self):
        '''Le median peut se calculer en temps linéaire,
           mais pour simplifier le code, une solution
           en temps O(k log k) est proposée.
        '''
        A = [e.val() for e in self.L]
        A.sort()
        median = A[len(A)//2]
        return median


if __name__=="__main__":
    a = len(argv)
    if   a==2:
        A = F0Naive()
    elif a==3:
        A = MedianTrick(F0AMS, sqrt(2)/3, float(argv[2]))
    elif a==4:
        F0BJKST.epsilon = float(argv[2])
        A = MedianTrick(F0BJKST, 1./6, float(argv[3]))
    else:
        print("Usage: ./F0.py [filename]                   # pour l'algorithme naif")
        print("Usage: ./F0.py [filename] [delta]           # pour l'algorithme AMS")
        print("Usage: ./F0.py [filename] [epsilon] [delta] # pour l'algorithme BJKST")
        exit(1)

    n = 0
    for ip in streamIP(argv[1]):
        A.update(ip)
        n += 1
        if n % 1000000 == 0:
            print("estimation au bout de %d lignes est %d" % (n, A.val()))
    print (A.val())