| 1 | package net.digitaltsunami.word.trie; |
| 2 | |
| 3 | import java.util.Arrays; |
| 4 | import java.util.Iterator; |
| 5 | |
| 6 | /** |
| 7 | * Container for a character providing links to siblings, parents, and children. |
| 8 | * |
| 9 | * @author dhagberg |
| 10 | * |
| 11 | */ |
| 12 | public abstract class LinkedCharTrieNode implements CharTrieTerminusNode { |
| 13 | private final char value; |
| 14 | private LinkedCharTrieNode parent; |
| 15 | private LinkedCharTrieNode firstChild; |
| 16 | private LinkedCharTrieNode priorSibling; |
| 17 | private LinkedCharTrieNode nextSibling; |
| 18 | private boolean terminus; |
| 19 | private final boolean root; |
| 20 | |
| 21 | /** |
| 22 | * Create new Node with the provided value. |
| 23 | * |
| 24 | * @param parent |
| 25 | * @param value |
| 26 | */ |
| 27 | protected LinkedCharTrieNode(CharTrieNode parent, char value) { |
| 28 | this.parent = (LinkedCharTrieNode) parent; |
| 29 | this.value = value; |
| 30 | this.root = false; |
| 31 | } |
| 32 | |
| 33 | /** |
| 34 | * Create new Node with the provided value. |
| 35 | * |
| 36 | * @param value |
| 37 | */ |
| 38 | protected LinkedCharTrieNode(char value) { |
| 39 | this.value = value; |
| 40 | this.root = false; |
| 41 | } |
| 42 | |
| 43 | /** |
| 44 | * Create new root node. This node will not contain a value. |
| 45 | * |
| 46 | * @param value |
| 47 | */ |
| 48 | protected LinkedCharTrieNode(boolean rootNode) { |
| 49 | this.value = '\0'; |
| 50 | this.root = rootNode; |
| 51 | } |
| 52 | |
| 53 | /** |
| 54 | * Marks this node as the terminus in a sequence indicating a complete word |
| 55 | * from root to this node. |
| 56 | * |
| 57 | * @param terminus |
| 58 | * true if this node completes a word from root to here. |
| 59 | */ |
| 60 | protected void setTerminus(boolean terminus) { |
| 61 | this.terminus = terminus; |
| 62 | } |
| 63 | |
| 64 | /* |
| 65 | * (non-Javadoc) |
| 66 | * |
| 67 | * @see net.digitaltsunami.util.CharTrieNode#isTerminus() |
| 68 | */ |
| 69 | @Override |
| 70 | public boolean isTerminus() { |
| 71 | return terminus; |
| 72 | } |
| 73 | |
| 74 | /* |
| 75 | * (non-Javadoc) |
| 76 | * |
| 77 | * @see net.digitaltsunami.util.CharTrieNode#isRoot() |
| 78 | */ |
| 79 | @Override |
| 80 | public boolean isRoot() { |
| 81 | return root; |
| 82 | } |
| 83 | |
| 84 | /* |
| 85 | * (non-Javadoc) |
| 86 | * |
| 87 | * @see net.digitaltsunami.util.CharTrieNode#getValue() |
| 88 | */ |
| 89 | @Override |
| 90 | public char getValue() { |
| 91 | return value; |
| 92 | } |
| 93 | |
| 94 | /* |
| 95 | * (non-Javadoc) |
| 96 | * |
| 97 | * @see net.digitaltsunami.util.CharTrieNode#getParent() |
| 98 | */ |
| 99 | @Override |
| 100 | public CharTrieNode getParent() { |
| 101 | return this.parent; |
| 102 | } |
| 103 | |
| 104 | /** |
| 105 | * Return the left sibling for this node or null if first node. |
| 106 | * |
| 107 | * @return the left sibling for this node or null if first node. |
| 108 | */ |
| 109 | protected LinkedCharTrieNode getPriorSibling() { |
| 110 | return this.priorSibling; |
| 111 | } |
| 112 | |
| 113 | /** |
| 114 | * Set the sibling that precedes this node. |
| 115 | * |
| 116 | * @param sibling |
| 117 | */ |
| 118 | protected void setPriorSibling(LinkedCharTrieNode sibling) { |
| 119 | this.priorSibling = sibling; |
| 120 | } |
| 121 | |
| 122 | /** |
| 123 | * Return the next sibling for this node or null if first node. |
| 124 | * |
| 125 | * @return the next sibling for this node or null if first node. |
| 126 | */ |
| 127 | protected LinkedCharTrieNode getNextSibling() { |
| 128 | return this.nextSibling; |
| 129 | } |
| 130 | |
| 131 | /** |
| 132 | * Set the sibling that follows this node. |
| 133 | * |
| 134 | * @param sibling |
| 135 | */ |
| 136 | protected void setNextSibling(LinkedCharTrieNode sibling) { |
| 137 | this.nextSibling = sibling; |
| 138 | } |
| 139 | |
| 140 | /** |
| 141 | * Return the first child node for this node or null if node has no |
| 142 | * children. |
| 143 | * |
| 144 | * @return the first child node for this node or null if node has no |
| 145 | * children. |
| 146 | */ |
| 147 | protected LinkedCharTrieNode getFirstChild() { |
| 148 | return this.firstChild; |
| 149 | } |
| 150 | |
| 151 | /** |
| 152 | * Set the first child node for this node. |
| 153 | * |
| 154 | * @param child |
| 155 | * the first child node for this node. |
| 156 | */ |
| 157 | protected void setFirstChild(LinkedCharTrieNode child) { |
| 158 | this.firstChild = child; |
| 159 | } |
| 160 | |
| 161 | /* |
| 162 | * (non-Javadoc) |
| 163 | * |
| 164 | * @see net.digitaltsunami.util.CharTrieTerminusNode#getTerm() |
| 165 | */ |
| 166 | @Override |
| 167 | public String getTerm() { |
| 168 | int buffSize = 128; |
| 169 | char[] buff = new char[buffSize]; |
| 170 | int buffPos = buffSize; |
| 171 | |
| 172 | LinkedCharTrieNode currNode = this; |
| 173 | while (currNode.parent != null) { |
| 174 | // This entry will exceed buffer limits: double size and copy |
| 175 | if (buffPos == 0) { |
| 176 | // Save off original values |
| 177 | int origBuffSize = buffSize; |
| 178 | char[] origBuff = buff; |
| 179 | // Double size of buffer |
| 180 | buffSize = buffSize * 2; |
| 181 | buff = new char[buffSize]; |
| 182 | // Copy original to new buffer |
| 183 | buffPos = buffSize - 1; |
| 184 | for (int origIdx = origBuffSize - 1; origIdx > 0; buffPos--, origIdx--) { |
| 185 | buff[buffPos] = origBuff[origIdx]; |
| 186 | } |
| 187 | } |
| 188 | |
| 189 | buffPos--; |
| 190 | buff[buffPos] = currNode.value; |
| 191 | currNode = currNode.parent; |
| 192 | } |
| 193 | |
| 194 | char[] termBuff = Arrays.copyOfRange(buff, buffPos, buffSize); |
| 195 | return new String(termBuff); |
| 196 | } |
| 197 | |
| 198 | /** |
| 199 | * Return the child of this node that matches the provided value or null if |
| 200 | * not found. |
| 201 | * <p> |
| 202 | * This implmentation will traverse the entire sibling list if the element is |
| 203 | * not found. Concrete classes should override this method if the traversal |
| 204 | * can be short circuited. |
| 205 | * |
| 206 | * @param value |
| 207 | * child element to search for. |
| 208 | * @return Child node if found or null if the value is not a child of this |
| 209 | * node. |
| 210 | * |
| 211 | */ |
| 212 | @Override |
| 213 | public CharTrieNode getChild(char value) { |
| 214 | LinkedCharTrieNode sibling = getFirstChild(); |
| 215 | while (sibling != null) { |
| 216 | if (value == sibling.getValue()) { |
| 217 | // Value == child, return |
| 218 | return sibling; |
| 219 | } else { |
| 220 | sibling = sibling.getNextSibling(); |
| 221 | } |
| 222 | } |
| 223 | return null; |
| 224 | } |
| 225 | |
| 226 | /* |
| 227 | * (non-Javadoc) |
| 228 | * |
| 229 | * @see net.digitaltsunami.util.CharTrieNode#iterator() |
| 230 | */ |
| 231 | @Override |
| 232 | public Iterator<CharTrieNode> iterator() { |
| 233 | return new ChildIterator(this); |
| 234 | } |
| 235 | |
| 236 | @Override |
| 237 | public String toString() { |
| 238 | return "CharTrieNodeImpl [value=" + value + ", p=" |
| 239 | + (parent == null ? "null" : parent.value) + ", fc=" |
| 240 | + (firstChild == null ? "null" : firstChild.value) + ", l=" |
| 241 | + (priorSibling == null ? "null" : priorSibling.value) + ", r=" |
| 242 | + (nextSibling == null ? "null" : nextSibling.value) + ", terminus=" + terminus |
| 243 | + "]"; |
| 244 | } |
| 245 | |
| 246 | /** |
| 247 | * Insert the provided node prior to this node. Fix all pointers of siblings |
| 248 | * and parent as applicable. |
| 249 | * |
| 250 | * @param node |
| 251 | * to insert prior to the node. |
| 252 | */ |
| 253 | protected void prependNode(LinkedCharTrieNode node) { |
| 254 | node.setPriorSibling(this.priorSibling); |
| 255 | node.setNextSibling(this); |
| 256 | |
| 257 | if (priorSibling == null) { |
| 258 | this.parent.setFirstChild(node); |
| 259 | } else { |
| 260 | priorSibling.setNextSibling(node); |
| 261 | } |
| 262 | |
| 263 | this.priorSibling = node; |
| 264 | } |
| 265 | |
| 266 | /** |
| 267 | * Append the provided node prior to this node. Fix all pointers of siblings |
| 268 | * and parent as applicable. |
| 269 | * |
| 270 | * @param node |
| 271 | * to insert prior to the node. |
| 272 | */ |
| 273 | protected void appendNode(LinkedCharTrieNode node) { |
| 274 | if (this.nextSibling != null) { |
| 275 | nextSibling.setPriorSibling(node); |
| 276 | } |
| 277 | node.setNextSibling(this.nextSibling); |
| 278 | |
| 279 | this.nextSibling = node; |
| 280 | node.setPriorSibling(this); |
| 281 | } |
| 282 | |
| 283 | /** |
| 284 | * Iterates over the children for this node. |
| 285 | * |
| 286 | * @author dhagberg |
| 287 | * |
| 288 | */ |
| 289 | private class ChildIterator implements Iterator<CharTrieNode> { |
| 290 | |
| 291 | private LinkedCharTrieNode parent; |
| 292 | private LinkedCharTrieNode currentNode; |
| 293 | |
| 294 | protected ChildIterator(LinkedCharTrieNode parent) { |
| 295 | this.parent = parent; |
| 296 | } |
| 297 | |
| 298 | @Override |
| 299 | public boolean hasNext() { |
| 300 | if (currentNode == null) { |
| 301 | return parent.firstChild != null; |
| 302 | } else { |
| 303 | return currentNode.nextSibling != null; |
| 304 | } |
| 305 | } |
| 306 | |
| 307 | @Override |
| 308 | public CharTrieNode next() { |
| 309 | if (currentNode == null) { |
| 310 | currentNode = parent.firstChild; |
| 311 | } else { |
| 312 | currentNode = currentNode.nextSibling; |
| 313 | } |
| 314 | return currentNode; |
| 315 | } |
| 316 | |
| 317 | /** |
| 318 | * Remove is not supported. |
| 319 | */ |
| 320 | @Override |
| 321 | public void remove() { |
| 322 | throw new UnsupportedOperationException("Remove not supported"); |
| 323 | } |
| 324 | |
| 325 | } |
| 326 | |
| 327 | } |