It's always interesting to look at the way in which people overcome the problem of navigating the web. The problem being that nowdays content is full of sidelines and links. As you're reading your favourite blog (mine, surely ;)) they might link to another post, such as this one about The Problem With Tabbed Interfaces. From there you might be intreaged by Cyrus Najmabadi's post. And from there Tabbrowser extension. Before long you've got a long list of things to read. Even before you're finished with Jeff's post there are 10 possible other interesting pages to read, and that's excluding the comments. Reach into each of these and there are hundreds of possible fasinating webpages.
If you're anything like Jeff that means you will have one or two browser windows with hundreds of tabs (despite this coming up a few times in his blog I annoyingly can't find any references to it now). If you're anything like me that means you'll have five or six browser windows with six or seven tabs each as I split things up into logical chunks. Maintaining and navigating this hodgepot of links is a difficult task.
This is because navigation is a tree, but most browsers like to make you think it's a list. A list is easy enough for people to understand. With under 10 items it's easy enough to maintain. The trouble is it just doesn't scale.
Back to Jeff's post - here's what links one may visit organised firstly as a tree in which you can easily understand what links to what, giving you the context of how it relates to other content.
The Problem With Tabbed Interfaces
- iRider
- Make Vista's Alt+Tab Thumbnail Bigger
Obviously once you get to Wikipedia there's no end of interesting things. And from every website on the internet you will almost always get to Wikipedia. And then never leave.
The cosmological argument, via Where's Waldo, is bizaarly removed from the problems with tabbed interfaces. But nether the less, that's inevitably how people navigate the web. So what does this bizaar sequence of interesting reads look like in Firefox as I'm browsing?
The Problem With Tabbed Interfaces I hate tabs in web browsers Tabextension3 Outsider FAQ iRider iRider Download Make Vista's Alt+Tab Thumbnail Bigger Where's Waldo? Where's Waldo (TV Series) HIT Entertainment Thomas and Friends Anthropomorthism Cosmological Argument
Except whilst doing that I was talking to a couple of people on IM, and one of my friends always sends me about 4 links as a replacement for the traditional "Hello, how are you?" so it really looks like this:
The Problem With Tabbed Interfaces I hate tabs in web browsers Openmoko Tabextension3 Outsider FAQ iRider Apple March 6th Event iRider Download Make Vista's Alt+Tab Thumbnail Bigger Audiosurf Where's Waldo? Where's Waldo (TV Series) HIT Entertainment Thomas and Friends Anthropomorthism Cosmological Argument
What links are related to the origional post? Which are the one's my friend sent me? How on earth did I get to Thomas and Friends? Who knows.
Interestingly IE uses a kludged tree. All the links you open from a webpage open in a list of new tabs after the current one. This means that you get a tree, only flattened into a list. It's quite confusing at first, but once you realise what it's doing it's useful at times. But why squash it into a list?
There's probably a plugin to make Firefox use a tree for tabs, but I've yet to find it.
I quite often find myself needing to store relationships between objects and as such have developed a small library for defining relation tables.
What sort of things would you need to store relationships about?
- The similarity between music tracks.
- The number of words spoken in an IM conversation between people.
- The position of a playoff in a tournament.
- How much people feel they trust other people.
This sort of information is perhaps best visualised in a table:
| Colour | Red | Green | Blue |
|---|---|---|---|
| Red | Red | Yellow | Magenta |
| Green | Yellow | Green | Cyan |
| Blue | Magenta | Cyan | Blue |
Here we are storing the relationship of colour combinations. If we want to find out what green combied with blue makes we look across to the row headered green, then down to the column headered blue and find that they combine to make cyan.
A table such as this is essentially a dictionary that takes a sequence as a key. An example C# implimentation would be:
public class RelationTable : Dictionary<IList, TValue>
{
private class SequenceEqualityComparer : IEqualityComparer<IList>
{
public bool Equals(IList x, IList y)
{
if (x.Count != y.Count) return false;
for (int i = 0; i < x.Count; i++)
{
if (!x[i].Equals(y[i])) return false;
}
return true;
}
public int GetHashCode(IList obj)
{
// TODO: Find a better hash function.1
int tally = 0;
foreach (TKey item in obj)
{
int hash = item.GetHashCode();
tally += (hash * hash);
}
return tally;
}
}
public RelationTable() : base(new SequenceEqualityComparer()) { }
}
Notice we had to define our own comparer so that two different objects containing the same values will be considered equal.
This is all well and good, but if you take a closer look at the table you should be able to see that we are actually duplicating a lot of information. Red combined with blue makes magenta, but then so does blue combined with red. This is because the arguments are commutative - the order can change without affecting the result. Because of this we can get away with storing only half the information (well, \frac{n^2+n} {2} to be precise):
| Colour | Red | Green | Blue |
|---|---|---|---|
| Red | Red | Yellow | Magenta |
| Green | Yellow | Green | Cyan |
| Blue | Magenta | Cyan | Blue |
In such a representation we can be more efficient about what we store by saying it is a dictionary that takes an unordered set as a key. An example C# implimentation would be:
public class CommutativeRelationTable : Dictionary<HashSet<TKey>, TValue>
{
public CommutativeRelationTable() : base(new SetEqualityComparer()) { }
public class SetEqualityComparer : IEqualityComparer<HashSet<TKey>>
{
public bool Equals(HashSet<TKey> x, HashSet<TKey> y)
{
return x.All(i => y.Contains(i)) && y.All(i => x.Contains(i));
}
public int GetHashCode(HashSet<TKey> obj)
{
// TODO: Find a better hash function.1
int tally = 0;
foreach (TKey item in obj)
{
int hash = item.GetHashCode();
tally += (hash * hash);
}
return tally;
}
}
}
This adds a little more time to the equality comparison, but makes managing the table a lot easier if you find yourself needing to change values often.
However, what is perhaps a little more interesting is how to model a commutative relation table with dense data over a finite set of orderable keys. If you have such a situation you can model it as a linear array:
| Row: | 0 | 1 | 2 | 3 | ||||||
| Index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| Column: | 0 | 1 | 2 | 3 | 1 | 2 | 3 | 2 | 3 | 3 |
The row and column of the diagram above correspond to the row and column index's of the commutative relation table. So, for instance, if you wanted to find the relationship between the 1st and the 3rd element you would look at index 6 of the array. Likewise, if you wanted to find the relationship between the 2nd and 0th element you would look at index 2.
The psuedocode for finding the index given the row and column is as follows:
row ← min(a, b)
column ← max(a, b)
row_start ← row*(size + 1) - 0.5*(row)*(row-1)
column_offset ← column - row
index ← row_start + column_offset
where size is the number of items in the relation
Note that we must first order the key values before we find the index.
Hopefully other people will find this information useful, I know I've certainly been using these classes alot lately.
1 If you know of a better hashing algorithm for these cases people tell me.
As I hinted in the update in my last post, I discovered a very nice addition to Gmail 2.0 which allows for much better Greasemonkey integration, meaning it's possible for me to update the script.
There are now two different versions, one for Firefox and one for Safari*. The one for Firefox will work with both Gmail 1.0 and Gmail 2.0. However, the one for Safari will unfortunately only work with Gmail 1.0 as the integration point isn't exposed in Safari.
I'll work on better integration (rather than a popup window) sometime later this week. However now I really need to sleep.
* Why two different scripts rather than checking for the presence of the API? It comes down to the differences between the implimentation of Greasemonkey. Greasemonkey uses unsafeWindow whereas Greasekit and Opera use window.
A while ago I wrote a plugin for Firefox that added a link to gmail enabling you to easily delegate emails to Todoist. Unfortunately the update of Gmail to 2.0 broke the plugin. Fortunately you can still use the old interface, and I suspect that's what a few people have been doing.
I've looked a few times into how to update it but I could never get the new interfact (turns out it doesn't work with English (U.K.)). Finally today I got it working but there is a bit problem. Gmail 2.0 preloads the messages, making it quicker to view messages but there is also now no request when you view an email, which the plugin relied upon to know when an email was being looked at and hence to inject the button.
It's probably possible to do some fancy injecting, function overriding or specific browser plugin tricks. However, all of those are beyond my immediate capabilities and I would have to either trawl through and understand Gmails compressed code or learn a heck of a lot more about plugins.
As an apology, here is a greasemonkey script which does what the old code did (minus the greybox stuff, which I'll probably add sometime soon). It can be used with Firefox's Greasemonkey plugin, Safari's Greasekit plugin or Opera 8's user scripting functionality (It probably works with some IE plugin, but I can't find or get one to work).
Update: I just discovered Google have release an experimental API. It now works with Gmail 2.0 in Firefox.
