Executing structure without data duplication

Question

Let's say I have the following classes:

public class Tagged { private List<String> tags; } public class ContainerOfTagged { private List<Tagged> tagged; } 

With this structure, when I need to find a Tagged with a specific tag, I need to iterate over all those tagged in ContainerOfTagged and iterate over all the tags of each Tagged . This may affect performance depending on the size of the lists.

A simple solution will change the ContainerOfTagged class to use Map , displaying tags in Tagged lists:

 public class ContainerOfTagged { private Map<String, List<Tagged>> tagMapping; } 

Now all I have to do is provide a tag, and Map will return all the Tagged with the specified tag. However, by doing this, I cause data duplication, because the same tags exist in both the Tagged and ContainerOfTagged classes.

So, is there a way to solve this problem with a simple solution that does not duplicate data?

Answer 1

You really cannot avoid the “duplication” of tags, but remember that you do not actually duplicate them, since lists and maps contain only links to the tag string, not values ​​(however, the links probably have a lot of space in themselves).

The problem is that you need two indexes:

• You need to find the list of tags given the Tagged object.
• You need to find the Tagged object specified by the tag.

Ideally, your solution would look like this. You can solve your problems related to what you get due to synchronization by having one tag management method.

Note that in Tagged you should use Set instead of a list to avoid duplicate tags.

 public class Tagged { Set<String> tags; } public class TagContainer { Map<String, Tagged> tagIndex; public tag(String tag, Tagged tagged) { tagged.tags.add(tag); tagIndex.put(tag, tagged); } 

If memory usage is a serious problem, you can try some kind of link compression. Using this technique, you can store your tags in an array, and then reference them by index. If you had few of them, you could use bytes or short instead of a link, but the code would be much messy, and I would not recommend it.

EDIT:

In my first post, I suggested that Tagged be a Tagable interface. This is cleaner, but lengthens the solution, so I went back to class. However, you might consider having a Tagable interface and implementing it in the Tagged class.

 public interface Tagable { Set<String> getTags; tag(String tag); }