2.4/dev/core/src/com/google/gwt/dev/util/editdistance/CharIndex.java - gwt - Git at Google

 /*
  * Copyright 2010 Google Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License"); you may not
  * use this file except in compliance with the License. You may obtain a copy of
  * the License at
  *
  * http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
  * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
  * License for the specific language governing permissions and limitations under
  * the License.
  */
 package com.google.gwt.dev.util.editdistance;

 /**
  * A performance-oriented character-indexed map.
  * Provides a mapping from characters in a limited alphabet
  * (defined by a CharSequence) to integer values (for array indexing).
  * Emphasis is on performance (e.g., compared to using a generic HashMap),
  * in terms of speed of (post-construction) lookup and space required.
  *
  * Maps are constructed using a static <tt>getInstance</tt> method that
  * chooses an efficient implementation for a given string.
  * The map interface consists of:
  *    a <tt>size</tt> method for determining the maximum range of indices used;
  *    a <tt>lookup</tt> method for translating a character to its index; and,
  *    a <tt>nullElement</tt> method that returns the index that is not
  *     returned by <tt>lookup</tt> for any characer actually in the map.
  *
  * The target application is the mapping of natural-language strings.
  * Most strings include characters from a single language, and thus
  * fall into a small slice of the Unicode space.  In particular,
  * many strings fall into just the Latin series.
  */
 public abstract class CharIndex {
   /**
    * An index based on a garden-variety hash map.
    * This is the implementation of last recourse (from a
    * performance perspective).
    *
    * TODO(mwyoung): there may be value in an implementation
    * that falls in between the masked and fullhash variants;
    * for example, one using a closed hash table with rehashing.
    */
   public static class FullHash extends CharIndex {
     /**
      * Mutable holder for a character.
      */
     static class Char {
       char c;
       @Override
       public boolean equals(Object x) {
         return (x != null) && (((Char) x).c == this.c);
       }
       @Override
       public int hashCode() {
         return c;
       }
       @Override
       public String toString() {
         return "'" + c + "'";
       }
     }

     static final int NULL_ELEMENT = 0;
     protected int lastUsed = NULL_ELEMENT;
     /**
      * Mapping from pattern characters to their integer index values.
      */
     final java.util.HashMap<Char,Integer> map;

     /**
      * Constructs a full hash-based mapping.
      */
     FullHash(CharSequence s) {
       /* Choose a hash size larger at least twice the string length */
       int len = s.length();
       int power = Integer.highestOneBit(len);

       /* Create the map */
       map = new java.util.HashMap<Char,Integer>(
           power << ((power == len) ? 1 : 2));

       /*
        * Add characters one at a time to the map
        */

       Char test = new Char();                   /* (re)used for lookup */
       for (int i = 0; i < s.length(); i++) {
         test.c = s.charAt(i);
         if (map.get(test) == null) {
           /* Not there... add it */
           map.put(test, new Integer(++lastUsed));

           /* Grow a new holder for subsequent lookups */
           test = new Char();
         }
       }
     }

     @Override
     public int lookup(char c) {
       final Char lookupTest = new Char();
       lookupTest.c = c;
       Integer result = map.get(lookupTest);
       return (result != null) ? result.intValue() : 0;
     }

     @Override
     public int[] map(CharSequence s, int[] mapped) {
       /* Create one mutable Char, and reuse it for all lookups */
       final Char lookupTest = new Char();

       int len = s.length();
       if (mapped.length < len) {
         mapped = new int[len];
       }

       for (int i = 0; i < len; i++) {
         lookupTest.c = s.charAt(i);
         Integer result = map.get(lookupTest);
         mapped[i] = (result != null) ? result.intValue() : NULL_ELEMENT;
       }
       return mapped;
     }

     @Override
     public int nullElement() {
       return NULL_ELEMENT;
     }

     @Override
     public int size() {
       return lastUsed + 1;
     }
   }

   /**
    * An index based on a simple mask: index(c) = (c & MASK).
    * This allows for a very fast index function for many
    * languages outside of the ASCII spectrum.  Most languages
    * fit in a single 8-bit Unicode slice.  Even languages
    * that cross slices for special characters (such as extended
    * Latin) often have no collisions under simple masking.
    */
   public static class Masked extends CharIndex {
     /**
      * Hash table size.
      */
     static final int SIZE = 0x100;

     /**
      * Mask used for hashing.
      */
     static final int MASK = (SIZE - 1);

     /**
      * Where we may invalid characters: beyond the hash table.
      */
     static final int NULL_ELEMENT = SIZE;

     /**
      * Generates an instance of this implementation if possible.
      * @param s pattern string
      * @return an instance of this CharIndex if the pattern satisfies
      *         the constraints for this implementation; otherwise, null
      */
     static Masked generate(CharSequence s) {
       /*
        * This implementation requires that there be no hash collisions
        * among the pattern characters, using a simple mask-based hash.
        */
       char [] contains = new char[SIZE];

       /* Ensure that for all x, hash(contains[x]) != x initially. */
       contains[0] = (char) 1;

       /* Hash characters, recording values seen, rejecting collisions */
       for (int i = 0; i < s.length(); i++) {
         char c = s.charAt(i);
         int index = c & MASK;
         if (contains[index] != c) {
           if ((contains[index] & MASK) == index) {
             return null;
           }
           contains[index] = c;
         }
       }
       return new Masked(contains);
     }

     /**
      * Closed hash table: characters actually indexed.
      * Unused cells contain values inappropriate to their index.
      */
     final char[] contains;

     /**
      * Constructor based on hash table built by generate().
      */
     private Masked(char [] contains) {
       this.contains = contains;
     }

     @Override
     public int lookup(char c) {
       int index = c & MASK;
       return (c == contains[index]) ? index : NULL_ELEMENT;
     }

     @Override
     public int[] map(CharSequence s, int[] mapped) {
       int len = s.length();
       if (mapped.length < len) {
         mapped = new int[len];
       }
       for (int i = 0; i < len; i++) {
         char c = s.charAt(i);
         int index = c & MASK;
         mapped[i] = (c == contains[index]) ? index : NULL_ELEMENT;
       }
       return mapped;
     }

     @Override
     public int nullElement() { return NULL_ELEMENT; }

     @Override
     public int size() { return NULL_ELEMENT + 1; }
   }

   /**
    * An index based on the identity mapping: index(c) = c.
    * This requires minimal computation and no additional space
    * for the basic ASCII character set.
    */
   public static class Straight extends CharIndex {
     /**
      * The largest character we will map (directly).
      */
     static final int MAX = 0x80;

     /**
      * A mask used to find characters that fall outside.
      */
     static final int MASK = ~(MAX - 1);

     /**
      * A map result we never generate for valid characters.
      */
     static final int NULL_ELEMENT = MAX;

     /**
      * Generates an instance of this implementation if possible.
      * @param s pattern string
      * @return an instance of this CharIndex if the pattern satisfies
      *         the constraints for this implementation; otherwise, null
      */
     static Straight generate(CharSequence s) {
       /* This implementation requires that all characters fall below MAX */
       for (int i = 0; i < s.length(); i++) {
         if ((s.charAt(i) & MASK) != 0) {
           return null;
         }
       }

       return new Straight();
     }

     /**
      * Simple private constructor, no state required.
      */
     private Straight() { }

     @Override
     public int lookup(char c) {
       return ((c & MASK) == 0) ? c : NULL_ELEMENT;
     }

     @Override
     public int[] map(CharSequence s, int[] mapped) {
       int len = s.length();
       if (mapped.length < len) {
         mapped = new int[len];
       }
       for (int i = 0; i < len; i++) {
         char c = s.charAt(i);
         mapped[i] = ((c & MASK) == 0) ? c : NULL_ELEMENT;
       }
       return mapped;
     }

     @Override
     public int nullElement() {
       return NULL_ELEMENT;
     }

     @Override
     public int size() {
       return NULL_ELEMENT + 1;
     }
   }

   /**
    * Generates an index for a given alphabet, defined by a character sequence.
    * An appropriate implementation is chosen for the alphabet.  The
    * character sequence is allowed to contain multiple instances of
    * the same character.
    *
    * @param s the alphabet to be indexed
    * @return an index appropriate to this alphabet
    */
   public static CharIndex getInstance(CharSequence s) {
     CharIndex result;

     /* Try fastest mappings first, then more general ones */

     if ((result = Straight.generate(s)) != null) {
       return result;
     }

     if ((result = Masked.generate(s)) != null) {
       return result;
     }

     /* Full hash always works */
     return new FullHash(s);
   }

   /**
    * Returns the index (mapping result) for a given character.
    * If the character is present in the alphabet, then a unique index
    * is returned; other characters may be mapped to unique
    * values, *or* may be mapped to a shared <tt>nullElement</tt> value.
    * @param c character for which an index is sought
    * @return an integer index for the character
    */
   public abstract int lookup(char c);

   /**
    * Performs lookups on an entire sequence of characters.
    * This allows an entire string to be mapped with fewer
    * method invocations, and possibly with some added internal
    * efficiencies.
    *
    * @param s character sequence to be indexed
    * @param mapped array for storing results
    * @return an array of indices for the character sequence,
    *  either the <tt>mapped</tt> parameter or a larger newly-allocated
    *  array if required
    */
   public abstract int[] map(CharSequence s, int[] mapped);

   /**
    * Returns an index that is not used for any character in
    * the alphabet.  This index *may* be returned for characters
    * not in the alphabet.
    * @return an index not used for a valid character
    */
   public abstract int nullElement();

   /**
    * Returns the maximum index result that can be returned by
    * the <tt>lookup</tt> function (including the <tt>nullElement</tt> result
    * if applicable).  No negative values are ever returned
    * from <tt>lookup</tt>.
    * @return maximum index returned from any <tt>lookup</tt>
    */
   public abstract int size();
 }
	/*
	* Copyright 2010 Google Inc.
	*
	* Licensed under the Apache License, Version 2.0 (the "License"); you may not
	* use this file except in compliance with the License. You may obtain a copy of
	* the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
	* WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
	* License for the specific language governing permissions and limitations under
	* the License.
	*/
	package com.google.gwt.dev.util.editdistance;

	/**
	* A performance-oriented character-indexed map.
	* Provides a mapping from characters in a limited alphabet
	* (defined by a CharSequence) to integer values (for array indexing).
	* Emphasis is on performance (e.g., compared to using a generic HashMap),
	* in terms of speed of (post-construction) lookup and space required.
	*
	* Maps are constructed using a static <tt>getInstance</tt> method that
	* chooses an efficient implementation for a given string.
	* The map interface consists of:
	* a <tt>size</tt> method for determining the maximum range of indices used;
	* a <tt>lookup</tt> method for translating a character to its index; and,
	* a <tt>nullElement</tt> method that returns the index that is not
	* returned by <tt>lookup</tt> for any characer actually in the map.
	*
	* The target application is the mapping of natural-language strings.
	* Most strings include characters from a single language, and thus
	* fall into a small slice of the Unicode space. In particular,
	* many strings fall into just the Latin series.
	*/
	public abstract class CharIndex {
	/**
	* An index based on a garden-variety hash map.
	* This is the implementation of last recourse (from a
	* performance perspective).
	*
	* TODO(mwyoung): there may be value in an implementation
	* that falls in between the masked and fullhash variants;
	* for example, one using a closed hash table with rehashing.
	*/
	public static class FullHash extends CharIndex {
	/**
	* Mutable holder for a character.
	*/
	static class Char {
	char c;
	@Override
	public boolean equals(Object x) {
	return (x != null) && (((Char) x).c == this.c);
	}
	@Override
	public int hashCode() {
	return c;
	}
	@Override
	public String toString() {
	return "'" + c + "'";
	}
	}

	static final int NULL_ELEMENT = 0;
	protected int lastUsed = NULL_ELEMENT;
	/**
	* Mapping from pattern characters to their integer index values.
	*/
	final java.util.HashMap<Char,Integer> map;

	/**
	* Constructs a full hash-based mapping.
	*/
	FullHash(CharSequence s) {
	/* Choose a hash size larger at least twice the string length */
	int len = s.length();
	int power = Integer.highestOneBit(len);

	/* Create the map */
	map = new java.util.HashMap<Char,Integer>(
	power << ((power == len) ? 1 : 2));

	/*
	* Add characters one at a time to the map
	*/

	Char test = new Char(); /* (re)used for lookup */
	for (int i = 0; i < s.length(); i++) {
	test.c = s.charAt(i);
	if (map.get(test) == null) {
	/* Not there... add it */
	map.put(test, new Integer(++lastUsed));

	/* Grow a new holder for subsequent lookups */
	test = new Char();
	}
	}
	}

	@Override
	public int lookup(char c) {
	final Char lookupTest = new Char();
	lookupTest.c = c;
	Integer result = map.get(lookupTest);
	return (result != null) ? result.intValue() : 0;
	}

	@Override
	public int[] map(CharSequence s, int[] mapped) {
	/* Create one mutable Char, and reuse it for all lookups */
	final Char lookupTest = new Char();

	int len = s.length();
	if (mapped.length < len) {
	mapped = new int[len];
	}

	for (int i = 0; i < len; i++) {
	lookupTest.c = s.charAt(i);
	Integer result = map.get(lookupTest);
	mapped[i] = (result != null) ? result.intValue() : NULL_ELEMENT;
	}
	return mapped;
	}

	@Override
	public int nullElement() {
	return NULL_ELEMENT;
	}

	@Override
	public int size() {
	return lastUsed + 1;
	}
	}

	/**
	* An index based on a simple mask: index(c) = (c & MASK).
	* This allows for a very fast index function for many
	* languages outside of the ASCII spectrum. Most languages
	* fit in a single 8-bit Unicode slice. Even languages
	* that cross slices for special characters (such as extended
	* Latin) often have no collisions under simple masking.
	*/
	public static class Masked extends CharIndex {
	/**
	* Hash table size.
	*/
	static final int SIZE = 0x100;

	/**
	* Mask used for hashing.
	*/
	static final int MASK = (SIZE - 1);

	/**
	* Where we may invalid characters: beyond the hash table.
	*/
	static final int NULL_ELEMENT = SIZE;

	/**
	* Generates an instance of this implementation if possible.
	* @param s pattern string
	* @return an instance of this CharIndex if the pattern satisfies
	* the constraints for this implementation; otherwise, null
	*/
	static Masked generate(CharSequence s) {
	/*
	* This implementation requires that there be no hash collisions
	* among the pattern characters, using a simple mask-based hash.
	*/
	char [] contains = new char[SIZE];

	/* Ensure that for all x, hash(contains[x]) != x initially. */
	contains[0] = (char) 1;

	/* Hash characters, recording values seen, rejecting collisions */
	for (int i = 0; i < s.length(); i++) {
	char c = s.charAt(i);
	int index = c & MASK;
	if (contains[index] != c) {
	if ((contains[index] & MASK) == index) {
	return null;
	}
	contains[index] = c;
	}
	}
	return new Masked(contains);
	}

	/**
	* Closed hash table: characters actually indexed.
	* Unused cells contain values inappropriate to their index.
	*/
	final char[] contains;

	/**
	* Constructor based on hash table built by generate().
	*/
	private Masked(char [] contains) {
	this.contains = contains;
	}

	@Override
	public int lookup(char c) {
	int index = c & MASK;
	return (c == contains[index]) ? index : NULL_ELEMENT;
	}

	@Override
	public int[] map(CharSequence s, int[] mapped) {
	int len = s.length();
	if (mapped.length < len) {
	mapped = new int[len];
	}
	for (int i = 0; i < len; i++) {
	char c = s.charAt(i);
	int index = c & MASK;
	mapped[i] = (c == contains[index]) ? index : NULL_ELEMENT;
	}
	return mapped;
	}

	@Override
	public int nullElement() { return NULL_ELEMENT; }

	@Override
	public int size() { return NULL_ELEMENT + 1; }
	}

	/**
	* An index based on the identity mapping: index(c) = c.
	* This requires minimal computation and no additional space
	* for the basic ASCII character set.
	*/
	public static class Straight extends CharIndex {
	/**
	* The largest character we will map (directly).
	*/
	static final int MAX = 0x80;

	/**
	* A mask used to find characters that fall outside.
	*/
	static final int MASK = ~(MAX - 1);

	/**
	* A map result we never generate for valid characters.
	*/
	static final int NULL_ELEMENT = MAX;

	/**
	* Generates an instance of this implementation if possible.
	* @param s pattern string
	* @return an instance of this CharIndex if the pattern satisfies
	* the constraints for this implementation; otherwise, null
	*/
	static Straight generate(CharSequence s) {
	/* This implementation requires that all characters fall below MAX */
	for (int i = 0; i < s.length(); i++) {
	if ((s.charAt(i) & MASK) != 0) {
	return null;
	}
	}

	return new Straight();
	}

	/**
	* Simple private constructor, no state required.
	*/
	private Straight() { }

	@Override
	public int lookup(char c) {
	return ((c & MASK) == 0) ? c : NULL_ELEMENT;
	}

	@Override
	public int[] map(CharSequence s, int[] mapped) {
	int len = s.length();
	if (mapped.length < len) {
	mapped = new int[len];
	}
	for (int i = 0; i < len; i++) {
	char c = s.charAt(i);
	mapped[i] = ((c & MASK) == 0) ? c : NULL_ELEMENT;
	}
	return mapped;
	}

	@Override
	public int nullElement() {
	return NULL_ELEMENT;
	}

	@Override
	public int size() {
	return NULL_ELEMENT + 1;
	}
	}

	/**
	* Generates an index for a given alphabet, defined by a character sequence.
	* An appropriate implementation is chosen for the alphabet. The
	* character sequence is allowed to contain multiple instances of
	* the same character.
	*
	* @param s the alphabet to be indexed
	* @return an index appropriate to this alphabet
	*/
	public static CharIndex getInstance(CharSequence s) {
	CharIndex result;

	/* Try fastest mappings first, then more general ones */

	if ((result = Straight.generate(s)) != null) {
	return result;
	}

	if ((result = Masked.generate(s)) != null) {
	return result;
	}

	/* Full hash always works */
	return new FullHash(s);
	}

	/**
	* Returns the index (mapping result) for a given character.
	* If the character is present in the alphabet, then a unique index
	* is returned; other characters may be mapped to unique
	* values, or may be mapped to a shared <tt>nullElement</tt> value.
	* @param c character for which an index is sought
	* @return an integer index for the character
	*/
	public abstract int lookup(char c);

	/**
	* Performs lookups on an entire sequence of characters.
	* This allows an entire string to be mapped with fewer
	* method invocations, and possibly with some added internal
	* efficiencies.
	*
	* @param s character sequence to be indexed
	* @param mapped array for storing results
	* @return an array of indices for the character sequence,
	* either the <tt>mapped</tt> parameter or a larger newly-allocated
	* array if required
	*/
	public abstract int[] map(CharSequence s, int[] mapped);

	/**
	* Returns an index that is not used for any character in
	* the alphabet. This index may be returned for characters
	* not in the alphabet.
	* @return an index not used for a valid character
	*/
	public abstract int nullElement();

	/**
	* Returns the maximum index result that can be returned by
	* the <tt>lookup</tt> function (including the <tt>nullElement</tt> result
	* if applicable). No negative values are ever returned
	* from <tt>lookup</tt>.
	* @return maximum index returned from any <tt>lookup</tt>
	*/
	public abstract int size();
	}