import java.util.TreeSet;
import java.util.Map;
import java.util.HashMap;
import java.util.Random;
import java.io.InputStream;
import java.net.URL;

import static java.lang.System.exit;

class Peer implements Comparable<Peer> {

    final static int KEYSPACE = 65535;

    int id;
    Peer next, pred;
    TreeSet<Peer> fingers;

    Map<Integer, String> store;

    Peer(int id) {
	this.id = id;
	this.next = this;
	this.pred = this;
	this.fingers = new TreeSet<>();

	this.store = new HashMap<>();
    }

    boolean own(int x) {
	if (this.pred == this) return true; // cas d'un pair seul
	return
	    (this.id >= x && x > this.pred.id)
	    ||
	    (this.pred.id > this.id && (this.id >= x || this.pred.id < x));
    }

    // En moyenne, le routage est en O(log(N)) sauts au lieu de O(N), avec N le nombre de pairs.
    // Voir la preuve dans "Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications" by Stoica et al.
    Peer lookup(int x, boolean trace) {
	if (own(x)) return this;
	if (next.own(x)) return next;
	Peer n = fingers.floor(new Peer(x));
	if (n == null) n = this.next;
	if (trace) System.out.println("next: "+ n +" looking for " + x);
	return n.lookup(x, trace);
    }

    void join(Peer p) {
	if (p == null) return; // DHT vide
	Peer n = p.lookup(this.id, false);
	this.next = n;
	this.pred = n.pred;
	n.pred.next = this;
	this.pred.fingers.add(this);
	n.pred = this;
    }

    void leave() {
	this.next.pred = this.pred;
	this.pred.next = this.next;
    }

    void computeFingers() {
	for (int k=0; k < (Math.log(KEYSPACE)/Math.log(2)); k++) { // Erratum: le sujet mentionne le nombre de pairs au lieu de KEYSPACE 
	    int x = (this.id + (int) Math.pow(2,k)) % KEYSPACE;
	    assert x>0;
	    Peer p = lookup(x, true);
	    if (!p.equals(this)) {
		fingers.add(p);
	    }
	}
    }

    @Override
    public int compareTo(Peer p) {
	if (this.id == p.id) return 0;
	if (this.id > p.id) return 1;
	return -1;
    }

    @Override
    public boolean equals(Object o) {
	if (!(o instanceof Peer)) return false;
	Peer other = (Peer) o;
	return this.id == other.id;
    }

    @Override
    public int hashCode() {
	return id;
    }

    @Override
    public String toString(){
	StringBuilder sb = new StringBuilder();
	sb.append("Peer("+this.id
		  +", pred="+this.pred.id
		  +", next="+this.next.id);
	sb.append(", [ ");
	this.fingers.stream().forEach(x -> sb.append(x.id+" "));
	sb.append("])");
	return sb.toString();
    }

    public static void main(String[] args) {
	Peer p4 = new Peer(4);
	Peer p12 = new Peer(12);
	p12.join(p4);
	Peer p42 = new Peer(42);
	p42.join(p12);
	Peer p23 = new Peer(23);
	p23.join(p4);
	Peer p36 = new Peer(36);
	p36.join(p12);

	// fingers
	p4.computeFingers();
	p12.computeFingers();
	p23.computeFingers();
	p42.computeFingers();
	p36.computeFingers();

	Peer current = p4.next;
	do {
	    System.out.println(current);
	    current = current.next;
	} while (current != p4);

	p42.lookup(33,true);

    }

}

class DistributedHashTable {

    Peer peer;

    DistributedHashTable(Peer p) {
	this.peer = p;
    }

    void put(int k, String v) {
	System.out.println("put("+k+", "+v+")");
	peer.lookup(k, false).store.put(k,v);
    }

    String get(int k) {
	return peer.lookup(k, false).store.get(k);
    }

    boolean verify() {
	Peer head = this.peer.lookup(0, false);
	Peer current = head;
	do {
	    if (current.next.id < current.id) return false;
	    current.computeFingers();
	    current = current.next;
	} while (!current.next.equals(head));
	return true;
    }

}

class Main {

    public static void main(String[] args) {

	if (args.length != 1) {
	    System.err.println("Usage: number of peers");
	    exit(1);
	}

	// construction de la DHT avec N pairs
	int N = Integer.parseInt(args[0]);
	Random rand = new Random();
	Peer p = null;
	for (int i=0; i<N; i++) {
	    Peer q = new Peer(rand.nextInt(Peer.KEYSPACE));
	    q.join(p);
	    q.computeFingers();
	    System.out.println(q + " has joined");
	    p = q;
	}
	DistributedHashTable dht = new DistributedHashTable(p);

	// correction
	assert dht.verify();

	// ajout d'un elt aleatoire
	int k = rand.nextInt(Peer.KEYSPACE);
	String v = Integer.toString(k);
	dht.put(k,v);
	assert dht.get(k).equals(v);

	// stockage de pages web
	try {
	    URL[] urls = {
		new URL("https://telecom-sudparis.eu"),
		new URL("https://www.ip-paris.fr/")};

	    for (URL url: urls) {
		InputStream is = url.openStream();
		StringBuffer buffer = new StringBuffer();
		int ptr = 0;
		while ((ptr = is.read()) != -1) {
		    buffer.append((char)ptr);
		}
		dht.put(Math.abs(url.hashCode()%Peer.KEYSPACE), buffer.toString());
	    }
	} catch(Exception e) {
	    System.err.println("Error while fetching web pages: " + e.getMessage());
	}

    }

}