1a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com/* 2a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comThe MIT License 3a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 4a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comCopyright (c) 2008 Tahseen Ur Rehman 5a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 6a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comPermission is hereby granted, free of charge, to any person obtaining a copy 7a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comof this software and associated documentation files (the "Software"), to deal 8a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comin the Software without restriction, including without limitation the rights 9a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comto use, copy, modify, merge, publish, distribute, sublicense, and/or sell 10a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comcopies of the Software, and to permit persons to whom the Software is 11a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comfurnished to do so, subject to the following conditions: 12a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 13a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comThe above copyright notice and this permission notice shall be included in 14a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comall copies or substantial portions of the Software. 15a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 16a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comTHE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 17a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comIMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 18a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comFITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 19a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comAUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 20a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comLIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 21a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comOUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 22a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comTHE SOFTWARE. 23a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com*/ 24a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 25a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.compackage ds.tree; 26a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 27a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comimport java.util.ArrayList; 28a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comimport java.util.List; 29a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 30a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com/** 31a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * Represents a node of a Radix tree {@link RadixTreeImpl} 32a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * 33a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @author Tahseen Ur Rehman 34a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @email tahseen.ur.rehman {at.spam.me.not} gmail.com 35a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * @param <T> 36a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com */ 37a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.comclass RadixTreeNode<T> { 38a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com private String key; 39a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 40a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com private List<RadixTreeNode<T>> childern; 41a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 42a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com private boolean real; 43a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 44a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com private T value; 45a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 46a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com /** 47a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * intailize the fields with default values to avoid null reference checks 48a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com * all over the places 49a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com */ 50a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public RadixTreeNode() { 51a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com key = ""; 52a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com childern = new ArrayList<RadixTreeNode<T>>(); 53a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com real = false; 54a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 55a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 56a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public T getValue() { 57a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com return value; 58a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 59a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 60a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public void setValue(T data) { 61a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com this.value = data; 62a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 63a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 64a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public String getKey() { 65a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com return key; 66a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 67a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 68a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public void setKey(String value) { 69a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com this.key = value; 70a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 71a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 72a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public boolean isReal() { 73a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com return real; 74a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 75a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 76a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public void setReal(boolean datanode) { 77a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com this.real = datanode; 78a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 79a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 80a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public List<RadixTreeNode<T>> getChildern() { 81a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com return childern; 82a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 83a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 84a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public void setChildern(List<RadixTreeNode<T>> childern) { 85a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com this.childern = childern; 86a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 87a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 8840c48da564efb8c95ed0599f0783b0fd676b6c1fBen Gruver public int getNumberOfMatchingCharacters(String key) { 8940c48da564efb8c95ed0599f0783b0fd676b6c1fBen Gruver int numberOfMatchingCharacters = 0; 90a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com while (numberOfMatchingCharacters < key.length() && numberOfMatchingCharacters < this.getKey().length()) { 91a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com if (key.charAt(numberOfMatchingCharacters) != this.getKey().charAt(numberOfMatchingCharacters)) { 92a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com break; 93a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 94a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com numberOfMatchingCharacters++; 95a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 9640c48da564efb8c95ed0599f0783b0fd676b6c1fBen Gruver return numberOfMatchingCharacters; 9740c48da564efb8c95ed0599f0783b0fd676b6c1fBen Gruver } 98a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com 99a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com @Override 100a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com public String toString() { 10140c48da564efb8c95ed0599f0783b0fd676b6c1fBen Gruver return key; 102a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com } 103a6e5671a627284347484db96f40a29a45e4e4ed1JesusFreke@JesusFreke.com} 104