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...

Improve this question
6
  • "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." Commented Apr 9, 2019 at 16:00
  • Can you explain why move doesn't make sense? Commented Apr 9, 2019 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. Commented Apr 9, 2019 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. Commented Apr 10, 2019 at 9:10
  • Please edit your question to make it clearer what you mean. Commented Apr 10, 2019 at 13:25

1 Answer 1

Reset to default
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.

Improve this answer
2
  • I apologize for the Microsoft-centric technologies, but it's what I know. Commented Apr 9, 2019 at 15:34
  • Let us continue this discussion in chat. Commented Apr 10, 2019 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.