VK_VERYLONGKEYNAME (on reflection in Clojure)

So, I'm still writing a game. As it happens with games, I rely on keypresses for the user to tell me what he wants to do. That made me fall back on Java's KeyListener/KeyAdapter facilities.

The basic idea is that I get callbacks with information about the pressed key as argument (WARNING: GROSS OVERSIMPLIFICATION.), among other things the keycode, which is an integer. Now, I'm supposed to dispatch it using constants defined in KeyListener/KeyAdapter/KeyEvent/probably some other places.

Problem?

It's a lot of typing in Clojure. Especially since each constant is called VK_(something). I had large maps looking like that:

{ KeyEvent/VK_UP [some function]

  KeyEvent/VK_DOWN [some function]

  KeyEvent/VK_RIGHT [some function]

... }

You get the idea. Since I have several keymaps, that gets annoying quickly. So I started to define aliases for some frequently used ones in a seperate "keys" namespace. Now I only had to write, for example, "keys/up" instead of "KeyAdapter/VK_UP". That's a lot of saved space (and some gained readability).

But that introduced something else that annoyed me: Some of the more rare keys were still written out fully, and it created an aesthetic discrepancy, which upset my minor OCD. Besides, having to redefine tons of variables by hand isn't particularly elegant in itself.

(Disclaimer: I am aware of clojure.contrib/import-static. But I don't rely on that library enough to warrant including it in my project just for this.)

Sure enough, there is a better way.
The first nugget of information I needed was... how to get a list of all fields in a Java class?

Of course, Stack Overflow helped me there. It's

(clojure.reflect/reflect java.awt.event.KeyEvent)

It spews out a LOT of things like this:

{:bases #{java.awt.event.InputEvent},

 :flags #{:public},

 :members

 #{{:name VK_F17,

    :type int,

    :declaring-class java.awt.event.KeyEvent,

    :flags #{:static :public :final}}

   {:name VK_DEAD_DOUBLEACUTE,

    :type int,

    :declaring-class java.awt.event.KeyEvent,

    :flags #{:static :public :final}}

...}

This is the abridged pretty-print output of the stuff. We know all the VK_ fields are keycodes. Everything else falls in place itself, basically. Most of what I need I covered in a previous post already.

We want to:
1. From the list of members, filter out everything that is not a keycode.
2. Define the aliases over it.

Simple enough.

(->> (clojure.reflect/reflect java.awt.event.KeyEvent)

     (:members) (map :name) (filter #(.startsWith (str %) "VK_")))

This yields us a list of symbols (which I am grateful for, as it simplifies the next step) of all fields that contain keycodes. Now, as in my earlier post, we doseq over the list and define the aliases via eval in the loop. I also wanted the VK_ dropped and the entire name downcased, but that's just my whim.

(doseq [sym (->> (clojure.reflect/reflect java.awt.event.KeyEvent)

            (:members) (map :name) (filter #(.startsWith (str %) "VK_")))]

  (eval `(def ~(symbol (.toLowerCase (drop 3 (str sym))))

           (. java.awt.event.KeyEvent ~sym))))

That's it. Now, there are vars like "a", "up" and so on that hold the corresponding keycodes. I put the entire thing into a new namespace (game.keys) that I require like that:

(ns game.some-module

  (:require [game.keys :as keys])

Another nonproblem solved! :D

A Simple Solution; Part Two

A Short Solution, Part 2:

In the previous part, I laid out the initial draft of the solution to the problem described there, as well as, in the end, pointed out a few problems with said solution.
In addition, you might have noticed that the definition of generate-node was superfluous; in fact, I factored it out. The (cons chunk...) was added directly inside generate-tree.

Anyways. First we shall deal with dealing with duplicate entries in the chunk list and there not being a value in the root node.

(defn to-tree

  "Generates a solution tree for the given word and chunk list."

  [word chunks]

  (cons word (generate-tree word (keys (group-by identity chunks)))))

 
This function will be the one called in the end - it's not done yet, but both the mentioned problems are solved. The value of the root node is now the word being assembled, and
the chunk list is filtered of duplicate entries (I am not sure whether there is some other, more efficient method, this was what I thought of off the top of my head when writing).

Now, for the harder part. Filtering invalid entries out of the tree. Any branch that ends without an entry is invalid - but guessing which ones are invalid before everything is
generated would be impossible (I think?), or at least extremely hard to implement. So I went for the simpler, more functional approach: Filter out invalid entries after everything
is generated. Since the user will never see the unfiltered step inbetween, we can mark invalid branches in some way instead of writing a function that assembles a branch in order
to check it for validity.

So, first we need to modify our tree generation function:

(defn generate-tree

  [word chunks]

  (if-let [nexts (seq (possible-nexts word chunks))]

    (map #(cons % (generate-tree (drop (count %) word) chunks)) nexts)

    (when (seq word) '((:invalid)))))

(This also contains the correction with generate-node.)

Now, when there are no possible nexts, and there still remains some part of the word to be assembled (note again how (seq ...) is used as emptiness check), we add a node with the
value of :invalid. So now we have all invalid branches marked.

Then, the filtering...
First, we need a validity predicate, let's call it "valid?" (how imaginative).
First, let's consider which branches are technically invalid.
Given:

"valid?" ["va" "li" "id" "l" "d" "d?"]

We have:

va \ - l - id - :invalid
   \ - li \ - d - :invalid
            - d?

From the viewpoint of the "va" node, the "l" branch is invalid, and the "li" branch is valid. That is because all the children of the "l" branch are invalid, but one child of the
"li" branch is valid. Seeing that, we can conclude that nodes are invalid if:

1) It has at least one child and all children are invalid
  or
2) The own value is :invalid

Let's code it:

(defn valid?

  "Returns whether a node in the tree is valid."

  [[value & children]]

  (cond (= value :invalid) false

        (not children)     true

        :else (reduce #(or %1 %2) false (map valid? children))))

Fairly simple, is it not? The check is, obviously, recursive. I suppose that if we could traverse the tree from the lowermost nodes instead from the root, the algorithm would be faster
(we could simply hack off invalid branches without having to check the entire depth if a branch is invalid), but our tree nodes are not aware of their parents, nor do we have a list of
branch tips.

So, given this check, we can now filter.

(defn filter-valid

  "Filters invalid branches from the tree."

  [[value & children]]

  (cons value (map filter-valid (filter valid? children))))

Again pretty much one single line.
Now, add this to to-tree...

(defn to-tree

  "Generates a solution tree for the given word and chunk list."

  [word chunks]

  (filter-valid (cons word (generate-tree word (keys (group-by identity chunks))))))

DONE. Simply call to-tree with the word and the chunks and it spews out the final result. You can run it through clojure.pprint/pprint to make it readable, but that only aesthetics. ;P

Final program:

(defn possible-nexts

  "Given a word and a list of chunks, returns a list containing the chunks that are contained at the beginning of the word."

  [word chunks]

  (filter #(= (take (count %) word) (seq %)) chunks))

(defn generate-tree

  [word chunks]

  (if-let [nexts (seq (possible-nexts word chunks))]

    (map #(cons % (generate-tree (drop (count %) word) chunks)) nexts)

    (when (seq word) '((:invalid)))))

(defn valid?

  "Returns whether a node in the tree is valid."

  [[value & children]]

  (cond (= value :invalid) false

        (not children)     true

        :else (reduce #(or %1 %2) false (map valid? children))))

(defn filter-valid

  "Filters invalid branches from the tree."

  [[value & children]]

  (cons value (map filter-valid (filter valid? children))))

(defn to-tree

  "Generates a solution tree for the given word and chunk list."

  [word chunks]

  (filter-valid (cons word (generate-tree word (keys (group-by identity chunks))))))

So, that's it. FIVE function ranging from one to three lines of executed code each.