0

I'm looking for a data structure that supports this use case - there must be one out there!

A set of objects of type T can be stored in a Group, parameterised by the type T. A grouping has a GroupIdentity that uniquely identifies the group. Any T can only exist in one Group.

A management object, let's call it GroupStore, is capable of the following operations:

group(Set[T]) : GroupIdentity // Add or update a group and return its identity 
remove(Set[T]) // Remove the specified Ts from any existing groups
replaceOrMove(T1, T2) // Update any group that has T1 and replace it with T2. If T2 is already in a group the effect is that T1 is removed from its source group. Otherwise, T2 is created in T1's existing group.
getIdentity(T) : GroupIdentity

Some example test cases:

group(a, b, c)
= GroupIdentity(f98eh3)
getIdentity(b)
= GroupIdentity(f98eh3)
remove(b)
getIdentity(b)
= <empty>
group(a, b, c)
= GroupIdentity(f98eh3) // a and c already exist, so add b to the group and return the existing identity
group(a, d)
= GroupIdentity(f98eh3) // a already exists, so add d to the group 
move(b, e)
getIdentity(b)
= <empty>
getIdentity(e)
= GroupIdentity(f98eh3)
move(e, a)              // in effect this is a removal of e and adding a to the group that e existed in
getIdentity(e)
= <empty>
getIdentity(a)
= GroupIdentity(f98eh3)
group(x, y, z)
= GroupIdentity(e9g86z)
move(a, z)
getIdentity(a)
= <empty>
getIdentity(z)
= GroupIdentity(e9g86z)

I'm guessing this already exists...

  • "Any T can only exist in one Group." Did you mean any object of type T can be stored in at most one group? If so, the comment of move doesn't make sense. Otherwise, I don't get that sentence, since "a Group, parameterised by the type T." – D Drmmr Apr 9 at 16:00
  • Can you explain why move doesn't make sense? – Dan Gravell Apr 9 at 16:13
  • 1
    "Update all groups that have the T1 in a group" There is only 1 group (or none) that contains T1. It doesn't make sense to talk about "all" when referring to a single group. Seems like "replace" would be a better name for the function. – D Drmmr Apr 9 at 20:02
  • Gotcha! Yes, much better, thanks. Thing is, it could replace or move. These confusing semantics make me think this isn't the right solution, hence part of the original motivation for the question. – Dan Gravell Apr 10 at 9:10
  • Please edit your question to make it clearer what you mean. – D Drmmr Apr 10 at 13:25
1

In general, you would solve this problem by using a nested collection, as in

Dictionary<TGroupKey, Dictionary<TItemKey, TItem>> collection;

Microsoft offers a KeyedByTypeCollection Class which might prove useful.

You can enforce the "can only belong in one group" rule by also putting all of your items in a separate dictionary.

Dictionary<TItemKey, TGroupKey> itemIndex;

This dictionary will enforce the rule that you only allow the item to be added to the entire collection once. To move it to a different group, remove it from both collections, add it to the new group, and put it back into the itemIndex dictionary.

When you use GroupBy in Linq, it produces an IGrouping<TKey,TElement> as a result.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.