Dan Byström’s Bwain

Blog without an interesting name

Better late than never

Posted by Dan Byström on September 15, 2008

Now this was nice – and unexpected:
http://www.telegraph.co.uk/news/newstopics/religion/2910447/Charles-Darwin-to-receive-apology-from-the-Church-of-England-for-rejecting-evolution.html

Darwin: 1 – Creationism: 0

BTW, isn’t it odd that a thing called “intelligent design” tends to be the very opposite? 🙂 Ekeforshus

Posted in Uncategorized | Leave a Comment »

Soft edged images in GDI+

Posted by Dan Byström on August 24, 2008

Last week I felt a sudden urge to create bitmaps with rounded corners and soft edges. Partly because I thought it would look nice, but mostly just as an intellectual exercise. (And also, according to Joel Spolsky, much of the success behind the iPod and iPhone can be attributed to their rounded corner design. That’s the best explanation I have come across, anyway!!! So, rounded corners sell! 🙂 )

Here are some sample pictures:

  1. Ordinary Graphics.DrawImage
  2. We can use a ColorMatrix to draw a semi-transparent image. However, I can’t figure out a way to use this technique to achieve the result I’m after.
  3. This is what I’m trying to achieve. What shall I call it? Smooth edges? Soft edges? Fluffy edges?
  4. In order to achieve 3) I’m about to inject this mask into the original image’s alpha channel.
  5. Although not discussed anymore in the article, we can use Graphics.SetClip to draw an image with round corners, but note the jaggedness at the corners. There may be some way to create anti-aliased clipping regions. If so, please drop a comment and tell me!
  6. Here I have used the technique which I’m discussing here (which produced 3) but without the “fluff” (a PathGradientBrush to be exact). Notice the smooth corners.

After spending way to much time figuring out a “pure” way to do this in GDI+, I gave up and decided to use LockBits to directly manipulate the pixels in the image. This is actually very straightforward and easy, but I can’t help feeling that there ought to be another way. If you know one, please drop a comment here. Using LockBits will result in an IntPtr pointing to the actual bits, leaving us with some different ways to access them:

  1. System.Runtime.InteropServices.Marshal.Copy. We can copy the pixels into a byte array, manipulate them and then copy them back. Unless we´re batch processing large amount of 16 mega pixels images I’ll guess we won’t notice much performance degradation, but it feels a little backward. If we’re going for a pure VB.NET solution, this is our only option I guess.
  2. The unsafe keyword in C#. This is just perfect, if it wasn’t for my previous traumatic experience with how .NET restricts unsafe assemblies. Anyway, this is what I’ll use in the sample code below.
  3. C++ with Managed Extensions. I suspect that most .NET programmers feel uneasy with this, but I think this is a much underestimated option. I’m not kidding you when I say that it actually takes less than ten minutes to add a new C++ project to your Visual Studio solution and write a C++ version of the unsafe code that I’m about to use. A few years ago I wrote a short tutorial on this.

The strategy I decided to go for is simple:

  1. Create a mask like the one in picture 4). This is done by the methods createRoundRect and createFluffyBrush below. The meaning of this mask is simple: the darker a pixel is, the more transparent shall the real image become in that particular place. And vice versa: the lighter a pixel is, the more opaque shall the image become in that part. Is is no coincidence that this is just the way the alpha channel works. 🙂
  2. Then I create a new bitmap as an exact copy of the original image (if I have more use of the original image that is, otherwise this can be skipped).
  3. Finally, I take one of the red, blue or green channels (irrelevant which one) from the mask and copy it into the new bitmap’s alpha channel! This is done by transferOneARGBChannelFromOneBitmapToAnother (surprise!).
  4. Done

