//
// label.hpp
//
// Main program for the programming contest on cartographic label placement.
//
// Label placement algorithm by...
//
//
// Base code copyright (c) 2000 by Dave Sullivan
// Written for Computer Science S-111 at Harvard University
//

#include "map.hpp"
#include <iomanip.h>
#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//
// PUT ANY HELPER FUNCTIONS FOR YOUR LABELING FUNCTION HERE.
//

//
// YOUR LABELING FUNCTION GOES HERE.  IT SHOULD RETURN THE
// RESULTING SCORE.  SEE RANDOM_LABEL() BELOW FOR A MODEL.
//

//  label_posn { UR, LR, UL, LL, NONE };

int russ_label(map *m)
{
    point *trav = m->first_point();
    
    int currentScore;							// score tracer
    int newScore;
    		
    while (trav != NULL) {
    
		currentScore = m->score();				// find current score
		
		// loop through all possible label positions
		for (int i = 0; i < NUM_LABEL_POSNS; i++) {
		
			// set new label pos
			trav->set_label_posn( (label_posn) i);
			
			// find new score
			newScore = m->score();
			
			// if newScore == currentScore then label OK
			if ( currentScore == newScore) {	// pt placed cleanly
				break;							// so exit loop
			}
		}
		
		trav = m->next_point(trav);				// mv to next pt
    }

    return m->score();
}



//
// random_label - pick a random label position for each point in 
// the map pointed to by m.  Return the resulting score.
//
int random_label(map *m)
{
    label_posn lposn;
    point *trav = m->first_point();
    
    while (trav != NULL) {
		lposn = (label_posn) (rand() % NUM_LABEL_POSNS);
		trav->set_label_posn(lposn);
		trav = m->next_point(trav);
    }

    return m->score();
}

//
// add_points - add points to the map pointed to by m.
// - points_target is the number of points that we're supposed to have.
// - filename is either the file from which the points should be read,
//   the file to which the generated points should be saved, or NULL,
//   in which case we generate the points but don't save them.
// We return the number of points that were added to the map.  If we
// read in the points from a file, this may be different than points_target.
//
int add_points(int points_target, char *filename, map *m, bool verbose)
{
    int points_added = 0;

    // If a filename has been specified, try to read the points from it.
    if (filename != NULL) {
	points_added = m->read_points(filename);
	if (points_added > 0  &&  verbose) {
	    cout << endl << "Read " << points_added
		 << " points from " << filename << endl;
	}
    }

    // If we haven't read any points, generate them instead.
    if (points_added == 0) {
	if (verbose) {
	    cout << endl << "Generating " << points_target
		 << " random points..." << endl;
	}
	m->generate_points(points_target);
	
	// If the user specified a file with no points in it,
	// that means that we should store the generated points there.
	if (filename != NULL) {
	    m->write_points(filename);
	    if (verbose)
		cout << "Points are saved in "
		     << filename << endl;
	}
	
	points_added = points_target;
    }

    return points_added;
}

int main(int argc, char* argv[])
{
    bool verbose;
    int num_points, base, score;
    char rand_filename[80], my_alg_filename[80];

    // Make sure that the user has at least specified the number of
    // points. 
    if (argc < 2) {
	cout << "Usage: label num_pts [filename]" << endl;
	exit(-1);
    }

    // Seed the random number generator with the time so that we don't
    // always get the same sequence of random numbers.
    srand((unsigned int) time(NULL));

    // Verbose results messages?  The user can specify -q after the
    // filename (or anything, for that matter) to turn these off.
    verbose = (argc <= 3);

    // Create the map, add the points to it, and precompute
    // all of the possible overlaps for each point.
    map *the_map = new map;
    num_points = add_points(atoi(argv[1]), argv[2], the_map, verbose);
    the_map->determine_possible_overlaps();

    //
    // Use random as a baseline.
    // Hopefully, your algorithm will do better!
    //
    base = random_label(the_map);
    sprintf(rand_filename, "random%d.ps", num_points);
    the_map->generate_postscript(rand_filename);
    if (verbose) {
	cout << endl;
	cout << "Random labels:   score = "
	     << setw(5) << setiosflags(ios::right) << base
	     << "/" << num_points
	     << "     file = " << rand_filename << endl;
    } else {
	cout << setw(25) << setiosflags(ios::left) << argv[2]
	     << setw(5) << setiosflags(ios::right) << base;
    }

    //
    // Now try your algorithm.
    // MODIFY THE SECOND LINE BELOW TO CALL YOUR FUNCTION!!
    //
    the_map->remove_labels();
    score = russ_label(the_map);
    sprintf(my_alg_filename, "my_alg%d.ps", num_points);
    the_map->generate_postscript(my_alg_filename);
    if (verbose) {
	cout << "My algorithm:    score = "
	     << setw(5) << setiosflags(ios::right) << score
	     << "/" << num_points
	     << "     file = " << my_alg_filename << endl << endl;
    } else {
	cout << setw(5) << setiosflags(ios::right) << score
	     << setw(5) << setiosflags(ios::right) << num_points
	     << endl;
    }

    // Clean up.
    delete the_map;
}
