implement ChangeableOrderedSet

[luithefirst]

A changeable data structure like there is Aardvark.Base.Increment with ChangeableOrderedSet (ChangeableIndexSet?) allows precise expression on what an application state can be, can directly provide IAdaptiveHashSet and IAdaptiveIndexList views and has ideal runtime complexity when operating on item values.

Assuming the internal state contains a HashMap<'a, Index> and IndexList<'a> the data structure could provide the following runtime complexity compared to a ChangeableIndexList:

Add(item: 'a) // O(log N) vs O(log N)
AddBefore(before : 'a, item :'a) // O(log N) vs O(N)
AddAfter(after : 'a, item : 'a) // O(log N) vs O(N)
Remove(item: 'a) // O(log n) vs O(n)
Contains(item: 'a) // O(log n) vs O(n)

It would be nice to consider this as an extension to this library.

[luithefirst]

To give an update, this is the substitute I have been using since the port to FSharp.Data.Adaptive:

public class ChangeableOrderedSet<T> : IList<T>
{
    ChangeableIndexList<T> m_list = new ChangeableIndexList<T>();
    HashSet<T> m_set = new HashSet<T>();
    IAdaptiveHashSet<T> m_adaptiveSet;

    public ChangeableOrderedSet()
    {
        m_adaptiveSet = m_list.ToAdaptiveHashSet();
    }

    public bool Contains(T item)
    {
        return m_set.Contains(item);
    }

    public bool Add(T item)
    {
        if (m_set.Add(item))
        {
            m_list.Add(item);
            return true;
        }
        return false;
    }

    public bool Remove(T item)
    {
        if(m_set.Remove(item))
        {
            m_list.Remove(item);
            return true;
        }
        return false;
    }

    public void Clear()
    {
        m_list.Clear();
        m_set.Clear();
    }

    public int IndexOf(T item)
    {
        return m_list.Value.IndexOf(item);
    }

    public void Insert(int index, T item)
    {
        m_list.InsertAt(index, item);
    }

    public void RemoveAt(int index)
    {
        m_list.RemoveAt(index);
    }

    void ICollection<T>.Add(T item)
    {
        Add(item);
    }

    public void CopyTo(T[] array, int arrayIndex)
    {
        ((IList<T>)m_list.Value).CopyTo(array, arrayIndex);
    }

    public IEnumerator<T> GetEnumerator()
    {
        return ((IEnumerable<T>)m_list.Value).GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return ((IEnumerable)m_list.Value).GetEnumerator();
    }

    public int Count => m_set.Count;

    public IAdaptiveHashSet<T> Set => m_adaptiveSet;
    public IAdaptiveIndexList<T> List => m_list;

    /// <summary>
    /// ICollection view. Can be used for faster enumeration if the order does not matter.
    /// </summary>
    public ICollection<T> Collection => m_set;

    public bool IsReadOnly => false;

    public T this[int index]
    {
        get => m_list[index];
        set
        {
            if (index >= m_set.Count)
                throw new IndexOutOfRangeException();
            if (m_set.Contains(value))
                throw new InvalidOperationException("Item already contained in the ChangeableOrderedSet");

            var old = m_list[index];
            m_set.Remove(old);
            m_list[index] = value;
            m_set.Add(value);
        }
    }
}