So, here are the three helper methods:


        static public GraphicsPath createRoundRect( int x, int y, int width, int height, int radius )
        {
            GraphicsPath gp = new GraphicsPath();

            if (radius == 0)
                gp.AddRectangle( new Rectangle( x, y, width, height ) );
            else
            {
                gp.AddLine( x + radius, y, x + width - radius, y );
                gp.AddArc( x + width - radius, y, radius, radius, 270, 90 );
                gp.AddLine( x + width, y + radius, x + width, y + height - radius );
                gp.AddArc( x + width - radius, y + height - radius, radius, radius, 0, 90 );
                gp.AddLine( x + width - radius, y + height, x + radius, y + height );
                gp.AddArc( x, y + height - radius, radius, radius, 90, 90 );
                gp.AddLine( x, y + height - radius, x, y + radius );
                gp.AddArc( x, y, radius, radius, 180, 90 );
                gp.CloseFigure();
            }
            return gp;
        }


		public static Brush createFluffyBrush(
			GraphicsPath gp,
			float[] blendPositions,
			float[] blendFactors )
		{
			PathGradientBrush pgb = new PathGradientBrush( gp );
			Blend blend = new Blend();
			blend.Positions = blendPositions;
			blend.Factors = blendFactors;
			pgb.Blend = blend;
			pgb.CenterColor = Color.White;
			pgb.SurroundColors = new Color[] { Color.Black };
			return pgb;
		}

		public enum ChannelARGB
		{
			Blue = 0,
			Green = 1,
			Red = 2,
			Alpha = 3
		}

		public static void transferOneARGBChannelFromOneBitmapToAnother(
			Bitmap source,
			Bitmap dest,
			ChannelARGB sourceChannel,
			ChannelARGB destChannel )
		{
			if ( source.Size!=dest.Size )
				throw new ArgumentException();
			Rectangle r = new Rectangle( Point.Empty, source.Size );
			BitmapData bdSrc = source.LockBits( r, ImageLockMode.ReadOnly, PixelFormat.Format32bppArgb );
			BitmapData bdDst = dest.LockBits( r, ImageLockMode.ReadWrite, PixelFormat.Format32bppArgb );
			unsafe
			{
				byte* bpSrc = (byte*)bdSrc.Scan0.ToPointer();
				byte* bpDst = (byte*)bdDst.Scan0.ToPointer();
				bpSrc += (int)sourceChannel;
				bpDst += (int)destChannel;
				for ( int i = r.Height * r.Width; i > 0; i-- )
				{
					*bpDst = *bpSrc;
					bpSrc += 4;
					bpDst += 4;
				}
			}
			source.UnlockBits( bdSrc );
			dest.UnlockBits( bdDst );
		}

I’m not about to explain how any of the above methods work. If you don’t understand… just google for any of the keywords and you’ll find tons of tutorials. If something is still unclear, drop a comment here and I’ll see what I can do. The purpose of this article is the simple idea that you can inject a mask created with normal GDI+ operations into an image’s alpha channel, making that image transparent, semi-transparent or opaque exactly where you want it to. So now we just put it all together:

			Bitmap bmpFluffy = new Bitmap( bmpOriginal );
			Rectangle r = new Rectangle( Point.Empty, bmpFluffy.Size );

			using ( Bitmap bmpMask = new Bitmap( r.Width, r.Height ) )
			using ( Graphics g = Graphics.FromImage( bmpMask ) )
			using ( GraphicsPath path = createRoundRect(
				r.X, r.Y,
				r.Width, r.Height,
				Math.Min( r.Width, r.Height ) / 5 ) )
			using ( Brush brush = createFluffyBrush(
				path,
				new float[] { 0.0f, 0.1f, 1.0f },
				new float[] { 0.0f, 0.95f, 1.0f } ) )
			{
				g.FillRectangle( Brushes.Black, r );
				g.SmoothingMode = SmoothingMode.HighQuality;
				g.FillPath( brush, path );
				transferOneARGBChannelFromOneBitmapToAnother(
					bmpMask,
					bmpFluffy,
					ChannelARGB.Blue,
					ChannelARGB.Alpha );
			}
			// bmpFluffy is now powered up and ready to be used

