Netxus Foundries

Been a quite long time since the last update. I’m a bit ashamed for not keeping the blog updated regularly but I must confess that I’ve been expending my time on other affairs more important to me.

Anyways, in this weeks I’ve been working again on TextAreaPlus, actually I’ve been busy making a full rewrite of the lexing scanner and optimizing the implementation to the limits of my knowledge. The algorithm used is described in the project wiki

Today I was re-installing the PC at work since it broke havoc yesterday. After finishing the installation of almost all softwares I decided to have a look for a notepad replacement which was more feature packed than Scite and a bit faster than Notepad++ to perform some minor editing of config files mainly. In the search I found a couple of new editors which I didn’t knew about but which seem to be gaining momentum. Both seem to be based on a successful Mac text editor called TextMate, which I have heard about from Ruby-on-Rails evangelist but given to my allergic reactions to anything mac related lately I didn’t check before. Today, trying those two new editors I got interested in TextMate and I’ve been learning about it in the last hour.

So long history short, I thought I had invented the sliced bread with my implementation and design ideas for TextAreaPlus but it turns out that Allan Oddgaard, the TextMate developer, already implemented it in a very similar way a couple of years ago. My feelings are a bit conflictive right now, in one way I feel sad because I just reinvented the wheel but in the other I feel reassured to have come up with a solution which turns out to be proved and successful.

I’ve written a couple hundred words with a couple of links in this post using a lame browser textarea, in moments like this I wish I had already a production ready version of TextAreaPlus. Lets hope I don’t keep wishing for it too long.

Long time since I last wrote here so I’ll take the opportunity to introduce (just joking) the Binary Search algorithm.

I was looking for a safe way to find the line of text where a user clicks the mouse. I needed this for the TextArea+ editor. Fortunately Mozilla supports the DOM3’s compareDocumentPosition() function, so I took advantatge of it. Since I’m using a UL with an LI child element for each line of text, I can say that UL.childNodes is an ordered array, which fits perfectly for the Binary Search algorithm.

The algorithm is really simple (I’m sure most of you have used it before), we just need to find the middle point between two points and compare its value with the one we’re looking for. We do this recursively until we either find the value or the right point becomes smaller than the left one, which means that the value is just not there.

Here comes a really simple example of this algorithm (without using recursive calls)

var left = 0;

var right = 100;

while (left <= right)

{
  middle = floor( (right-left)/2 ) + left;
  if (haystack[mid] == needle)
  {
    alert('Found!');
    break;
  }
  if ( needle < haystack[middle] )
    right = middle-1;
  else 
    left = middle+1;

}

The Binary Search algorithm performs at O(log n) time, but for TextArea+ I use a number of further optimizations. Since it’s likely that the user will click closely to where the cursor currently is, I just check the N precedding and following lines before. If this fails I check the current viewport and if still not found, then just do a full search.
And this is just for the Mozilla code path! hell, how I hate cross-browser coding!

This post is meant to remind us how important is to learn already known and proved algorithms and that even when having a good algorithm, there is always room to optimize by taking advantge of our specific problem.