#!/usr/bin/env python3

"""very simple gnutella path folding simulator."""

from random import random, choice
from collections import defaultdict

def randomnodes(num=8000):
    """Generate num nodes with locations between 0 and 1."""
    nodes = set()
    for n in range(num):
       n = random()
       while n in nodes:
           n = random()
       nodes.add(n)
    return list(nodes)

def generateflat(nodes, connectionspernode=10):
    """generate a randomly connected network with the given connectionspernode."""
    net = defaultdict(list)
    for node in nodes:
        connections = []
        for n in range(connectionspernode - len(net[node])):
            conn = choice(nodes)
            while (conn == node or 
                   node in net[conn] or 
                   net[conn][connectionspernode-1:]):
                conn = choice(nodes)
            connections.append(conn)
            net[conn].append(node)
    for node, conns in net.items():
        net[node] == sorted(conns)
    return net

def closest(target, sortedlist):
    """return the node which is closest to the target."""
    dist = 1
    for n in sortedlist:
        d = abs(n - target)
        if d < dist:
            best = n
            dist = d
        else: 
            return best
    return best

def findroute(target, start, net):
    """Find the best route to the target usinggreedy routing."""
    best = start
    seen = set()
    route = []
    while not best == target:
        prev = best
        best = closest(target, net[prev])
        # never repeat a route
        if best in seen:
            best = choice(net[prev])
        route.append(best)
        seen.add(best)
    return route

if __name__ == "__main__":
    nodes = randomnodes()
    net = generateflat(nodes)
    start = choice(nodes)
    target = choice(nodes)
    route = findroute(target, start, net)
    print (route)