loading...

Lists

jessekphillips profile image Jesse Phillips ・2 min read

In this article I will be using list as the concept of sequence of items and not a specific implementation.

If we take C# as an starting point, specific implementations would be:

  • List
  • Array
  • ArrayList
  • LinkedList

The general list concept in C# is IEnumerable. Objects implementing this can be used where processing a list is needed.

Note that not all code examples are valid, this will help me focus. Use the linked documentation to get correct implementation.

// C#
public class MyList : IEnumerable {
    IEnumerator IEnumerable.GetEnumerator() {
        return new MyListEnumerator(...);
    }
} 

public class MyListEnumerator : IEnumerator {
    public bool MoveNext()
    {
       ... 
    }

    public void Reset()
    {
       ... 
    }

    object IEnumerator.Current
    {
      ... 
    } 
} 

The actual iteration is handled by a IEnumerator which needs to be given what to iterate.

Java calls their's Iterable

public class MyList : Iterable {
    Iterator iterator() {
        return new MyListEnumerator(...);
    } 
} 

public class MyListEnumerator : Iterator {
    public boolean hasNext()
    {
       ... 
    }

    Object next() 
    {
      ... 
    } 
} 

Similar

  • identify if there are elements
  • obtain an element

Difference

  • advancement either happens while getting the item or while determining if iteration should stop

In D it is called a range

public struct MyList Enumerator {
    bool empty() {...} 
    Object front() {...} 
    void popFront() {...} 
} 

Similar

  • identify if there are elements
  • obtain an element

Difference

  • advancement is separate and not part of the other operations

Now I can tell you from experience that being able to obtain the current element can require having a temporary storage due to the underlying container or heavy computation.

It may also appear that D is cheating, in both Java and C# have two classes defined, a container and then the iterator. D does have the concept of a container, however foreach does not operate at that level, it is expected that to slice the container to get its range. This reduces overhead to chaining ranges while enumerable needs to contain and then enumerate.

Posted on by:

jessekphillips profile

Jesse Phillips

@jessekphillips

Senior Quality Assurance (SDET) ¶ Avid hobby D programmer ¶ Telling people what to do because I am right.

Discussion

markdown guide