Colección ordenable de C # que permite claves duplicadas

Estoy escribiendo un programa para establecer una secuencia en la que aparecerán varios objetos en el informe. La secuencia es la posición Y (celda) en la hoja de cálculo de Excel.

A continuación se muestra una parte de demostración del código. Lo que quiero lograr es tener una colección, lo que me permitirá agregar varios objetos y puedo obtener una colección ordenada según la secuencia

SortedList list = new SortedList();

Header h = new Header();
h.XPos = 1;
h.name = "Header_1";
list.Add(h.XPos, h);

h = new Header();
h.XPos = 1;
h.name = "Header_2";
list.Add(h.XPos, h);

Sé que SortedListno lo permitirán y he estado buscando una alternativa. No quiero eliminar los duplicados y ya lo intenté List<KeyValuePair<int, object>>.

Gracias.

¡Utilice su propio IComparer!

Como ya se indicó en algunas otras respuestas, debe usar su propia clase de comparación. Por este motivo, uso una clase IComparer genérica, que funciona con cualquier cosa que implemente IComparable:

/// <summary>
/// Comparer for comparing two keys, handling equality as beeing greater
/// Use this Comparer e.g. with SortedLists or SortedDictionaries, that don't allow duplicate keys
/// </summary>
/// <typeparam name="TKey"></typeparam>
public class DuplicateKeyComparer<TKey>
                :
             IComparer<TKey> where TKey : IComparable
{
    #region IComparer<TKey> Members

    public int Compare(TKey x, TKey y)
    {
        int result = x.CompareTo(y);

        if (result == 0)
            return 1;   // Handle equality as beeing greater
        else
            return result;
    }

    #endregion
}

Lo usará cuando instale un nuevo SortedList, SortedDictionary, etc.

SortedList<int, MyValueClass> slist = new SortedList<int, MyValueClass>(new DuplicateKeyComparer<int>());

Aquí int es la clave que se puede duplicar.

Puede utilizar List <> de forma segura. La Lista tiene un método Sort, una sobrecarga del cual acepta IComparer. Puede crear su propia clase clasificadora como. He aquí un ejemplo:

private List<Curve> Curves;
this.Curves.Sort(new CurveSorter());

public class CurveSorter : IComparer<Curve>
{
    public int Compare(Curve c1, Curve c2)
    {
        return c2.CreationTime.CompareTo(c1.CreationTime);
    }
}

Yo uso lo siguiente:

public class TupleList<T1, T2> : List<Tuple<T1, T2>> where T1 : IComparable
{
    public void Add(T1 item, T2 item2)
    {
        Add(new Tuple<T1, T2>(item, item2));
    }

    public new void Sort()
    {
        Comparison<Tuple<T1, T2>> c = (a, b) => a.Item1.CompareTo(b.Item1);
        base.Sort(c);
    }

}

Mi caso de prueba:

[TestMethod()]
    public void SortTest()
    {
        TupleList<int, string> list = new TupleList<int, string>();
        list.Add(1, "cat");
        list.Add(1, "car");
        list.Add(2, "dog");
        list.Add(2, "door");
        list.Add(3, "elephant");
        list.Add(1, "coconut");
        list.Add(1, "cab");
        list.Sort();
        foreach(Tuple<int, string> tuple in list)
        {
            Console.WriteLine(string.Format("{0}:{1}", tuple.Item1,tuple.Item2));
        }
        int expected_first = 1;
        int expected_last = 3;
        int first = list.First().Item1;  //requires using System.Linq
        int last = list.Last().Item1;    //requires using System.Linq
        Assert.AreEqual(expected_first, first);
        Assert.AreEqual(expected_last, last);
    }

La salida:

1:cab
1:coconut
1:car
1:cat
2:door
2:dog
3:elephant

El problema es que el diseño de la estructura de datos no coincide con los requisitos: es necesario almacenar varios encabezados para los mismos XPos. Por lo tanto, SortedList<XPos, value>no debería tener un valor de Header, sino un valor de List<Header>. Es un cambio simple y pequeño, pero resuelve todos los problemas y evita la creación de nuevos problemas como otras soluciones sugeridas (ver explicación a continuación):

using System;
using System.Collections.Generic;

