Sortierung in eigener Liste

Paranoia

Paranoia

Erfahrenes Mitglied
Hallo zusammen

Ich habe vor langer Zeit mit Hilfe des Interfaces IEnumerator eine eigene "Listen-Klasse" programmiert. Es war damals eigentlich eher ein Spielerei. Doch mittlerweile ist diese Klasse in einigen Projekten im Einsatz. Grundsätzlich funktioniert auch alles einwandfrei. Jetzt muss ich diese Klasse aber mit einer Sortierung erweitern und irgendwie herrscht da in meinem Kopf ziemliche Leere zu diesem Thema :(

Ich weiss, dass es heute viel bessere und simplere Ansätze für eine solche Liste gibt, nur wie gesagt, ist sie halt bereits in produktivem Einsatz.

Kann mir jemand einen Tipp geben, wie ich in untenstehendem Source Code eine Sortierung anbringen kann (z. B. dass ich IComparable einsetzen kann)? Die Sortierung sollte nicht auf den Key sondern auf die Values angewandt werden. Ich wäre auch offen, die Klasse komplett zu überarbeiten (vereinfachen), wenn danach dieselbe Funktionalität gewährleistet ist.

Code: 
	public class ObjectIterator : IEnumerable
	{
		private const short MINIMUM_SIZE = 16;
		private const short MINIMUM_GROW = 4;

		private string[] _keys;
		private object[] _values;
		private int      _size;
		private int      _capacity;

		public ObjectIterator()
		{
			_keys     = new string[MINIMUM_SIZE];
			_values   = new object[MINIMUM_SIZE];
			_size     = 0;
			_capacity = 0;			
		}

		public int Count
		{
			get { return _size; }
		}

		public ICollection Keys
		{
			get 
			{
				Array newKeys = null;				
				copyTo(ref newKeys, 0); 
				return newKeys;
			}
		}
		
		public ICollection Values
		{
			get
			{
				Array newValues = null;
				copyTo(_values, ref newValues, 0);                
				return newValues;
			}
		}

		public object this [string key]
		{
			set 
			{
				if (value == null)
				{
					throw new Exception("null values are not allowed!");
				}

				int position = getPositionByKey(key);

				if (position < 0)
				{
					throw new Exception(string.Format("key '{0}' does not exist!", key));
				}

				_values[position] = value;
			}
			get { return get(key); }
		}

		public void add(string key, object value)
		{
			if (key == null)
			{
				throw new Exception("key must not be null!");
			}

			if (getPositionByKey(key) >= 0)
			{
				throw new Exception("key already exists!");
			}

			if (_size == _keys.Length) 
			{
				int newCapacity = _keys.Length * 2;
				if (newCapacity < _keys.Length + MINIMUM_GROW) 
				{
					newCapacity = _keys.Length + MINIMUM_GROW;
				}
				setCapacity(newCapacity);
			}
    
			_keys[_capacity]   = key;
			_values[_capacity] = value;
			_capacity = (_capacity + 1) % _keys.Length;
			_size++;
		}

		public object get(string key)
		{
			int position = getPositionByKey(key);

			if (position < 0)
			{
				throw new Exception(string.Format("no value for key '{0}' found!", key));
			}
			return _values[position];
		}

		public void clear()
		{			
			if (_capacity > 0)
			{
				Array.Clear(_keys, 0, _size);
				Array.Clear(_values, 0, _size);
			}
			else 
			{
				Array.Clear(_keys, 0, _keys.Length);				
				Array.Clear(_keys, 0, _capacity);
				Array.Clear(_values, 0, _values.Length);
				Array.Clear(_values, 0, _capacity);
			}
 
			_capacity = 0;
			_size     = 0;
		}

		public bool containsKey(string key)
		{
			return getPositionByKey(key) >= 0;
		}

        public bool containsObject(object obj)
        {
            return getPositionByValue(obj) >= 0;
        }

        public void remove(string key)
        {
            if (getPositionByKey(key) < 0)
            {
                throw new Exception(string.Format("key '{0}' does not exist!", key));
            }

            string[] newKeys = new string[_keys.Length];
            object[] newValues = new object[_values.Length];

            int remove = 0;
            for (int i = 0; i < _capacity; i++)
            {
                if (_keys[i].CompareTo(key) == 0)
                {
                    remove++;
                    continue;
                }
                newKeys[i - remove] = _keys[i];
                newValues[i - remove] = _values[i];
            }
            _keys = newKeys;
            _values = newValues;
            _capacity = (_capacity - 1) % _keys.Length;
            _size--;
        }

        public void remove(object obj)
        {
            if (getPositionByValue(obj) < 0)
            {
                throw new Exception("object does not exist!");
            }

            string[] newKeys = new string[_keys.Length];
            object[] newValues = new object[_values.Length];

            int remove = 0;
            for (int i = 0; i < _capacity; i++)
            {
                if (_values[i].Equals(obj))
                {
                    remove++;
                    continue;
                }
                newKeys[i - remove] = _keys[i];
                newValues[i - remove] = _values[i];
            }
            _keys = newKeys;
            _values = newValues;
            _capacity = (_capacity - 1) % _keys.Length;
            _size--;
        }

		public void copyTo(ref Array array, Int32 index)
		{
			copyTo(_keys, ref array, index);
		}

		private void copyTo(Array source, ref Array destination, Int32 index)
		{
			if (_capacity == 0)
			{
                // zero length array
                destination = Array.CreateInstance((new object()).GetType(), _size);
			}

			if (destination == null)
			{
				destination = Array.CreateInstance(source.GetValue(0).GetType(), _size);
			}

			if (destination.Length < _size)
			{
				throw new Exception("array size is to small for copying!");
			}

			Array.Copy(source, index, destination, index, _size - index);
		}

		public IEnumerator GetEnumerator()
		{
			return new ObjectIteratorEnumerator(this);
		}

		private void setCapacity(int capacity) 
		{
			string[] newKeys   = new String[capacity];
			object[]  newValues = new object[capacity];
			
			if (_size > 0) 
			{
				if (_capacity > 0) 
				{
					Array.Copy(_keys, 0, newKeys, 0, _size);
					Array.Copy(_values, 0, newValues, 0, _size);
				} 
				else 
				{
					Array.Copy(_keys, 0, newKeys, 0, _keys.Length);
					Array.Copy(_keys, 0, newKeys, _keys.Length, _capacity);
					Array.Copy(_values, 0, newValues, 0, _values.Length);
					Array.Copy(_values, 0, newValues, _values.Length, _capacity);
				}
			}
    
			_keys     = newKeys;
			_values   = newValues;
			_capacity = _size;
		}

		// 0..* = key found
		// -1   = key not found
		private int getPositionByKey(string key)
		{
			for (int i = 0; i < _keys.Length; i++)
			{
				if (_keys[i] == null)
				{
					continue;
				}

				int j = _keys[i].CompareTo(key);
				if (_keys[i].CompareTo(key) == 0)
				{
					return i;
				}
			}
			return -1;
		}

		// 0..* = key found
		// -1   = key not found
		private int getPositionByValue(object value)
		{
			for (int i = 0; i < _values.Length; i++)
			{
				if (_values[i] == null)
				{
					continue;
				}

				if (_values[i].Equals(value))
				{
					return i;
				}
			}
			return -1;
		}

		internal Object GetElement(int i)
		{
			return _keys[i % _keys.Length];
		}

		class ObjectIteratorEnumerator : IEnumerator 
		{

			private ObjectIterator _o;
			private int            _index;
			private Object         currentElement;

			internal ObjectIteratorEnumerator(ObjectIterator o) 
			{
				_o = o;

				_index = 0;
				currentElement = _o._keys;

				if (_o._size == 0)
					_index = -1;
			}

			public virtual bool MoveNext() 
			{
    
				if (_index < 0) 
				{  
					currentElement = _o._keys;

					return false;
				}
				currentElement = _o.GetElement(_index);
				_index++;

				if (_index == _o._size)
					_index = -1;

				return true;
			}

			public virtual void Reset() 
			{

				if (_o._size == 0)
					_index = -1;
				else
					_index = 0;

				currentElement = _o._keys;
			}

			public virtual Object Current 
			{
				get 
				{
					if (currentElement == _o._keys)
					{
						if (_index == 0)
							throw new InvalidOperationException("Invalid Operation");
						else
							throw new InvalidOperationException("Invalid operation");
					}

					return currentElement;
				}
			}
		}
	}

Für eure Hilfestellungen bedanke ich mich bereits im Voraus.

Grüsse
Paranoia
 
Intern würde ich aufjedenfall anstatt key und value selbst zu halten ein Dictionary verwenden.
So könntest du dir zum Beispiel einige Überprüfungen in der Add Methode ersparen, da Dictionary selbst auch eine Exception schmeißt (bei Verwendung der Add Methode) wenn ein Key schon vorhanden ist.

get, clear, containsObject, remove Methoden könntest du so auch vereinfachen. (Und noch einige andere :D)

zur Sortierung:
Bin eigentlich sogar am überlegen ein neues Objekt anzulegen welches als Eigenschaften Value und Key beinhaltet und dann intern kein Dictionary halten sondern eine Liste (List<T>)
Solche eine Liste bittet von Haus aus eine Funktion der du ein delegate zum sortieren übergeben könntest.

Die öffentlichen Objekte/Methoden könntest du beibehalten aber intern würde ich die Speicherung neu anlegen/ändern.
Sprich dein Obejkt bleibt von Hausen hin gleich.
Soweit ich das sehe sollte das von der Performance her auch besser sein.
 
Hallo

Erst einmal möchte ich mich entschuldigen, dass ich so lange nicht auf den Vorschlag geantwortet habe - ich konnte mich aber erst jetzt wieder diesem Thema widmen.

Mittlerweile habe ich meine Klasse umgeschrieben, was ich euch natürlich nicht vorenthalten möchte. Wer weiss, vielleicht kann jemand diesen Code verwenden. Interessant (zumindest für mich :rolleyes:) sind die zwei Methoden zur Sortierung (worum es mir in diesem Thema ja ging) am Ende der Klasse:

Code: 
using System;
using System.Collections;
using System.Collections.Generic;

namespace ConsoleApplication1
{
    public class TestCollection
    {
        protected Dictionary<string, object> _list;

        public TestCollection()
        {
            _list = new Dictionary<string, object>();
        }

        public int Count
        {
            get { return _list.Count; }
        }

        public ICollection Keys
        {
            get { return _list.Keys; }
        }

        public ICollection Values
        {
            get { return _list.Values; }
        }

        public IEnumerator GetEnumerator()
        {
            return (IEnumerator)this;
        }

        public object this[string key]
        {
            set
            {
                _list[key] = value;
            }
            get { return _list[key]; }
        }

        public void addObject(string key, object value)
        {
            _list.Add(key, value);
        }

        public void addInt(string key, Int32 value)
        {
            addObject(key, value);
        }
        
        public object getObject(string key)
        {
            return _list[key];
        }

        public Int32 getInt(string key)
        {
            object o = getObject(key);
            if (o is Int32)
            {
                return (Int32)o;
            }
            throw new Exception(string.Format("no System.Int32 value for key '{0}' found!", key));
        }

        public void remove(string key)
        {
            _list.Remove(key);
        }

        public void clear()
        {
            _list.Clear();
        }

        public bool containsKey(string key)
        {
            return _list.ContainsKey(key);
        }

        public bool containsValue(object value)
        {
            return _list.ContainsValue(value);
        }

        public void sort()
        {
            List<KeyValuePair<string, object>> result = new List<KeyValuePair<string, object>>(_list);

            result.Sort(
                delegate(
                    KeyValuePair<string, object> a,
                    KeyValuePair<string, object> b)
                {
                    return a.Key.CompareTo(b.Key);
                });

            _list.Clear();
            foreach (KeyValuePair<string, object> o in result)
            {
                _list.Add(o.Key, o.Value);
            }
        }

        public void sort(IComparer<KeyValuePair<string, object>> comparer)
        {
            List<KeyValuePair<string, object>> result = new List<KeyValuePair<string, object>>(_list);

            result.Sort(comparer);

            _list.Clear();
            foreach (KeyValuePair<string, object> o in result)
            {
                _list.Add(o.Key, o.Value);
            }
        }
    }
}

Ob es für das Befüllen des Dictionary nach der Sortierung einen eleganteren Weg geben würde, weiss ich nicht. Wenn dem so ist, wäre ich natürlich für jeden Hinweis dankbar :)
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück