Accessibility Keyboard Demo
Note: This work was inspired by a similar feature of
Android's switchaccess. The original code is
here. You will want to in particular look at
HuffmanTreeBuilder.java and
PPMTrie.java
###############################################################################
# An implementation of a very basic typing interface designed for users with
# motor imparment who are not able to use a traditional keyboard but are rather
# rather constrained to using only one or two switches.
#
# In paricular this typing interface is designed to show how Huffman encoding
# can improve the typing efficiency of these users in particular if a good
# language model is utilized. Here we're using a naive language model that is
# based only on English letter frequencies. A better model would further
# illustrate how powerful Huffman encoding can be in improving the typing
# efficiency.
#
# Author: Rudina Morina (rmorina@andrew.cmu.edu)
##############################################################################
from Animation import Animation
from tkinter import *
import string
import heapq
def rgbString(red, green, blue):
return "#%02x%02x%02x" % (red, green, blue)
# A class utilized to build the huffman and the linear tree
class TreeNode(object):
def __init__(self, freq=None, char=None, left=None, right=None):
self.char = char
self.freq = freq
self.left = left
self.right = right
def isLeaf(self):
return (self.left == None and self.right == None)
# needed mainly for debugging purposes
def __repr__(self):
return "TreeNode(char=%s, freq=%s)" % (self.char, self.freq)
def __lt__(self, other):
return self.freq < other.freq
class TextBox(object):
def __init__(self, font, canvas, width, height):
self.font = font
self.canvas = canvas
self.width = width
self.height = height
self.typedSequence = ""
self.textMargin = 10
self.boxXMargin, self.boxYMargin = 50, 60
self.textBoxHeight = self.height/2 - 3*self.boxYMargin
self.textBoxWidth = self.width - 2*self.boxXMargin
def textSize(self, text):
temp = self.canvas.create_text(0, 0, text=text, anchor=NW, font=self.font)
(x0, y0, x1, y1) = self.canvas.bbox(temp)
self.canvas.delete(temp)
return (x1-x0, y1-y0)
def draw(self):
# draw the text box
textBoxLeft, textBoxTop = self.boxXMargin, self.boxYMargin
textBoxRight = textBoxLeft + self.textBoxWidth
textBoxBottom = textBoxTop + self.textBoxHeight
self.canvas.create_rectangle(textBoxLeft, textBoxTop, textBoxRight,
textBoxBottom)
# draw the text
textXStart = self.boxXMargin + self.textMargin
textYStart = self.boxYMargin + self.textMargin
maxCharHeight = 0
for char in self.typedSequence:
charWidth, charHeight = self.textSize(char)
maxCharHeight = max(charHeight, maxCharHeight)
if (textXStart + charWidth > textBoxRight - self.textMargin):
# filled the current line, move to the next line
textYStart += (maxCharHeight + self.textMargin)
textXStart = self.boxXMargin + self.textMargin
if (textYStart > textBoxBottom - self.textMargin):
print("The current page is filled")
return
self.canvas.create_text(textXStart, textYStart, text=char,
font=self.font, anchor=NW)
textXStart += charWidth
def addChar(self, char):
if (char == "_"):
# add space
self.typedSequence += " "
else:
self.typedSequence += char
class Keyboard(object):
KEYS = list(string.ascii_lowercase) + ["_"]
# scanning methods: linear and probability-based utilizing huffman encoding
HUFFMAN = "huffman"
LINEAR = "linear"
# we're utilizing binary trees to create the huffman and linear encoding so
# the keys of a keyboard are seperated into two buckets.
LEFT = "left"
RIGHT = "right"
def __init__(self, canvas, width, height, languageModel=None):
self.languageModel = languageModel
self.keyboardContent = [
Keyboard.KEYS[0 : 10],
Keyboard.KEYS[10 : 19],
Keyboard.KEYS[19 : ]
]
self.canvas = canvas
self.width = width
self.height = height
self.unreachableKeys = set()
self.rightKeys = set()
self.leftKeys = set()
self.scanningMethod = Keyboard.LINEAR
self.leftKeysColor = rgbString(204, 255, 204) # light green
self.rightKeysColor = rgbString(255, 255, 255) # white
def draw(self):
xMargin, yMargin, keyMargin = 50, 100, 10
keyboardX, keyboardY = xMargin, self.height/2 + yMargin
#TODO: fix the magic numbers
keySize = (self.width - 2*xMargin - 9*keyMargin) / 10
rowMargin = keySize / 3
for row in range(len(self.keyboardContent)):
keyboardX += row*rowMargin
for col in range(len(self.keyboardContent[row])):
curChar = self.keyboardContent[row][col]
curKeyX = keyboardX + (keySize + keyMargin)*col
curKeyY = keyboardY + (keySize + keyMargin)*row
rectFill = rgbString(255, 255, 255)
border = rgbString(0, 0, 0)
if curChar in self.leftKeys:
rectFill = self.leftKeysColor
elif curChar in self.rightKeys:
rectFill = self.rightKeysColor
elif curChar in self.unreachableKeys:
border = rgbString(136,136,136) # light gray
self.canvas.create_rectangle(curKeyX, curKeyY, curKeyX + keySize,
curKeyY + keySize, fill=rectFill, outline=border)
self.canvas.create_text(curKeyX + keySize/2, curKeyY + keySize/2,
text=curChar, fill=border)
def addUnreachableKeys(self, keys):
self.unreachableKeys = self.unreachableKeys.union(keys)
def resetKeys(self):
self.unreachableKeys = set()
self.rightKeys = set()
self.leftKeys = set()
def setRightKeys(self, keys):
self.rightKeys = keys
def setLeftKeys(self, keys):
self.leftKeys = keys
def setScanningMethod(self, scanningMethod):
self.resetKeys()
self.scanningMethod = scanningMethod
if (self.scanningMethod == Keyboard.LINEAR):
self.leftKeysColor = rgbString(204, 255, 204) # light green
self.rightKeysColor = rgbString(255, 255, 255) # white
else:
self.leftKeysColor = rgbString(204, 255, 204) # light green
self.rightKeysColor = rgbString(255,239,213) # light orange
class Editor(Animation):
def __init__(self, font="Arial 30", languageModel=None):
self.languageModel = languageModel
self.font = font
def buildLinearTree(self):
tree = None
for i in range(len(Keyboard.KEYS) - 1, -1, -1):
char = Keyboard.KEYS[i]
charNode = TreeNode(char=char)
tree = TreeNode(left=charNode, right=tree)
return tree
def buildHuffmanTree(self):
huffmanNodes = []
for char in self.languageModel:
huffmanNodes.append(TreeNode(self.languageModel[char], char))
heapq.heapify(huffmanNodes)
while (len(huffmanNodes) > 1):
# obtain the two minimum-frequency Huffman nodes
child1 = heapq.heappop(huffmanNodes)
child2 = heapq.heappop(huffmanNodes)
parent = TreeNode(child1.freq + child2.freq, left=child1, right=child2)
heapq.heappush(huffmanNodes, parent)
return None if huffmanNodes == [] else heapq.heappop(huffmanNodes)
def getNodes(self, path):
# get all the node to the left or to the right of the current node
nodesToHighlight = set()
if (self.curNode == None):
return nodesToHighlight
def walkTree(tree):
if (tree == None): return
if (tree.left == None and tree.right == None):
nodesToHighlight.add(tree.char)
walkTree(tree.left)
walkTree(tree.right)
if (path == Keyboard.LEFT):
walkTree(self.curNode.left)
else:
walkTree(self.curNode.right)
return nodesToHighlight
def drawScanPrefButtons(self):
if (self.keyboard.scanningMethod == Keyboard.HUFFMAN):
hBoxFill = rgbString(192,192,192)
lBoxFill = rgbString(255, 255, 255)
else:
hBoxFill = rgbString(255, 255, 255)
lBoxFill = rgbString(192,192,192)
hBoxLeft = self.boxLeft
self.canvas.create_rectangle(hBoxLeft, self.boxTop, hBoxLeft + self.boxWidth,
self.boxTop + self.boxHeight, fill=hBoxFill)
self.canvas.create_text(hBoxLeft + self.boxWidth/2,
self.boxTop + self.boxHeight/2, text="Huffman Scan")
lBoxLeft = hBoxLeft + self.boxWidth + self.boxMargin
self.canvas.create_rectangle(lBoxLeft, self.boxTop, lBoxLeft + self.boxWidth,
self.boxTop + self.boxHeight, fill=lBoxFill)
self.canvas.create_text(lBoxLeft + self.boxWidth/2,
self.boxTop + self.boxHeight/2, text="Linear Scan")
def redrawAll(self):
self.keyboard.draw()
self.textBox.draw()
self.drawScanPrefButtons()
if (self.keyboard.scanningMethod == Keyboard.HUFFMAN):
text = "Press Space to select the orange keys and Enter to select"\
" the green keys."
else:
text = "Press Space to move to the next key and Enter to select"\
" the currently highlighted key"
self.canvas.create_text(self.instructionLeft, self.instructionTop,
text=text)
def init(self):
self.boxTop, self.boxLeft = self.height/2, 50
self.boxWidth = 150
self.boxHeight = 30
self.boxMargin = 20
self.instructionLeft = self.width/2
self.instructionTop = 20
self.keyboard = Keyboard(self.canvas, self.width, self.height,
self.languageModel)
self.textBox = TextBox(self.font, self.canvas, self.width, self.height)
self.treeRoot = self.buildLinearTree()
self.curNode = None
def mousePressed(self, event):
# We don't have a language model so the only scanning method we can use
# is linear
if (self.languageModel == None): return
hBoxLeft = self.boxLeft
lBoxLeft = hBoxLeft + self.boxWidth + self.boxMargin
boxBottom = self.boxTop + self.boxHeight
if (event.x >= hBoxLeft and event.x <= hBoxLeft + self.boxWidth and
event.y >= self.boxTop and event.y <= boxBottom):
self.keyboard.setScanningMethod(Keyboard.HUFFMAN)
self.treeRoot = self.buildHuffmanTree()
self.curNode = None
elif (event.x >= lBoxLeft and event.x <= lBoxLeft + self.boxWidth and
event.y >= self.boxTop and event.y <= boxBottom):
self.keyboard.setScanningMethod(Keyboard.LINEAR)
self.treeRoot = self.buildLinearTree()
def keyPressed(self, event):
# only recognize 2 keys
if(event.keysym != "space" and event.keysym != "Return"): return
if (event.keysym == "space"):
if (self.curNode == None):
self.curNode = self.treeRoot
else:
# if we move to the right of the current node, all the nodes to
# the left of the current node won't be reachable anymore
newUnreachableKeys = self.getNodes(Keyboard.LEFT)
self.keyboard.addUnreachableKeys(newUnreachableKeys)
self.curNode = self.curNode.right
elif (event.keysym == "Return"):
if (self.curNode == None):
self.curNode = self.treeRoot
else:
# if we move to the left of the current node, all the nodes to
# the right of the current node won't be reachable anymore
newUnreachableKeys = self.getNodes(Keyboard.LEFT)
self.keyboard.addUnreachableKeys(newUnreachableKeys)
self.curNode = self.curNode.left
if (self.curNode == None):
self.keyboard.resetKeys()
self.curNode = self.treeRoot
elif (self.curNode.isLeaf()):
self.textBox.addChar(self.curNode.char)
self.keyboard.resetKeys()
self.curNode = self.treeRoot
# based on the curNode, divide the reachable keys into two buckets, the
# one to the left of the current node and the one to the right of the
# current node
self.keyboard.setLeftKeys(self.getNodes(Keyboard.LEFT))
self.keyboard.setRightKeys(self.getNodes(Keyboard.RIGHT))
# a language model based on frequency of English letters
languageModel = {
"e": 10.02, "t": 9.10, "a": 8.12, "o": 7.68, "i": 7.31, "n": 6.95,
"s": 6.28, "r": 6.02, "h": 5.92, "d": 4.32, "l": 3.98, "u": 2.88,
"c": 2.71, "m": 2.61, "f": 2.30, "y": 2.11, "w": 2.09, "g": 2.03,
"_": 2.0, "p": 1.82, "b": 1.49, "v": 1.11, "k": 0.69, "x": 0.17, "q": 0.11,
"j": 0.10, "z": 0.07
}
editor = Editor(languageModel=languageModel)
editor.run(800, 800)