namespace TrySortedList {
  class Program {

    class Header {
      public int XPos;
      public string Name;
    }

    static void Main(string[] args) {
      SortedList<int, List<Header>> sortedHeaders = new SortedList<int,List<Header>>();
      add(sortedHeaders, 1, "Header_1");
      add(sortedHeaders, 1, "Header_2");
      add(sortedHeaders, 2, "Header_3");
      foreach (var headersKvp in sortedHeaders) {
        foreach (Header header in headersKvp.Value) {
          Console.WriteLine(header.XPos + ": " + header.Name);
        }
      }
    }

    private static void add(SortedList<int, List<Header>> sortedHeaders, int xPos, string name) {
      List<Header> headers;
      if (!sortedHeaders.TryGetValue(xPos, out headers)){
        headers = new List<Header>();
        sortedHeaders[xPos] = headers;
      }
      headers.Add(new Header { XPos = xPos, Name = name });
    }
  }
}

Output:
1: Header_1
1: Header_2
2: Header_3

Tenga en cuenta que agregar una clave "divertida", como agregar un número aleatorio o pretender que 2 XPos con el mismo valor son diferentes conduce a muchos otros problemas. Por ejemplo, resulta difícil o incluso imposible eliminar un encabezado en particular.

También tenga en cuenta que el rendimiento de clasificación es mucho mejor si solo List<Header>se deben clasificar unos pocos que todos Header. Ejemplo: si hay 100 XPos y cada uno tiene 100 encabezados, es Headernecesario ordenar 10000 en lugar de 100 List<Header>.

Por supuesto, esta solución también tiene una desventaja: si hay muchos XPos con solo 1 encabezado, se deben crear tantas listas, lo que supone una sobrecarga.

Solución más simple (en comparación con todas las anteriores): use SortedSet<T>, acepta una IComparer<SortableKey>clase, luego implemente el método Compare de esta manera:

public int Compare(SomeClass x, SomeClass y)
{
    var compared = x.SomeSortableKeyTypeField.CompareTo(y.SomeSortableKeyTypeField);
    if (compared != 0)
        return compared;

    // to allow duplicates
    var hashCodeCompare = x.GetHashCode().CompareTo(y.GetHashCode());
    if (hashCodeCompare != 0)
        return hashCodeCompare;

    if (Object.ReferenceEquals(x, y))
        return 0;

    // for weird duplicate hashcode cases, throw as below or implement your last chance comparer
    throw new ComparisonFailureException();

}

Muchas gracias por tu ayuda. Mientras buscaba más, encontré esta solución. (Disponible en Stackoverflow.com en otra pregunta)

Primero, creé una clase que encapsularía mis objetos para clases (encabezados, pie de página, etc.)

public class MyPosition
{
    public int Position { get; set; }
    public object MyObjects{ get; set; }
}

Entonces, se supone que esta clase se mantiene en los objetos, y PosX de cada objeto va como int Position

List<MyPosition> Sequence= new List<MyPosition>();
Sequence.Add(new MyPosition() { Position = 1, Headerobject });
Sequence.Add(new MyPosition() { Position = 2, Headerobject1 });
Sequence.Add(new MyPosition() { Position = 1, Footer });

League.Sort((PosA, PosB) => PosA.Position.CompareTo(PosB.Position));

Lo que finalmente obtengo es la lista ordenada de "Secuencia".

¿Intentó Lookup<TKey, TElement>que permita claves duplicadas http://msdn.microsoft.com/en-us/library/bb460184.aspx

Puede usar SortedList, usar su valor para TKey e int (count) para TValue.

Aquí tienes un ejemplo: una función que ordena las letras de una palabra.

    private string sortLetters(string word)
    {
        var input = new System.Collections.Generic.SortedList<char, int>();

        foreach (var c in word.ToCharArray())
        {
            if (input.ContainsKey(c))
                input[c]++;
            else
                input.Add(c, 1);
        }

        var output = new StringBuilder();

        foreach (var kvp in input)
        {
            output.Append(kvp.Key, kvp.Value);
        }

        string s;

        return output.ToString();

    }

