import pickle, sys, os
from sets import Set
## import Gnuplot, Gnuplot.funcutils

## def latex(f):
##     g('set terminal push')
##     #g('set terminal latex 10')
##     g('set terminal epslatex "default" 10')
##     g('set format xy "$%g$"')
##     g.set_string('output', f.replace(".tex",".eps"))
##     g('set size .675, .675')
##     #g('set size 3/5, 3/5')
##     g.refresh()
##     g('set terminal pop')
##     g.set_string('output')
##     # Darnit, fix the path in the output file
## ##     os.system("echo ',s,{%(b)s},{figures/%(b)s},\nw' | ed %(e)s" %
## ##               {'b': f.replace(".tex",""), 'e': f})

## def png(f):
##     g('set terminal push')
##     g('set terminal png')
##     g.set_string('output', f)
##     g.refresh()
##     g('set terminal pop')
##     g.set_string('output')

class Entry:
    def __init__(self, aspath):
        self.aspath = aspath

def parseTable(lines):
    splitprefix = None

    # 0 to print no status, 1 to print line numbers, 2 to print
    # prefixes
    status = 2

    lnum = 0
    for line in lines:
        try:
            lnum += 1
            if status == 1 and lnum % 1000 == 0:
                sys.stdout.write("\r%d" % lnum)
                sys.stdout.flush()

            if splitprefix is None and not line.startswith("*"):
                continue

            line = line[:-1]

            if len(line) < 46:
                # Gah, it's a split line
                splitprefix = line[3:].strip()
                continue

            prefix, nexthop, med, locprf, rest = \
                    line[3:20], line[20:35], line[35:46], line[46:53], \
                    line[53:]

            prefix = prefix.strip()
            if splitprefix:
                if len(prefix):
                    raise RuntimeError, "splitprefix and prefix"
                prefix = splitprefix
                splitprefix = None
            if not len(prefix):
                prefix = None

            if status == 2 and prefix is not None:
                sys.stdout.write("     \r")
                sys.stdout.write(prefix)
                sys.stdout.flush()

#             nexthop = nexthop.strip()

#             med = med.strip()
#             if len(med):
#                 med = int(med)
#             else:
#                 med = None

#             locprf = locprf.strip()
#             if len(locprf):
#                 locprf = int(locprf)
#             else:
#                 locprf = None

            rest = rest.split()
            weight = int(rest[0])
            if "{" in rest[-2]:
                rest = rest[:-1]
            aspath = [int(x) for x in rest[1:-1]]
            
            reduce(lambda l, x: x not in l and l.append(x) or l, aspath, [])

            yield Entry(aspath)
        except:
            print "Exception caught while parsing:"
            print line
            raise
    print

def readAndParse(filename):
    f = file(filename)
    connectivity = {}
    aspaths = Set()
    
    def addLink(as1, as2):
        try:
            connectivity[as1].add(as2)
        except KeyError:
            connectivity[as1] = Set()
            connectivity[as1].add(as2)

    for ent in parseTable(f):
        aspaths.add(tuple(ent.aspath))
        for i in range(len(ent.aspath)-1):
            x = ent.aspath[i]
            y = ent.aspath[i+1]
            addLink(x, y)
            addLink(y, x)
    pickle.dump(connectivity, file("connectivity.dat", "w"))
    pickle.dump(aspaths, file("aspaths.dat", "w"))
    return (connectivity, aspaths)

def getConnectivity():
    try:
        return pickle.load(file("connectivity.dat"))
    except IOError:
        print "IOError"
        return readAndParse("oix-full-snapshot-2005-09-20-2200.dat")[0]

def getAspaths():
    try:
        return pickle.load(file("aspaths.dat"))
    except IOError:
        print "IOError"
        return readAndParse("oix-full-snapshot-2005-09-20-2200.dat")[1]

connectivity = getConnectivity()
aspaths = getAspaths()

for x in connectivity.keys():
    if x in connectivity[x]:
        connectivity[x].remove(x)

degrees = [(len(connectivity[x]), x) for x in connectivity.keys()]
degrees.sort()
degrees.reverse()
print degrees[0:10]

ccdf = []
for i in range(degrees[0][0]):
    ccdf.append(float(len([x for x in degrees if x[0] >= i]))/len(degrees))

## global g
## g = Gnuplot.Gnuplot(debug=1)
## g('set logscale x 10')
## g('set logscale y 10')
## g('set yrange [0.0001:1]')
## g('set xrange [1:2500]')
## g('set data style linespoints')
## g('set ylabel "CCDF" 1.5, 0')
## g('set xlabel "Degree" 0, .5')
## g('set terminal x11')
## g.plot(Gnuplot.Data(ccdf))
## latex("ccdf.tex")

global transits
transits = {}
for x in connectivity.keys():
    transits[x] = Set()

for path in aspaths:
    p = list(path)
    maxDegree = max([len(connectivity[x]) for x in p])
    for x in path:
        if len(connectivity[x]) == maxDegree:
            hilltop = p.index(x)
        
    for i in range(len(p)):
        if (i < hilltop):
            transits[p[i]].add(p[i+1])
        elif i > hilltop:
            transits[p[i]].add(p[i-1])

def relationship(a,b):
    if b in transits[a]:
        print a, " -> ", b
    if a in transits[b]:
        print a, " <- ", b