I've created a extension method to count every available descendant starting from a single, given key.
The data is a flat list, there's is no hierarchical structure. (Well, not entirely true. There is an hierarchy in the data-model, but not in the list itself)
self-reference parent-reference some other members
10045 => 0 ..
10046 => 10045 ..
10044 => 10063 ..
10061 => 10044 ..
10063 => 10046 ..
10064 => 10046 ..
10021 => 10061 ..
10028 => 10000 ..
10030 => 10000 ..
10031 => 10000 ..
10000 => 10000 ..
As an example, counting the descendant of the entry with the self-reference number 10046 would result in 6.
Let's take 10021 as an possible related entry to entry 10046, for example.
10021 refers to 10061, 10061 refers to 10044, 10044 refers to 10063, 10063 refers to 10046 => related!
My extension method is actually split up in two different methods.
public static int CountDescendants<TSource, T>(
this IEnumerable<TSource> source,
T startKey,
Func<TSource, T> selfReference,
Func<TSource, T> parentReference)
{
if(source == null) {
throw new ArgumentNullException("source");
}
return Count(source, startKey, selfReference, parentReference);
}
startKey
defines our filter, the key we're looking for. In the example above I've used
10046
selfReference
defines a unique key a dataset can be identified with.
parentReference
defines a unique key which refers to another dataset.
The actual algorithm looks like this.
private static int Count<TSource, T>(
IEnumerable<TSource> source,
T key,
Func<TSource, T> selfReference,
Func<TSource, T> parentReference)
{
// hash-map + .Where is faster than using IEnumerable + .Where
ReadOnlyDictionary<T, T> consolidatedSource =
new ReadOnlyDictionary<T, T>(source.ToDictionary(selfReference, parentReference));
int count = 0;
// to keep track of every reference which is somehow related to "key"
HashSet<T> keys = new HashSet<T> {
key
};
// using a stack instead of recurison
Stack<KeyValuePair<T, T>> stack = new Stack<KeyValuePair<T, T>>();
// get all first level entries with the given key
foreach(KeyValuePair<T,T> item in consolidatedSource.Where(x => x.Value.Equals(key))) {
stack.Push(item);
}
// using .Any over .Count because we don't care how many items we have but rather that the stack is not empty
while (stack.Any()) {
KeyValuePair<T, T> current = stack.Pop();
if (keys.Contains(current.Value)) {
count++;
keys.Add(current.Key);
// get all first level entries with the new key
foreach (KeyValuePair<T, T> item in consolidatedSource.Where(x => x.Value.Equals(current.Key) && !x.Key.Equals(current.Key))){
stack.Push(item);
}
}
}
return count;
}
The method can be called like this
this.AllProfiles.CountDescendants(CurrentProfile.Ref, x => x.Ref, x => x.ParentRef);
Is stuff like using a Dictionary to speed up things micro-optimization which I shouldn't worry about? Personally, wherever I can impact performance, I try to get the best out of it. Or at least not make it any worse.
Also, I'm not entirely sure if there are any constraints I can apply to the generic types. I don't think there's one that actually fits and is needed.