Esta clase de colección mantendrá duplicados e insertará el orden de clasificación para el duplicado. El truco consiste en etiquetar los elementos con un valor único a medida que se insertan para mantener un orden de clasificación estable. Luego lo envolvemos todo en una interfaz ICollection.

public class SuperSortedSet<TValue> : ICollection<TValue>
{
    private readonly SortedSet<Indexed<TValue>> _Container;
    private int _Index = 0;
    private IComparer<TValue> _Comparer;

    public SuperSortedSet(IComparer<TValue> comparer)
    {
        _Comparer = comparer;
        var c2 = new System.Linq.Comparer<Indexed<TValue>>((p0, p1) =>
        {
            var r = _Comparer.Compare(p0.Value, p1.Value);
            if (r == 0)
            {
                if (p0.Index == -1
                    || p1.Index == -1)
                    return 0;

                return p0.Index.CompareTo(p1.Index);

            }
            else return r;
        });
        _Container = new SortedSet<Indexed<TValue>>(c2);
    } 

    public IEnumerator<TValue> GetEnumerator() { return _Container.Select(p => p.Value).GetEnumerator(); }

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

    public void Add(TValue item) { _Container.Add(Indexed.Create(_Index++, item)); }

    public void Clear() { _Container.Clear();}

    public bool Contains(TValue item) { return _Container.Contains(Indexed.Create(-1,item)); }

    public void CopyTo(TValue[] array, int arrayIndex)
    {
        foreach (var value in this)
        {
            if (arrayIndex >= array.Length)
            {
                throw new ArgumentException("Not enough space in array");
            }
            array[arrayIndex] = value;
            arrayIndex++;
        }
    }

    public bool Remove(TValue item) { return _Container.Remove(Indexed.Create(-1, item)); }

    public int Count {
        get { return _Container.Count; }
    }
    public bool IsReadOnly {
        get { return false; }
    }
}

una clase de prueba

[Fact]
public void ShouldWorkWithSuperSortedSet()
{
    // Sort points according to X
    var set = new SuperSortedSet<Point2D>
        (new System.Linq.Comparer<Point2D>((p0, p1) => p0.X.CompareTo(p1.X)));

    set.Add(new Point2D(9,10));
    set.Add(new Point2D(1,25));
    set.Add(new Point2D(11,-10));
    set.Add(new Point2D(2,99));
    set.Add(new Point2D(5,55));
    set.Add(new Point2D(5,23));
    set.Add(new Point2D(11,11));
    set.Add(new Point2D(21,12));
    set.Add(new Point2D(-1,76));
    set.Add(new Point2D(16,21));

    var xs = set.Select(p=>p.X).ToList();
    xs.Should().BeInAscendingOrder();
    xs.Count.Should()
       .Be(10);
    xs.ShouldBeEquivalentTo(new[]{-1,1,2,5,5,9,11,11,16,21});

    set.Remove(new Point2D(5,55));
    xs = set.Select(p=>p.X).ToList();
    xs.Count.Should()
       .Be(9);
    xs.ShouldBeEquivalentTo(new[]{-1,1,2,5,9,11,11,16,21});

    set.Remove(new Point2D(5,23));
    xs = set.Select(p=>p.X).ToList();
    xs.Count.Should()
       .Be(8);
    xs.ShouldBeEquivalentTo(new[]{-1,1,2,9,11,11,16,21});

    set.Contains(new Point2D(11, 11))
       .Should()
       .BeTrue();

    set.Contains(new Point2D(-1, 76))
        .Should().BeTrue();

    // Note that the custom compartor function ignores the Y value
    set.Contains(new Point2D(-1, 66))
        .Should().BeTrue();

    set.Contains(new Point2D(27, 66))
        .Should().BeFalse();

}

La estructura de etiquetado

public struct Indexed<T>
{
    public int Index { get; private set; }
    public T Value { get; private set; }
    public Indexed(int index, T value) : this()
    {
        Index = index;
        Value = value;
    }

    public override string ToString()
    {
        return "(Indexed: " + Index + ", " + Value.ToString () + " )";
    }
}

public class Indexed
{
    public static Indexed<T> Create<T>(int indexed, T value)
    {
        return new Indexed<T>(indexed, value);
    }
}

El ayudante del comparador lambda

