| 1 | package net.digitaltsunami.word.trie; |
| 2 | |
| 3 | public class WeightedCharTrieNode extends LinkedCharTrieNode { |
| 4 | |
| 5 | private final float weight; |
| 6 | public static final float MIN_WEIGHT = 0.0F; |
| 7 | |
| 8 | public WeightedCharTrieNode(CharTrieNode parent, char value, float weight) { |
| 9 | super(parent, value); |
| 10 | this.weight = weight; |
| 11 | } |
| 12 | |
| 13 | public WeightedCharTrieNode(CharTrieNode parent, char value) { |
| 14 | this(parent, value, MIN_WEIGHT); |
| 15 | } |
| 16 | |
| 17 | public WeightedCharTrieNode(char value, float weight) { |
| 18 | super(value); |
| 19 | this.weight = weight; |
| 20 | } |
| 21 | |
| 22 | public WeightedCharTrieNode(char value) { |
| 23 | this(value, MIN_WEIGHT); |
| 24 | } |
| 25 | |
| 26 | public WeightedCharTrieNode(boolean rootNode) { |
| 27 | super(rootNode); |
| 28 | this.weight = MIN_WEIGHT; |
| 29 | } |
| 30 | |
| 31 | @Override |
| 32 | public CharTrieNode addChild(char value) { |
| 33 | return addChild(value, MIN_WEIGHT); |
| 34 | } |
| 35 | |
| 36 | /** |
| 37 | * Document placement of nodes Equal value (previously added) Lesser weight |
| 38 | * Greater weight Same weight as existing entry. |
| 39 | * |
| 40 | * @param value |
| 41 | * @param valueWeight |
| 42 | * @return |
| 43 | */ |
| 44 | protected CharTrieNode addChild(char value, float valueWeight) { |
| 45 | WeightedCharTrieNode sibling = (WeightedCharTrieNode) getFirstChild(); |
| 46 | while (sibling != null) { |
| 47 | if (valueWeight <= sibling.getWeight()) { |
| 48 | /* |
| 49 | * Sibling is still greater than new value's weight. Must go |
| 50 | * until end of list sibling with lesser weight. Equal weights |
| 51 | * must be searched as the value may already exist. |
| 52 | */ |
| 53 | if (value == sibling.getValue()) { |
| 54 | // Value == sibling, already exists, just return |
| 55 | return sibling; |
| 56 | } else if (sibling.getNextSibling() != null) { |
| 57 | // Not yet at end of list. Keep searching. |
| 58 | sibling = (WeightedCharTrieNode) sibling.getNextSibling(); |
| 59 | } else { |
| 60 | // Reached the end of the sibling list. Add new node and |
| 61 | // append to the last node in the list. |
| 62 | WeightedCharTrieNode newNode = new WeightedCharTrieNode(this, value, |
| 63 | valueWeight); |
| 64 | sibling.appendNode(newNode); |
| 65 | return newNode; |
| 66 | } |
| 67 | } else { |
| 68 | /* |
| 69 | * Expected value weight > sibling's weight, list is in |
| 70 | * descending order of weight, so it won't be found. Create new, |
| 71 | * insert it, and return the new node. |
| 72 | */ |
| 73 | WeightedCharTrieNode newNode = new WeightedCharTrieNode(this, value, valueWeight); |
| 74 | sibling.prependNode(newNode); |
| 75 | return newNode; |
| 76 | } |
| 77 | } |
| 78 | |
| 79 | // First child node to be added, add and return. |
| 80 | WeightedCharTrieNode newNode = new WeightedCharTrieNode(this, value, valueWeight); |
| 81 | setFirstChild(newNode); |
| 82 | return newNode; |
| 83 | } |
| 84 | |
| 85 | protected float getWeight() { |
| 86 | return weight; |
| 87 | } |
| 88 | } |