Toolman in the Toyshop of the World

Infix search using a Trie data structure

noreply@blogger.com (Toolman) — Mon, 22 Mar 2010 08:21:00 +0000

I am authoring a jQuery plugin to enhance drop down selects; UFD: The Unobtrusive Fast-filter Drop-down. Try it out easily on your own app with the bookmarklet. Be amazed. Show your friends.

One of the important requirements was filtering of the the drop down options from the input. The naive way to do this is a linear search through each list item, but this is way too slow for large lists; the list needs to be re-filtered after every keystroke.

I decided on a Trie implementation, which gives great prefix search performance. A Trie stores objects on a tree, constructed by slicing the key-string for each object into characters. Starting at the root, each character maps to a node - see the incoming vertex in the diagram below.

Each node has a map of character to child nodes, and an optional target object. Target objects are placed where the chain of characters maps to the objects key, so you can easily traverse the nodes with a key-string to find a given the target object. The structure is a tree, but the path to a given object is similar to a linked list of each character in the key string.

The blue nodes are ones that have objects on them - in this example we see the words: to,tea,ted,ten,it,int,into. Notice how objects are on the leaf nodes, unless their key is a substring of another key.

It is easy to see how we can do quick prefix searching:start at the root node (which represents the empty string) and traverse the nodes, consuming each character of the key prefix string. Once the prefix key string is consumed, that subtree has all the matches of the given key prefix.

But what if we want to find all nodes that have a given key infix? After failing to find a better data structure, I decided to hack an extension to the data structure.

Is there a better data structure that I should be using? Suggestions welcome. Anyway:

Instead of starting at the root node, we need an array of start points. During creation I put a reference to each new node in a list. There is one list for every unique character across the whole key set. This means that each list has references to all nodes of that character. These lists of start points are called the infixRoots.

Yes, some of these lists could be quite large. For example, the "e" list for a 1000-item list may have over 1000 items.

Lets look at a filtering example: lets search for the objects that match the infix key "to".

We start by getting the infix list matching the start character ("t") from the infixRoots set. The highlighted nodes and all of their child nodes, by definition, have "t" in their key - no surprises there.

We next iterate over the that list of "t" nodes, creating a new list with child nodes that match the next character; "o". Any node without a match is not added to the new list. We keep iteratively mapping node lists from one character to the next, until we consume the infix keys' characters.

The nodes left in the final set, and all of their child nodes, all are matches. Iterate over each subtree and get the attached objects. In our example above, the nodes representing to,into are found. Had the key top been in the tree, it would also match, as it would be a child of to.

Have a look at the javascript implementation for UFD, the InfixTrie is a self-contained prototype inside the source near the bottom.

At last: a proper multi booting OSX/Win7/Linux box lives!

noreply@blogger.com (Toolman) — Tue, 02 Mar 2010 07:47:00 +0000

I have nutted out the final few problems with my multi-boot drama.

(hd0): MBR - grub2, win7, Liunx
(hd1): dataz
(hd2): bootable OSX 10.6 with GPT partition, Chameleon booter etc.

I can point my bios to hd2 and OSX boots, but it took ages to get grub2 to boot my OSX disc (hd2). Ended up being real simple; in /etc/grub.d/40_custom :

menuentry "Mac OSX" {
set root=(hd2)
chainloader +1
}

and then a sudo update-grub

Yay, it boots. My second major drama was with macFUSE and fuse-ext2; it doesn't work with the 64-bit kernel. Here is the console output:

toolmans-Mac-Pro:Volumes toolman$ sudo fuse-ext2 /dev/disk2s1 /Volumes/Untitled\ 30

fuse-ext2: version:'0.0.7', fuse_version:'27' [main (../../fuse-ext2/fuse-ext2.c:324)]

fuse-ext2: enter [do_probe (../../fuse-ext2/do_probe.c:30)]

fuse-ext2: leave [do_probe (../../fuse-ext2/do_probe.c:55)]

Mounting /dev/disk2s1 Read-Only.

Use 'force' or 'rw+' options to enable Read-Write mode

fuse-ext2: opts.device: /dev/disk2s1 [main (../../fuse-ext2/fuse-ext2.c:351)]

fuse-ext2: opts.mnt_point: /Volumes/Untitled 30 [main (../../fuse-ext2/fuse-ext2.c:352)]

fuse-ext2: opts.volname:  [main (../../fuse-ext2/fuse-ext2.c:353)]

fuse-ext2: opts.options: (null) [main (../../fuse-ext2/fuse-ext2.c:354)]

