001/* Copyright (C) 2013 TU Dortmund 002 * This file is part of AutomataLib, http://www.automatalib.net/. 003 * 004 * AutomataLib is free software; you can redistribute it and/or 005 * modify it under the terms of the GNU Lesser General Public 006 * License version 3.0 as published by the Free Software Foundation. 007 * 008 * AutomataLib is distributed in the hope that it will be useful, 009 * but WITHOUT ANY WARRANTY; without even the implied warranty of 010 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 011 * Lesser General Public License for more details. 012 * 013 * You should have received a copy of the GNU Lesser General Public 014 * License along with AutomataLib; if not, see 015 * http://www.gnu.de/documents/lgpl.en.html. 016 */ 017package net.automatalib.util.tries; 018 019import java.util.ArrayList; 020import java.util.Collection; 021import java.util.Collections; 022import java.util.List; 023import java.util.Map; 024 025import net.automatalib.graphs.abstractimpl.AbstractGraph; 026import net.automatalib.graphs.dot.DOTPlottableGraph; 027import net.automatalib.graphs.dot.EmptyDOTHelper; 028import net.automatalib.graphs.dot.GraphDOTHelper; 029 030public class SuffixTrie<I> extends AbstractGraph<SuffixTrieNode<I>,SuffixTrieNode<I>> implements DOTPlottableGraph<SuffixTrieNode<I>,SuffixTrieNode<I>> { 031 032 public static final boolean DEFAULT_GRAPH_REPRESENTABLE = true; 033 034 protected final SuffixTrieNode<I> root; 035 protected final List<SuffixTrieNode<I>> nodes; 036 037 /** 038 * Constructor. Constructs a graph-representable suffix trie. 039 */ 040 public SuffixTrie() { 041 this(DEFAULT_GRAPH_REPRESENTABLE); 042 } 043 044 /** 045 * Constructor. Constructs a suffix trie. 046 * @param graphRepresentable whether the trie should be graph representable. 047 */ 048 public SuffixTrie(boolean graphRepresentable) { 049 this(graphRepresentable, new SuffixTrieNode<I>()); 050 } 051 052 /** 053 * Internal constructor. Allows to override the root node. 054 * @param root the root node. 055 */ 056 protected SuffixTrie(SuffixTrieNode<I> root) { 057 this(DEFAULT_GRAPH_REPRESENTABLE, root); 058 } 059 060 /** 061 * Internal constructor. Allows to override the root node 062 * and graph representability. 063 * @param graphRepresentable whether the trie should be graph representable. 064 * @param root the root node. 065 */ 066 protected SuffixTrie(boolean graphRepresentable, SuffixTrieNode<I> root) { 067 this.root = root; 068 if(graphRepresentable) { 069 this.nodes = new ArrayList<>(); 070 this.nodes.add(root); 071 } 072 else { 073 this.nodes = null; 074 } 075 } 076 077 /* 078 * (non-Javadoc) 079 * @see net.automatalib.graphs.Graph#getNodes() 080 */ 081 @Override 082 public Collection<SuffixTrieNode<I>> getNodes() { 083 if(nodes == null) 084 throw new UnsupportedOperationException("This trie is not graph representable"); 085 086 return Collections.unmodifiableCollection(nodes); 087 } 088 089 090 /* 091 * (non-Javadoc) 092 * @see net.automatalib.graphs.IndefiniteGraph#getOutgoingEdges(java.lang.Object) 093 */ 094 @Override 095 public Collection<SuffixTrieNode<I>> getOutgoingEdges(SuffixTrieNode<I> node) { 096 if(nodes == null) 097 throw new UnsupportedOperationException("This trie is not graph representable"); 098 099 SuffixTrieNode<I> parent = node.getParent(); 100 if(parent == null) 101 return Collections.emptySet(); 102 return Collections.singleton(parent); 103 } 104 105 /* 106 * (non-Javadoc) 107 * @see net.automatalib.graphs.IndefiniteGraph#getTarget(java.lang.Object) 108 */ 109 @Override 110 public SuffixTrieNode<I> getTarget(SuffixTrieNode<I> edge) { 111 if(nodes == null) 112 throw new UnsupportedOperationException("This trie is not graph representable"); 113 114 return edge; 115 } 116 117 /* 118 * (non-Javadoc) 119 * @see net.automatalib.graphs.dot.DOTPlottableGraph#getGraphDOTHelper() 120 */ 121 @Override 122 public GraphDOTHelper<SuffixTrieNode<I>, SuffixTrieNode<I>> getGraphDOTHelper() { 123 if(nodes == null) 124 throw new UnsupportedOperationException("This trie is not graph representable"); 125 126 return new EmptyDOTHelper<SuffixTrieNode<I>,SuffixTrieNode<I>>() { 127 128 /* (non-Javadoc) 129 * @see net.automatalib.graphs.dot.DefaultDOTHelper#getNodeProperties(java.lang.Object, java.util.Map) 130 */ 131 @Override 132 public boolean getNodeProperties(SuffixTrieNode<I> node, 133 Map<String, String> properties) { 134 if(!super.getNodeProperties(node, properties)) 135 return false; 136 if(node.isRoot()) 137 properties.put(LABEL, "ε"); 138 else 139 properties.put(LABEL, String.valueOf(node.getSymbol())); 140 return true; 141 } 142 143 }; 144 } 145 146 147 /** 148 * Adds a word to the trie. 149 * @param symbol the first symbol of the word. 150 * @param parent the remaining suffix of the word. 151 * @return a trie node corresponding to the inserted word. 152 */ 153 public SuffixTrieNode<I> add(I symbol, SuffixTrieNode<I> parent) { 154 SuffixTrieNode<I> n = new SuffixTrieNode<>(symbol, parent); 155 if(nodes != null) { 156 nodes.add(n); 157 } 158 return n; 159 } 160 161 /** 162 * Returns the root of this trie. 163 * @return the root of this trie. 164 */ 165 public SuffixTrieNode<I> getRoot() { 166 return root; 167 } 168 169 170}