//
// map.cpp
//
// Functions to maintain the maps used in the programming contest
// on cartographic label placement.
//
// Copyright (c) 2000 by Dave Sullivan
// Written for Computer Science S-111 at Harvard University
//

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


//
// constructor
//
map::map()
{
    for (int r = 0; r < NUM_ROWS; r++) {
	for (int c = 0; c < NUM_COLS; c++) {
	    points[r][c] = NULL;
	    num_points[r][c] = 0;
	}
    }

    total_points = 0;
}

//
// destructor
//
map::~map()
{
    clear();
}

//
// add_point - creates an object to represent a point feature at
// coordinates (x, y), and adds it to the appropriate list of points.
//
void
map::add_point(int x, int y)
{
    // Create and initialize the point.
    point *pt = new point(x, y, this);

    // Sanity check.
    assert(pt->row >= 0  &&  pt->row < NUM_ROWS  &&
	   pt->col >= 0  &&  pt->col < NUM_COLS);

    // Add it to the front of the list of points for the
    // appropriate cell of the map.
    int r = pt->row;
    int c = pt->col;
    pt->next = points[r][c];
    points[r][c] = pt;
    num_points[r][c]++;
    total_points++;
}

//
// first_point - return a pointer to the "first" point in the map.
// The comments below for next_point() describe how this method
// can be used.
//
point *
map::first_point()
{
    // We just return the point at the front of the list
    // of the first cell that has points in it.
    for (int r = 0; r < NUM_ROWS; r++) {
	for (int c = 0; c < NUM_COLS; c++) {
	    if (points[r][c] != NULL) 
		return points[r][c];
	}
    }

    return NULL;
}

//
// next_point - return the "next" point in the map after the one pointed to
// by pt.  By starting with first_point() and repeatedly calling next_point(),
// you can iterate over all of the points in the map.  After all points
// have been seen, next_point() will return NULL.
//
point *
map::next_point(point *pt)
{
    if (pt == NULL)
	return NULL;
    else if (pt->next != NULL) {
	// Return the next point in this cell.
	return pt->next;
    }
    else {   // The cell that pt belongs to has no more points in it.
	int col = pt->col;
	int row = pt->row;
	
	// Move on to the next cell with points in it.
	do {
	    col++;

	    // Wrap around to the next row if needed.
	    if (col == NUM_COLS) {
		col = 0;
		row++;
		if (row == NUM_ROWS)
		    return NULL;
	    }
	} while (points[row][col] == NULL);

	return points[row][col];
    }
}

//
// first_point_in_cell - return a pointer to the front of the
// list of points for the cell with the specified row and column
// numbers.  If there are no points in that cell, return NULL.
//
point *
map::first_point_in_cell(int row, int col)
{
    // Sanity check.
    assert(row >= 0  &&  row < NUM_ROWS  &&
	   col >= 0  &&  col < NUM_COLS);

    return points[row][col];
}

//
// num_points_in_cell - return the number of points in the cell with
// the specified row and column numbers.
//
int
map::num_points_in_cell(int row, int col)
{
    // Sanity check.
    assert(row >= 0  &&  row < NUM_ROWS  &&
	   col >= 0  &&  col < NUM_COLS);
    
    return num_points[row][col];
}    

//
// determine_possible_overlaps - once all of the points have been
// added, this function is used to initialize all of their poss_overlaps
// arrays.
//
void
map::determine_possible_overlaps()
{
    point *trav = first_point();
    while (trav != NULL) {
	trav->determine_possible_overlaps();
	trav = next_point(trav);
    }
}    

//
// score - determine the number of points involved in overlaps.
//
int
map::score()
{
    int score = 0;

    point *trav = first_point();
    while (trav != NULL) {
	if (trav->num_overlaps > 0)
	    score++;
	trav = next_point(trav);
    }

    return score;
}

//
// read_points - read a file containing a list of point coordinates 
// and add the points to the map.  Return the number of points read.
//
int
map::read_points(char *filename)
{
    int x, y, num_read;

    ifstream pts_file(filename, ios::in | ios::nocreate);
    if (pts_file == NULL) 
	return 0;

    num_read = 0;
    do {
	pts_file >> x;
	if (! pts_file.eof()) {
	    pts_file >> y;
	    add_point(x, y);
	    num_read++;
	}
    } while (! pts_file.eof());

    return num_read;
}

