#!/usr/bin/awk -f
# get free coordinate to place a new icon on rox pinboard
# (C) James Budiono 2013
# License: GNU GPL Version 3 or later.
#
# input: see *configuration* section below

#########################
### helper functions ####

# convert grid-index to screen coordinates
# in: x, vert, xgrid, ygrid, left, top, cellx, celly
# out: xy[0] = x-coord, xy[1] = y-coord
function grid_to_coord(x, xy) {
	if (vert) {
		xy[0] = int (x / celly ) * xgrid + left;
		xy[1] = int (x % celly ) * ygrid + top;
	} else {
		xy[0] = int (x % cellx ) * xgrid + left;
		xy[1] = int (x / cellx ) * ygrid + top;
	}
}

# convert screen coordinates to grid-index
# in: x, y, cellx, celly, xgrid, ygrid, windx, windy
# out: return value is grid-index
function coord_to_grid(x,y) {
	x = x - left; y = y - top;
	
	# don't go off-screen 
	if (x < 0) x = 0; 
	if (y < 0) y = 0; 
	if (x > windx) x = windx; 
	if (y > windy) y = windy;
	
	if (vert) return int (y / ygrid) + int ( x / xgrid ) * celly;
	else return int (x / xgrid) + int ( y / ygrid ) * cellx; 
}

# get distance between z2 and z1 in terms of cells
# in: z1, z2 (cell grid-index), cellx, cellt
function get_distance (z1, z2, dxy) {
	z2 -= z1;
	if (vert) {
		dxy[0] = int ( z2 / celly ) # x distance
		dxy[1] = z2 % celly # y distance	
	} else {
		dxy[0] = z2 % cellx # x distance
		dxy[1] = int ( z2 / cellx ) # y distance
	}
}

# DEBUG: display the grid used for calculation
# in: cells, cellx, celly, vert
function print_grid() {
	if (!debug) return;
	if (vert) {
		for (j=0; j < celly; j++) {
			for (k=0; k < cellx; k++) 
				if (cells [k * celly + j] == 1) printf "*";
				else if (cells [k * celly + j] == 2) printf "s";
				else if (cells [k * celly + j] == 3) printf "x";
				else printf "-"; 
			print ""
		}	
	} else {
		for (j=0; j < celly; j++) {
			for (k=0; k < cellx; k++) 
				if (cells [j * cellx + k] == 1) printf "*";
				else if (cells [j * cellx + k] == 2) printf "s";
				else if (cells [j * cellx + k] == 3) printf "x";
				else printf "-"; 
			print ""
		}
	}
}

BEGIN {
	### *configuration* - should be set externally
	# debug = 0; # set to 1 to print output grid
	if (!pinboard) pinboard = "/dev/null"; # so it doesn't stall on input
	if (!xgrid) xgrid = 64;	# grid size - should be bigger than icon size
	if (!ygrid) ygrid = 64;	
	if (!xicon) xicon = 48; # estimated icon size
	if (!yicon) yicon = 52;
	if (!top) top = 32;     # margins
	if (!bottom) bottom = 64; 
	if (!left) left = 32; 
	if (!right) right = 64;
	if (!align) align = "bottom" # or "bottom" or "left" or "right"
	
	############
	### main ###
	
	# 1. get screen dimensions
	while ("xwininfo -root" | getline) {
		if ($1 == "Width:") xwin = $2
		if ($1 == "Height:") ywin = $2
	}
	close ("xwininfo -root")
	
	# 2. calc grid parameters	
	# exclude the margins
	windx = xwin - left - right; 
	windy = ywin - top - bottom;
	
	# number of cells
	cellx = int ( windx / xgrid )+1; # how many cells in x-coord
	celly = int ( windy / ygrid )+1; # how many cells in y-coord
	cellmax = celly * cellx; # total number of cells
	
	# convert icon size to number of cells
	xiconoffset = int (xicon/2);
	yiconoffset = int (yicon/2);
		
	# 3. calc search parameters based on "align"
	vert = 0;        # 0 for horizontal, 1 for vertical	
	divisor = cellx; # each "row of cell" consist of cellx's cells
	if (align == "left" || align == "right") {
		vert = 1;   # vertical mode
		divisor = celly; # each "row of cell" consist of celly's cells
	}
	
	if (align == "left" || align == "top") {
		nextline = 0;  # go to next line
		start = 0;
	} else {
		nextline = -2; # go to previous line
		if (vert) start = (cellx - 1 ) * celly;
		else start = (celly - 1) * cellx;
	}
	#print cellx, celly, cellmax, nextline, start;
	
	# 4. mark used cells from existing pinboard
	while (getline < pinboard) {
		if (match ($0,/<icon/)) {
			split($2,x,"\"");
			split($3,y,"\"");
			
			# get the bounding rectangle
			cx = x[2]-xiconoffset;
			cy = y[2]-yiconoffset;
			ex = x[2]+xiconoffset;
			ey = y[2]+yiconoffset;
			
			# compute the bounding rectangle in term of grid-index
			z1 = coord_to_grid(cx, cy);
			z2 = coord_to_grid(ex, ey);
			
			# get the grid-index distances of the bounding rectangles
			get_distance(z1, z2, dxy);
			
			# and mark cells in between them as "used"
			for (j=0; j <= dxy[1]; j++)
				for (k=0; k <= dxy[0]; k++)
					if (vert) cells [z1 + k * celly + j] = 1;
					else cells [z1 + j * cellx + k] = 1;
			
			# DEBUG: print coord, indexes and distances
			#grid_to_coord(z1, xy); grid_to_coord(z2, xy2); 
			#print x[2], y[2], z1, z2, xy[0], xy[1], xy2[0], xy2[1], dxy[0], dxy[1] #, cx, cy, ex, ey
		}
	}
	
	# DEBUG: stress test
	#for (i=start; i<start+cellx; i++) cells[i]=1; # fill bottom
	#for (i=start; i<start+celly; i++) cells[i]=1; # fill right
	
	# 5. now get new free coord - as simple as finding an empty cell
	while (1) {
		if ( ! cells [ start ] ) break;
		cells [ start ] = 2;	# debug, for visualising search steps
		start++ 
		if (! (start % divisor) )
		start = start + nextline * divisor;
		if (start < 0 || start > cellmax) break;
	}
	cells [ start ] = 3;	# debug, for visualising found locatation
	
	# DEBUG: print the final grid
	print_grid();
	
	# 6. output
	grid_to_coord( start, xy );
	print xy[0]+xiconoffset, xy[1]+yiconoffset; 
	
	# 7. finish
	exit # don't ask for input
}
