Coleção classificável C # que permite chaves duplicadas

Estou escrevendo um programa para definir uma sequência na qual vários objetos aparecerão no relatório. A sequência é a posição Y (célula) na planilha do Excel.

Uma parte de demonstração do código está abaixo. O que desejo realizar é ter uma coleção, o que me permitirá adicionar vários objetos e posso obter uma coleção ordenada com base na sequência

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);

Eu sei que a SortedList não permitirá isso e estou procurando uma alternativa. Não quero eliminar as duplicatas e já tentei List<KeyValuePair<int, object>>.

Obrigado.

Use seu próprio IComparer!

Como já foi dito em algumas outras respostas, você deve usar sua própria classe de comparação. Para isso, uso uma classe IComparer genérica, que funciona com qualquer coisa 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
}

Você o usará ao criar uma nova SortedList, SortedDictionary etc:

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

Aqui, int é a chave que pode ser duplicada.

Você pode usar List <> com segurança. The List tem um método Sort, uma sobrecarga que aceita IComparer. Você pode criar sua própria classe de classificação como. Aqui está um exemplo:

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);
    }
}

Eu uso o seguinte:

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);
    }

}

Meu caso de teste:

[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);
    }

A saída:

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

O problema é que o design da estrutura de dados não atende aos requisitos: É necessário armazenar vários cabeçalhos para os mesmos XPos. Portanto, SortedList<XPos, value>não deve ter um valor de Header, mas um valor de List<Header>. É uma mudança simples e pequena, mas que resolve todos os problemas e evita a criação de novos problemas como outras soluções sugeridas (ver explicação abaixo):

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

Observe que adicionar uma chave "engraçada", como adicionar um número aleatório ou fingir que 2 XPos com o mesmo valor são diferentes, leva a muitos outros problemas. Por exemplo, torna-se difícil ou mesmo impossível remover um cabeçalho específico.

Observe também que o desempenho de classificação é muito melhor se apenas alguns List<Header>tiverem que ser classificados do que todos Header. Exemplo: se houver 100 XPos e cada um tiver 100 cabeçalhos, 10.000 Headerprecisam ser classificados em vez de 100 List<Header>.

Obviamente, essa solução também tem uma desvantagem: se houver muitos XPos com apenas 1 cabeçalho, muitas Listas precisarão ser criadas, o que é uma sobrecarga.

Solução mais simples (em comparação com todas as anteriores): use SortedSet<T>, ele aceita uma IComparer<SortableKey>classe e, em seguida, implemente o método Compare desta forma:

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();

}

Muito obrigado por sua ajuda. Enquanto procurava mais, encontrei esta solução. (Disponível em Stackoverflow.com em outra pergunta)

Primeiro, criei uma classe que encapsularia meus objetos para classes (cabeçalhos, rodapé etc)

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

Portanto, esta classe deve conter os objetos, e PosX de cada objeto vai 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));

O que eventualmente recebo é a lista classificada de "Sequência".

Você tentou Lookup<TKey, TElement>que permitirá chaves duplicadas http://msdn.microsoft.com/en-us/library/bb460184.aspx

Você pode usar SortedList, usar seu valor para TKey e int (contagem) para TValue.

Aqui está um exemplo: uma função que classifica as letras de uma palavra.

    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 classe de coleção irá manter duplicatas e inserir ordem de classificação para as duplicatas. O truque é marcar os itens com um valor exclusivo à medida que são inseridos para manter uma ordem de classificação estável. Em seguida, encerramos tudo em uma interface 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; }
    }
}

uma aula de teste

[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();

}

A estrutura de marcação

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);
    }
}

O ajudante 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);
    }
}

O problema é que você usa algo como chave que não é uma chave (porque isso ocorre várias vezes).

Portanto, se você tiver coordenadas reais, talvez deva considerar o Pointcomo a chave para sua SortedList.

Ou você cria um List<List<Header>>onde seu primeiro índice de lista define a posição x e o índice de lista interno a posição y (ou vice-versa, se preferir).

A chave (trocadilho) para isso é criar uma IComparableclasse baseada em-que mantém igualdade e hashing, mas nunca se compara a 0 se não for igual. Isso pode ser feito e pode ser criado com alguns bônus - classificação estável (ou seja, os valores adicionados à lista classificada primeiro manterão sua posição) e ToString()pode simplesmente retornar o valor da string de chave real.

Aqui está uma chave de estrutura que deve fazer o truque:

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 é legal e tudo, mas se o seu objetivo é simplesmente fazer um loop sobre as "chaves" enquanto permite que sejam duplicadas, você pode usar esta estrutura:

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"),
};

Então você pode escrever:

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

HTH

O truque é aumentar seu objeto com uma chave exclusiva. Veja o seguinte teste que passa. Quero manter meus pontos classificados por seu valor X. Apenas usar um Point2D nu na minha função de comparação fará com que pontos com o mesmo valor X sejam eliminados. Portanto, envolvo o Point2D em uma classe de marcação chamada Indexada.

[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});

}

Os utilitários para fazer este trabalho são

Um comparador que leva um 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);
    }
}

Uma estrutura de marcação

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);
    }
}

Foi assim que resolvi o problema. É feito para ser thread-safe, embora você possa simplesmente remover os locks se não precisar disso. Observe também que arbitrário Insertem um índice não é suportado porque isso pode violar a condição de classificação.

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();
    }
}

Crie uma classe e consulte a 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);

Aqui está minha opinião sobre isso. Esteja ciente, aqui podem ser dragões, C # ainda é bastante novo para mim.

• Chaves duplicadas são permitidas, os valores são armazenados em uma lista
• Usei-o como uma fila classificada, daí os nomes e 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);
  }
}