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}