Class TrieST<Value>

java.lang.Object

TrieST<Value>

public class TrieST<Value>
extends java.lang.Object

A string symbol table (ST) for ASCII strings, implemented using a 256-way trie. The keys of the ST are keys and the values are of type Value.

Esta é uma tabela de símbolos (TS) para strings ASCII, implementada usando uma trie em que cada nó tem 256 potenciais filhos. As chaves da TS são strings e os valores são do tipo Value.

Constructor Summary

Constructors

Constructor and Description
TrieST()

Method Summary

Methods

Modifier and Type	Method and Description
void	collect(TrieST.Node x, java.lang.String prefix, java.lang.String pat, Queue<java.lang.String> q) Adds to the queue q all the keys in the trie that have the given prefix and match pattern pat (Assumes that prefix.length() <= pat.length().)
boolean	contains(java.lang.String key) Is the key in the symbol table? A chave key está na TS?
void	delete(java.lang.String key) Deletes from the ST the given key and its associated value.
Value	get(java.lang.String key) Returns the value associated with key in the ST.
java.lang.Iterable<java.lang.String>	keys() Returns all the keys in the ST.
java.lang.Iterable<java.lang.String>	keysThatMatch(java.lang.String pat) Returns all the keys that match the pattern pat (in particular, all characters .
java.lang.Iterable<java.lang.String>	keysWithPrefix(java.lang.String prefix) Takes a string as argument and returns all the keys in the ST having that string as prefix.
java.lang.String	longestPrefixOf(java.lang.String query) Find the longest prefix of query that is a key in the ST represented by this trie.
static void	main(java.lang.String[] args) Test client.
void	put(java.lang.String key, Value val) Insert (key,value) pair into the ST.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

TrieST

public TrieST()

Method Detail

contains

public boolean contains(java.lang.String key)

Is the key in the symbol table? A chave key está na TS?

get

public Value get(java.lang.String key)

Returns the value associated with key in the ST. Returns null if key is not in the ST.

Devolve o valor associado à chave key na TS. Devolve null se key não estiver na TS.

put

public void put(java.lang.String key,
       Value val)

Insert (key,value) pair into the ST. Insere o par (key,value) na TS.

longestPrefixOf

public java.lang.String longestPrefixOf(java.lang.String query)

Find the longest prefix of query that is a key in the ST represented by this trie. Assumes root of this trie is not null and the empty string "" is not a key (i.e., assumes root.val is null). Hence, it makes sense to return the empty string "" if no key in the ST is a prefix of query.

Encontra o mais longo prefixo de query que é uma chave da TS representada por essa trie. Supõe que a raiz da trie não é null e que a string vazia "" não é uma chave (ou seja, supõe que root.val é null). Assim, faz sentido devolver a string vazia "" se nenhuma chave da TS for prefixo de query.

keys

public java.lang.Iterable<java.lang.String> keys()

Returns all the keys in the ST. Devolve todas as chaves na TS.

keysWithPrefix

public java.lang.Iterable<java.lang.String> keysWithPrefix(java.lang.String prefix)

Takes a string as argument and returns all the keys in the ST having that string as prefix.

Devolve todas as chaves na TS que têm prefixo prefix.

keysThatMatch

public java.lang.Iterable<java.lang.String> keysThatMatch(java.lang.String pat)

Returns all the keys that match the pattern pat (in particular, all characters . in pat are wildcards).

Devolve todas as chaves que casam com o padrão pat (em particular, todos os caracteres . em pat são curingas).

collect

public void collect(TrieST.Node x,
           java.lang.String prefix,
           java.lang.String pat,
           Queue<java.lang.String> q)

Adds to the queue q all the keys in the trie that have the given prefix and match pattern pat (Assumes that prefix.length() <= pat.length().)

Acrescenta à fila q todas as chaves da trie que têm prefixo prefix e casam com o padrão pat. (Supõe que prefix.length() <= pat.length().)

delete

public void delete(java.lang.String key)

Deletes from the ST the given key and its associated value.

Remove da TS a chave key e o valor associado.

main

public static void main(java.lang.String[] args)

Test client. Cliente de teste. Recebe uma lista de palavras pela entrada padrão, insere cada palavra na TS e registra o número de ordem da última ocorrência de cada palavra na entrada. Exemplo:

 
  % more shellsST.txt
  she sells sea shells by the sea shore
  % java TrieST < shellsST.txt 
  by 4
  sea 6
  sells 1
  she 0
  shells 3
  shore 7
  the 5