fuse-ext2: parsed_options: allow_other,local,noappledouble,ro,fsname=/dev/disk2s1,fstypename=ext2,volname=disk2s1 [main (../../fuse-ext2/fuse-ext2.c:355)]

fuse-ext2: mounting read-only [main (../../fuse-ext2/fuse-ext2.c:371)]

/Library/Filesystems/fusefs.fs/Support/fusefs.kext failed to load - (libkern/kext) link error; check the system/kernel logs for errors or try kextutil(8).

the MacFUSE file system is not available (71)

toolmans-Mac-Pro:Volumes toolman$

The highlighted line is the clincher; the 32-bit kext won't work with 64 bit kernel. thankfully, I can run 64 bit apps on the 32-bit kernel anyway :)

It took me ages to figure out that chameleon uses

/Extra/com.apple.Boot.plist

not the default kernel boot file !

/Library/Preferences/SystemConfiguration/com.apple.Boot.plist

By editing the correct file, and updating the kernel flags

Kernel Flags
-x32

And now I have grub2 booting to any OS I want, with my ext3 mounting in all OSes :D

Annoying iE6 bug of the day:

noreply@blogger.com (Toolman) — Fri, 11 Dec 2009 20:11:00 +0000

If you add a border on any edge of a < button ..> element, iE6 adds a second, inner border/padding, making your background image offset and the background color to show through!

This link describes it and a few side step options:

http://justaddwater.dk/2008/11/05/ie-css-bug-background-image-gap-to-border/

For my purposes, the easiset thing to do was not have a border, and have the parent supply a pseudo border using the background color. If you find a way to stop iE6 doing this, please let me know!

YESS DVB-T9900HD

noreply@blogger.com (Toolman) — Wed, 28 Oct 2009 08:48:00 +0000

So I decided to get a Freeview decoder, and I ended getting a HD (== terrestrial not satellite) decoder even though I don't yet have a HD TV. I got this YESS DVB-T9900HD is a single tuner unit with a HDMI port and the promise of PVR functionality via the USB port.

It looks a little ghetto with a USB port at the front, but I care not for asthetics anyway. Anyone who remembers my milk crate constructions can attest to that...

The freeview signal is super strong where I am in west AK, and it gets a glitchy signal with no aerial at all. My UHF aerial is well aligned so it gives 100% signal, and the programme guide comes through fine.

was skeptical that the PVR functionality of the unit would work via the USB port, but it does. Unfortunately, the PVR integration is basic and lacks in a number of areas. But its ok; you can pause and rewind TV, schedule and record TV as advertised.

I'm real happy for the price of the unit, but here is the laundry list of what is a bit shit about this unit for anyone else looking for an uber cheap PVR:

No integration between freeview EPG listings and the recording feature! I hope other units can do this? Scheduling a recording is like setting a VHS; this channel from then till then, click.
Single tuner means it can only buffer the channel you are watching. This is obvious, but a good PVR needs 2+ tuners.
I haven't checked, but I expect that the recording is in standard definition irrespective of the HD-ness. I haven't confirmed this one, anyone want to give me a HD screen? Actually I havent even checked the HD signal is HD when "realtime"!
Seems to use the disk regularly, not a great buffering technique. For this reason, I don't leave the PVR live buffering 24/7. Use of flash or solid state might dodge that bullet.
Seems to not like playing too close to realtime, needs 5+ second buffer, else it glitches and drops audio.

So the PVR is basically like a VHS, except you can do poor-mans timeshifting: start watching the recording before its finished.

The problem of evil:

noreply@blogger.com (Toolman) — Fri, 16 Oct 2009 23:36:00 +0000

Reading a great essay on: The problem of Evil. Here is a quote from it:

Assumption (1): God exists.
Assumption (1a): God is all-knowing.
Assumption (1b): God is all-powerful.
Assumption (1c): God is perfectly loving.
Assumption (1d): Any being that did not possess all three of the above properties would not be God.
Premise (2): Evil exists.
Premise (3): An all-knowing being would be aware of the existence of evil.
Premise (4): An all-powerful being would be able to eliminate evil.
Premise (5): A perfectly loving being would desire to eliminate evil.
Conclusion (6): Evil does not exist. (from (1),(3),(4),(5))
Contradiction: But evil does exist. (from (2))
Conclusion (7): There is no being that is all-knowing, all-powerful, and perfectly loving. (from (2),(3),(4),(5))
Conclusion (8): God does not exist. (from (7),(1d))
The argument's logic is ironclad, and its simple but far-reaching conclusion is that the existence of evil in the world disproves the existence of an omniscient, omnipotent, perfectly loving god. The only way to refute the problem of evil without surrendering the assumption that such a god exists is to deny one of its premises.

