Coffeehouse Post

Single Post Permalink

View Thread: Immutable collections for .NET arrive
  • User profile image
    evildictait​or

    Why is List.Add O(lg n) for immutable? You can abuse the fact that any subset of an immutable list is immutable to make it O(1) surely:

    class ImmutableList<T> 
    {
      int cachedPrefixLen = -1;
      Immutable<T> prefix;
      T[] item;
      ImmutableList<T>(Immutable<T> prefix, params T[] nextItems)
      {
        prefix = prefix:
        item = nextItems;

      }
      public ImmutableList<T> Add(T item)
      {
        // O(1)
        return new ImmutableList(this, item);
      }
      public ImmutableList<T> AddRange(T[] items)
      {
        // O(1)
        return new ImmutableList(this, items);
      }
      private int PrefixLen { get { if(cachedPrefixLen == -1) cachedPrefixLen = prefix == null? 0 : prefix.Count; return cachedPrefixLen; }}
      public int Count { get { return PrefixLen + item.Length; } }
      public void ToArray(T[] dst, int offset, int count)
      {
        int a = Math.Min(dst.Length, count);
        int b = count - a;
        prefix.ToArray(dst, offset, a);
        Array.Copy(dst, offset + a, b);
      }
      public bool Contains(T t)
      {
        return prefix.Contains(item) || item.Contains(t);
      }

      public T this[int index] 
      {
        get { if(index < PrefixLen) return prefix[index]; else return items[PrefixLen - index];
      }

    // etc
    }