Going Round and Round

Did you think iteration was simple? Well, there’s more than one way to do it. For this example, let’s imagine we have a class called Provider. Let’s imagine it has a Get function which either returns the next item or returns null when there are none left. How would you empty this provider and add all its objects to a list or concatenate them in a string?

We saw some code which looked like this

            // append to StringBuilder
            StringBuilder builder = new StringBuilder();

            while (true)
            {
                string next = provider.Get(); // get next
                if (next == null)
                {
                    break;
                }
                builder.Append(next); // append
            }

The old while-true solution. It just looks wrong. In the code we saw, there was a little more to the “GetNext” and the “Append” lines, so it looked worse.

Surely there are other ways of doing it? Well, let’s have a look at some.

Firstly we need a testable provider:

    /// <summary>
    /// A simple provider that will return C, B, A and then nulls
    /// </summary>
    public class Provider
    {
        private Stack<string> data;
        public Provider()
        {
            data = new Stack<string>();
            data.Push("A");
            data.Push("B");
            data.Push("C");
        }

        public string Get()
        {
            if (data.Count>0)
            {
                return data.Pop();
            }

            return null;
        }
    }

And a test case that proves our methods actually work. I’ve put my different implementations of the iteration into a class called SimpleIterators.

        [Test]
        public void WhileTrueImplementation()
        {
            Assert.That(SimpleIterators.BuildWithWhileTrue(new Provider()), Is.EqualTo("CBA"));
        }

Alternative 1 – put the setup outside the while

        public static string BuildWithSetupAndWhile(Provider provider)
        {
            StringBuilder builder = new StringBuilder();

            string next = provider.Get();
            while (next!=null)
            {
                builder.Append(next);
                next = provider.Get();
            }


            return builder.ToString();
        }

This is interesting – the provider’s “Get” function is called twice. It’s simple to read and doesn’t rely on breaking out of an infinite loop. It still seems to have some wasted code in it.

Alternative 2 – put the setting up of next into the while condition

This is the C++ style way of doing it:

        public static string BuildWithSetupAndWhileInline(Provider provider)
        {
            StringBuilder builder = new StringBuilder();

            string next;
            while ((next = provider.Get()) != null)
            {
                builder.Append(next);
            }

            return builder.ToString();
        }

That while statement is nigh on unreadable. It’s computer-readable code… it’s doing two things at once and isn’t especially nice.

Alternative 3 – For

There is more to a loop than a while construct:

        public static string BuildWithFor(Provider provider)
        {
            StringBuilder builder = new StringBuilder();

            for(string next = provider.Get(); next!=null; next=provider.Get())
            {
                builder.Append(next);
            }


            return builder.ToString();
        }

This is really just the while solution with the whole workings of the loop in a single line. In some ways this is what “for” is for. It feels ok, but there are still two calls to “Get” and when we’ve tried this with more real-world code, it’s come across as unreadable.

Alternative 4 – The Enumerator

Let’s ignore the implementation of the enumerator and look at the calling code first:

        public static string BuildWithEnumerator(Provider provider)
        {
            StringBuilder builder = new StringBuilder();

            foreach (string next in provider.Enumerator())
            {
                builder.Append(next);
            }

            return builder.ToString();
        }

That is very nice. The entire problem of iterating over the provider is encapsulated by the provider.

How does the provider’s code look?

Well, for this example, I’ve assumed that the only way to process is by use of a “Get” function which returns either null or the item.

// In the provider class:
        public IEnumerable<string> Enumerator()
        {
            string next; 
            do
            {
                next = Get();
                if (next!=null)
                {
                    yield return next;
                }
            } while (next != null);
        }

A do while loop with an if statement seemed to work here. In fact, we could have used pretty much all of the above looping constructs to achieve this enumerator replacing the “Append” with the “yield” statement, which represents the magic of this enumeration syntax-sugar that C# lets us use to build enumerators over collections.

But if I’m working close to the class
When I was within the internals of the provider class I realised I could write this enumerator:

        public IEnumerable<string> Enumerator2()
        {
            while (data.Count>0)
            {
                yield return Get();
            }
        } 

This was because I could see when there was no data left.

In fact this is what would have been possible to write in the client code if Provider had originally given us an “Eof()” function or its equivalent.

Conclusion
The biggest conclusion here is that “return null for end of list” is an awful way to provide client code with an interface to read from you. The “bool Eof()” pattern is clearly better.

However, the next conclusion is that the client code should be optimised for readability and the foreach + Enumerator is a really good solution. You can write a custom iterator to act as a middle man between client code and an object that has a terrible way of managing its internals.

Advertisements

5 comments

  1. When you implement the Enumerator on the provider you can are able to shorten the method BuildWithEnumerator ->

    public static string BuildWithEnumerator(Provider provider)
    {
    StringBuilder builder = new StringBuilder();
    provider.Enumerator().Aggregate(builder,(builder,next)=>builder.Append(next));
    return builder.ToString();
    }

    • of course to ->

      public static string BuildWithEnumerator(Provider provider)
      {
      StringBuilder builder = new StringBuilder();
      provider.Enumerator().Aggregate(builder,(sb,next)=>sb.Append(next));
      return builder.ToString();
      }

  2. From the first implementation of your enumerator, I extracted the Logic in a class an build a “static extension method”, so the calling side looks like ->

    // The calling
    IterateUntilNull iun = new IterateUntilNull();
    foreach(var item in iun.Enumerator() ) {
    System.Console.WriteLine(item);
    }
    System.Console.ReadLine();

    where IteratorUntilNull has the GetNext() method, which return null, when finished ….

    http://pastebin.com/JfdvX866 <- the code

    thx, for the interesting articles

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s