Collections Data Structure Java

//package com.ryanm.util.text;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
/**
 * Useful for string set lookups and command completion stuff
 * 
 * @author ryanm
 */
public class RadixTree
{
  private Node root = new Node( "" );
  private final boolean caseSensitive;
  /**
   * @param caseSensitive
   *           true if case matters. Note that a
   *           case-insensitive {@link RadixTree} will convert all
   *           strings passed to it for insertion or query to lower
   *           case.
   */
  public RadixTree( boolean caseSensitive )
  {
    this.caseSensitive = caseSensitive;
    root.isString = false;
  }
  /**
   * Adds string to the set
   * 
   * @param string
   */
  public void add( CharSequence string )
  {
    if( !caseSensitive )
    {
      string = string.toString().toLowerCase();
    }
    root.addString( string );
  }
  /**
   * Removes a string from the set
   * 
   * @param string
   */
  public void remove( CharSequence string )
  {
    if( !caseSensitive )
    {
      string = string.toString().toLowerCase();
    }
    root.removeString( string );
  }
  /**
   * Tests if the string is contained in the set
   * 
   * @param string
   * @return true if the entire string is contained in
   *         the tree
   */
  public boolean contains( CharSequence string )
  {
    if( !caseSensitive )
    {
      string = string.toString().toLowerCase();
    }
    return findPredecessor( string ).length() == string.length();
  }
  /**
   * Finds the substring of the string that is in the set
   * 
   * @param string
   * @return The substring that belongs
   */
  public String findPredecessor( CharSequence string )
  {
    if( !caseSensitive )
    {
      string = string.toString().toLowerCase();
    }
    StringBuilder buff = new StringBuilder();
    root.findPredecessor( string, buff );
    return buff.toString();
  }
  /**
   * Finds possible completions that fit in the set
   * 
   * @param string
   * @param depth
   *           How deeply to search the tree, the maximum number of
   *           decisions that need to be made to type any one
   *           completion
   * @return A list of possible completions
   */
  public List findSuccessors( CharSequence string, int depth )
  {
    if( !caseSensitive )
    {
      string = string.toString().toLowerCase();
    }
    List completions = new LinkedList();
    root.findSuccessors( string, depth, completions );
    return completions;
  }
  @Override
  public String toString()
  {
    StringBuilder buff = new StringBuilder();
    root.buildString( buff, -1 );
    return buff.toString();
  }
  private class Node implements Comparable
  {
    private CharSequence value;
    private Node[] children = new Node[ 0 ];
    /**
     * Indicates that the string ending at this node is a string in
     * the set
     */
    private boolean isString = true;
    private Node( CharSequence string )
    {
      value = string;
    }
    private void findSuccessors( CharSequence string, int depth, List completions )
    {
      int d = findDivergenceIndex( string );
      if( d < value.length() || d == string.length() )
      {
        StringBuilder prefix = new StringBuilder( value.subSequence( d, value.length() ) );
        if( isString )
        {
          completions.add( prefix.toString() );
        }
        if( depth > 0 )
        {
          for( int i = 0; i < children.length; i++ )
          {
            children[ i ].getCompletions( prefix, depth - 1, completions );
          }
        }
      }
      else
      {
        Node c = findChild( string.charAt( d ) );
        if( c != null )
        {
          c.findSuccessors( string.subSequence( d, string.length() ), depth, completions );
        }
      }
    }
    private void getCompletions( StringBuilder prefix, int depth, List completions )
    {
      int pl = prefix.length();
      prefix.append( value );
      if( isString )
      {
        completions.add( prefix.toString() );
      }
      if( depth > 0 )
      {
        for( int i = 0; i < children.length; i++ )
        {
          children[ i ].getCompletions( prefix, depth - 1, completions );
        }
      }
      prefix.delete( pl, prefix.length() );
    }
    private void addString( CharSequence string )
    {
      int d = findDivergenceIndex( string );
      if( d < value.length() )
      {
        // need to split this node
        Node child = new Node( value.subSequence( d, value.length() ) );
        child.children = children;
        child.isString = isString;
        value = value.subSequence( 0, d );
        children = new Node[] { child };
        isString = false;
      }
      if( d == string.length() && d > 0 )
      {
        isString = true;
      }
      else
      {
        Node c = findChild( string.charAt( d ) );
        if( c != null )
        {
          c.addString( string.subSequence( d, string.length() ) );
        }
        else
        {
          insertNode( new Node( string.subSequence( d, string.length() ) ) );
        }
      }
    }
    private void removeString( CharSequence string )
    {
      int d = findDivergenceIndex( string );
      if( d == value.length() && d == string.length() )
      {
        isString = false;
        if( children.length == 1 )
        { // unify nodes
          StringBuilder buff = new StringBuilder( value );
          buff.append( children[ 0 ].value );
          value = buff;
          isString = children[ 0 ].isString;
          children = children[ 0 ].children;
        }
      }
      else
      {
        if( d == value.length() )
        {
          // check children
          Node c = findChild( string.charAt( d ) );
          if( c != null )
          {
            c.removeString( string.subSequence( d, string.length() ) );
          }
        }
      }
    }
    private void findPredecessor( CharSequence string, StringBuilder buff )
    {
      int d = findDivergenceIndex( string );
      if( d == value.length() && d <= string.length() )
      { // this entire node was in the tree and there still some
        // to go
        buff.append( value.subSequence( 0, d ) );
        // check children
        if( d < string.length() )
        {
          CharSequence c = string.subSequence( d, string.length() );
          Node child = findChild( c.charAt( 0 ) );
          child.findPredecessor( c, buff );
        }
      }
    }
    private Node findChild( char c )
    {
      for( int i = 0; i < children.length; i++ )
      {
        if( c == children[ i ].value.charAt( 0 ) )
        {
          return children[ i ];
        }
      }
      return null;
    }
    private int findDivergenceIndex( CharSequence string )
    {
      int d = 0;
      while( d < value.length() && d < string.length() && value.charAt( d ) == string.charAt( d ) )
      {
        d++;
      }
      return d;
    }
    private void insertNode( Node child )
    {
      int i = Arrays.binarySearch( children, child );
      assert i < 0;
      i += 1;
      i = -i;
      Node[] nc = new Node[ children.length + 1 ];
      System.arraycopy( children, 0, nc, 0, i );
      nc[ i ] = child;
      if( i < nc.length )
      {
        System.arraycopy( children, i, nc, i + 1, children.length - i );
      }
      children = nc;
    }
    @Override
    public int compareTo( Node o )
    {
      return TextUtils.compareTo( value, o.value );
    }
    private void buildString( StringBuilder buff, int indent )
    {
      for( int i = 0; i < indent; i++ )
      {
        buff.append( " " );
      }
      if( isString )
      {
        buff.append( "\"" );
      }
      buff.append( value );
      if( isString )
      {
        buff.append( "\"" );
      }
      indent++;
      for( int i = 0; i < children.length; i++ )
      {
        buff.append( "\n" );
        children[ i ].buildString( buff, indent );
      }
    }
  }
}
/**
 * Utility methods for dealing with text
 * 
 * @author ryanm
 */
