/*
    * Copyright (C) 2012 The Guava Authors
    *
    * 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.common.base;
  
  import com.google.common.annotations.GwtIncompatible;
  import com.google.common.annotations.VisibleForTesting;
  import com.google.common.base.CharMatcher.FastMatcher;
  
  import java.util.BitSet;
  
  /**
   * An immutable version of CharMatcher for smallish sets of characters that uses a hash table
   * with linear probing to check for matches.
   *
   * @author Christopher Swenson
   */
  @GwtIncompatible("no precomputation is done in GWT")
  final class SmallCharMatcher extends FastMatcher {
    static final int MAX_SIZE = 1023;
    private final char[] table;
    private final boolean containsZero;
    private final long filter;
  
    private SmallCharMatcher(char[] table, long filter, boolean containsZero,
        String description) {
      super(description);
      this.table = table;
      this.filter = filter;
      this.containsZero = containsZero;
    }
    
    private static final int C1 = 0xcc9e2d51;
    private static final int C2 = 0x1b873593;
  
    /*
     * This method was rewritten in Java from an intermediate step of the Murmur hash function in
     * http://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp, which contained the
     * following header:
     *
     * MurmurHash3 was written by Austin Appleby, and is placed in the public domain. The author
     * hereby disclaims copyright to this source code.
     */
    static int smear(int hashCode) {
      return C2 * Integer.rotateLeft(hashCode * C1, 15);
    }
  
    private boolean checkFilter(int c) {
      return 1 == (1 & (filter >> c));
    }
  
    // This is all essentially copied from ImmutableSet, but we have to duplicate because
    // of dependencies.
  
    // Represents how tightly we can pack things, as a maximum.
    private static final double DESIRED_LOAD_FACTOR = 0.5;
  
   /**
    * Returns an array size suitable for the backing array of a hash table that
    * uses open addressing with linear probing in its implementation.  The
    * returned size is the smallest power of two that can hold setSize elements
    * with the desired load factor.
    */
    @VisibleForTesting static int chooseTableSize(int setSize) {
      if (setSize == 1) {
        return 2;
      }
      // Correct the size for open addressing to match desired load factor.
      // Round up to the next highest power of 2.
      int tableSize = Integer.highestOneBit(setSize - 1) << 1;
      while (tableSize * DESIRED_LOAD_FACTOR < setSize) {
        tableSize <<= 1;
      }
      return tableSize;
    }
  
    static CharMatcher from(BitSet chars, String description) {
      // Compute the filter.
      long filter = 0;
      int size = chars.cardinality();
      boolean containsZero = chars.get(0);
      // Compute the hash table.
      char[] table = new char[chooseTableSize(size)];
      int mask = table.length - 1;
      for (int c = chars.nextSetBit(0); c != -1; c = chars.nextSetBit(c + 1)) {
        // Compute the filter at the same time.
       filter |= 1L << c;
       int index = smear(c) & mask;
       while (true) {
         // Check for empty.
         if (table[index] == 0) {
           table[index] = (char) c;
           break;
         }
         // Linear probing.
         index = (index + 1) & mask;
       }
     }
     return new SmallCharMatcher(table, filter, containsZero, description);
   }
 
   @Override
   public boolean matches(char c) {
     if (c == 0) {
       return containsZero;
     }
     if (!checkFilter(c)) {
       return false;
     }
     int mask = table.length - 1;
     int startingIndex = smear(c) & mask;
     int index = startingIndex;
     do {
       // Check for empty.
       if (table[index] == 0) {
         return false;
       // Check for match.
       } else if (table[index] == c) {
         return true;
       } else {
         // Linear probing.
         index = (index + 1) & mask;
       }
       // Check to see if we wrapped around the whole table.
     } while (index != startingIndex);
     return false;
   }
 
   @Override
   void setBits(BitSet table) {
     if (containsZero) {
       table.set(0);
     }
     for (char c : this.table) {
       if (c != 0) {
         table.set(c);
       }
     }
   }
 }