Planar binary trees with MetaPost

I recently needed to draw planar binary trees (PBT) for a paper I wrote with my collaborator. The paper is written in plain TeX with a minimal set of macros from a modified version of harvmac (named harvmacM).

At first I used tikz since it works with plain TeX. The drawback is that for each PBT one needs to write down the precise Cartesian coordinates for the root and each of its leaves.

After some boring time wasted with tikz, I decided to write a general macro to draw planar binary trees with MetaPost. The result looks nice. Furthermore, there is no need to manually specify the coordinates of the leaves, just how they are related to each other.

For example,

prologues:=3;
filenametemplate "%j-%c.eps";
defaultscale := 3.4;
u := 5.5cm;
input PBT.mp;

beginfig(1);
pickup pencircle scaled 3.8bp;
setupLegs(5);
i2 := whatever[bL2,t2] = whatever[origin,t1];
i3 := whatever[bL3,t3] = whatever[origin,t1];
i4 := whatever[bL4,t4] = whatever[origin,t1];
drawPBT(origin, 5);
endfig;


and,

beginfig(2);
pickup pencircle scaled 3.8bp;
setupLegs(5);
i2 := whatever[bL2,t2] = whatever[origin,t1];
i3 := whatever[bR3,t3] = whatever[bL4,t4];
i4 := whatever[bL4,t4] = whatever[origin,t1];
drawPBT(origin, 5);
endfig;


So one can see that the iN positions mean the intersection points of the leaves, where the leaf 1 is the line [origin, t1], leaf 3 is [bL3, t3] if its angle is 45 degrees or [bR3, t3] if its angle is 135 degrees and so forth. Very easy to specify and the calculations to find the coordinates of the intersection points are done by MetaPost.

The macros below can be put in a file PBT.mp and loaded with "input PBT.mp". They contain the coordinates Hoffset and Voffset which are useful when drawing more than one tree in the same figure. The first parameter of drawPBT() specifies the position of the root, so e.g. drawPBT(origin, 5); and drawPBT(Hoffset, 5);  would draw the diagrams shifted horizontally by the amount Hoffset.

pair t[], i[]; % top and intersection points
pair bL, bL[], bR, bR[]; % bottom left and right
pair Hoffset, Voffset, V;

def setupLegs(expr n) =
% n is the number of leaves, u is the scale

t1     := (-1.0u, 1.0u); % first leg
t[n]   := (+1.0u, 1.0u); % last leg
t[n+1] := (0.0u, -0.3u); % the offshell leg is defined as the (N+1)-th leg
bL     := (-2.0u, 0.0u); % far bottom left
bR     := (+2.0u, 0.0u); % far bottom right
Hoffset := (2.7u,0.0u);   % horizontal offset between diagrams
Voffset := (0.0u,2.8u);   % vertical offset between diagrams
V      := (0.0u, -0.07u);
i[1]   := origin;   % first leg
i[n]   := origin;   % last leg
i[n+1] := origin;   % offshell leg

for i:=2 upto (n-1):
        if n = 2:
                t[2] := (1u,1u);
        else:
                j := ((i-1)/(n-1));
                t[i] := j[t1,t[n]];     % top of legs are always in the same position
                bL[i] := j[bL,origin];  % bottom projection can be either on left or right
                bR[i] := j[origin,bR];  % bottom projection can be either on left or right
        fi
endfor
enddef;

def drawPBT(expr offset, n) =
% offset is the (x,y) position of the root, e.g. (0,0)

for j:=1 upto (n+1):
        draw (i[j]--t[j]) shifted offset;
        if j < (n+1):
                label.top(decimal(j),(t[j] + (0u,0.05u))) shifted offset;
        fi
endfor
enddef;

Plain TeX and hyperlinks with harvmac

I use plain TeX with a slightly modified version of harvmac for writing papers. 

Harvmac enables hyperlinks by loading hyperbasics.tex, so the dvi file generated with tex file.tex contains nice hyperlinks. I always wanted to have hyperlinks in the PDF too, but the result of dvipdf file.dvi unfortunately has no hyperlinks. Today I found out the procedure after some googling;

  tex file.tex
 dvi2ps -z file.dvi
 ps2pdf14 file.ps

After these steps the PDF file contains hyperlinks. However they are slightly annoying because of  ugly blue boxes around them. But anyway, the links are nevertheless useful to check that the equations are being referred correctly etc.

