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

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:
            ip = map(int, line.split()[0].split('.'))
            val = 0
            for x in ip:
                val = val*256 + x
            yield val
            # ligne suivante serait plus court en code, mais plus lent en temps (x3)
            # yield int(IPv4Address(line.split()[0]))

class MisraGries:
    ''' 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, k):
        self.A = {}
        self.k = k

    def update(self, token):
        if token in self.A:
            self.A[token] += 1
        elif len(self.A)< self.k:
            self.A[token] = 1
        else:
            to_remove = []
            for x in self.A:
                self.A[x] -= 1
                if self.A[x] == 0:
                    to_remove.append(x)
            for x in to_remove:
                del self.A[x]

    def val(self):
        return self.A

if __name__=="__main__":
    if len(argv) != 3:
        print("Usage: ./MisraGries.py [filename] [delta] ")
        print(" returns elements with frequency at least delta")
        exit(1)
    delta = float(argv[2])
    k = int(1+1/delta)
    filename = argv[1]

    M = MisraGries(k)
    n = 0
    for token in streamIP(filename):
        M.update(token)
        n += 1
    c = M.val()
    
    for l in c:
        c[l] = 0
    for token in streamIP(filename):
        if token in c:
            c[token] += 1

    L = [(-c[l], l) for l in c if c[l]>=n*delta]

    L.sort()
    for neg_fx, x in L:
        print("%d\t%s" % (-neg_fx, str(IPv4Address(x))))