You've received that email, "Please print, sign, scan, and return." Possibly it said FAX - but like me, you just can't wrap you're head around using a FAX in 2010. So you fire up gimp (or xsane), scan a page, crop it, save it; repeat for N pages; then spend 10 minutes reading the absurdly obfuscated ImageMagick man pages to finally stitch the images together into a PDF, and return to sender. You do this once, and the memory of it provides a very significant mental barrier to ever repeating the process.

I had to do this again today for a pair of documents. The Simple Scan tool caught my eye and I gave it a try. It's pure genius, in an "OMFG why did it take 10 years for this to appear?" kind of way. Simple Scan handles the intermediate files behind the scenes, crops all the pages to the same size, displays a thumbnail of each page you scan, and finally saves the document as a PDF. Like, wow. Thanks Simple Scan!

read more

Red Black trees are a critical data-structure in the Linux kernel. I've often wondered what made them unique to other trees, but ignored the impulse to dive into it much beyond reading the excellent Wikipedia article on red black trees.

An rbtree achieves O(log n) time complexity for search, insert, and remove. The key properties of an rbtree are as follows:

1. A node is either red or black.
2. The root is black. (This rule is used in some definitions and not others. Since the root can always be changed from red to black but not necessarily vice-versa this rule has little effect on analysis.)
3. All leaves are black.
4. Both children of every red node are black.
5. Every simple path from a given node to any of its descendant leaves contains the same number of black nodes.

I finally manned-up and decided to write a sample red black tree in python. Despite having covered binary trees ad nauseam in college, I was surprised how challenging it was to write a completely functional red black tree. After a few nights of "free time" dedicated to the project, I finally have something to show for it.

$ ./rbtree.py 
***** Populating Red Black Tree with 1000 Nodes *****
***** Test Insert Complexity O(log N) *****
  PASS
***** Test In-Order Traversal *****
  PASS
***** Test Search Complexity O(log N)*****
  PASS
***** Test Remove Functionality *****
  PASS

The source comes with a built-in self test that inserts the values 1-1000 in random order, locates them all, then removes them in random order. It verifies the 5 properties of the rbtree at each step, and prints the results.

While I am glad to have done it, I am truly embarrassed at how long it took me to complete. On the bright side, the principles I had to dust off to get this done are now painfully fresh in my head. If you'd like to see the source, it's available here: rbtree.py

Lastly, there is a clever interactive demo here (requires java):
Red Black Tree Demonstration

Next up... python metaclasses, and why Guido is an evil bastard.

read more

I finally got tired of lack specifiers in "git grep" and the cscope ncurses interface. I spent a few minutes and setup the vim cscope plugin using this mighty fine tutorial:

http://cscope.sourceforge.net/cscope_vim_tutorial.html

The one gotcha I ran into was having to disable my vim setting that automatically changed the working directory to that of the open file - it broke the cscope plugin relative filenames.

" automatically switch the cwd to that of the file in the buffer
" This breaks cscope plugin
" autocmd BufEnter * :cd %:p:h

Very, VERY VEERRRYYY nice. Now if only I could get a full call graph out of it...

read more

I use rdiff-backup to keep a few months worth of daily backups for my home systems (and those of my parents for that matter). The ability to recover any version of a file is great - although the process still requires a geek (me).

$ rdiff-backup --restore-as-of "7D" user@backupserver::/path/to/backup/file

Wouldn't it be great if you could just mount the backup repository and browse by path or date and then just copy the desired version? Enter BackupFS, a fuse filesystem implemented with rdiff-backup.

I've only just started digging into this, and rdiff-backup's python packages were not intended to be used as libraries (not with all the code buried in rdiff_backup.Main and all the global module variables floating around. Still, I was able to get a server test and a listing of the repositories root increments by using the python modules (and not just making multiple subprocess() calls).

I have a glorified version of the example hello world fuse filesystem able to mount and list a few meta-directories:

dvhart@vin:backupfs.git$ ./backupfs.py mnt && (tree mnt; fusermount -u mnt)
Testing server started by:  ssh -C katara rdiff-backup --server
Server OK
mnt
|-- By Date
|   `-- increments.2010-01-07T22:11:42-08:00.dir
|-- By Path
`-- hello

3 directories, 1 file
Fatal Error: Lost connection to the remote system

I still have some basic research to do in order to understand how to operate within the rdiff-backup packages (API isn't quite the right term ;-). After that, it'll be on to a more formal design and then some nicer code.

read more

I had Dad ship his old laptop for an upgrade. After installing Ubuntu Lucid (from a USB key) and upgrading the RAM, I was _really_ impressed that Empathy video chat over Google Talk "just worked". I went and picked up a Logitech C120 web-cam for him for $20, took it home, plugged it in the USB slot and guess what - it just worked! We've come a long way in 10 years Linux! Honestly it felt weird... I kept thinking... isn't there a driver I should have to download, build, fix, patch, build, etc... It's like... having a mac or something. The only thing that would have made it better would be if the box had a penguin logo on the back.