public class Comparer<T> : IComparer<T>
{
    private readonly Func<T, T, int> _comparer;

    public Comparer(Func<T, T, int> comparer)
    {
        if (comparer == null)
            throw new ArgumentNullException("comparer");
        _comparer = comparer;
    }

    public int Compare(T x, T y)
    {
        return _comparer(x, y);
    }
}

El problema es que usas algo como clave que no es una clave (porque ocurre varias veces).

Entonces, si tiene coordenadas reales, tal vez debería tomar Pointcomo clave para su SortedList.

O crea un List<List<Header>>donde su primer índice de lista define la posición xy la lista interna indexa la posición y (o viceversa si lo desea).

La clave (juego de palabras intencionado) para esto es crear una IComparableclase basada en que mantenga la igualdad y el hash, pero nunca se compare con 0 si no es igual. Esto se puede hacer y se puede crear con un par de bonificaciones: clasificación estable (es decir, los valores agregados a la lista ordenada primero mantendrán su posición) y ToString()simplemente puede devolver el valor real de la cadena de claves.

Aquí hay una clave de estructura que debería funcionar:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;

namespace System
{
    /// <summary>
    /// Defined in Totlsoft.Util.
    /// A key that will always be unique but compares
    /// primarily on the Key property, which is not required
    /// to be unique.
    /// </summary>
    public struct StableKey : IComparable<StableKey>, IComparable
    {
        private static long s_Next;
        private long m_Sequence;
        private IComparable m_Key;

        /// <summary>
        /// Defined in Totlsoft.Util.
        /// Constructs a StableKey with the given IComparable key.
        /// </summary>
        /// <param name="key"></param>
        public StableKey( IComparable key )
        {
            if( null == key )
                throw new ArgumentNullException( "key" );

            m_Sequence = Interlocked.Increment( ref s_Next );
            m_Key = key;
        }

        /// <summary>
        /// Overridden. True only if internal sequence and the
        /// Key are equal.
        /// </summary>
        /// <param name="obj"></param>
        /// <returns></returns>
        public override bool Equals( object obj )
        {
            if( !( obj is StableKey ) )
                return false;

            var dk = (StableKey)obj;

            return m_Sequence.Equals( dk.m_Sequence ) &&
                Key.Equals( dk.Key );
        }

        /// <summary>
        /// Overridden. Gets the hash code of the internal
        /// sequence and the Key.
        /// </summary>
        /// <returns></returns>
        public override int GetHashCode()
        {
            return m_Sequence.GetHashCode() ^ Key.GetHashCode();
        }

        /// <summary>
        /// Overridden. Returns Key.ToString().
        /// </summary>
        /// <returns></returns>
        public override string ToString()
        {
            return Key.ToString();
        }

        /// <summary>
        /// The key that will be compared on.
        /// </summary>
        public IComparable Key
        {
            get
            {
                if( null == m_Key )
                    return 0;

                return m_Key;
            }
        }

        #region IComparable<StableKey> Members

        /// <summary>
        /// Compares this Key property to another. If they
        /// are the same, compares the incremented value.
        /// </summary>
        /// <param name="other"></param>
        /// <returns></returns>
        public int CompareTo( StableKey other )
        {
            var cmp = Key.CompareTo( other.Key );
            if( cmp == 0 )
                cmp = m_Sequence.CompareTo( other.m_Sequence );

            return cmp;
        }

        #endregion

        #region IComparable Members

        int IComparable.CompareTo( object obj )
        {
            return CompareTo( (StableKey)obj );
        }

        #endregion
    }
}

Linq.Lookup es genial y todo, pero si su objetivo es simplemente recorrer las "claves" mientras permite que se dupliquen, puede usar esta estructura:

List<KeyValuePair<String, String>> FieldPatterns = new List<KeyValuePair<string, string>>() {
   new KeyValuePair<String,String>("Address","CommonString"),
   new KeyValuePair<String,String>("Username","UsernamePattern"),
   new KeyValuePair<String,String>("Username","CommonString"),
};

Entonces puedes escribir:

foreach (KeyValuePair<String,String> item in FieldPatterns)
{
   //use item.Key and item.Value
}

HTH