I like this argument as it doesn't completely deny God; but it relegates him to (in my view):

A God that isn't Perfectly Loving; or
A God that doesn't desire to eliminate evil.

To remove any of the other attributes of God is unacceptable (all-knowing, all-powerful), so he must either not exist, or be a bit of a bastard. So lets talk about your beliefs in bastard Gods only - the benevolent ones seem unlikely.

Negative signal-to-noise ratios

noreply@blogger.com (Toolman) — Fri, 04 Sep 2009 05:59:00 +0000

I'm reading an awesome technical book at the moment: Bob Katz, Mastering Audio. This guy is a audio master - read it! One thing thats really tripping me at the moment is this part.

We can hear signals below the noise floor? It seems like the LSB (least significant bit) represents the smallest variation in amplitude available digitally, so where is that signal actually coded and stored? My understanding of the explanation (not shown) is that it exists in the time domain as a modulation on the LSB.

Thats some tricksy stuff right there!

iCompass

noreply@blogger.com (Toolman) — Mon, 31 Aug 2009 11:16:00 +0000

The compass isn't perfect, but its ok.

I wonder what the Android sensor is like in comparison. Come on internet, send me a video of your android doing this.

Invisible Guard for iPhone 3GS

noreply@blogger.com (Toolman) — Wed, 12 Aug 2009 10:24:00 +0000

So now I have a shiny new iPhone, I have a few important things to do to it.

Extend its functionality..

and install a cover. I got an invisible guard, a kiwi-made transparent cover.

It is installed with some soapy water and lots of patience. I applied and smooshed for about an hour, but it ended up fitting very well. The corners took a while, but eventually I got them all in place.

2G on the left, 3GS + invisible guard on the right. The plastic has a slight orange-peel look to it, but it doesn't affect the picture quality.

It does feel quite different to the glass, slightly stickier. But it is still great to use. The extra grip on the back is a welcome addition. Even the home button has a guard, which fit perfectly.

Here you can see how the shield covers most of the corner, and how tight and accurate the cover is. Check around the headphone socket and the volume keys.

Another shot of the corner. Also note the one blemish that I decided I didn't care about: the chrome bezel has a flake of missing chrome. It looks like a manufacturing defect, but is too small for me to care.

This is how the rounded back is handled: a slit up each corner.

The back looks nice, like its been duraseal-ed. The guard can be peeled off without damaging the phone. So far, I'm really happy with how it come out, its hardly visible at all, and no bubbles!

Is that an Iceberg?

noreply@blogger.com (Toolman) — Tue, 11 Aug 2009 00:36:00 +0000

From http://www.stuff.co.nz/national/2739551/Is-that-an-iceberg-in-Wellington-Harbour/:

A fake 'iceberg' in Wellington's Oriental Bay this morning was made by special effects wizards Weta for a climate change stunt.

iPicky

noreply@blogger.com (Toolman) — Wed, 05 Aug 2009 10:21:00 +0000

So I got a brand new iPhone 3GS and it isn't up to Apples' quality control. Its' silver bevel surrounding the screen sits proud of the glass in the top left corner and runs half the left edge, and a third of the top.

The chrome is slightly proud on the bevel on the outer edge of the same corner, but not very much.

update: Apple happily replaced the unit, and my new one is flush and nice...

How I lowered my speakers noise floor by 6db

noreply@blogger.com (Toolman) — Wed, 22 Jul 2009 10:03:00 +0000

As many of you know, I use Behringer B2031A amplified speakers plugged directly to my soundcards' line level output, with software based volume control and a custom cable with a 3.5mm headphone to 2 x 1/4" jack cable.

They sound completely awesome I love this set up so much. The only little thing that bugged me was that I can hear the noise floor of my soundcard at louder slider settings. If I turned them up for quiet material or for stuff with large dynamic headroom the white noise was just perceptible.

The SB Live wiki page has an uncited note that "the original SB Live! had a very low noise floor for its time". Doh! I considered getting a better soundcard with balanced outputs to lower the floor, but meh - money, linux support etc. just for something that is so minor and uncommon.

In practice, I usually stay within something like 2-10% of max signal level from my soundcard on the speakers, and the noise floor is far below hearing level.

