What Is Ruby (1.8.7) Analog to Sorteddictionary in C#/.Net

What is Ruby (1.8.7) analog to SortedDictionary in C#/.NET?

There is nothing in the core library or the standard library now, that will fit your bill.

There is, however, a feature request to add a Red/Black-Tree implementation to Ruby 1.9.3/2.0.

If you are able to force your users to only ever use XRuby or JRuby, you could just use one of the implementations of Java's java.util.SortedMap<K, V> such as java.util.TreeMap<K, V>.

If you are able to force your users to only ever use Ruby.NET or IronRuby, you could just use .NET's System.Collections.Generic.SortedDictionary<TKey, TValue>.

If you are able to force your users to only ever use MRI or YARV, you could use the Ruby/RBTree library. It might also work on Rubinius or the not-yet-released JRuby 1.6. Note that there seem to be multiple independent updated forks of that library in the wild. It is not obvious, which one of those is the most recent and/or best maintained one.

The only solution I know of which is guaranteed to be portable, is Kanwei Li's Algorithms and Containers GSoC 2008 project, which actually contains two implementations of a sorted, key-indexed collection: Containers::RBTreeMap based on a Red/Black-Tree and Containers::SplayTreeMap based on a Splay Tree.

How do you sort a dictionary by value?

Use:

using System.Linq.Enumerable;
...
List<KeyValuePair<string, string>> myList = aDictionary.ToList();

myList.Sort(
    delegate(KeyValuePair<string, string> pair1,
    KeyValuePair<string, string> pair2)
    {
        return pair1.Value.CompareTo(pair2.Value);
    }
);

Since you're targeting .NET 2.0 or above, you can simplify this into lambda syntax -- it's equivalent, but shorter. If you're targeting .NET 2.0 you can only use this syntax if you're using the compiler from Visual Studio 2008 (or above).

var myList = aDictionary.ToList();

myList.Sort((pair1,pair2) => pair1.Value.CompareTo(pair2.Value));

Convert HashTable to Dictionary in C#

public static Dictionary<K,V> HashtableToDictionary<K,V> (Hashtable table)
{
   return table
     .Cast<DictionaryEntry> ()
     .ToDictionary (kvp => (K)kvp.Key, kvp => (V)kvp.Value);
}

Generic Key/Value pair collection in that preserves insertion order?

There is not. However, System.Collections.Specialized.OrderedDictionary should solve most need for it.

EDIT: Another option is to turn this into a Generic. I haven't tested it but it compiles (C# 6) and should work. However, it will still have the same limitations that Ondrej Petrzilka mentions in comments below.

    public class OrderdDictionary<T, K>
    {
        public OrderedDictionary UnderlyingCollection { get; } = new OrderedDictionary();

        public K this[T key]
        {
            get
            {
                return (K)UnderlyingCollection[key];
            }
            set
            {
                UnderlyingCollection[key] = value;
            }
        }

        public K this[int index]
        {
            get
            {
                return (K)UnderlyingCollection[index];
            }
            set
            {
                UnderlyingCollection[index] = value;
            }
        }
        public ICollection<T> Keys => UnderlyingCollection.Keys.OfType<T>().ToList();
        public ICollection<K> Values => UnderlyingCollection.Values.OfType<K>().ToList();
        public bool IsReadOnly => UnderlyingCollection.IsReadOnly;
        public int Count => UnderlyingCollection.Count;
        public IDictionaryEnumerator GetEnumerator() => UnderlyingCollection.GetEnumerator();
        public void Insert(int index, T key, K value) => UnderlyingCollection.Insert(index, key, value);
        public void RemoveAt(int index) => UnderlyingCollection.RemoveAt(index);
        public bool Contains(T key) => UnderlyingCollection.Contains(key);
        public void Add(T key, K value) => UnderlyingCollection.Add(key, value);
        public void Clear() => UnderlyingCollection.Clear();
        public void Remove(T key) => UnderlyingCollection.Remove(key);
        public void CopyTo(Array array, int index) => UnderlyingCollection.CopyTo(array, index);
    }

How to insert as first element in dictionary?

Dictionary<K,V> does not have an ordering. Any perceived order maintenance is by chance (and an artifact of a particular implementation including, but not limited to, bucket selection order and count).

These are the approaches (just using the Base Class Libraries BCL) I know about:

1. Lookup<K,V>
   
   • .NET4, immutable, can map keys to multiple values (watch for duplicates during building)
2. OrderedDictionary
   
   • Old, non-generic, expected Dictionary performance bounds (other two approaches are O(n) for "get(key)/set(key)")
3. List<KeyValuePair<K,V>>
   
   • .NET2/3 okay, mutable, more legwork, can map keys to multiple values (watch for duplicates in inserts)

Happy coding.

---

