1

I'm looking for a data structure for working with a set of data which is most efficient to do the following :

  1. Check whether an item has been categorized or not. (The categorized and uncategorized set are disjoint sets).
  2. Get the category of an item.
  3. Get all the items in a particular category.
  4. Get all the uncategorized items.
  5. Remove a particular item from the data set.

I was thinking of having a Dictionary<String, Set<String>> to hold all the items in a given category, but that doesn't solve 2.

  • If it is ML or a related language in which you would code this data structure, you could use SOME (category name) or NONE in the place of String. Could you otherwise use a null string to indicate uncategorized information? – vpit3833 Nov 6 '13 at 5:27
  • Do you want to make a relational database? – Pieter B Nov 6 '13 at 11:06
1

You tried to model “Category has-many Item”. However, your requirements state that the relationship is bidirectional. I would therefore start with “Item has-one-or-none Category”. Requirements 1,2,5 can be fulfilled with the following design:

enum Category { FOO, BAR }

class Item {
  private Category category;

  // Req 1
  public boolean  isCategorized()           { return category != null; }
  // Req 2
  public Category getCategory()             { return category; }
  // Req 5
  public void     removeCategory()          { category = null; }
}

This representation of categories is not sufficient, because requirements 3 and 4 are not fulfilled. For that, we need a reference back from each Category to each Item.

enum Category {
  NONE, FOO, BAR;

  private Set<Item> items = new HashSet<Item>();

  // Reqs 3, 4
  public Iterable<Item> items() { return items; }

  // only to be called by Item
  boolean add   (Item item) { return items.add(item);    }
  boolean remove(Item item) { return items.remove(item); }
}

class Item {
  private Category category;

  public Item(Category cat) { setCategory(cat != null ? cat : Category.NONE); }

  // Req 1
  public boolean isCategorized() { return !category.equals(Category.NONE); }
  // Req 2
  public Category getCategory()  { return category; }
  // Req 5
  public void removeCategory() {
    setCategory(Category.EMPTY)
  }

  private void setCategory(Category cat) {
    if (category != null && !category.remove(this)) throw SomeException ...;
    if (!cat.add(this)) throw SomeException ...;
    category = cat;
  }
}

Notice that Item is solely responsible for maintaining referential integrity. Because every Item has a non-null category where it is registered, we can obtain all “uncategorized” items via Category.NONE.items().

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.