I recently realised that I had the input trim on each speaker central at 0db, but they could go to -6db. By setting both speakers to this, I am forced to have a higher output signal from the soundcard to compensate. This makes the soundcards' signal to noise ratio much better (by 6db!) for any given actual listening level. Of course, my 100% setting is also 6db quieter, but I dare anyone to site in front of these at 100%!

So now I probably use something like the 20-40% signal level, with plenty in reserve should I wish to wind something up loud. This is a much more sensible use of the range, as I was right at the bottom 1/4 of the mixer sliders most of the time. I can't hear the sound floor, even with everything at 100%/max/11 !

Google Reader keys:

noreply@blogger.com (Toolman) — Wed, 08 Jul 2009 05:27:00 +0000

I have been using a few of them, but OMG in list view, the spacebar is awesome. its a page down, and at the bottom of the post, space also auto jumps to the next post. Can skim view high volume sites the best way.

http://www.google.com/help/reader/faq.html#shortcuts

Keys are so much quicker.

Travel company offers free three-month holiday to promote NZ

noreply@blogger.com (Toolman) — Thu, 18 Jun 2009 05:23:00 +0000

Check this job out: http://www.nzherald.co.nz/new-zealand-travel/news/article.cfm?c_id=1500882&objectid=10577599

"We're a relatively new company ... and as you can imagine we've had we've had quite a few suppliers jump on board in a relatively short period of time," she said.
"We had the option of either taking time out of what we're doing now and going and travelling and meeting everybody ourselves, or offering this opportunity to somebody who would really enjoy it and have a lot of fun with it."
The winning candidate will be provided with free accommodation, transport, a daily food allowance and some spending money in return for blogging about their experiences.
"But there's no set wage as such," Forsyth added. "It's just a free trip."

Pity I have just got a job, that sounds like fun! Thanks Preeti for the link.

Toolman is employed

noreply@blogger.com (Toolman) — Thu, 18 Jun 2009 02:25:00 +0000

Hey all: Just a note that I am back to making Java web applications for VTech (not Honda VTEC :) ), the inhouse development team at Vero Insurance. Really enjoying the job, just completed my first week and enjoying engaging the brain a little more.

GIF vs JIF

noreply@blogger.com (Toolman) — Fri, 12 Jun 2009 11:13:00 +0000

From http://www.olsenhome.com/gif/:

You disagree? Hey, I'm just quoting the inventors of the format. Here's the evidence:

CompuServe used to distribute a graphics display program called CompuShow. In the documentation for version 8.33 in the FAQ section, it states:
The GIF (Graphics Interchange Format), pronounced "JIF", was designed by CompuServe and the official specification released in June of 1987.
There, straight from the inventors of the format.

So nerds, GIF or JIF?

Muppets album conversions:

noreply@blogger.com (Toolman) — Thu, 30 Apr 2009 06:14:00 +0000

This is a project that I was doing prior to traveling.

I spent months painfully converting these albums to CD. These albums got heavy airtime in my youth...

I carefully recorded the vinyl, then carefully cleaned the recordings by hand. Adobe Audition is the best wave editor I have ever used, and the results are fantastic. The finals still have the full warmth of the original vinyl, and no major pops or clicks. This took an unbelievable length of time, I ended up redoing the process multiple times as I learned better techniques.

I also scanned and processed all the cover artwork for the CD replicas.

The discs are printed on directly (no stickers!), and the art is a mock of the original vinyls' center label. I had to change the track numbers (no side B!) and shoehorn both sides listings onto a single side.

The sleeves are complete, with the inner and outer artwork just like the original vinyl sleeve.

Again, the track listings were subtly tweaked to reflect the single side and track numbers. Also, the back of a jewel case is not square (but the front sleeve is) so the rear artwork had to be cropped carefully to look correct. Compare left and right above.

In any case, really happy with how these turned out.

below the 42:

noreply@blogger.com (Toolman) — Thu, 30 Apr 2009 04:29:00 +0000

My mum gave me an excellent booze tip recently:

Stil vodka: this nice vodka comes from none other then 42 Below. Its their off-label, and is cheaper then 42 Below.

Still tastes pretty damn nice to me. Zing!

Recovering the mini

noreply@blogger.com (Toolman) — Mon, 27 Apr 2009 05:03:00 +0000

Heya all, me and Princess flew down to Welly last weekend.

My pal Andre got married, and we caught up with lots of you fullas down there :)