Creating a hash data-structure that maintains insertion order is actually only a slight modification of a standard hash implementation (Ruby hashes now maintain insertion order); however, this was not done in .NET nor, more importantly, is it part of the Dictionary/IDictionary contract.

Can I write this .NET foreach loop shorter?

Whats the point, this is perfectly short.

And for the record, you can make an extension method for Dictioary (or IDictioary) that does this. From then on, you can call the extension method on any dictioary.

How to make C# Switch Statement use IgnoreCase

As you seem to be aware, lowercasing two strings and comparing them is not the same as doing an ignore-case comparison. There are lots of reasons for this. For example, the Unicode standard allows text with diacritics to be encoded multiple ways. Some characters includes both the base character and the diacritic in a single code point. These characters may also be represented as the base character followed by a combining diacritic character. These two representations are equal for all purposes, and the culture-aware string comparisons in the .NET Framework will correctly identify them as equal, with either the CurrentCulture or the InvariantCulture (with or without IgnoreCase). An ordinal comparison, on the other hand, will incorrectly regard them as unequal.

Unfortunately, switch doesn't do anything but an ordinal comparison. An ordinal comparison is fine for certain kinds of applications, like parsing an ASCII file with rigidly defined codes, but ordinal string comparison is wrong for most other uses.

What I have done in the past to get the correct behavior is just mock up my own switch statement. There are lots of ways to do this. One way would be to create a List<T> of pairs of case strings and delegates. The list can be searched using the proper string comparison. When the match is found then the associated delegate may be invoked.

Another option is to do the obvious chain of if statements. This usually turns out to be not as bad as it sounds, since the structure is very regular.

The great thing about this is that there isn't really any performance penalty in mocking up your own switch functionality when comparing against strings. The system isn't going to make a O(1) jump table the way it can with integers, so it's going to be comparing each string one at a time anyway.

If there are many cases to be compared, and performance is an issue, then the List<T> option described above could be replaced with a sorted dictionary or hash table. Then the performance may potentially match or exceed the switch statement option.

Here is an example of the list of delegates:

delegate void CustomSwitchDestination();
List<KeyValuePair<string, CustomSwitchDestination>> customSwitchList;
CustomSwitchDestination defaultSwitchDestination = new CustomSwitchDestination(NoMatchFound);
void CustomSwitch(string value)
{
    foreach (var switchOption in customSwitchList)
        if (switchOption.Key.Equals(value, StringComparison.InvariantCultureIgnoreCase))
        {
            switchOption.Value.Invoke();
            return;
        }
    defaultSwitchDestination.Invoke();
}

Of course, you will probably want to add some standard parameters and possibly a return type to the CustomSwitchDestination delegate. And you'll want to make better names!

If the behavior of each of your cases is not amenable to delegate invocation in this manner, such as if differnt parameters are necessary, then you’re stuck with chained if statments. I’ve also done this a few times.

    if (s.Equals("house", StringComparison.InvariantCultureIgnoreCase))
    {
        s = "window";
    }
    else if (s.Equals("business", StringComparison.InvariantCultureIgnoreCase))
    {
        s = "really big window";
    }
    else if (s.Equals("school", StringComparison.InvariantCultureIgnoreCase))
    {
        s = "broken window";
    }

What is boxing and unboxing and what are the trade offs?

Boxed values are data structures that are minimal wrappers around primitive types*. Boxed values are typically stored as pointers to objects on the heap.

Thus, boxed values use more memory and take at minimum two memory lookups to access: once to get the pointer, and another to follow that pointer to the primitive. Obviously this isn't the kind of thing you want in your inner loops. On the other hand, boxed values typically play better with other types in the system. Since they are first-class data structures in the language, they have the expected metadata and structure that other data structures have.

In Java and Haskell generic collections can't contain unboxed values. Generic collections in .NET can hold unboxed values with no penalties. Where Java's generics are only used for compile-time type checking, .NET will generate specific classes for each generic type instantiated at run time.

Java and Haskell have unboxed arrays, but they're distinctly less convenient than the other collections. However, when peak performance is needed it's worth a little inconvenience to avoid the overhead of boxing and unboxing.

* For this discussion, a primitive value is any that can be stored on the call stack, rather than stored as a pointer to a value on the heap. Frequently that's just the machine types (ints, floats, etc), structs, and sometimes static sized arrays. .NET-land calls them value types (as opposed to reference types). Java folks call them primitive types. Haskellions just call them unboxed.

** I'm also focusing on Java, Haskell, and C# in this answer, because that's what I know. For what it's worth, Python, Ruby, and Javascript all have exclusively boxed values. This is also known as the "Everything is an object" approach***.

*** Caveat: A sufficiently advanced compiler / JIT can in some cases actually detect that a value which is semantically boxed when looking at the source, can safely be an unboxed value at runtime. In essence, thanks to brilliant language implementors your boxes are sometimes free.

---

Related Topics