Incidentally, compiling the TeX file with xetex generates a PDF file with invisible hyperlinks. One becomes aware that the hyperlink is there only when passing the mouse over some reference. Since I know beforehand what's supposed to be hyperlinks, that's not a problem. In fact, that's a virtue because the blue boxes around links spoil the efforts to make the paper look typographically nice.

My Gmail setup with mutt, offlineimap, mailcheck, wmbiff, some shell scripts and notify-send

I often say that I prefer interacting with most people over email than face to face, especially when it involves discussions about physics because I have more time to think. So I consider reading and writing emails as efficiently as possible an essential task, and one that I also must have fun with.

For many years I used Thunderbird to manage my emails. I would keep it open and maximized all the time in its own Window Maker workspace in order to receive pop up notifications as new emails arrived. But its creeping featurism  conflicted with my minimalist views of computer software. So I decided to try mutt on December 2007.

I like it and I never looked back. However, for a long time I would still keep thunderbird open just to get the new email notifications even though I would read them using mutt. I had to do something about it.

I used a Window Maker dockapp called wmckgmail for some time, but it was restricted to gmail and I wanted notifications for my other accounts too. So I needed to find other tools and tweak them to my needs.

In the end the solution I found is in lines with the Unix philosophy:

Write programs that do one thing and do it well. Write programs to work together. Write programs to handle text streams, because that is a universal interface.

My email setup

1. Sync emails from various servers with my local Mail folder with offlineimap
2. Display the number of new emails in each mailbox in wmbiff
3. Pop up notifications using notify-send, mailcheck and shell scripts

The above tasks are managed by wmbiff, a Window Maker dockapp which apart from displaying the number of new emails on each configured mailbox, can be used to periodically invoke a 'fetchcmd' command to fetch emails (task 1).

Furthermore, wmbiff periodically checks (every checkinterval seconds) whether the watched mailboxes received new emails and calls the 'globalnotify' command in case they did. That takes care of task 3 above.

As you can see in my $HOME/.wmbiffrc file below, I configured the 'fetchcmd' command to be the shell script update-emails.sh, which contains the line:

offlineimap -o -a DAMTP,gmail

and the 'globalnotify' command to be the script notify-emails-wmbiff.sh.

The notify-emails-wmbiff script is the following:

#!/bin/bash

new_mail=0

maildir=" "

sum_mail=0

mailcheck | grep new 2>&1 >/dev/null

if [ $? -eq 0 ];

then

maildir=`mailcheck | grep new | awk '{ print $NF }' \

| sed 's/\// /g' | awk '{ print $NF }' \

| awk '{ printf "%s ", $0 }' | sed 's/ /, /g' \

| sed 's/, $//'`

new_mail=`mailcheck | grep new | awk '{ print $3 }'`

for N in `echo $new_mail`

do

sum_mail=`expr $sum_mail + $N`

done

if [ $sum_mail -eq 1 ] ;

then

notify-send -c email.arrived -u normal -i mail_new \

"You have $sum_mail new mail:" "$maildir"

else

notify-send -c email.arrived -u normal -i mail_new \

"You have $sum_mail new mails:" "$maildir"

fi

fi

The script above uses mailcheck to count the new messages in each mailbox. It's a very simple program whose output appears in the snapshot below:

Parsing that output explains all the awk's and sed's in the script (I modified this script from somewhere in the internet).

After counting how many new emails I have, the script uses the program 'notify-send' to create a pop-up notification window on the top right:

Notice how the "Gmail" line in the wmbiff dockapp in the snapshot above has a red entry displaying "02". It means there are 2 new emails in my gmail inbox. Clicking that line opens up the mutt client inside the Gmail inbox -- to check exactly which command is run, see the wmbiffrc configuration file.

So that's how I traded thunderbird by mutt. It's much nicer this way!

PS:  My ~/.wmbiffrc contains (among other things):

# Seconds between checking mailboxes

interval=30

# Interval between mail auto-fetching; use 0 to disable

# right-clicking the dockapp makes it execute fetchcmd.0 right away

# use -1 for auto-fetching on new mail arrival

fetchinterval.0=600

# Command for fetching mail.

fetchcmd.0=/home/mafra/bin/update-emails.sh

label.1=Gmail