With Princess hanging out with Loulou, Nick and I went to unpack the mini and get it on to the road. The mini was stored well, and was straightforward to get on the road. All that was needed was a new battery and a damned good clean. So shes is now legit: WOF, rego, insurance.

When taking out the sub box to replace the battery, I found that a mousey had setup house in my sub box - he chewed the inside of the seat sponge!

The bastard also gnawed a hole in my sub and dragged lots of crud in there! I found him dead where you see him, the rubber and foam must have killed him. I cleaned the sub box and did a ghetto duct tape fix. Temporary, but it'll do.

I headed up the country.

7 hours of nonstop mini driving was real noisey! I did get a great day for cruising.

The mountain from afar...

..and up close - mint weather! Thankfully, no breakdowns or weird noises.

Synchronise your iPhone in Linux .. kinda

noreply@blogger.com (Toolman) — Sun, 12 Apr 2009 01:59:00 +0000

Hey guys; I finally got around to getting my iPhone to work in a Virtualbox installation of Windows. Now I can finally sync my iPhone without rebooting! I gathered up info from a few sources, and compiled it into the Ubuntu howto wiki.

https://help.ubuntu.com/community/PortableDevices/iPhone#Using%20iTunes%20via%20Sun%20Virtualbox%20running%20Windows

Sync away!

Digital Glitching

noreply@blogger.com (Toolman) — Wed, 08 Apr 2009 01:27:00 +0000

Saw this music video by Kanye West over the weekend:

KANYE WEST "Welcome To Heartbreak" Directed by Nabil from nabil elderkin on Vimeo.

Interesting how its using the errors produced by missing keyframes for artistic effect. I saw a few experimental videos like this, but to see it on A-List music videos is interesting. It the video analog to audio glitching artifacts being used in music. Interesting, but unless you are a codec master, you have little control over the effect, so this technique may have limited scope for expansion. Still cool - wonder if and encoders get confused encoding it :) ? Also, how many geeks give their satellite box a smack, thinking that the MTV feed is playing up ....

Ben Heck does it again: C64 laptop

noreply@blogger.com (Toolman) — Wed, 08 Apr 2009 00:46:00 +0000

Hey all;

I probably linked to the Picommodore C64 laptop project that someone did a while ago, it is a cool idea. I actually got myself a couple of the C64 all-in-one joysticks used in the project while I was in Europe. Ben Heck, custom-console-maker-extraordinaire has made a C64 laptop of such awesomeness that it kinda puts the rest to shame.

That is tidy. A SD card floppy emulator, original keyboard with Fn keys chopped off, and replacements by the fake trackpad (actually a LCD for the SD-floppy bridge), all the real hardware: SID chip, cartridge slot... Go look at the full writeup from Ben himself. A legendary hack.

http://benheck.com/04-05-2009/commodore-64-original-hardware-laptop

NIIICE!

The Cult of Done Manifesto

noreply@blogger.com (Toolman) — Sun, 29 Mar 2009 22:09:00 +0000

I want to join this cult:

http://www.brepettis.com/blog/2009/3/3/the-cult-of-done-manifesto.html

The Cult of Done Manifesto

There are three states of being. Not knowing, action and completion.
Accept that everything is a draft. It helps to get it done.
There is no editing stage.
Pretending you know what you're doing is almost the same as knowing what you are doing, so just accept that you know what you're doing even if you don't and do it.
Banish procrastination. If you wait more than a week to get an idea done, abandon it.
The point of being done is not to finish but to get other things done.
Once you're done you can throw it away.
Laugh at perfection. It's boring and keeps you from being done.
People without dirty hands are wrong. Doing something makes you right.
Failure counts as done. So do mistakes.
Destruction is a variant of done.
If you have an idea and publish it on the internet, that counts as a ghost of done.
Done is the engine of more.

Amen!

Norty

noreply@blogger.com (Toolman) — Thu, 26 Mar 2009 08:25:00 +0000

Here is a link for all my pal who know my mate, Norty...

http://www.stuff.co.nz/dominion-post/entertainment/blogs/the-lost-boys/2287212/The-initiators

Head Tracking for VR using a standard screen.

noreply@blogger.com (Toolman) — Wed, 25 Mar 2009 00:26:00 +0000

Hey this is a nice example of how to use our existing components for 3D goodness.

Nice one Jonny Lee.

Java magic trick

noreply@blogger.com (Toolman) — Sun, 22 Mar 2009 21:38:00 +0000

http://blogs.atlassian.com/developer/2008/07/magic_trick_in_java.html

Can you solve this one?