The code above is sprinkled with magic numbers, so you can tell that it’s not production code! 🙂

  • Math.Min( r.Width, r.Height ) / 5. This is just may way of saying that I want the size of the rounded corners to be 20% the size of the shortest bitmap side.
  • new float[] { 0.0f, 0.1f, 1.0f } and float[] { 0.0f, 0.95f, 1.0f } this controls how much “fluff” I want at the edges. For example, you may find that new float[] { 0.0f, 0.1f, 0.2, 1.0f } and float[] { 0.0f, 0.9f, 1.0f, 1.0f } suits you better!
  • The arguments to transferOneARGBChannelFromOneBitmapToAnother. Why do I copy the blue channel??? Well, red or green will just just fine too! Since we have painted only gray scale values to bmpMask, the red, green and blue channels will be identical!

And of course, the mask doesn’t have to be created this way. Among other things, you could save a predefined Edge from Paint Shop Pro’s Picture Frames and load it into your app.

Happy coding! Ekeforshus

Posted in .NET, GDI+, Programming | 9 Comments »

Real Programmers don’t use Pascal – 25 year annivarsary

Posted by Dan Byström on July 31, 2008

I just happened to notice that the legendary text “Real Programmers Don’t Use Pascal” was published exactly 25 years ago this month (and I just have a couple of hours left before this month ends, so I thouht I had to write up something quickly). You can often find it on the Net filed under “humor”. This can, of course, only be done by Quiche Eaters! Sometimes someone has replaced Pascal with Visual Basic. I have no problem with that. 🙂

Among all the words of wisdom, I found these:

  • Real Programmers aren’t afraid to use GOTOs.
  • Real Programmers can write five page long DO loops without getting confused.
  • Real Programmers like Arithmetic IF statements– they make the code more interesting.
  • Real Programmers write self-modifying code, especially if they can save 20 nanoseconds in the middle of a tight loop.
  • Real Programmers don’t need comments– the code is obvious.
  • Since Fortran doesn’t have a structured IF, REPEAT … UNTIL, or CASE statement, Real Programmers don’t have to worry about not using them. Besides, they can be simulated when necessary using assigned GOTOs.

I guess that the number of programmers out there who have written (or even know what it means to write) arithmetic IF-statements or self-modifying code are decreasing rapidly by the day. And writing a five page long DO loops without getting confused may be a cool party trick, but nothing to applause in real work. But the remaining two points are something I’d like to comment!

Real Programmers aren’t afraid to use GOTOs

Well, why on earth should they be? Really? This “truth” seems to be something that all student know by heart. Thou shalt not use GOTO. Thou shalt not use GOTO. Without even understanding why GOTO was such a big problem in the first place. In a structured language it is not. How could it be that more students seem to know about this silly “non-problem” while at the same time failing to understand the most fundamental thing about programming: Thou shalt never duplicate code. Thou shalt not use copy-and-paste. I just wonder…

Real Programmers don’t need comments– the code is obvious

I think this is almost true! It only needs slight modification:

Real Programmes write code in such a way that the code becomes obvious

I have come to realise that when I download a piece of code from the Net, the first thing I usually have to do is delete all the comments so that I can read the code!!! Most of the time, comments seem to have been put there just “because you must write comments”. Then after a time, changes are made to the code and the comments are not updated, leaving any reader totally confused! Skip the comments and write clean code with long descriptive methods and variable names I say!

(This goes for much of the documentation too, I think. The code is the best documentations because it is “the truth”! This is one of the reasons Tests (Test Driven Development) is such a great thing: you get “true documentation” for free.)

Posted in Nostalgia, Programming | Leave a Comment »

Quote of the day

Posted by Dan Byström on July 18, 2008

“He doesn’t seem to have all his methods compiled”.
— Douglas Nilsson Ekeforshus

Posted in Programming | Leave a Comment »

VB.NET as a DSL

Posted by Dan Byström on July 4, 2008

The other day I got a glimpse of something that could turn out to be really useful. Or maybe a Pandora’s Box. I really don’t know until I investigated it more. 🙂

I was asked to add some simple string manipulation functions (to something that we for simplicity can think of as a report generator).

After thinking about the problem I decided that I would violate the YAGNI (you ain’t gonna need it) principle and give the customer the full Monty directly. Why? Because I realized that it was so incredibly easy to give them the possibility to write full fledged VB.NET code directly that it would probably take the same amount of time to code as some basic string manipulation functions together with a UI!

