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 net.automatalib.words.Alphabet; 020 021public class SharedSuffixTrie<I> extends SuffixTrie<I> { 022 023 private final Alphabet<I> alphabet; 024 025 public SharedSuffixTrie(Alphabet<I> alphabet) { 026 super(new SharedSuffixTrieNode<I>()); 027 this.alphabet = alphabet; 028 } 029 public SharedSuffixTrie(Alphabet<I> alphabet, boolean graphRepresentable) { 030 super(graphRepresentable, new SharedSuffixTrieNode<I>()); 031 this.alphabet = alphabet; 032 } 033 034 /* (non-Javadoc) 035 * @see net.automatalib.util.tries.SuffixTrie#add(java.lang.Object, net.automatalib.util.tries.SuffixTrieNode) 036 */ 037 @Override 038 @SuppressWarnings("unchecked") 039 public SuffixTrieNode<I> add(I symbol, SuffixTrieNode<I> parent) { 040 if(parent.getClass() != SharedSuffixTrieNode.class) { 041 throw new IllegalArgumentException("Invalid suffix trie node"); 042 } 043 044 int symbolIdx = alphabet.getSymbolIndex(symbol); 045 SharedSuffixTrieNode<I> sparent = (SharedSuffixTrieNode<I>)parent; 046 047 SharedSuffixTrieNode<I> child; 048 SharedSuffixTrieNode<I>[] children = sparent.children; 049 if(children == null) { 050 children = sparent.children = new SharedSuffixTrieNode[alphabet.size()]; 051 } 052 else if((child = children[symbolIdx]) != null) { 053 return child; 054 } 055 child = new SharedSuffixTrieNode<>(symbol, sparent); 056 children[symbolIdx] = child; 057 return child; 058 } 059 060 061 062}