El truco consiste en aumentar tu objeto con una clave única. Vea la siguiente prueba que pasa. Quiero mantener mis puntos ordenados por su valor X. El solo uso de un Point2D desnudo en mi función de comparación hará que se eliminen los puntos con el mismo valor X. Así que envuelvo el Point2D en una clase de etiquetado llamada Indexado.

[Fact]
public void ShouldBeAbleToUseCustomComparatorWithSortedSet()
{
    // Create comparer that compares on X value but when X
    // X values are uses the index
    var comparer = new 
        System.Linq.Comparer<Indexed<Point2D>>(( p0, p1 ) =>
        {
            var r = p0.Value.X.CompareTo(p1.Value.X);
            return r == 0 ? p0.Index.CompareTo(p1.Index) : r;
        });

    // Sort points according to X
    var set = new SortedSet<Indexed<Point2D>>(comparer);

    int i=0;

    // Create a helper function to wrap each point in a unique index
    Action<Point2D> index = p =>
    {
        var ip = Indexed.Create(i++, p);
        set.Add(ip);
    };

    index(new Point2D(9,10));
    index(new Point2D(1,25));
    index(new Point2D(11,-10));
    index(new Point2D(2,99));
    index(new Point2D(5,55));
    index(new Point2D(5,23));
    index(new Point2D(11,11));
    index(new Point2D(21,12));
    index(new Point2D(-1,76));
    index(new Point2D(16,21));
    set.Count.Should()
       .Be(10);
    var xs = set.Select(p=>p.Value.X).ToList();
    xs.Should()
      .BeInAscendingOrder();
    xs.ShouldBeEquivalentTo(new[]{-1,1,2,5,5,9,11,11,16,21});

}

Las utilidades para hacer que esto funcione son

Un comparador que lleva una lambda

public class Comparer<T> : IComparer<T>
{
    private readonly Func<T, T, int> _comparer;

    public Comparer(Func<T, T, int> comparer)
    {
        if (comparer == null)
            throw new ArgumentNullException("comparer");
        _comparer = comparer;
    }

    public int Compare(T x, T y)
    {
        return _comparer(x, y);
    }
}

Una estructura de etiquetado

public struct Indexed<T>
{
    public int Index { get; private set; }
    public T Value { get; private set; }
    public Indexed(int index, T value) : this()
    {
        Index = index;
        Value = value;
    }

    public override string ToString()
    {
        return "(Indexed: " + Index + ", " + Value.ToString () + " )";
    }
}

public class Indexed
{
    public static Indexed<T> Create<T>(int indexed, T value)
    {
        return new Indexed<T>(indexed, value);
    }
}

Así es como resolví el problema. Está destinado a ser seguro para subprocesos, aunque simplemente puede eliminar la locks si no lo necesita. También tenga Inserten cuenta que no se admite arbitrario en un índice porque eso podría violar la condición de clasificación.

public class ConcurrentOrderedList<Titem, Tsort> : ICollection<Titem>
{
    private object _lock = new object();
    private SortedDictionary<Tsort, List<Titem>> _internalLists;
    Func<Titem, Tsort> _getSortValue;
    
    public ConcurrentOrderedList(Func<Titem,Tsort> getSortValue)
    {
        _getSortValue = getSortValue;
        _internalLists = new SortedDictionary<Tsort, List<Titem>>();            
    }

    public int Count { get; private set; }

    public bool IsReadOnly => false;

    public void Add(Titem item)
    {
        lock (_lock)
        {
            List<Titem> values;
            Tsort sortVal = _getSortValue(item);
            if (!_internalLists.TryGetValue(sortVal, out values))
            {
                values = new List<Titem>();
                _internalLists.Add(sortVal, values);
            }
            values.Add(item);
            Count++;
        }            
    }

    public bool Remove(Titem item)
    {
        lock (_lock)
        {
            List<Titem> values;
            Tsort sortVal = _getSortValue(item);
            if (!_internalLists.TryGetValue(sortVal, out values))
                return false;

            var removed = values.Remove(item);
            if (removed)
                Count--;
            return removed;
        }
    }

    public void Clear()
    {
        lock (_lock)
        {
            _internalLists.Clear();
        }
    }

