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.List; 020 021import net.automatalib.words.Word; 022import net.automatalib.words.WordBuilder; 023 024/** 025 * A node in a {@link SuffixTrie}. 026 * 027 * @author Malte Isberner <malte.isberner@gmail.com> 028 * 029 * @param <I> symbol class. 030 */ 031public class SuffixTrieNode<I> extends Word<I> { 032 033 /** 034 * Optimized iterator for the implicit word representation. 035 * 036 * @author Malte Isberner <malte.isberner@gmail.com> 037 * 038 * @param <I> symbol class 039 */ 040 private static final class Iterator<I> implements java.util.Iterator<I> { 041 042 private SuffixTrieNode<I> current; 043 044 public Iterator(SuffixTrieNode<I> node) { 045 this.current = node; 046 } 047 048 /* 049 * (non-Javadoc) 050 * @see java.util.Iterator#hasNext() 051 */ 052 @Override 053 public boolean hasNext() { 054 return !current.isRoot(); 055 } 056 057 /* 058 * (non-Javadoc) 059 * @see java.util.Iterator#next() 060 */ 061 @Override 062 public I next() { 063 I sym = current.symbol; 064 current = current.parent; 065 return sym; 066 } 067 068 /* 069 * (non-Javadoc) 070 * @see java.util.Iterator#remove() 071 */ 072 @Override 073 public void remove() { 074 throw new UnsupportedOperationException(); 075 } 076 } 077 078 public static <I> void appendSuffix(SuffixTrieNode<I> node, List<? super I> symList) { 079 while(node.parent != null) { 080 symList.add(node.symbol); 081 node = node.parent; 082 } 083 } 084 085 public static <I> Word<I> toExplicitWord(SuffixTrieNode<I> node) { 086 WordBuilder<I> wb = new WordBuilder<I>(node.depth()); 087 appendSuffix(node, wb); 088 return wb.toWord(); 089 } 090 091 public static <I> int depth(SuffixTrieNode<I> node) { 092 int d = 0; 093 while(node.parent != null) { 094 d++; 095 node = node.parent; 096 } 097 return d; 098 } 099 100 public static <I> I getSymbol(SuffixTrieNode<I> node, int index) { 101 while(index-- > 0) 102 node = node.parent; 103 return node.symbol; 104 } 105 106 107 108 109 110 private final I symbol; 111 private final SuffixTrieNode<I> parent; 112 113 114 /** 115 * Root constructor. 116 */ 117 public SuffixTrieNode() { 118 this.symbol = null; 119 this.parent = null; 120 } 121 122 123 public SuffixTrieNode(I symbol, SuffixTrieNode<I> parent) { 124 this.symbol = symbol; 125 this.parent = parent; 126 } 127 128 // TODO: replace by getter/attribute? 129 public int depth() { 130 return depth(this); 131 } 132 133 public I getSymbol() { 134 return symbol; 135 } 136 137 public SuffixTrieNode<I> getParent() { 138 return parent; 139 } 140 141 142 public boolean isRoot() { 143 return (parent == null); 144 } 145 146 public void appendSuffix(List<? super I> symList) { 147 appendSuffix(this, symList); 148 } 149 150 public Word<I> getSuffix() { 151 if(parent == null) 152 return Word.epsilon(); 153 WordBuilder<I> wb = new WordBuilder<>(depth()); 154 appendSuffix(wb); 155 return wb.toWord(); 156 } 157 158 @Override 159 public I getSymbol(int index) { 160 return getSymbol(this, index); 161 } 162 163 @Override 164 public int length() { 165 return depth(); 166 } 167 168 @Override 169 public Iterator<I> iterator() { 170 return new Iterator<I>(this); 171 } 172}