path.1=maildir:/home/mafra/Mail/Gmail/INBOX

action.1=xterm -geometry 140x48+50+0 -bg black -fg white +sb +sm -fn 10x20 -sl 4000 -cr yellow -name Gmail -e mutt -f /home/mafra/Mail/Gmail/INBOX

# Command which will be executed for new mail in any watched mailbox

globalnotify=/home/mafra/bin/notify-emails-wmbiff.sh

My ~/.offlineimaprc contains:

[general]

accounts = DAMTP, gmail

fsync = false

ui = Curses.Blinkenlights, TTY.TTYUI,

Noninteractive.Basic, Noninteractive.Quiet

maxsyncaccounts = 3

socktimeout = 60

[Account gmail]

localrepository = Local-gmail

remoterepository = Remote-gmail

autorefresh = 4

quick = 10

[Repository Local-gmail]

type = Maildir

localfolders = ~/Mail/Gmail

[Repository Remote-gmail]

type = Gmail

remoteuser = myemail

remotepass = mypassword

maxconnections = 3

realdelete = yes

folderfilter = lambda foldername: foldername not in ['[Gmail]/Spam','[Gmail]/Trash','[Gmail]/All Mail']

Ambientes fechados

Eu concordo que os alemães são inteligentes, organizados e tudo isso que escutamos por aí. Eu tenho uma profunda admiracão pelo povo alemão. O nível de desenvolvimento que eles atingiram é um testemunho da sua inteligência coletiva. Mas tem uma coisa em que eles não tem nocão alguma, que é: MANTER INVARIAVELMENTE TODAS AS JANELAS FECHADAS!

Eu não suporto isso. No inverno eu até que entendo (mesmo assim abrir as janelas de vez em quando seria saudável, mas essa esperanca eu já perdi faz tempo), mas no verão não há desculpa. Até hoje eu não compreendo por que eles fazem isso. Sério, é uma sensaćão de "por que diabos essa janela está fechada enquanto aqui dentro está tão quente?". É ilógico, é absurdo, é incompreensível.

Isso sem mencionar que o instituto onde estudo tem pouquíssimas janelas. Então o problema já comeca por aí. E as janelas que eu abro quando ninguém está vendo já estão fechadas quando passo pelo mesmo lugar alguns minutos depois. Tem sempre alguém (não necessariamente alemão, já que há gente de muitos países aqui) que vai lá e a fecha. Por que será que é tão difícil manter uma janela aberta em um instituto cujo ar está sempre viciado? Será que há algo errado _comigo_?

Há alguns dias eu voltei do centro dentro de um ônibus lotado, às 14h de um dia em que a temperatura máxima chegou a 30 graus. E adivinha? Havia somente uma janelinha ridícula aberta no fundo do ônibus!

Sério, acho que eles esqueceram do seu próprio ditado: Frische Luft gesund ist.

Maximus - Tiled Maximization in Window Maker

In the last few days I was more curious about the inner workings of Window Maker than that of Nature herself. I read a good amount of code and applied patches from others and a few of my own to my git repo and it was fun. Now that I am back to "Physics mode" I felt the need to write about a new feature of "my" Window Maker, the tiled maximization a.k.a. Maximus.

It all started when someone in the wmaker-dev mailing list asked for this new feature, and I realized that I would like that too (besides, I liked the name!). The idea is simple: to maximize an existing window to the greatest area without overlapping others (if any). It is quite useful in big widescreen monitors like the one I use at the institute.

Once I decided to code it, it took me 4 hours to come up with an algorithm and implement it in Window Maker. But I liked the result and I am already using it every day, so I am happy. You can see it in action in the screenshots above. The second picture is obtained from the first by maximizing the xterm using the new Maximus feature, which I defined to have a shortcut Alt+. This is an artificial example in my laptop's small screen, but you can see that it is cool :-)

Una artista en mi corazón

Mi esposa además de ser una física es también una artista con gran talento. El dibujo arriba es una pequeña muestra de su sensibilidad, que hace mi corazón golpear más fuerte toda vez que lo admiro con más cuidado. Yo lo veo todas las mañanas porque el se queda en la cabecera de mi cama, pero a veces lo miro con más atención do que el habitual al coger mis gafas cuando despierto.

