Я написал код StringTrie.java, реализованный через интерфейс Trie.java:
package il.ac.tau.cs.sw1.trie;
import java.util.Set;
/**
* Represents a generic trie data structure, where K is the type of keys that
* are saved in the trie, and V is the type of values that can be saved for each
* key.
*/
public interface Trie<K, V> {
/**
* Adds the input key to the data structure with the given value. If the key
* is invalid for this trie (implementation-dependent) an exception is
* thrown.
*/
void addKey(K key, V value);
/**
* Searches all the keys in the trie structure with the given prefix. If
* there are no such keys - an empty Set is returned. Otherwise, all the values saved
* for these keys are added to the output value set. If the prefix is invalid for this
* trie (implementation-dependent) an exception is thrown.
*
* @post the return value is not null
*/
Set<V> searchByPrefix(K prefix);
}
вместе с StringTrieNode.java, реализованным через TrieNode.java:
package il.ac.tau.cs.sw1.trie;
import java.util.List;
import java.util.Set;
/**
* Represents a node in a generic trie, where K is the type of keys that are
* saved in the trie, and V is the type of values that can be saved for each
* key.
*/
public interface TrieNode<K, V> {
/**
* Adds the key suffix to this trie node, with the given value, by
* recursively adding the suffix of this suffix to the relevant child node.
*
* @pre suffix is a valid suffix for this trie (implementation-dependent)
* @post if the key ends in this trie node, the input value is added to the
* set of values returned by getValues().
*/
void addSuffix(K suffix, V value);
/**
* Returns the set of values for keys that end in this node
*/
Set<V> getValues();
/**
* Returns the child trie node such that the input suffix is saved in it or
* in its descendant
*
* @pre suffix is a valid suffix for this trie (implementation-dependent)
* @post if no key with such a suffix exists in the trie, or if suffix ends
* in the current node, return null; otherwise return the relevant
* child node
*/
TrieNode<K, V> getNext(K suffix);
/**
* Returns a list with all the child trie nodes of this node. The list may
* contain null values.
*
* @post $ret != null
*/
List<TrieNode<K, V>> getNexts();
}
теперь я реализовал все функции (надеюсь правильно) и теперь у меня проблема только с Set searchByPrefix(K prefix); я не могу найти работающий алгоритм + у меня проблема с конструктором. пользователь вызывает это следующим образом: Имена Trie = new StringTrie‹>(); поэтому первое должно быть там. но только второй инициализирует поля. Это нормально?
