#!/bin/gawk -f
#
# 			Automatic keyboard layout
#		http://www.freaknet.org/alpt/src/misc/akl/akl.awk
#
# --
#
# A program which, given a text as input, computes the most efficient keyboard
# layout for the given text.
#
# "Most efficient keyboard layout" means a layout which permits to write the
# given text in the fastest and easiest way. 
#
# *** Usage
#
# 	./akl.awk < input | less -R
# 
# Note: the non printable ASCII character are printed in their hexadecimal
# form.
#
# *** Example
#
#$ echo idiki the wiki | ./akl.awk 
#,___________________.
#|___|___|___|___|___|
#|___|_t_|_d_|___|___|
#|___|_h_|_i_|_w_|___|
#|___|_e_|_k_|_ _|___|
#|___|___|___|___|___|
#
#,_______________________.
#|___|___|___|___|___|___|
#|___|___|_t_|_h_|_e_|___|
#|___|___|_d_|_i_|_k_|___|
#|___|___|___|_w_|_ _|___|
#|___|___|___|___|___|___|
#
# *** Algorithm
#	
#	- build the frequency list for each pair of keys
#	
#	- sort the list and traverse it, starting from the most frequent
#	  pair
#
#		- Let (a,b) be the current pair
#
#		- If  a  has been previously added in the layout matrix, set
#		  p=coordinates_of_a
#
#		- If  a  doesn't exists in the layout matrix, try the swapped
#		  pair: t=b, b=a, a=t
#
#		- If  a  still doesn't exist, find the a key  p  in the
#		  layout matrix such that (p,a) is an existing pair and the
#		  frequency of (p,a) is higher than (x,a), for any valid
#		  x.
#
#		- Find, in the layout matrix, the nearest empty points to  p.
#
#		- Choose the nearest empty point  e  to  p  in term of
#		  frequency, i.e. (e,p) must be higher than any other (e',p).
#
#		- Add  b  in  e.
#
# 
# AlpT (@freaknet.org)
# 


# ord.awk --- do ord and chr
# Global identifiers:
#    _ord_:        numerical values indexed by characters
#    _ord_init:    function to initialize _ord_
#
# Arnold Robbins, arnold@gnu.org, Public Domain
# 16 January, 1992
# 20 July, 1992, revised
BEGIN    { _ord_init() }

function _ord_init(    low, high, i, t)
{
    low = sprintf("%c", 7) # BEL is ascii 7
    if (low == "\a") {    # regular ascii
        low = 0
        high = 127
    } else if (sprintf("%c", 128 + 7) == "\a") {
        # ascii, mark parity
        low = 128
        high = 255
    } else {        # ebcdic(!)
        low = 0
        high = 255
    }

    for (i = low; i <= high; i++) {
        t = sprintf("%c", i)
        _ord_[t] = i
    }
}
function ord(str,    c)
{
    # only first character is of interest
    c = substr(str, 1, 1)
    return _ord_[c]
}
function chr(c)
{
    # force c to be numeric by adding 0
    return sprintf("%c", c + 0)
}



function frequencies(str,         i,a,b)
{
	strl=length(str)

	for(i=1; i<=strl-1; i++) {
		a=substr(str, i,1)
		b=substr(str, i+1,1)

		freq[a,b]++
		freq[b,a]++
		singlefreq[a]++
	}
}

function buildmatrix(              i, maxf, maxfi, idx)
{
	# Choose the most frequent key and put it in x=0,y=0
	maxf=0
	for(i in singlefreq) {
		if(singlefreq[i] >= maxf) {
			maxf=singlefreq[i]
			maxfi=i
		}
	}
	layout[0,0]=maxfi
	hl[maxfi]=(0 SUBSEP 0)

	# Sort the `freq' array
	for(i in  freq) {
		if((freq[i]) in freqi)
			freqi[freq[i]]=(freqi[freq[i]] ":J:" i)
		else
			freqi[freq[i]]=(i)
	}
	n = asorti(freqi, freqis)

	# Traverse the sorted array
	for(i=n; i>=1; i--) {
		idx=freqis[i]
		e=split(freqi[idx], links, ":J:")
		for(x=1; x<=e; x++) {
			if(split(links[x], a, SUBSEP) >= 2) {
				add_layout(a[1], a[2])
			}
		}
	}
}

