//
// point.cpp
//
// Functions to manipulate the point objects 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>


//
// constructor
//
point::point(int xcoord, int ycoord, map *m)
{
    assert(m != NULL);
    my_map = m;
    x = xcoord;
    y = ycoord;
    row = (y - Y_MIN) / LABEL_HEIGHT;
    col = (x - X_MIN) / LABEL_WIDTH;
    lposn = NONE;
    num_overlaps = 0;
    for (int n = 0; n < NUM_LABEL_POSNS; n++)
	poss_overlaps[n] = NULL;
    next = NULL;
}

//
// destructor
//
point::~point()
{
    overlap *trav, *temp;

    // Free up all of our overlap structs.
    for (int i = 0; i < NUM_LABEL_POSNS; i++) {
	trav = poss_overlaps[i];
	while (trav != NULL) {
	    temp = trav;
	    trav = trav->next;
	    delete temp;
	}
    }
}

//
// determine_possible_overlaps - initialize the poss_overlaps array
// for this point.  After it is called, poss_overlaps[n] will contain
// a linked list of overlap structs, each of which contains
// information about possible overlaps that can occur when this
// point's label is in position n.  See the definition of the overlap
// struct in map.hpp for more info.
//
void
point::determine_possible_overlaps()
{
    point *trav;
    overlap *olap;
    int overlaps;

    // boundaries of the range of cells containing points that we
    // could possibly overlap.  Note that we make sure not to go
    // beyond the edges of the map.
    int min_row = (row - 2 < 0 ? 0 : row - 2);
    int max_row = (row + 2 >= NUM_ROWS ? NUM_ROWS - 1 : row + 2);
    int min_col = (col - 2 < 0 ? 0 : col - 2);
    int max_col = (col + 2 >= NUM_COLS ? NUM_COLS - 1 : col + 2);

    // Iterate over the cells in this range.
    for (int r = min_row; r <= max_row; r++) {
	for (int c = min_col; c <= max_col; c++) {
	    
	    // Iterate over the points in each cell.
	    trav = my_map->points[r][c];
	    while (trav != NULL) {
		// Consider all possible combinations of
		// the label positions for us and trav,
		// and determine if they would lead
		// to an overlap.
		for (int n = 0; n < NUM_LABEL_POSNS; n++) {
		    overlaps = 0;
		    for (int m = 0; m < NUM_LABEL_POSNS; m++) {
			if (would_overlap((label_posn) n,
					  trav, (label_posn) m)) {
			    // Update the overlap bitmap that will be	
			    // will be used for this point.
			    overlaps |= (1 << m);
			}
		    }

		    if (overlaps != 0) {
			olap = new overlap;
			olap->pt = trav;
			olap->overlap_positions = overlaps;
			
			// Insert at front of appropriate poss_overlaps list.
			olap->next = poss_overlaps[n];
			poss_overlaps[n] = olap;
		    }
		}
		
		// Move onto the next point in this cell.
		trav = trav->next;
	    }
	}
    }
}