    public bool Contains(Titem item)
    {
        lock (_lock)
        {
            List<Titem> values;
            Tsort sortVal = _getSortValue(item);
            if (!_internalLists.TryGetValue(sortVal, out values))
                return false;
            return values.Contains(item);
        }
    }

    public void CopyTo(Titem[] array, int arrayIndex)
    {
        int i = arrayIndex;
        lock (_lock)
        {
            foreach (var list in _internalLists.Values)
            {
                list.CopyTo(array, i);
                i += list.Count;
            }
        }
    }

    public IEnumerator<Titem> GetEnumerator()
    {
        foreach (var list in _internalLists.Values)
        {
            foreach (var item in list)
                yield return item;
        }
    }

    public int IndexOf(Titem item)
    {
        int i = 0;
        var sortVal = _getSortValue(item);
        lock (_lock)
        {               
            foreach (var list in _internalLists)
            {
                if (object.Equals(list.Key, sortVal))
                {
                    int intIndex = list.Value.IndexOf(item);
                    if (intIndex == -1)
                        return -1;
                    return i + intIndex;
                }
                i += list.Value.Count;
            }
            return -1;
        }           
    }

    public void Insert(int index, Titem item)
    {
        throw new NotSupportedException();
    }

    // Note this method is indeterminate if there are multiple
    // items in the same sort position!
    public void RemoveAt(int index)
    {
        int i = 0;
        lock (_lock)
        {
            foreach (var list in _internalLists.Values)
            {
                if (i + list.Count < index)
                {
                    i += list.Count;
                    continue;
                }
                else
                {
                    list.RemoveAt(index - i);
                    return;
                }
            }
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }
}

Crea una clase y consulta la lista:

Public Class SortingAlgorithm
{
    public int ID {get; set;}
    public string name {get; set;}
    public string address1 {get; set;}
    public string city {get; set;}
    public string state {get; set;}
    public int age {get; set;}
}

//declare a sorting algorithm list
List<SortingAlgorithm> sortAlg = new List<SortingAlgorithm>();

//Add multiple values to the list
sortAlg.Add( new SortingAlgorithm() {ID = ID, name = name, address1 = address1, city = city, state = state, age = age});
sortAlg.Add( new SortingAlgorithm() {ID = ID, name = name, address1 = address1, city = city, state = state, age = age});
sortAlg.Add( new SortingAlgorithm() {ID = ID, name = name, address1 = address1, city = city, state = state, age = age});

//query and order by the list
  var sortedlist = (from s in sortAlg
                    select new { s.ID, s.name, s.address1, s.city, s.state, s.age })
                                                     .OrderBy(r => r.ID)
                                                     .ThenBy(r=> r.name)
                                                     .ThenBy(r=> r.city)
                                                     .ThenBy(r=>r.state)
                                                     .ThenBy(r=>r.age);

Esta es mi opinión sobre esto. Tenga en cuenta que aquí puede haber dragones, C # todavía es bastante nuevo para mí.

• Se permiten claves duplicadas, los valores se almacenan en una lista
• Lo usé como una cola ordenada, de ahí los nombres y métodos

Uso:

SortedQueue<MyClass> queue = new SortedQueue<MyClass>();
// new list on key "0" is created and item added
queue.Enqueue(0, first);
// new list on key "1" is created and item added
queue.Enqueue(1, second);
// items is added into list on key "0"
queue.Enqueue(0, third);
// takes the first item from list with smallest key
MyClass myClass = queue.Dequeue();

class SortedQueue<T> {
  public int Count;
  public SortedList<int, List<T>> Queue;

  public SortedQueue() {
    Count = 0;
    Queue = new SortedList<int, List<T>>();
  }

  public void Enqueue(int key, T value) {
    List<T> values;
    if (!Queue.TryGetValue(key, out values)){
      values = new List<T>();
      Queue.Add(key, values);
      Count += 1;
    }
    values.Add(value);
  }

  public T Dequeue() {
    if (Queue.Count > 0) {
      List<T> smallest = Queue.Values[0];
      if (smallest.Count > 0) {
        T item = smallest[0];
        smallest.Remove(item);
        return item;
      } else {
        Queue.RemoveAt(0);
        Count -= 1;
        return Dequeue();
      }
    }
    return default(T);
  }
}