I have an exercise that I am doing to help me understand and learn about the use of generics, and the understanding of interfaces and interface inheritance. This is done by implementing and using my own class(es).
I think I have done part 1 successfully (followed a tutorial) and was able to hash and add to my dictionary without any problems. If there are parts I am missing from the solution to part 1 feel free to let me know.
The second part is the main problem. From what I understood I am supposed to let the key be the latitude and longitude of a city. My own implementation of Dictionary Dict is of the Dict<K, V> so it is not possible to have the key be of 2 values.
That is where I think struct could come in and pass my struct as the key while storing the values for latitude and longitude.
Below I will try to outline the exercise description with the requirements to make my question more understandable.
The exercise has 2 parts
Part 1
In this part you will create your own class that implements the IDictionary<K,V>.
In order to implement the IDictionary<K,V> you must implement the ICollection, and the IEnumerable interfaces.
You are not allowed to use the
C#Dictionary implementation as a delegate as this would make the exercise insignificant.
Part 2
We want to use the recently created Dictionary class to map the latitude and longitude values to their matching cities.
The key itself should be a class that represents a
GeoLocationconsisting of alatitudeand alongitude. Make all the necessary functions and operator overloads to make it possible to use this class as a key for the Dictionary class
Code
Dict :
public class Dict<K, V>:IEnumerable<KeyValuePair<K,V>>
{
private const int INI_Size = 16;
LinkedList<KeyValuePair<K, V>>[] values;
public Dict()
{
this.values = new LinkedList<KeyValuePair<K, V>>[INI_Size];
}
public int Count { get; private set; }
public int Capacity
{
get
{
return this.values.Length;
}
}
public void Add(K key, V value)
{
var hash = this.HashKey(key);
if(this.values[hash]== null)
{
this.values[hash] = new LinkedList<KeyValuePair<K, V>>();
}
var keyExistsAlready = this.values[hash].Any(p => p.Key.Equals(key));
if (keyExistsAlready)
{
throw new InvalidOperationException("key already exist");
}
var pair = new KeyValuePair<K, V>(key, value);
this.values[hash].AddLast(pair);
this.Count ;
if (this.Count >= this.Capacity * 0.75)
{
this.ResizeAndReAddValues();
}
}
public V Find (K key)
{
var hash = this.HashKey(key);
if(this.values[hash] == null)
{
return default(V);
}
var collection = this.values[hash];
return collection.First(p => p.Key.Equals(key)).Value;
}
public bool ContainsKey(K key)
{
var hash = HashKey(key);
if (this.values[hash] == null)
{
return false;
}
var collection = this.values[hash];
return collection.Any(pair => pair.Key.Equals(key));
}
private int HashKey(K key)
{
var hash = Math.Abs(key.GetHashCode()) % this.Capacity;
return hash;
}
private void ResizeAndReAddValues()
{
var cachedValues = this.values;
this.values = new LinkedList<KeyValuePair<K, V>>[2 * this.Capacity];
this.Count = 0;
foreach (var collection in cachedValues)
{
if (collection != null)
{
foreach (var value in collection)
{
this.Add(value.Key, value.Value);
}
}
}
}
public IEnumerator<KeyValuePair<K, V>> GetEnumerator()
{
foreach(var collection in this.values)
{
if (collection != null)
{
foreach (var value in collection)
{
yield return value;
}
}
}
}
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
}
GeoLocation :
public struct GeoLocation
{
public float X;
public float Y;
public GeoLocation(float x, float y)
{
X = x;
Y = y;
}
}
My thought process
if I used the already implemented Dictionary from System.Collections.Generic
var dict = new Dictionary<GeoLocation, string>() {
[new GeoLocation(12, 78)] = "Paris",
[new GeoLocation(98, -18)] = "Frankfurt"
};
//test for part 1 (works)
/* var d = new Dict<int, string>
{
{ 10, "Washington" }
};*/
This is possible, would I do the same with my implementation or is the solution completely different to what I imagine?
Another thing to add as I have said from before if my implementation is also wrong on part 1 please let me know as I am trying to understand thing by coding and asking questions.
CodePudding user response：
As
it seems like my solution is not completely done for part 1 I will post where I am at with the implementation of the Dictionary. I am doing this so the question doesn't get confusing for others and it will also showcase my progress.
Dict :
public class Dict<TKey, TValue> : ICollection<KeyValuePair<TKey, TValue>>
{
private const int INI_Size = 16;
LinkedList<KeyValuePair<TKey, TValue>>[] values;
public Dict()
{
this.values = new LinkedList<KeyValuePair<TKey, TValue>>[INI_Size];
}
public int Count { get; private set; }
public int Capacity
{
get
{
return this.values.Length;
}
}
public bool IsReadOnly
{
get { return false; }
}
public void Add(KeyValuePair<TKey, TValue> item)
{
var hash = this.HashKey(item.Key);
if (this.values[hash] == null)
{
this.values[hash] = new LinkedList<KeyValuePair<TKey, TValue>>();
}
var keyExistsAlready = this.values[hash].Any(p => p.Key.Equals(item.Key));
if (keyExistsAlready)
{
throw new InvalidOperationException("key already exist");
}
var pair = new KeyValuePair<TKey, TValue>(item.Key, item.Value);
this.values[hash].AddLast(pair);
this.Count ;
if (this.Count >= this.Capacity * 0.75)
{
this.ResizeAndReAddValues();
}
}
public TValue Find(TKey key)
{
var hash = this.HashKey(key);
if (this.values[hash] == null)
{
return default(TValue);
}
var collection = this.values[hash];
return collection.First(p => p.Key.Equals(key)).Value;
}
public bool Contains(KeyValuePair<TKey, TValue> item)
{
var hash = HashKey(item.Key);
if (this.values[hash] == null)
{
return false;
}
var collection = this.values[hash];
return collection.Any(pair => pair.Key.Equals(item.Key));
}
private int HashKey(TKey key)
{
var hash = Math.Abs(key.GetHashCode()) % this.Capacity;
return hash;
}
private void ResizeAndReAddValues()
{
var cachedValues = this.values;
this.values = new LinkedList<KeyValuePair<TKey, TValue>>[2 * this.Capacity];
this.Count = 0;
foreach (var collection in cachedValues)
{
if (collection != null)
{
foreach (var value in collection)
{
this.Add(value);
}
}
}
}
public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
{
foreach (var collection in this.values)
{
if (collection != null)
{
foreach (var value in collection)
{
yield return value;
}
}
}
}
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
public void Clear()
{
throw new NotImplementedException();
}
public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
{
throw new NotImplementedException();
}
public bool Remove(KeyValuePair<TKey, TValue> item)
{
throw new NotImplementedException();
}
}
As part 2 is connected to part 1 it is the safest to wait for feedback on this solution. Before continuing with the exercise.
Hopefully I am not confusing anyone.
CodePudding user response：
I'm not going to give you a plug and play answer, as this is an exercise, and I find it problematic to just solve it for you.
I'll give you some hints that should be sufficient, and some feedback to your code.
First of all:
Implement IDictionary<TK, TV> to get the syntax mentioned in your post for free (and a standardized API that everyone knows how to use in C#).
Some general tips:
- Hide implementation details (also mentioned by pm100)
- Unit-Test implementation, specifically also for edge cases (always write tests please!)
- Use modern C#:
private int HashKey(TKey key)
{
var hash = Math.Abs(key.GetHashCode()) % this.Capacity;
return hash;
}
could be
private int HashKey(TKey key)
=> Math.Abs(key.GetHashCode()) % this.Capacity;
and
public bool IsReadOnly
{
get { return false; }
}
could be
public bool IsReadOnly => false;
// or
public bool IsReadOnly { get; } = false;
Some more specific tips:
A key used in a dictionary (This is a simplification but these are usually the most two relevant) behaves according to two properties:
- Equality: The dictionary uses comparison (e.g. the equals method or the == operator) to decide if two elements (of type key) are equal
- Hashing: The key must implement a hash function that holds to the following:
- When Equals returns true, the
GetHashCodefunction must return the same hash code for those objects deemed "equal" GetHashCodemay return the same value for many unequal objects. This is fine - it may hurt performance if there are many collisions, but it must not be unique for a group of equal objects. Microsoft says the following:
- When Equals returns true, the
Do not test for equality of hash codes to determine whether two objects are equal.
So after you found your candidate(s) through the hash code, you must check for equality. You already do that correctly in your find method.
So: Implement Hashing and Equality correctly for your Key. The default in C# is (for your own classes) reference equality. Override the equality and hashing functions for your type that you use as key.
Structs are fun, as they are compared by-value as a default, and GetHashCode behaves in a way that is useful for you. The modern way would be to use records (or record structs) to get equality and hash code for free. I would recommend you understand both concepts enough to implement them manually to avoid possible mis-understandings and bugs in the future!