A mi me gusta la combinación amarillo + negro, y muchas veces es así que pongo mi ropa y es así que aparezco en el dibujo. Mi esposa y yo salimos muchas veces a caminar en el parque charquito, en nuestra adorada Cali con nuestra querida Mariposa.
Después que la bonita perrita ya se cansó (lo que no es muy difícil, debo decir), nos quedamos un rato sentados en la banquita junto a ella, esperando a que esté lista para volver a la casa (cosa que a ella nunca le gusta hacer de modo que siempre intenta irse por otro camiño). Y ni es necesário decir que siempre estamos muy felizes con la compañia del otro.

Eses son los eventos que mi esposa amada puso en el dibujo, y ahora es él que hace mis recuerdos volveren a aquellos días maravillosos que pasamos en Cali junto a nuestra hija, la adorable Mariposa.

Son durante esas miradas más largas que muchas veces las lágrimas llegan a mis ojos, por saber que debo esperar lleno de nostalgia a que ellas estén conmigo otra vez, caminando felices y cansadas por las calles de Cali bajo el sol que añade aún más calor a nuestros ya calientes corazones de pasión.

Mientras tanto, sigo mirando sus dibujos y ansiando al día en que estaremos juntos otra vez, para que también esos días sirvan de inspiración para otros dibujos, futuros testigos de nuestra felicidad.

Chasing a bug

This afternoon I was a bit tired with my 5-pt computation at 1-loop, because I have to check if something very boring is true and I know from consistency that it has to be true.

So I tried to occupy my mind with something interesting instead, and get back to my long problem later on.

A post [1] to the Window Maker list was enough to make me curious and I decided to think about it. The problem was an apparent bug with Window Maker, which was not recognizing the release of a shortcut key called Mod4, with keycode == 115.

My first reaction was to ask for more information, because it looked like a X bug to me due to the fact that the reporter had a non-standard Sun keyboard, and it had already uncovered a X bug last month, IIRC.

After a few private emails I learned how to reproduce the issue with my keyboard too, using the "Windows" key (maybe this name or even the logo has some special ability to make bugs happen). Having something which I could test myself I went to the wmaker source code to learn where the problem was happening.

A few 'git grep'(s) later I found the source responsable for this anomaly in src/cycling.c

            case KeyRelease:
#ifdef DEBUG
           printf("Got key release\n");
#endif
           for (i = 0; i <>max_keypermod; i++) {
               if (keymap->modifiermap[i] == ev.xkey.keycode &&
                   wKeyBindings[WKBD_FOCUSNEXT].modifier
                   & 1<<(i/keymap->max_keypermod)) {
                   done = True;
                   break;
               }
           }
           break;

and at first I thought that the problem was about keymap->max_keypermod being 3 instead of 4. But that hypothesis did not withstand my tests, and the scenario which emerged after some debug printf's was

1. The modifier (Mod4) keycode was equal to 115 (I looked at 'xev' output)
2. There was no keymap->modifiermap[i] for any 1<= i <= 24 which was equal to 115, so the condition inside the if () was not being satisfied and the key would never be recognized as being released.
   
3. For this particular Mod4 key, whe have wKeyBindings[WKBD_FOCUSNEXT].modifier== 64
   

Therefore, as 1<<( i / keymap->max_keypermod) == 64 for i == 18 (remember that keymap->max_keypermod == 3) I simply set keymap->modifiermap[18] = 115 before the 'for' loop, and it fixed the issue for me!

I wrote the workaround patch and asked it to be tested, and it worked for the reporter too. The origin of the problem was found, but the proper fix was yet to be written.

I went out for a cappuccino I had the idea of searching about it with google. After some time I found out [2] that this is really a X bug, which can be "fixed" by adding to the .Xmodmap file the following

    remove mod4 = Super_L
   keycode 127 = NoSymbol
   add mod4 = Super_L

I wrote about it back to the list and the original reporter confirmed that doing this modification fixed the problem for him too.

And that is how my quest for some fun ended, and Window Maker remains bug-free as far as this issue is concerned (I don't know of any other wmaker bug, though).

The lesson I guess is, ask the almighty google first and hack the code later...

...but if I had done that I wouldn't have some fun learning new things about the inner workings of Window Maker.


[1] http://lists.windowmaker.info/dev/msg00123.html
[2] http://modeemi.fi/~tuomov/ion/faq/entries/Modifier_releases.html