function add_layout(a, b, 	d, i, max, x, y, pxy, fxy, f, xx,yy,p,r)
{

	if(!((a) in hl)) {
		t=a
		a=b
		b=t
	}
	
	if(!((a) in hl)) {
		max=0
		p=""
		for(i in layout) {
			if(!((a,layout[i]) in freq))
				continue

			f=freq[a,layout[i]]
			if(max < f) {
				max=f
				p=i
			}
		}
		if(!p)
			p=(0 SUBSEP 0)
		#print "add_layout2 ", layout[p], a, p
		add_layout(layout[p], a)
	}

	if(((b) in hl)) {
		#print "'"b"' rejected"
		return 0
	}

	p=hl[a]
	split(p, pxy, SUBSEP)
	#print "add_layout ", "'"a"'", "'"b"'", pxy[1], pxy[2]

	for(r=1;  ; r++) {
		f=0
		delete foundxy

		y=pxy[2]
		for(x=pxy[1]-r+1; x <= pxy[1]+r-1; x++) {
			if(((x, y-r) in layout) && ((x, y+r) in layout))
				continue

			if(!((x, y-r) in layout)) {
				foundxy[++f]=(x SUBSEP y-r)
			} else if(!((x, y+r) in layout)) {
				foundxy[++f]=(x SUBSEP y+r)
			}
		}

		x=pxy[1]
		for(y=pxy[2]-r+1; y <= pxy[2]+r-1; y++) {
			if(((x-r, y) in layout) && ((x+r, y) in layout))
				continue

			if(!((x-r, y) in layout)) {
				foundxy[++f]=(x-r SUBSEP y)
			} else if(!((x+r, y) in layout)) {
				foundxy[++f]=(x+r SUBSEP y)
			}
		}

		if(!f) {
			#try the corners

			x=pxy[1]-r; y=pxy[2]-r
			if(!((x, y) in layout))
				foundxy[++f]=(x SUBSEP y)
			x=pxy[1]-r; y=pxy[2]+r
			if(!((x, y) in layout))
				foundxy[++f]=(x SUBSEP y)
			x=pxy[1]+r; y=pxy[2]-r
			if(!((x, y) in layout))
				foundxy[++f]=(x SUBSEP y)
			x=pxy[1]+r; y=pxy[2]+r
			if(!((x, y) in layout))
				foundxy[++f]=(x SUBSEP y)
		}

		if(f)
			break
	}

	max=0
	maxi=1
	for(i=1; i<=f; i++) {
		split(foundxy[i], fxy, SUBSEP)

		for(xx=-1; xx<=1; xx++)
			for(yy=-1; yy<=1; yy++) {
				if(!((b, fxy[1]+xx,fxy[2]+yy) in layout))
					continue
				f=freq[b, layout[fxy[1]+xx,fxy[2]+yy] ]
				if(max < f) {
					max=f
					maxi=i
				}
			}
	}

	hl[b]=foundxy[maxi]
	layout[hl[b]]=b
	#print "new", foundxy[maxi], "'"b"'", layout[hl[b]]
}

function abs(n)
{
	return n >= 0 ? n : -n;
}

function c2c(c)
{
	if(c == "_" || c !~ /[[:print:]]/)
		c=sprintf("x%02x", ord(c))
	else
		c="_"toupper(c)"_"
	return c
}

function print_layout(       i,p, x,y, maxx, maxy,c)
{
	maxx=maxy=0
	for(i in layout) {
		split(i, p, SUBSEP)

		if(maxx < p[1])
			maxx=abs(p[1])*2
		if(maxy < p[2])
			maxy=abs(p[2])*2
	}

	printf(",")
	for(x=-maxx*5; x<=5*maxx-2; x++)
		printf("_")
	printf(".\n")
	for(y=+maxy; y>=-maxy; y--) {
		if((+maxx,y) in layout) {
			printf("|%s|", c2c(layout[+maxx,y]))
		} else
			printf("|___|")
		for(x=+maxx-1; x>=-maxx; x--) {
			if((x,y) in layout) {
				printf("%s|", c2c(layout[x,y]))
			} else
				printf("___|")
		}
		printf("\n")
	}
	printf("\n")

	printf(",")
	for(y=-maxy*5; y<=5*maxy+2; y++)
		printf("_")
	printf(".\n")
	for(x=+maxx; x>=-maxx; x--) {
		if((+maxx,y) in layout) {
			printf("|%s|", c2c(layout[+maxx,y]))
		} else
			printf("|___|")

		for(y=+maxy; y>=-maxy; y--) {
			if((x,y) in layout) {
				printf("%s|", c2c(layout[x,y]))
			} else
				printf("___|")
		}
		printf("\n")
	}
	printf("\n")
}

{
	INPUT=INPUT "\n" tolower($0)
}

END {
	frequencies(INPUT)
	buildmatrix()
	print_layout()
}