class TextUtils
{
  /**
   * Tests if s starts with t, ignoring the case of the characters
   * 
   * @param s
   * @param t
   * @return true if s.toLowerCase().equals(
   *         t.toLowerCase() ), but more efficiently
   */
  public static boolean startsWithIgnoreCase( CharSequence s, CharSequence t )
  {
    if( s.length() < t.length() )
    {
      return false;
    }
    for( int i = 0; i < t.length(); i++ )
    {
      char slc = Character.toLowerCase( s.charAt( i ) );
      char tlc = Character.toLowerCase( t.charAt( i ) );
      if( slc != tlc )
      {
        return false;
      }
    }
    return true;
  }
  /**
   * See {@link String#compareToIgnoreCase(String)}
   * 
   * @param s
   * @param t
   * @return See {@link String#compareToIgnoreCase(String)}
   */
  public static int compareToIgnoreCase( CharSequence s, CharSequence t )
  {
    int i = 0;
    while( i < s.length() && i < t.length() )
    {
      char a = Character.toLowerCase( s.charAt( i ) );
      char b = Character.toLowerCase( t.charAt( i ) );
      int diff = a - b;
      if( diff != 0 )
      {
        return diff;
      }
      i++;
    }
    return s.length() - t.length();
  }
  /**
   * See {@link String#compareTo(String)}
   * 
   * @param s
   * @param t
   * @return See {@link String#compareTo(String)}
   */
  public static int compareTo( CharSequence s, CharSequence t )
  {
    int i = 0;
    while( i < s.length() && i < t.length() )
    {
      char a = s.charAt( i );
      char b = t.charAt( i );
      int diff = a - b;
      if( diff != 0 )
      {
        return diff;
      }
      i++;
    }
    return s.length() - t.length();
  }
  /**
   * Splits a string
   * 
   * @param composite
   *           The composite string
   * @param leftBracket
   *           the opening parenthesis character
   * @param rightBracket
   *           the closing parenthesis character
   * @param separator
   *           The character that separates tokens. Separators that
   *           lie between at least one pair of parenthesis are
   *           ignored
   * @return An array of individual tokens
   */
  public static String[] split( String composite, char leftBracket, char rightBracket,
      char separator )
  {
    List c = new ArrayList();
    int start = 0;
    int i;
    int lbcount = 0;
    for( i = 0; i < composite.length(); i++ )
    {
      if( composite.charAt( i ) == leftBracket )
      {
        lbcount++;
      }
      else if( composite.charAt( i ) == rightBracket )
      {
        lbcount--;
      }
      else if( composite.charAt( i ) == separator && lbcount == 0 )
      {
        c.add( composite.substring( start, i ).trim() );
        start = i + 1;
      }
    }
    c.add( composite.substring( start, i ).trim() );
    return c.toArray( new String[ c.size() ] );
  }
  /**
   * Wraps the input string in {@code } and breaks it up
   * into lines with {@code 
} elements. Useful for making
   * multi-line tootips and the like.
   * 
   * @param s
   *           The input String
   * @param lineLength
   *           The desired length of the output lines.
   * @return The HTMLised string
   */
  public static String HTMLiseString( String s, int lineLength )
  {
    if( s != null )
    {
      StringBuilder buff = new StringBuilder( s );
      int lineStart = 0;
      while( lineStart + lineLength < s.length() )
      {
        // find the first whitespace after the linelength
        int firstSpaceIndex = buff.indexOf( " ", lineStart + lineLength );
        // replace it with a 

        if( firstSpaceIndex != -1 )
        {
          buff.deleteCharAt( firstSpaceIndex );
          buff.insert( firstSpaceIndex, "
" );
          lineStart = firstSpaceIndex + 4;
        }
        else
        {
          lineStart = s.length();
        }
      }
      buff.insert( 0, "" );
      buff.append( "" );
      return buff.toString();
    }
    return null;
  }
}