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  }