# -*- coding: utf-8 -*-
# multicoloring.py

import random
import time
import sys


class Log(object):
    '''Class for logging of the results 

    results.txt logs the results after each testrun
    nodes.txt   logs the nodes and their assigned colors after each testrun
    plot.txt    logs the averaged performance after one round of testruns
    '''
    def __init__(self, node):
        self._results = open(str(node) + "nodes-results.txt", "w")
        self._nodes = open(str(node) + "nodes-nodes.txt", "w")
        self._plot = open(str(node) + "nodes-plot.txt", "w")
    def results(self, s): 
        self._results.write(s + "\n")
        self._results.flush()
    def nodes(self, s): 
        self._nodes.write(s + "\n")
        self._nodes.flush()
    def plot(self, s): 
        self._plot.write(s + "\n")
        self._plot.flush()
    def all(self, s):
        self.results(s)
        self.nodes(s)
        self.plot(s)

class Request(object):

    current_request_id = 0

    def __init__(self):
        'Return a new Request with a unique ID.'
        Request.current_request_id += 1
        self.id = Request.current_request_id
        self.color = None
    def __repr__(self):
        return '<Request #%d, color: %s>' % (self.id, str(self.color))


class Node(object):
    'Abstract base class for nodes.'

    def __init__(self, number):
        self.number = number

        # `prev` and `next` point to the neighboring nodes. You could actually
        # remove these two lines, since prev and next are assigned in
        # Line.__init__(). But this serves as a reminder that a nodes needs
        # these attributes.
        self.prev = None
        self.next = None

    def __str__(self): return self.__repr__()


class GreedyNode(Node):
    'A node which assigns colors using the Greedy algorithm.'

    def __init__(self, number):

        # Call __init__ of superclass, since we overwrite it here.
        Node.__init__(self, number)

        # A greedy node has one bucket
        self.bucket = set()

    def __repr__(self):
        return '<Node #%d: %s>' % (self.number, sorted(list(self.used_colors())))
        
    def max_number_of_requests_at_neighboring_pair(self):
        number_of_own_requests = len( self.bucket )
        left_neighbor = right_neighbor = 0
        if self.prev: left_neighbor = len( self.prev.bucket ) 
        if self.next: right_neighbor = len( self.next.bucket ) 
        return max( left_neighbor, right_neighbor ) + number_of_own_requests

    def used_colors(self):
        return set([req.color for req in self.bucket if req.color is not None])
        
    def used_requests(self, number):
        return set([req for req in self.bucket if req.color is not None])

    def used_colors_incl_neighbors(self):
        uc = self.used_colors()
        if self.prev: uc = uc.union(self.prev.used_colors())
        if self.next: uc = uc.union(self.next.used_colors())
        return uc

    def free_color(self):
        'Return the next free color not used by this node or its neighbors'
        uc = self.used_colors_incl_neighbors()
        c = 1
        while True:
            if c in uc: c += 1
            else: return c
        
    def handle_request(self, request):
        self.bucket.add(request)
        request.color = self.free_color()
        return request.color


class FourBucketNode(Node):
    'A node which assigns colors using the 4-bucket algorithm.'

    def __init__(self, number):
        Node.__init__(self, number)

        # A 4-bucket node has three buckets
        bucket_numbers = [n for n in range(4) if n != number % 4]
        self.buckets = dict([(bn, set()) for bn in bucket_numbers])

    def __repr__(self):
        bucket_str = ['%d:%s' % (bucket, sorted(list(reqs)))
                      for bucket, reqs in self.buckets.items()]
        return '<Node #%d: %s>' % (self.number, ' '.join(bucket_str))
        
    def max_number_of_requests_at_neighboring_pair(self):
        number_of_own_requests = sum( len( self.used_colors(bn) ) for bn in self.buckets )
        left_neighbor = sum( len( self.prev.used_colors(bn) ) for bn in self.prev.buckets ) if self.prev else 0
        right_neighbor = sum( len( self.next.used_colors(bn) ) for bn in self.next.buckets ) if self.next else 0
        return max( left_neighbor, right_neighbor ) + number_of_own_requests

    def used_colors(self, bucket_number):
        try:
            return set([req.color for req in self.buckets[bucket_number]
                        if req.color is not None])
        except KeyError:
            # bucket `bucket_numbber` not used by this node
            return set()

    def used_requests(self, bucket_number):
        try:
            return set([req for req in self.buckets[bucket_number]
                        if req.color is not None])
        except KeyError:
            # bucket `bucket_numbber` not used by this node
            return set()        
            
    def used_colors_incl_neighbors(self, bucket_number):
        uc = self.used_colors(bucket_number)
        if self.prev: uc = uc.union(self.prev.used_colors(bucket_number))
        if self.next: uc = uc.union(self.next.used_colors(bucket_number))
        return uc

    def number_of_emptiest_bucket(self):
        bucket_numbers = self.buckets.keys()
        eb = bucket_numbers[0]
        for b in bucket_numbers[1:]:
            if len(self.buckets[b]) < len(self.buckets[eb]): eb = b
        return eb

    def free_color(self, bucket_number):
        uc = self.used_colors_incl_neighbors(bucket_number)
        c = bucket_number
        if c is 0: c = 4
        while True:
            if c in uc: c += 4
            else: return c

    def handle_request(self, request):
        i = self.number_of_emptiest_bucket()
        self.buckets[i].add(request)
        request.color = self.free_color(i)
        return request.color

