Cook Computing

ArraySegment and SubArray

November 24, 2011 Written by Charles Cook

ArraySegment

I was looking at an algorithm which involves processing segments of an array recursively and I thought the code would be neater if instead of passing the array plus the offset and length of each segment I could use an array data type which provides a view onto a segment of an array. The ArraySegment type appeared in search results and it's name sounded promising. I'd not heard of it before but it's been around since .NET 2.0 and is used in various types including Socket and LogRecordSequence. Unfortunately it is essentially just a way of specifying a segment and doesn't provide any methods to access the data within the segment:

public struct ArraySegment<T>
{
  public ArraySegment(T[] array);
  public ArraySegment(T[] array, int offset, int count);
  public static bool operator !=(ArraySegment<T> a, ArraySegment<T> b);
  public static bool operator ==(ArraySegment<T> a, ArraySegment<T> b);
  public T[] Array { get; }
  public int Count { get; }
  public int Offset { get; }
  public bool Equals(ArraySegment<T> obj);
  public override bool Equals(object obj);
  public override int GetHashCode();
}

It also doesn't have a constructor which takes an ArraySegment so making it awkward to use for recursive algorithms, but it's a ready-made class if you need to specify segments of an array without making copies of the array, as in this example.

SubArray

At first I thought it would be nice if SubArray was an array type but I quickly realized you cannot derive from System.Array. According to MSDN:

The Array class is the base class for language implementations that support arrays. However, only the system and compilers can derive explicitly from the Array class. Users should employ the array constructs provided by the language.

So it's not possible to create an array type which represents a sub-array. The solution was to implement a type which derives from IList<T>. This provides methods for indexing and enumerating the sub-array. The Java interface List has a method called subList which provides some prior art for this:

Returns a view of the portion of this list between the specified fromIndex, inclusive, and toIndex, exclusive. (If fromIndex and toIndex are equal, the returned list is empty.) The returned list is backed by this list, so non-structural changes in the returned list are reflected in this list, and vice-versa. The returned list supports all of the optional list operations supported by this list...

...The semantics of the list returned by this method become undefined if the backing list (i.e., this list) is structurally modified in any way other than via the returned list. (Structural modifications are those that change the size of this list, or otherwise perturb it in such a fashion that iterations in progress may yield incorrect results.)

In the case of the new SubArray type we'll assume the underlying collection is an array, i.e. of fixed length, so the methods of IList<T> which change the length of the list will throw NotSupportedException. We will also allow an instance of a SubArray to be created as an offset into an existing SubArray (with the Offset property of the "sub-SubArray" referring to the original array and not to its parent SubArray). Finally as with ArraySegment the SubArray type will be a struct. Throw in some extension methods to make it easier to use and came up with this: SubArray.cs

Example Usage

Reconstruct a binary tree from arrays containing the inorder and preorder traversal of the tree (assuming no duplicates).

public void Sample()
{
  int[] preorder = { 7, 10, 4, 3, 1, 2, 8, 11 };
  int[] inorder = { 4, 10, 3, 1, 7, 11, 8, 2 };
  Node head = ReconstructTree(preorder, inorder);
}

Node ReconstructTree(int[] preorder, int[] inorder)
{
  // use a hashtable to retrieve position of sub-root node from inorder array 
  var inorderMapTable = new Dictionary<int, int>(preorder.Length);
  for (int i = 0; i < inorder.Length; i++)
    inorderMapTable[inorder[i]] = i;
  return ReconstructTreeHelper(preorder.SubArray(), inorder.SubArray(), inorderMapTable);
}

Node ReconstructTreeHelper(SubArray<int> preorder, SubArray<int> inorder,
  Dictionary<int, int> inorderMapTable)
{
  int rootVal = preorder[0];
  int rootPos = inorderMapTable[rootVal] - inorder.Offset;
  Node node = new Node { Id = rootVal };
  int nodesToLeft = rootPos;
  if (nodesToLeft > 0)
    node.Left = ReconstructTreeHelper(preorder.SubArray(1, nodesToLeft),
      inorder.SubArray(0, nodesToLeft), inorderMapTable);
  int nodesToRight = inorder.Count - rootPos - 1;
  if (nodesToRight > 0)
    node.Right = ReconstructTreeHelper(preorder.SubArray(rootPos + 1, nodesToRight),
      inorder.SubArray(rootPos + 1, nodesToRight), inorderMapTable);
  return node;
}

The expected result is:

        _______7______
       /              \
    __10__          ___2
   /      \        /
   4       3      _8
            \    /
             1  11

Postscript

It turns out that ArraySegment has richer functionality in .NET Framework 4.5 :

[SerializableAttribute]
public struct ArraySegment<T> : IList<T>,   ICollection<T>, IReadOnlyList<T>, 
    IEnumerable<T>, IEnumerable

It still doesn't provide a way of creating a ArraySegment as a sub-array of an existing ArraySegment but it would be trivial to supply an extension method to add this functionality.