//
// would_overlap - if you put this point's label in position "my_posn"
// and the label of the point specified by "other" in "other_posn,"
// would the two labels overlap?
//
bool
point::would_overlap(label_posn my_posn, point *other, label_posn other_posn)
{
    int my_xmin, my_xmax, my_ymin, my_ymax;
    int other_xmin, other_xmax, other_ymin, other_ymax;
    bool left, right, top, bottom, overlap;

    // Don't compare a point with itself.
    if (other == this)
	return false;

    // Determine the boundaries of this label if it were given
    // the position specified by my_posn.
    my_xmin = my_xmax = x;
    my_ymin = my_ymax = y;
    if (my_posn == UR || my_posn == LR)
	my_xmax += LABEL_WIDTH;
    else if (my_posn == UL || my_posn == LL)
	my_xmin -= LABEL_WIDTH;
    if (my_posn == UR || my_posn == UL)
	my_ymax += LABEL_HEIGHT;
    else if (my_posn == LR || my_posn == LL)
	my_ymin -= LABEL_HEIGHT;

    // Determine the boundaries of the other point's label if it
    // were given the position specified by other_posn.
    other_xmin = other_xmax = other->x;
    other_ymin = other_ymax = other->y;
    if (other_posn == UR || other_posn == LR)
	other_xmax += LABEL_WIDTH;
    else if (other_posn == UL || other_posn == LL)
	other_xmin -= LABEL_WIDTH;
    if (other_posn == UR || other_posn == UL)
	other_ymax += LABEL_HEIGHT;
    else if (other_posn == LR || other_posn == LL)
	other_ymin -= LABEL_HEIGHT;

    // There will be an overlap if any corner of this point's
    // label would fall within the other point's label.
    left =   ((my_xmin >= other_xmin)  &&  (my_xmin <= other_xmax));
    right =  ((my_xmax >= other_xmin)  &&  (my_xmax <= other_xmax));
    top =    ((my_ymax >= other_ymin)  &&  (my_ymax <= other_ymax));
    bottom = ((my_ymin >= other_ymin)  &&  (my_ymin <= other_ymax));
    overlap = ((left && top)  ||  (left && bottom)  ||
	       (right && top)  ||  (right && bottom));

    return overlap;
}

//
// set_label_posn - make the position of this point's label be
// "new_posn," and update the num_overlap fields of both this point
// and its neighbors.  Return the resulting change in the score
// (i.e., the change in the number of labels involved in overlaps).
//
int
point::set_label_posn(enum label_posn new_posn)
{
    int change_in_score = 0;
    overlap *trav;

    // First decrement the num_overlaps fields of points with labels
    // that overlap this point's label in its current position.
    if (num_overlaps > 0) {
	assert(lposn != NONE);
	
	trav = poss_overlaps[lposn];
	while (trav != NULL) {
	    // Is there currently an overlap with trav->pt's label?
	    // This will be the caseif the current position of its label
	    // is a member of the overlap_positions bitset for this
	    // overlap struct.  We check for this possibility using
	    // bitwise AND. 
	    if ((1 << trav->pt->lposn) & trav->overlap_positions) {
		num_overlaps--;
		trav->pt->num_overlaps--;
		
		// If either label is now free of overlaps, the
		// score will go down by one.
		if (num_overlaps == 0)
		    change_in_score -= 1;
		if (trav->pt->num_overlaps == 0)
		    change_in_score -= 1;
	    }

	    trav = trav->next;
	}
    }

    // Now increment the num_overlaps fields of points with labels
    // that will overlap this point's label in its new position.
    if (new_posn != NONE) {
	trav = poss_overlaps[new_posn];
	while (trav != NULL) {
	    // Will there be an overlap with trav->pt's label?
	    // There will be if the current position of its label
	    // is a member of the overlap_positions bitset.  We check
	    // for this possibility using bitwise AND.
	    if ((1 << trav->pt->lposn) & trav->overlap_positions) {
		num_overlaps++;
		trav->pt->num_overlaps++;
		
		// If either label used to be free of overlaps, the
		// score will go up by one.
		if (num_overlaps == 1)
		    change_in_score += 1;
		if (trav->pt->num_overlaps == 1)
		    change_in_score += 1;
	    }

	    trav = trav->next;
	}
    }

    // Set the position.
    lposn = new_posn;

    return change_in_score;
}

//
// change_in_score - determine the change in score (i.e., the
// change in the number of labels involved in overlaps) that would
// result if this point's label were in position "changed_posn," but
// don't actually change its position.
//
int
point::change_in_score(label_posn changed_posn)
{
    label_posn current_posn;
    int change;

    // Store label's current position.
    current_posn = lposn;

    // Temporarily change label's position to see
    // what the change in score would be.
    change = set_label_posn(changed_posn);

    // Put label back where it was.
    set_label_posn(current_posn);

    return change;
}