//
// write_points - write the coordinates of the points on the map to a file,
// with one point per line.
//
void
map::write_points(char *filename)
{
    ofstream out_file(filename);

    if (out_file == NULL) {
	cout << "Could not open file: " << filename << endl;
	return;
    }
    
    point *trav = first_point();
    while (trav != NULL) {
	out_file << trav->x << " " << trav->y << endl;
	trav = next_point(trav);
    }
}

//
// generate_points - add n points at random locations on the map. 
//
void
map::generate_points(int num_pts)
{
    int x, y;

    for (int i = 0; i < num_pts; i++) {
	do {
	    x = X_MIN + LABEL_WIDTH + (rand() % MAP_WIDTH);
	    y = Y_MIN + LABEL_HEIGHT + (rand() % MAP_HEIGHT);
	} while (existing_point(x, y));
	
	add_point(x, y);
    }
}

//
// existing point - is there already a point with the specified
// coordinates on the map?
//
bool
map::existing_point(int x, int y)
{
    int row = (y - Y_MIN) / LABEL_HEIGHT;
    int col = (x - X_MIN) / LABEL_WIDTH;
    
    point *trav = points[row][col];
    while (trav != NULL) {
	if (trav->x == x  &&  trav->y == y)
	    return true;
	trav = trav->next;
    }

    return false;
}

//
// clear - remove all points from the map
//
void
map::clear()
{
    point *trav, *temp;

    for (int r = 0; r < NUM_ROWS; r++) {
	for (int c = 0; c < NUM_COLS; c++) {
	    trav = points[r][c];
	    while (trav != NULL) {
		temp = trav;
		trav = trav->next;
		delete temp;
	    }

	    points[r][c] = NULL;
	    num_points[r][c] = 0;
	}
    }
}

//
// remove_labels - remove all labels from the map
//
void
map::remove_labels()
{
    point *trav = first_point();
    while (trav != NULL) {
	trav->lposn = NONE;
	trav->num_overlaps = 0;
	trav = next_point(trav);
    }
}

//
// generate_postscript - create a Postscript file for the map
//
bool
map::generate_postscript(char * filename)
{
    // Copy the Postscript functions for drawing
    // a point and a label.
    char command[80];
    sprintf(command, "cp %s %s", HEADER_FILE, filename);
    system(command);

    // Open the file.
    ofstream ps_file(filename, ios::app);
    if (ps_file == NULL) {
	cout << "Could not open file: " << filename << endl;
	return false;
    }

    // Output the Postscript commands for the individual
    // points and labels.
    draw_labels(ps_file);
    draw_points(ps_file);

    // PS commands to print the score at the bottom of the map.
    ps_file << endl << "/Helvetica findfont" << endl;
    ps_file << "12 scalefont" << endl;
    ps_file << "setfont" << endl << endl;
    ps_file << "50 20 moveto" << endl;
    ps_file << "(score: " << score();
    ps_file << " overlapped labels out of ";
    ps_file << get_total_points() << ") show" << endl << endl;

    ps_file << "showpage" << endl;
    return true;
}

//
// draw_labels - generate the Postscript commands to draw the labels
//
void
map::draw_labels(ofstream &file)
{
    point *trav = first_point();

    while (trav != NULL) {
	if (trav->lposn != NONE) {
	    // Indicate whether the box representing the label 
	    // should be shaded. 
	    if (trav->num_overlaps > 0)
		file << "false ";             
	    else
		file << "true ";            
	    
	    // Output coordinates.
	    file << trav->x << " " << trav->y << " ";
	    
	    // Output appropriate function for label.
	    switch (trav->lposn) {
	    case UL:
		file << "UL_label";
		break;
	    case UR:
		file << "UR_label";
		break;
	    case LL:
		file << "LL_label";
		break;
	    case LR:
		file << "LR_label";
		break;
	    default:
		break;
	    }
	}
	file << endl;
	
	trav = next_point(trav);
    }
}

//
// draw_points - generate the Postscript commands to draw the points
//
void
map::draw_points(ofstream &file)
{
    point *trav = first_point();

    while (trav != NULL) {
	if (trav->lposn != NONE) 
	    file << trav->x << " " << trav->y
		 << " draw_point" << endl;

	trav = next_point(trav);
    }
}
