background image

C# SortedBucketList

So I searched the internets for a while looking for a sorted list that could have multiple entries per key. I didn’t find one. Here is my go at it. This is not optimized and will be pretty memory heavy. I was just looking for speed. I could have used a different internal collection instead of the sorted list but I was using .Net 3.5 and I didn’t feel like rolling my own.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace Common.Collections
{
    public class SortedBucketList<TKey, TValue> : IDictionary<TKey, TValue>
    {
        /// <summary>
        /// This stores the first key and first value added to the collection.
        /// </summary>
        private readonly SortedList<TKey, TValue> _sort;
        /// <summary>
        /// The value of this is used to reference the first KeyValuePair stored in the SortedList
        /// </summary>
        private readonly Dictionary<TValue, TKey> _bucket;

        public SortedBucketList()
        {
            _sort = new SortedList<TKey, TValue>();
            _bucket = new Dictionary<TValue, TKey>();
        }

        public SortedBucketList(IComparer<TKey> comparer)
        {
            _sort = new SortedList<TKey, TValue>(comparer);
            _bucket = new Dictionary<TValue, TKey>();
        }
        public SortedBucketList(IDictionary<TKey, TValue> dictionary)
        {
            _sort = new SortedList<TKey, TValue>(dictionary);
            _bucket = new Dictionary<TValue, TKey>();
            foreach (var value in dictionary)
            {
                _bucket.Add(value.Value, value.Key);
            }
        }
        public SortedBucketList(int capacity)
        {
            _sort = new SortedList<TKey, TValue>(capacity);
            _bucket = new Dictionary<TValue, TKey>(capacity);
        }
        public SortedBucketList(IDictionary<TKey, TValue> dictionary, IComparer<TKey> comparer)
        {
            _sort = new SortedList<TKey, TValue>(dictionary, comparer);
            _bucket = new Dictionary<TValue, TKey>();
            foreach (var value in dictionary)
            {
                _bucket.Add(value.Value, value.Key);
            }
        }
        public SortedBucketList(int capacity, IComparer<TKey> comparer)
        {
            _sort = new SortedList<TKey, TValue>(capacity, comparer);
            _bucket = new Dictionary<TValue, TKey>(capacity);
        }
        public void Add(TKey key, TValue value)
        {
            if (!_sort.ContainsKey(key))
            {
                _sort.Add(key, value);
            }
            _bucket[value] = key;
        }
        public void Clear()
        {
            _sort.Clear();
            _bucket.Clear();
        }
        public bool ContainsKey(TKey key)
        {
            return _sort.ContainsKey(key);
        }
        public bool ContainsValue(TValue value)
        {
            return _bucket.ContainsKey(value);
        }

        public int IndexOfKey(TKey key)
        {
            return _sort.IndexOfKey(key);
        }
        public int IndexOfValue(TValue value)
        {
            TKey key;
            if (_bucket.TryGetValue(value, out key))
            {
                return _sort.IndexOfKey(key);
            }
            return -1;
        }

        public bool Remove(TKey key)
        {
            if (!_sort.Remove(key))
                return false;
            RemoveFromBucket(key);
            return true;
        }
        public void RemoveAt(int index)
        {
            var item = _sort.ElementAt(index);
            _sort.RemoveAt(index);
            RemoveFromBucket(item.Key);
        }

        private void RemoveFromBucket(TKey key)
        {
            var del = new List<TValue>();
            foreach (var kvp in _bucket)
            {
                if (kvp.Value.Equals(key))
                {
                    del.Add(kvp.Key);
                }
            }
            foreach (var item in del)
            {
                _bucket.Remove(item);
            }
        }

        ICollection<TKey> IDictionary<TKey, TValue>.Keys
        {
            get { return _bucket.Values; }
        }

        public bool TryGetValue(TKey key, out TValue value)
        {
            throw new NotImplementedException();
        }

        public ICollection<TValue> Values
        {
            get { return _bucket.Keys; }
        }

        TValue IDictionary<TKey, TValue>.this[TKey key]
        {
            get
            {
                throw new NotImplementedException();
            }
            set
            {
                throw new NotImplementedException();
            }
        }

        public IEnumerable<TValue> this[TKey key]
        {
            get
            {
                var output = new List<TValue>();

                //_bucket.EachParallel(kvp =>
                //                         {
                //                             if (kvp.Value.Equals(key))
                //                             {
                //                                 output.Add(kvp.Key);
                //                             }
                //                         });
                //output.AddRange(from kvp in _bucket where kvp.Value.Equals(key) select kvp.Key);
                foreach (var kvp in _bucket)
                {
                    if (kvp.Value.Equals(key))
                    {
                        output.Add(kvp.Key);
                    }
                }
                return output;
            }
            set
            {
                if (value == null)
                    return;
                if (!_sort.ContainsKey(key))
                {
                    _sort[key] = value.ElementAt(0);
                }
                foreach (var el in value)
                {
                    _bucket[el] = key;
                }
            }
        }

        void ICollection<KeyValuePair<TKey, TValue>>.Add(KeyValuePair<TKey, TValue> item)
        {
            Add(item.Key, item.Value);
        }

        void ICollection<KeyValuePair<TKey, TValue>>.Clear()
        {
            _sort.Clear();
            _bucket.Clear();
        }

        bool ICollection<KeyValuePair<TKey, TValue>>.Contains(KeyValuePair<TKey, TValue> item)
        {
            return ContainsKey(item.Key) && ContainsValue(item.Value);
        }

        void ICollection<KeyValuePair<TKey, TValue>>.CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
        {
            throw new NotImplementedException();
        }

        int ICollection<KeyValuePair<TKey, TValue>>.Count
        {
            get { return _sort.Count; }
        }

        bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly
        {
            get { throw new NotImplementedException(); }
        }

        bool ICollection<KeyValuePair<TKey, TValue>>.Remove(KeyValuePair<TKey, TValue> item)
        {
            throw new NotImplementedException();
        }

        IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator()
        {
            return _sort.GetEnumerator();
        }

        void IDictionary<TKey, TValue>.Add(TKey key, TValue value)
        {
            Add(key, value);
        }

        bool IDictionary<TKey, TValue>.ContainsKey(TKey key)
        {
            return ContainsKey(key);
        }

        bool IDictionary<TKey, TValue>.Remove(TKey key)
        {
            throw new NotImplementedException();
        }

        bool IDictionary<TKey, TValue>.TryGetValue(TKey key, out TValue value)
        {
            return _sort.TryGetValue(key, out value);
        }

        ICollection<TValue> IDictionary<TKey, TValue>.Values
        {
            get { return _bucket.Keys; }
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            throw new NotImplementedException();
        }
    }
}


Leave a Reply

Your email address will not be published. Required fields are marked *

Comment

You may use these tags : <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>