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

from math import ceil, sqrt, log
from random import getrandbits
from sys import argv

BITS = 32

class FluxIP:
    '''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.
    '''
    def __init__(self, filename):
        self.f = open(filename)

    def next(self):
        line = self.f.readline()
        if line:
            a = line.split()[0].split('.')
            return int(a[3]) + ((int(a[2]) + ((int(a[1]) + (int(a[0]) << 8)) << 8)) << 8)
        else:
            return 0


class StreamingAlgo:
    def update(self, ip):
        raise NotImplementedError

    def val(self):
        raise NotImplementedError


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


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

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

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


class F0Naive(StreamingAlgo):
    ''' 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, ip):
        if ip not in self.seen:
            self.seen.add(ip)

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


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

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

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


class F0BJKST(StreamingAlgo):
    '''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, ip):
        hj = self.h.hash(ip)
        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(StreamingAlgo):
    '''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):
        self.k = int(ceil(log(2 / delta) / log(1 / failProb)))
        self.L = [algo() for _ in range(2 * self.k - 1)]

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

    def val(self):
        '''Le médian 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[self.k]
        return median


if __name__ == "__main__":
    a = len(argv)
    if a == 2:
        A = F0Naive()
    elif a == 3:
        A = MedianTrick(F0AMS, 2*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:")
        print("./F0.py [filename]                   # pour l'algorithme naif")
        print("./F0.py [filename] [delta]           # pour l'algorithme AMS")
        print("./F0.py [filename] [epsilon] [delta] # pour l'algorithme BJKST")
        exit(1)

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