001/* 002 * Copyright (c) 2016-2017 Chris K Wensel <chris@wensel.net>. All Rights Reserved. 003 * 004 * Project and contact information: http://www.cascading.org/ 005 * 006 * This file is part of the Cascading project. 007 * 008 * Licensed under the Apache License, Version 2.0 (the "License"); 009 * you may not use this file except in compliance with the License. 010 * You may obtain a copy of the License at 011 * 012 * http://www.apache.org/licenses/LICENSE-2.0 013 * 014 * Unless required by applicable law or agreed to in writing, software 015 * distributed under the License is distributed on an "AS IS" BASIS, 016 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 017 * See the License for the specific language governing permissions and 018 * limitations under the License. 019 */ 020 021package cascading.util; 022 023import java.io.Serializable; 024import java.util.HashMap; 025import java.util.Map; 026 027/** 028 * This class is based on the work found here by Vladimir Kroz, made available without restriction. 029 * <p> 030 * https://vkroz.wordpress.com/2012/03/23/prefix-table-trie-implementation-in-java/ 031 */ 032public class Trie<V extends Serializable> implements Serializable 033 { 034 static public class Entry<V> implements Serializable 035 { 036 String prefix; 037 V value; 038 039 public Entry() 040 { 041 } 042 043 public Entry( String p, V v ) 044 { 045 prefix = p; 046 value = v; 047 } 048 049 public String prefix() 050 { 051 return prefix; 052 } 053 054 public V value() 055 { 056 return value; 057 } 058 059 @Override 060 public String toString() 061 { 062 final StringBuilder sb = new StringBuilder( "Entry{" ); 063 sb.append( "prefix='" ).append( prefix ).append( '\'' ); 064 sb.append( ", value=" ).append( value ); 065 sb.append( '}' ); 066 return sb.toString(); 067 } 068 } 069 070 Entry<V> entry; 071 char key; 072 Map<Character, Trie<V>> children; 073 074 public Trie() 075 { 076 this.children = new HashMap<>(); 077 this.entry = new Entry<>(); 078 } 079 080 Trie( char key ) 081 { 082 this.children = new HashMap<>(); 083 this.key = key; 084 entry = new Entry<V>(); 085 } 086 087 public void put( String key, V value ) 088 { 089 put( new StringBuffer( key ), new StringBuffer( "" ), value ); 090 } 091 092 void put( StringBuffer remainder, StringBuffer prefix, V value ) 093 { 094 if( remainder.length() <= 0 ) 095 { 096 this.entry.value = value; 097 this.entry.prefix = prefix.toString(); 098 return; 099 } 100 101 char keyElement = remainder.charAt( 0 ); 102 Trie<V> trie = null; 103 104 try 105 { 106 trie = children.get( keyElement ); 107 } 108 catch( IndexOutOfBoundsException ignored ) 109 { 110 } 111 112 if( trie == null ) 113 { 114 trie = new Trie<>( keyElement ); 115 children.put( keyElement, trie ); 116 } 117 118 prefix.append( remainder.charAt( 0 ) ); 119 trie.put( remainder.deleteCharAt( 0 ), prefix, value ); 120 } 121 122 public V get( String key ) 123 { 124 return get( new StringBuffer( key ), 0 ); 125 } 126 127 public boolean hasPrefix( String key ) 128 { 129 return ( this.get( key ) != null ); 130 } 131 132 V get( StringBuffer key, int level ) 133 { 134 if( key.length() <= 0 ) 135 return entry.value; 136 137 Trie<V> trie = children.get( key.charAt( 0 ) ); 138 139 if( trie != null ) 140 return trie.get( key.deleteCharAt( 0 ), ++level ); 141 else 142 return ( level > 0 ) ? entry.value : null; 143 } 144 145 public String getCommonPrefix() 146 { 147 StringBuffer buffer = new StringBuffer(); 148 149 if( children.size() != 1 ) 150 return buffer.toString(); 151 152 buildPrefix( buffer, this ); 153 154 return buffer.toString(); 155 } 156 157 private void buildPrefix( StringBuffer buffer, Trie<V> current ) 158 { 159 if( current.children.size() != 1 ) 160 return; 161 162 for( Map.Entry<Character, Trie<V>> entry : current.children.entrySet() ) 163 { 164 buffer.append( entry.getKey() ); 165 166 buildPrefix( buffer, entry.getValue() ); 167 } 168 } 169 170 @Override 171 public String toString() 172 { 173 final StringBuilder sb = new StringBuilder( "Trie{" ); 174 sb.append( "entry=" ).append( entry ); 175 sb.append( ", key=" ).append( key ); 176 sb.append( ", children=" ).append( children ); 177 sb.append( '}' ); 178 return sb.toString(); 179 } 180 }