class Line(dict):
    '''A line of nodes.

    First and last nodes have only one neighbor.
    '''

    def __init__(self, num_nodes, node_class):
        '''Create `num_nodes` nodes of class `node_class`.

        The nodes are linked via their `prev` and `next` attributes (thus
        creating a linked list).
        '''
        dict.__init__(self)
        for i in range(1, num_nodes+1):
            n = node_class(number=i)
            if 1 < i: # we cannot link anything before the second node is created
                n.prev = self[i-1]
                n.prev.next = n # this is the same as: self.nodes[i-1].next = n
            self[i] = n
        self._rand = random.Random()
        self.maximum = 0
        self.optimum = 0
        self.used_colors = set([])

    def get_random_node(self):
        'Return a random node.'
        i = self._rand.randint(min(self.keys()),
                               max(self.keys()))
        if ( self[i].max_number_of_requests_at_neighboring_pair() + 1 ) > self.optimum: self.optimum = self[i].max_number_of_requests_at_neighboring_pair() + 1
        return self[i]

    def run(self, num_requests=1, seed=None):
        if seed: self._rand.seed(seed)
        self.maximum = 0
        self.optimum = 0
        self.used_colors = set([])
        for i in range(num_requests):
            color = self.get_random_node().handle_request(Request())
            self.used_colors.add(color)
            if self.maximum < color: self.maximum = color
        return ( self.optimum, self.maximum,  len( self.used_colors ))
       
def test( num_tests, num_nodes, num_requests, seed):
    'Defining one testrun.'

    log.results("Number of Nodes " + str(num_nodes))
    log.results("Number of Requests " + str(num_tests))

    seeds = random.Random()
    seeds.seed(seed)
    
    averageBucket = averageNum = averageGreedy = 0

    for run in range( num_tests ):
        round_seed = seeds.randint(1, num_nodes + 1)
        gnodes = Line( num_nodes, GreedyNode )
        ( opt_greedy, max_greedy, num_greedy ) =  gnodes.run(num_requests=num_requests, seed=round_seed)
        
        fbnodes = Line( num_nodes, FourBucketNode )
        ( opt_fb, max_fb, num_fb ) =  fbnodes.run(num_requests=num_requests, seed=round_seed)
        
        averageGreedy += 1.0*max_greedy/opt_greedy * 1.0/num_tests
        averageBucket += 1.0*max_fb/opt_fb * 1.0/num_tests
        averageNum += 1.0*num_fb/opt_fb * 1.0/num_tests
        
        log.results( ("Run Number: %d 4-Bucket/opt: %0.4f opt: %d 4-Bucket: %d 4-Bucket_no: %d")%(run+1, 1.0*max_fb/opt_fb, opt_fb, max_fb, num_fb) )
        log.nodes("Greedy: " + str(list(n for n in gnodes.values() ))  )
        log.nodes("4-Bucket: " + str(list(n for n in fbnodes.values() )) + "\n")
        
    log.plot("%d %d %f %f %f" %(num_nodes, num_requests, averageGreedy, averageBucket, averageNum))
    


if '__main__' == __name__:  
   
   seed = 30
   number_of_tests = 100
   number_of_nodes = [4,10,20,40,50]
   range_exponent = 10

   for nodes in number_of_nodes:
      log = Log(nodes)
      log.plot("#Nodes Requests Greedy 4Bucket 4Bucket-number")
      i = 0
      while i < range_exponent:
	 log.all("#" * 90)
         log.plot("#nodes: %d runs: %d seed: %f power: %d" %(nodes, number_of_tests, seed, i))
         test( number_of_tests, nodes, int(10*nodes*pow(2,i)), seed)
         test( number_of_tests, nodes, int(12.5*nodes*pow(2,i)), seed)
         test( number_of_tests, nodes, int(15*nodes*pow(2,i)), seed)
         test( number_of_tests, nodes, int(17.5*nodes*pow(2,i)), seed)
         i += 1
      test( number_of_tests, nodes, int(10*nodes*pow(2,i)), seed)