Struttura dati che supporta le seguenti operazioni

Question

Struttura dati che supporta le seguenti operazioni

#1 da (1 voti)

1

Sto cercando una struttura dati per lavorare con un insieme di dati che sia il più efficiente per fare quanto segue:

Controlla se un elemento è stato classificato o meno. (Le serie categorizzate e non classificate sono insiemi disgiunti).
Ottieni la categoria di un articolo.
Ottieni tutti gli elementi in una particolare categoria.
Ottieni tutti gli oggetti non categorizzati.
Rimuovi un elemento particolare dal set di dati.

Stavo pensando di avere un Dictionary<String, Set<String>> per contenere tutti gli elementi in una determinata categoria, ma questo non risolve 2.

data-structures

posta 500865 06.11.2013 - 02:44

fonte

1 risposta

Leggi altre domande sui tag data-structures

Quali sono i casi di test validi per le chiamate di metodo all'interno della condizione if-else è un buon approccio per implementare l'iniezione di dipendenza in un'applicazione desktop?

score 1 · Answer 1

Hai provato a modellare " Category ha-molti Item ". Tuttavia, i tuoi requisiti stabiliscono che la relazione è bidirezionale. Vorrei quindi iniziare con " Item has-one-or-none Category ". I requisiti 1,2,5 possono essere soddisfatti con il seguente schema:

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; }
}

Questa rappresentazione di categorie non è sufficiente, poiché i requisiti 3 e 4 non sono soddisfatti. Per questo, abbiamo bisogno di un riferimento da ciascuna categoria a ciascun articolo.

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;
  }
}

Si noti che Item è il solo responsabile per il mantenimento dell'integrità referenziale. Poiché ogni Item ha un% noncategory nullo dove è registrato, possiamo ottenere tutti gli articoli "non categorizzati" tramite Category.NONE.items() .