Sunday, March 23, 2014

Gtk3 hit-a-hint: mouseless navigation module

I present gtkhah, a gtk module for hit-a-hint mouseless navigation of gtk3 applications.
It's been inspired by the various hit-a-hint browser extensions.
Usage at the project homepage. Here's a quick screenshot of Gedit:


Monday, January 20, 2014

Intersection test and optimal allocation of 2D axis-aligned boxes using linear programming

Either-or trick
In this solution, we will make use of the either-or trick. The constraints in a program are all in and, but we want some of them to be in or.
Consider the following logic formula: \(a\ge b\vee c\ge d\). It can be written with the following and constraints: \[ \begin{alignedat}{2}\, & M\cdot x\; & +a\; & \ge b\\ \, & M\cdot\left(1-x\right)\; & +c\; & \ge d\\ \, & \, & x\; & \in\left\{ 0,1\right\} \end{alignedat} \] where \(M \gt 0\) is big (depending on the specific context as we'll see later).
When \(x=0\), then \(a \ge b\) must hold, while the second constraint is always satisfied. When \(x=1\), then \(c \ge d\) must hold, while the first constraint is always satisfied.
In other words, either one of the two constraint must hold for a given value of \(x\). If neither do, then the original or formula is not satisfied.

Empty intersection test
Given two AABB boxes \(i,j\) at position \(x_i,y_i\) and \(x_j,y_j\) with size \(w_i,h_i\) and \(w_j,h_j\) respectively, we want to constraint our program such that their intersection is empty.
This can be expressed with the following logic formula:
\[ \left(x_{i}\ge x_{j}+w_{j}\vee x_{j}\ge x_{i}+w_{i}\right)\vee\left(y_{i}\ge y_{j}+h_{j}\vee y_{j}\ge y_{i}+h_{i}\right) \]
We can encode the above expression with 3 either-or tricks using 3 binary variables:
\[ \begin{alignedat}{3}\; & M\cdot b_{1}\; & \, & +M\cdot b_{3} & +x_{i}\; & \ge x_{j}+w_{j}\\ \; & M\cdot\left(1-b_{1}\right)\; & \, & +M\cdot b_{3} & +x_{j}\; & \ge x_{i}+w_{i}\\ \; & M\cdot b_{2}\; & \, & +M\cdot\left(1-b_{3}\right) & +y_{i}\; & \ge y_{j}+w_{j}\\ \; & M\cdot\left(1-b_{2}\right)\; & \, & +M\cdot\left(1-b_{3}\right) & +y_{j}\; & \ge y_{i}+w_{i}\\ \, & \, & \, & \; & b_{1},b_{2},b_{3}\; & \in\left\{ 0,1\right\} \end{alignedat} \] Real problem
Given a fixed area of size \((cols)\times(rows)\) and a set of boxes with fixed width \(w_i\) for each \(i=1..n\) (where \(n\) is the number of boxes), find the optimal allocation \(x_i, y_i, h_i\) for each box \(i=1..n\) such that we cover all the area and maximize the size of the boxes fairly.
To achieve fair allocation we choose to maximize the minimum height of the boxes. For example, if we had an area of size \(5\times100\), and two boxes of width \(5\) each, we prefer them to have height \(50\) and \(50\) respectively, rather than \(1\) and \(99\).

This problem can be encoded as follows: \[ max\; minh+C\cdot{\displaystyle \sum_{i=1}^{n}h_{i}} \] \[ subject\;to: \] \begin{equation} \forall i=1..n:\; minh\leq h_{i} \end{equation}
\[ \forall i=1..n-1,\, j=i+1..n: \] \begin{equation} \begin{alignedat}{3}\; & M\cdot b_{1}^{\left(ij\right)}\; & \, & +M\cdot b_{3}^{\left(ij\right)} & +x_{i}\; & \ge x_{j}+w_{j}\\ \; & M\cdot\left(1-b_{1}^{\left(ij\right)}\right)\; & \, & +M\cdot b_{3}^{\left(ij\right)} & +x_{j}\; & \ge x_{i}+w_{i}\\ \; & M\cdot b_{2}^{\left(ij\right)}\; & \, & +M\cdot\left(1-b_{3}^{\left(ij\right)}\right) & +y_{i}\; & \ge y_{j}+w_{j}\\ \; & M\cdot\left(1-b_{2}^{\left(ij\right)}\right)\; & \, & +M\cdot\left(1-b_{3}^{\left(ij\right)}\right) & +y_{j}\; & \ge y_{i}+w_{i}\\ \, & \, & \, & \; & b_{1}^{\left(ij\right)},b_{2}^{\left(ij\right)},b_{3}^{\left(ij\right)}\; & \in\left\{ 0,1\right\} \end{alignedat} \end{equation}
\[ \forall i=1..n: \] \begin{equation} \begin{alignedat}{1}x_{i}+w_{i}\; & \le cols\\ y_{i}+h_{i}\; & \leq rows\\ 0\leq x_{i}\; & \leq cols-1\\ 0\leq y_{i}\; & \leq rows-1\\ 1\leq h_{i}\; & \leq rows \end{alignedat} \end{equation} Equation \((1)\) is used to get the minimum height of the boxes together with the objective function. Equations \((2)\) ensure that the boxes do not overlap. Equations \((3)\) ensure that the boxes don't lie outside of the allocation area.
In the objective function we also add a second component, which ensures that on equal \(minh\) we chose the allocation that fills the remaining space. This component must thus be \(< 1\) to not bias the \(minh\) component.

Now, what are the values of \(M\) and \(C\)? The constant \(M\) must be big enough to make an inequality always true, so:
\begin{gather*} \forall i,j:\; M\ge x_{j}+w_{j}-x_{i}\\ M\ge\max\left\{ x_{j}+w_{j}-x_{i}\right\} \\ M\ge\max\left\{ x_{j}+w_{j}\right\} -\min\left\{ x_{i}\right\} \\ M\ge cols \end{gather*} Since it must hold also for rows, \(M\ge\max\left\{ cols,rows\right\}\). The result is very intuitive if you look at the original inequalities. We can choose a value of \(M=cols+rows\).
The constant \(C\) instead must be such that: \begin{gather*} C\cdot{\displaystyle \sum_{i=1}^{n}h_{i}}<1\\ C\cdot n\cdot\max\left\{ h_{i}\right\} <1\\ C\cdot n\cdot rows<1\\ C<\frac{1}{n\cdot rows} \end{gather*} This result is also very intuitive. We can choose \(C=\frac{1}{2\cdot n\cdot rows}\) to avoid numerical instability.

Demonstration
I've prepared a GMPL program to allocate \(10\) boxes with width \(3,4,10,7,4,8,2,9,8,5\) in an area of \(10\,cols\times100\, rows\). GLPK does not converge, so you can limit the time to 1 second (or more) in order to get a feasible but suboptimal solution.
You can visualize the result in the screenshot below of the two solutions while running for 1 second and 5 second respectively. After 60 seconds the solution didn't improve.
Please note that there is no relationship between the colors of the two tests.

image/svg+xml 1s 5s

Relaxing the integer constraint on \(x,y,h,minh\) might also give you better solutions in less time.
You can download the gist below and run it as: glpsol --tmlim 5 -m aabb_alloc.mod:

Friday, September 06, 2013

Regex in Haskell patterns

Have you ever wanted to do case expr of regexhere -> ... ?
You can do almost that with view patterns!

{-# LANGUAGE ViewPatterns #-}

import Text.Regex.Posix

-- Helper
pat :: String -> String -> [[String]]
pat p s = s =~ p

-- Function with matching
foo :: String -> String
foo (pat "foo(bar|baz)" -> [[_,x]]) = x
foo _ = "no!"

main :: IO ()
main = do
  print $ foo "foobar"
  print $ foo "foobaz"
  print $ foo "yes?"

The above code will print bar baz no! . Have fun!

Wednesday, July 03, 2013

Found my google reader alternative: the old reader

So I'd like to share with you my google reader alternative: theoldreader.
I've tried so far yoleo, feedly, goread and diggreader. Each of them is missing the following must have things for me:
  • The "next" button. I don't like using keyboard bindings when reading feeds.
  • Search through all feeds
  • Social by sharing/liking news
  • Exporting OPML
Additionally, theoldreader has a great (disabled by default) feature: clicking on a news will scroll to it. That is very handy if you don't want to stick your mouse clicking on the next button.

The only bad point of theoldreader is that there's an import queue, I'm currently in position 1566 (1481 after about 15 minutes). Other than that, it's perfect for my needs and resembles most of google reader.

Update: the search only looks for terms into post titles, not post contents :-(

Friday, June 28, 2013

Inline commenting system for blog sites

One side of the idea:
Lately I've seen some comment systems that inline comments in the text itself, see an example here.

Other side of the idea:
I've implemented a couple of unsupervised algorithms for news text extraction from web pages in Javascript, and they work generally well. They're also capable of splitting the news text into paragraphs and avoid image captions or other unrelated text.

The idea:
Merge the two ideas, as a new commenting service (like Disqus) for blogs, in a modern and interesting way.
  1. The algorithms are capable of extracting the news text from your blog and splitting it into paragraphs.
  2. For each paragraph, add a seamless event so that when the user overs a paragraph with the mouse, a comment action button appears.
  3. When clicking the comment button a popup will appear showing a text box at the top where you can write the comment, and the list of comments at the bottom that are related to that paragraph only. (I please you, let the user order comments by date.)
  4. Optional killer feature: together with the text box, you can also choose to add two buttons: "This is true", "This is false", so that there's a kind of voting system about the truth value of that paragraph from the readers perspective.
  5. Once you send the comment, that comment is tied to that paragraph.
  6. Give the possibility to create comments the old way, in case the user does not want to strictly relate the comment to a paragraph.
  7. Give the possibility to show all the comments at the bottom of the page (button "Show all comments"). If a comment is related to a paragraph, insert an anchor to the paragraph.
Given that the blogger shouldn't add any additional HTML code for the paragraphs because of the unsupervised news extraction algorithms, the comment service API will not differ in any way than the current ones being used.

Problems of this approach:
  • There's no clear chronology for the user between comments of two different paragraphs. In my opinion, this shouldn't be a big deal, as long as comments between two paragraphs are unrelated.
  • If a paragraph is edited/deleted, what happens to the comments? One solution is to not show them in the text, but add a button "Show obsolete comments" at the buttom of the page, or rather show them unconditionally.
  • The unsupervised algorithm may fail to identify the post. In that case, the blogger may fall back to manually define the DOM element containing the article.

Wednesday, June 05, 2013

Accessing simple private fields in PHP

A way of accessing private fields in PHP is by changing the accessibility of the fields themselves with http://php.net/manual/en/reflectionproperty.setaccessible.php.
However this approach requires PHP 5.3.

For PHP < 5.3 there's another subtle way of accessing private properties:

function getPrivateProperty($fixture, $propname) {
    try {
        $arr = (array)$fixture;
    } catch (Exception $e) {
    }
    $class = get_class($fixture);
    $privname = "\0$class\0$propname";
    return $arr[$privname];
}

Usage is pretty straightforward, pass in the object and the property name as string. The property must be private and must be convertible to array.

Saturday, April 06, 2013

Build Vala applications with Shake build system

I'm going to introduce you a very nice alternative to make: the Shake build system, by setting up a builder for your Vala application project.

First of all, you need to know that Shake is a library written in Haskell, and it's meant to be a better replacement for make. Let's start by installing cabal and then shake:
apt-get install cabal-install
cabal update
cabal install shake

TL;DR; this is the final Build.hs file:
#!/usr/bin/env runhaskell
import Development.Shake
import Development.Shake.FilePath
import Development.Shake.Sys
import Control.Applicative hiding ((*>))

app = "bestValaApp"
sources = words "file1.vala file2.vala file3.vala"
packages = words "gtk+-3.0 glib-2.0 gobject-2.0"

cc = "cc"
valac = "valac"
pkgconfig = "pkg-config"

-- derived
csources = map (flip replaceExtension ".c") sources
cobjects = map (flip replaceExtension ".o") csources

main = shakeArgs shakeOptions $ do
  want [app]
  app *> \out -> do
    need cobjects
    pkgconfigflags <- pkgConfig $ ["--libs"] ++ packages
    sys cc "-fPIC -o" [out] pkgconfigflags cobjects
  cobjects **> \out -> do
    let cfile = replaceExtension out ".c"
    need [cfile]
    pkgconfigflags <- pkgConfig $ ["--cflags"] ++ packages
    sys cc "-ggdb -fPIC -c -o" [out, cfile] pkgconfigflags
  csources *>> \_ -> do
    let valapkgflags = prependEach "--pkg" packages
    need sources
    sys valac "-C -g" valapkgflags sources
    
-- utilities
prependEach x = foldr (\y a -> x:y:a) []
pkgConfig args = (words . fst) <$> (systemOutput pkgconfig args)

Just tweak app, sources and packages to match your needs, chmod +x Build.hs then run ./Build.hs .

Explanation.
The words function splits a string by spaces to get a list of strings, e.g. ["file1.vala", "file2.vala", "file3.vala"].

The csources variable maps .vala file names to .c file names. Same goes for cobjects. It's the equivalent of $(subst .vala,.c,$(SOURCES)) you'd do with make.

There it comes the main. The shakeArgs shakeOptions part will run shake with default options. Shake provides handy command line options similar to make, run ./Build.hs -h for help.

The want [app] tells shake we want to build the app object by default. That's equivalent to the usual first make rule all: $(APP).

Then we define how to build the executable app with app *> \out -> do. We tell shake the dependencies with need cobjects. This is similar to $(APP): $(COBJECTS) in make but not equivalent. In shake dependencies are not static like in many other build systems. This is one of the most interesting shake features.
The rest is quite straightforward to understand.

Then we define how to build each .o object with cobjects **> \out -> do. Here the out variable contains the actual .o required to be built, equivalent to $@ in make. Then we need [cfile], in order to simulate %.o: %.c like in make.

One more feature shake has out-of-the-box that make doesn't is how to generate more files from a single command. With make you'd use a .stamp file due to valac generating several .c files out of .vala files. Then use the .stamp as dependency.
With shake instead we consistently define how to build .c files with csources *>> \_ -> do, then shake will do the rest.

The shake project is very active. You can read this tutorial to learn Haskell basics, and the reference docs of shake. The author homepage has links to cool presentations of the shake build system.