Consider the following facts:

  1. It is extremely easy (and fast) to compile a piece of VB.NET (or C#) code into an in-memory assembly and execute that code. It takes roughly 20 lines of code.
  2. This dynamically compiled code can easily be given access to any specified part of the application or it’s business objects (just by adding the appropriate assemblies).
  3. Of course the code to be compiled can be preprocessed first, in order to provide the user with a syntax as simple as possible.

I think that these facts taken together implies that opening up parts of the business logic code to the user / customer / domain expert could be worthwhile.

So, the next time I feel that:

  1. I am just transforming the domain expert’s words into executable code
  2. I may not have fully understood the intention of the domain expert
  3. the code I’m writing is likely to change in the future

Then I will definitely consider making that code modifiable by both the domain experts and me (or most likely: read by the domain experts and modified by me and them together). The choice of VB.NET over C# seems obvious; novices read Basic easier – it is no coincidence that “B” in BASIC stands for Beginner. Many users have also encountered VBA while playing around with macros in Word and Excel. Ekeforshus

Posted in .NET, Programming | Leave a Comment »

Wow – I’m on a list, I’m on a list

Posted by Dan Byström on May 5, 2008

http://www.computersweden.idg.se/2.2683/1.159414

For some reason (that eludes me) my name has just appeared on a list which claims to contain the top 75 developers and architects in Sweden.

Of course I didn’t deserve this. On the other hand, there are things I think I did deserve and didn’t get, so I hope that all these things will somehow add up in a fair and just way before my coffin gets nailed shut. Ekeforshus

Posted in Uncategorized | 3 Comments »

A Newer Age

Posted by Dan Byström on March 28, 2008

Dream Catcher

Are the guys at your marketing department running around with mighty New Age Crystals and sleep under Indian Dream Catchers? Do you believe this is the root of all you especially nasty bugs lately? Then you obviously are in need of an equally mighty Anti-Crystal (or really, a shrink).

Actually I guess it’s more likely that you just want to harass them a little. Then www.newer-age.com comes to your assistance! A third option is of course that you are bored enough to like to participate in a Whale Song Expedition (that is, you sing to the whales!).

I know the guy behind this. Are there any qualified psychiatrist out there who can tell me if he’s likely to become violent…? 😉

Anyway I know he will be thrilled if his visitors counter would somehow sky rock to one hundred visitors.

www.newer-age.com

Posted in Uncategorized | Leave a Comment »

Insomnia

Posted by Dan Byström on March 6, 2008

To iterate is human, to recurse divine.

L. Peter Deutsch

To iterate is boring, to recurse plesantly dizzying.

Dan Byström

Have you ever tried counting sheep when trying to sleep? For twenty years I’ve been utilizing a different method. I’ve been trying to solve the following problem:

How do you build a balanced binary search tree from a stream of sorted data of unknown size?

That is, given a stream of the letters: ABCDEFGHIJKLMNO, construct the following tree:

H
/ \
D L
/ \ / \
B F J N

/

\

/

\

/

\

/

\
A C E G I K M O

directly by reading the characters one by one and place them DIRECTLY in the correct position WITHOUT using any intermediate storage.

I’m confident that this has been thoroughly researched at least half a century ago, but I have never wanted to look up any solution – what’s the fun in solving a crossword puzzle if you look at the solution first?

This sleeping strategy has been very successful, up until last week, when baby Ellen gave up a horrible cry in the middle of the night – and while trying to go to sleep again I remembered this old problem. Accidentally I solved it and now it’s useless as a sleeping pill!!! But since I have a history with this problem for twenty years now, I thought I had to write a little memorial over it before letting go.

This will also be a tribute to the most powerful solving method I know of: Divide and Conquer!

Background

Two decades ago, when I was a student (that was at a time when I could also be called both young and promising) taking a programming course I chose to write a record register application using Turbo Pascal 3.0. This was a time when CD players were just as common a Bly-ray players today (that is: most people were still waiting for the prices to drop). Vinyl was the name of the game. (Turbo Pascal 3.0, by the way, was an incredible piece of work; the whole environment consisted of one file with the whopping size of 38kb containing the full runtime system, the compiler and the source code editor! You read right: 38kb – not 38Mb!)

I wanted this application to be able to run smoothly with its data files residing on a floppy disc (and of course, memory consumption had to be low). I chose to use binary search trees to keep track of the albums, artists and song titles. This worked well and it was quite fun figuring out all the things that were not in the books, like: given an arbitrary node in a tree, how do you implement a “next” function that will bring you to the next node in sort order when the user hits the “next” button? Not completely obvious the first time you try to acquaintance yourself with the concept of trees. Adn then embarrasingly simples once you figured it out.

However, there was this one thing that I never bothered to figure out, but took an easy way out. That has nagged me ever since.

Prequisities

Let’s declare a simple binary tree node:

public class Node<T> where T : IComparable<T>
{
  public readonly T Data;
  public Node<T> Left;
  public Node<T> Right;
  public Node( T data )
  {
    Data = data;
  }
}

Then let’s define a data pump that will read data/records/entities (or whatever we like to call them) from some kind of stream. The important thing here is that there is no look-ahead facility:

interface IStreamingDataPump<T> where T : IComparable<T>
{
  T GetNextData();
  boolEOF { get; }
}

Maybe it helps our thinking if we have a concrete example implementation of the interface as well:

public class TestCharPump : IStreamingDataPump<char>
{
  string data = "ABCDEFGHIJKLMNO";
  int index = 0;
  public char GetNextData()
  {
    return data[index++];
  }
  public bool EOF
  {
    get { return index >= data.Length; }
  }
}

Obviously, this data pump will deliver the sorted characters A to O (in order) to a consumer, throwing an error if trying read past the last character.

The problem with inserting already sorted data

The standard way of inserting data into a binary tree:

public static Node<T> Insert( Node<T> tree, T data )
{
  while ( true )
  switch ( Math.Sign( tree.Data.CompareTo( data ) ) )
  {
    case 1:
      if ( tree.Left == null )
        return tree.Left = new Node<T>( data );
      tree = tree.Left;
      break;
    case -1:
      if ( tree.Right == null )
        return tree.Right = new Node<T>( data );
      tree = tree.Right;
      break;
    case 0:
      throw new Exception( "Duplicate keys!" );
  }
}

If we read all the data from our stream containing sorted data and use the method above:

Node<T> tree = _pump.EOF ? null : new Node<T>( _pump.GetNextData() );
while( !_pump.EOF )
  Node<T>.Insert( tree, _pump.GetNextData() );

…then we effectively end up with a linked list instead of a binary tree:

A
B
C
D
E
F
G
H
I
J
K
L
M
N
O

The standard(?) solution

So, what I’ve did in my record register application was something like this:

public Node<T> CreateTreeFromList( List<T> list, int left, int right )
{
  if ( left > right )
    return null;
  int middle = (left + right) / 2;
  Node<T> tree = new Node<T>( list[middle] );
  tree.Left = CreateTreeFromList( list, left, middle - 1 );
  tree.Right = CreateTreeFromList( list, middle + 1, right );
  return tree;
}

And then made use of that function like this:

List<Song> list = new List<Song>();
while( !_pump.EOF )
  list.Add( new Song( _pump ) );
Node<Song> tree = Node<Song>.CreateTreeFromList( list, 0, list.Count - 1 );

As you can see, I first read the whole stream into memory and then I construct the tree from there.

This will construct a perfectly balanced tree and the performance will be good. So what’s the problem? Well, actually there is no real problem, it is just that I feel that first storing the data in a vector, when it is a tree we want is an unnecessary step!!!

Another approach

So, given ABCDEFGHIJKLMNO, I want to read one character at a time and place it at the correct position in the balanced tree:

H
/ \
D L
/ \ / \
B F J N

/

\

/

\

/

\

/

\
A C E G I K M O

And again, the number of nodes must not be known in advance!

So let’s think about it. Reading A into a node seems uncomplicated. Then we should read B and somehow realize that it must be placed in such a manner that it will become the new tree root and that the previous tree root should become the left node of the new root.

Reading C and placing it as the right node of the current tree root seems fair enough, and the next node D should be handled similar to the B node… but now it gets strange, the E node should be placed in a void because F hasn’t been seen yet… and what if there IS no F node? If E is the last element in the stream it should come directly under D but not if the F appears.

And thinking about what will happen after the G is read seems even stranger, although there clearly isa pattern here if you say “EFG” will be handled exactly like “ABC”, and in fact, B and F behaves similar… so… what makes A and E alike… aaaa….

This is were I used to fall asleep. 🙂

Up until a night last week, then my brain got bored of having to start all over again with this problem and thought that it was best to settle the thing once and for all. There was no quantum leap – just the most common tool we use every day: divide and conquer!

With the aid of first one and then two helper functions the solution was suddenly crystal clear.

Reasoning away…

Firstly, one thing that disturbs my thinking a great deal is that we always have the risk of running into EOF. We can reduce that problem somewhat by a tiny helper:

public Node<T> ReadNodeFromStream()
{
  if( _pump.EOF )
    return null;
  return new Node<T>( _pump.GetNextData() );
}

Thinking about it, what we now have is a function that can create a zero or one element sized tree. Not bad really! 😉 Also note one other important fact: we are allowed to call this many times after reaching EOF – it will return null every time.Can we extend this into a three element sized tree (=height of two)?

public Node<T> thinkingOutLoud_1()
{
  Node<T> left = ReadNodeFromStream();
  Node<T> tree = ReadNodeFromStream();
  Node<T> right = ReadNodeFromStream();
  tree.Left = left;
  tree.Right = right;
  return tree;
}

Well, not quite… this will work if there are at least two elements in the stream, but otherwise it will crash. It can be fixed very easily though:

public Node<T> thinkingOutLoud_2()
{
  Node<T> left = ReadNodeFromStream();
  Node<T> tree = ReadNodeFromStream();
  if ( tree == null )
    return left;
  Node<T> right = ReadNodeFromStream();
  tree.Left = left;
  tree.Right = right;
  return tree;
}

Spot on! What about a next step… modifying the method to create a one or two level high tree?

public Node<T> thinkingOutLoud_3( int height )
{
  if ( height == 1 )
    return ReadNodeFromStream();
  Node<T> left = ReadNodeFromStream();
  Node<T> tree = ReadNodeFromStream();
  if ( tree == null )
    return left;
  Node<T> right = ReadNodeFromStream();
  tree.Left = left;
  tree.Right = right;
  return tree;
}

This method knows how to create two different sized trees, and it has no trouble at all dealing with EOF. But wait a minute… can’t we just as well write it this way, it wouldn’t change a thing if we call it with parameter of 1 or 2:

public Node<T> thinkingOutLoud_4( int height )
{
  if ( height == 1 )
    return ReadNodeFromStream();
  Node<T> left = thinkingOutLoud_4( height-1 );
  Node<T> tree = ReadNodeFromStream();
  if ( tree == null )
    return left;
  Node<T> right = thinkingOutLoud_4( height-1 );
  tree.Left = left;
  tree.Right = right;
  return tree;
}

But what if we call it with a desired height of three… or four…? Wow! I think that we safely can rename this method:

public Node<T> CreateTreeOfDesiredHeight( int height )
{
  if ( height == 1 )
    return ReadNodeFromStream();
  Node<T> left = CreateTreeOfDesiredHeight( height-1 );
  Node<T> tree = ReadNodeFromStream();
  if ( tree == null )
    return left;
  Node<T> right = CreateTreeOfDesiredHeight( height-1 );
  tree.Left = left;
  tree.Right = right;
  return tree;
}

AHHH! Recursion. (Said like Homer Simpson.)

If we knew the length of the stream we could create our tree like this:

Node<T> tree = createTreeOfDesiredHeight(
  (
int)Math.Ceiling( Math.Log( _pump.Length ) / Math.Log( 2 ) ) );

But we don’t. So exactly how does this help us anyway? It actually helps quite a lot – we’re almost done. We just have an iterative method left. And since iterative methods are boring, I won’t say much about it:

public Node<Data> CreateBalancedTree()
{
  Node<Data> left = ReadNodeFromStream();
  for ( int height = 1 ; ; height++ )
  {
    Node<Data> tree = ReadNodeFromStream();
    if ( tree == null )
      return left;
    tree.Left = left;
    tree.Right = CreateTreeOfDesiredHeight( height );
    left = tree;
  }
}

Well, maybe I should say something…

  1. Create a “left tree” of height one and then try to tuck on a root above it.
  2. If there are no more elements, then out left tree is the tree and we´re done.
  3. Otherwise create a right tree of the same height as our left tree
  4. Name our newly created tree the new “left tree” and repeat step two

Note that the key to this solution is step 3 – creating a subtree of a desired height. The part that made me pleasantly dizzy! 🙂

But… wait a minute… is this really it? Isn’t it strange that we now use completely different pieces of code to produce the left tree and the right tree??? Indeed it is! The CreateTreeOfDesiredHeight method is only a helper method I used to arrive at the solution!!! Since our CreateBalancedTree method is obviously fully capable of of creating the left tree and there is no difference between a left tree and a right tree:

The solution

public Node<Data> CreateBalancedTree( int maxHeight )
{
  Node<Data> left = ReadNodeFromStream();
  for ( int height = 1 ; height<maxHeight ; height++ )
  {
    Node<Data> tree = ReadNodeFromStream();
    if ( tree == null )
      return left;
    tree.Left = left;
    tree.Right = CreateBalancedTree( height );
    left = tree;
  }
  return left;
}

Iteration begone! And since a caller doesn’t care about any maxHeight, we can create our final (overloaded) method as such:

public Node<Data> CreateBalancedTree()
{
  return CreateBalancedTree( int.MaxValue );
}

Again, it is so embarrassingly simple once you figured it out! And this tiny piece of (almost) trivial code eluded me for so long!

OK, so now this was really really old news I guess. And there are things to criticize as well. First of all, what’s the point really? The method of loading the stream into a vector works faster AND produces a better tree, since my solution actually isn’t balanced (it is in our case where the number of elements is 2N-1) – it just has the same height as a balanced tree. But I’m fine with that.

There seems to be a lot of misconceptions around recursion out there, like that it is slow and uses an excessive amount of stack memory. Of course, calculating Fibonacci numbers using recursion instead of iteration should only be done as an intellectual exercise. But the fact that people think that it’s slow may be due to reasoning like this:

Fact: A recursive algorithm is slower than an iterative method when an equal iterative method exist.
Conclusion: All recursive algorithms are slow.

This is of course exactly the same reasoning as:

Fact: All cheeses are round and the moon is round.
Conclusion: The moon is made out of cheese.

Well, well. I don’t know how to end this, but I’ll give it a try anyway:

Try and be nice to people, avoid eating fat, read a good book every now and then, get some walking in, and try and live together in peace and harmony with people of all creeds and nations.

Monty Python
The meaning of Life

Posted in Nostalgia, Programming | 4 Comments »

42

Posted by Dan Byström on February 26, 2008

  It is said that there is nothing surprising about the notion of, for instance, a person suddenly thinking about someone they haven’t thought about for years, and then discovering the next day that the person has in fact just died. There are always lots of people suddenly remembering people they haven’t thought about for ages, and always lots of people dying. In a population the size of, say, America the law of averages means that this particular coincidence must happen at least ten times a day, but it is none the less spooky to anyone who experiences it.  

The Long Dark Teatime of the Soul
Douglas Adams

Since this is my blog post number 42 – how can I avoid mentioning Douglas Adams and silly coincides? 🙂

I recently noticed that in a project I’ve been working on for some years now, the very first order entered into the system, order number 1, was handled by photographer number 42. And I thought to myself “how can a project starting out like this be anything less than a success”?!?

Speaking of blog post numbers, another equally pointless coincidence was that my blog post number 40 was about my 40th birthday. But still I cannot help myself from thinking that it is a little funny… :s

Posted in Uncategorized | Leave a Comment »

Jukebox II

Posted by Dan Byström on December 12, 2007

Exactly one year ago I created my Jukebox page. To celebrate the anniversary I uploaded a bunch of new tunes.

Posted in Uncategorized | Leave a Comment »