Namespace dict?

Question

I'm devising a template language. In it, there are 3 kinds of tokens: tags, directives, and variables. Each of these tokens have a name, and there's getting to be quite a few of them. They're extensible too.

To allow name reuse I want to add namespaces.

Right now all the variables are just stored in a dict. The key is the variable name, and the value is the variable value. That way I can quickly retrieve the value of a variable. However, supposing I want to allow dot-notation, namespace.variable, how can I store these variables, such that the namespace is optional? If the namespace is included the dict should only scan that namespace, if not, I guess it scans all namespaces.

Is there a container that will do this?

Answer 1

My solution:

Class

public class NamespaceDictionary<T> : IDictionary<string, T>
{
    private SortedDictionary<string, Dictionary<string, T>> _dict;
    private const char _separator = '.';

    public NamespaceDictionary()
    {
        _dict = new SortedDictionary<string, Dictionary<string, T>>();
    }

    public NamespaceDictionary(IEnumerable<KeyValuePair<string, T>> collection)
        : this()
    {
        foreach (var item in collection)
            Add(item);
    }

    #region Implementation of IEnumerable

    public IEnumerator<KeyValuePair<string, T>> GetEnumerator()
    {
        return _dict.SelectMany(x => x.Value).GetEnumerator();
    }

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

    #endregion

    private static Tuple<string, string> Split(string name)
    {
        int pos = name.LastIndexOf(_separator);
        string ns = pos == -1 ? "" : name.Substring(0, pos);
        string var = name.Substring(pos + 1);
        return new Tuple<string, string>(ns, var);
    }

    #region Implementation of ICollection<KeyValuePair<string,TValue>>

    public void Add(KeyValuePair<string, T> item)
    {
        Add(item.Key, item.Value);
    }

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

    public bool Contains(KeyValuePair<string, T> item)
    {
        throw new NotImplementedException();
    }

    public void CopyTo(KeyValuePair<string, T>[] array, int arrayIndex)
    {
        throw new NotImplementedException();
    }

    public bool Remove(KeyValuePair<string, T> item)
    {
        return Remove(item.Key);
    }

    public int Count
    {
        get { return _dict.Sum(p => p.Value.Count); }
    }

    public bool IsReadOnly
    {
        get { return false; }
    }

    #endregion

    #region Implementation of IDictionary<string,TValue>

    public bool ContainsKey(string name)
    {
        var tuple = Split(name);
        return ContainsKey(tuple.Item1, tuple.Item2);
    }

    public bool ContainsKey(string ns, string key)
    {
        if (ns == "")
            return _dict.Any(pair => pair.Value.ContainsKey(key));
        return _dict.ContainsKey(ns) && _dict[ns].ContainsKey(key);
    }

    public void Add(string name, T value)
    {
        var tuple = Split(name);
        Add(tuple.Item1, tuple.Item2, value);
    }

    public void Add(string ns, string key, T value)
    {
        if (!_dict.ContainsKey(ns))
            _dict[ns] = new Dictionary<string, T>();
        _dict[ns].Add(key, value);
    }

    public bool Remove(string ns, string key)
    {
        if (_dict.ContainsKey(ns) && _dict[ns].ContainsKey(key))
        {
            if (_dict[ns].Count == 1) _dict.Remove(ns);
            else _dict[ns].Remove(key);
            return true;
        }
        return false;
    }

    public bool Remove(string key)
    {
        var tuple = Split(key);
        return Remove(tuple.Item1, tuple.Item2);
    }

    public bool TryGetValue(string name, out T value)
    {
        var tuple = Split(name);
        return TryGetValue(tuple.Item1, tuple.Item2, out value);
    }

    public bool TryGetValue(string ns, string key, out T value)
    {
        if (ns == "")
        {
            foreach (var pair in _dict)
            {
                if (pair.Value.ContainsKey(key))
                {
                    value = pair.Value[key];
                    return true;
                }
            }
        }
        else if (_dict.ContainsKey(ns) && _dict[ns].ContainsKey(key))
        {
            value = _dict[ns][key];
            return true;
        }
        value = default(T);
        return false;
    }

    public T this[string ns, string key]
    {
        get
        {
            if (ns == "")
            {
                foreach (var pair in _dict)
                    if (pair.Value.ContainsKey(key))
                        return pair.Value[key];
            }
            else if (_dict.ContainsKey(ns) && _dict[ns].ContainsKey(key))
                return _dict[ns][key];
            throw new KeyNotFoundException();
        }
        set
        {
            if (!_dict.ContainsKey(ns))
                _dict[ns] = new Dictionary<string, T>();
            _dict[ns][key] = value;
        }
    }

    public T this[string name]
    {
        get
        {
            var tuple = Split(name);
            return this[tuple.Item1, tuple.Item2];
        }
        set
        {
            var tuple = Split(name);
            this[tuple.Item1, tuple.Item2] = value;
        }
    }

    public ICollection<string> Keys
    {
        get { return _dict.SelectMany(p => p.Value.Keys).ToArray(); }
    }

    public ICollection<T> Values
    {
        get { return _dict.SelectMany(p => p.Value.Values).ToArray(); }
    }

    #endregion
}

Test

        var dict = new NamespaceDictionary<int>();
        dict.Add("ns1.var1", 1);
        dict.Add("ns2.var1", 2);
        dict.Add("var2", 3);
        dict.Add("ns2.var2", 4);
        dict.Add("ns3", "var1", 5);
        dict["ns4.var1"] = 6;
        Console.WriteLine(dict["var1"]);
        Console.WriteLine(dict["ns2.var1"]);
        Console.WriteLine(dict["var2"]);
        Console.WriteLine(dict["ns2.var2"]);
        Console.WriteLine(dict["ns2", "var2"]);
        Console.WriteLine(dict["ns3.var1"]);
        Console.WriteLine(dict["ns4", "var1"]);

Output

1
2
3
4
4
5
6

Help

I used a SortedDictionary thinking it would retain the order that the namespaces were added, but it's actually sorting the namespaces alphabetically. Is there an dict class that will retain the order the items were added, but not sort them?

Answer 2

You can create your own implementation of IDictionary<string, object> instead of using the framework's Dictionary<TKey, TValue>.

Externally, there would be no change to the way you are consuming it.

Internally, it would consist of a Dictionary<string, Dictionary<string, object>>.

So, if your dictionary is asked for the value matching key "namespace.variable", internally it would split that string, get the Dictionary<string, Dictionary<string, object>> with key "namespace" and then return the value in that Dictionary<string, object> for key "variable."

To make the namespace optional, you have one entry where the key is string.Empty. Whether adding or getting items, any time a key is provided that does not contain ., you'll use the entry with key string.Empty.

Answer 3

You should structure your symbol data internally as a dictionary of dictionary of string. The top level dictionary is for namespaces, and each dictionary below each namespace name is the container for all symbols in that namespace.

Looking up an unqualified symbol is simply a matter of looking for the symbol in each namespace in a particular order. In C# or Delphi, the order is determined by the order in which the namespaces are declared at the top of the source file, in reverse order of declaration (most recent is the first to be searched).