/** Implementa PSSet mediante una Trie.
 */
 
import java.util.*; 
 
public class TriePSSet implements PSSet {

	private Map figli;   /* Character -> TriePSSet */
	private boolean terminale;
	private int conta;	

	/** Costruisce l'insieme (vuoto)  */
	public TriePSSet() {
		figli = new HashMap();
		terminale = false;
		conta = 0;
	}
	
	/** Implementa il metodo di PSSet. */
	public boolean add( String s ) {
		if ( s.equals( "" ) ) 
			if ( terminale ) return false;
			else {
				terminale = true;
				conta++;
				return true;
			}
		else {
			TriePSSet subtrie;
			Character c = new Character( s.charAt( 0 ) );

			subtrie = (TriePSSet) figli.get( c );
			if ( subtrie == null )
				figli.put( c, subtrie = new TriePSSet() );
			if ( subtrie.add( s.substring( 1 ) ) ) {
				conta++;
				return true;
			} else 
				return false;
		}
		
	}

	
	/** Implementa il metodo di PSSet. */
	public int retrieveNumber( String p ) {
		if ( p.equals( "" ) ) return conta;
		
		TriePSSet subtrie;
		Character c = new Character( p.charAt( 0 ) );
		
		subtrie = (TriePSSet) figli.get( c );
		if ( subtrie == null ) return 0;
		return subtrie.retrieveNumber( p.substring( 1 ) );
	}

	/** Implementa il metodo di PSSet. */
	public String retrieveUnique( String p ) {
		return retrieveUnique ( p, "" );
	}

	/** Implementa il metodo di PSSet. */
	private String retrieveUnique( String p, String prevPref ) {
		if ( p.equals( "" ) ) {
			if ( conta != 1 ) return null;
			return prevPref + visita();
		}
		else {
			Character c = new Character( p.charAt( 0 ) );
			TriePSSet subtrie = (TriePSSet) figli.get( c );
			if ( subtrie == null ) return null;
			return subtrie.retrieveUnique( p.substring( 1 ), prevPref + c );			
		}
	}
	
	/** Assume che la trie corrente contenga una sola stringa, e la restituisce. */
	private String visita() {
		if ( terminale ) return "";
		Iterator it = figli.keySet().iterator();
		Character c = (Character) it.next();
		return "" + c + ((TriePSSet)figli.get( c )).visita();
	}	
	
	public String toString() {
		return figli.toString();
	}	
}