StringKeyAnalyzer.java

  1. /*
  2.  * Licensed to the Apache Software Foundation (ASF) under one or more
  3.  * contributor license agreements.  See the NOTICE file distributed with
  4.  * this work for additional information regarding copyright ownership.
  5.  * The ASF licenses this file to You under the Apache License, Version 2.0
  6.  * (the "License"); you may not use this file except in compliance with
  7.  * the License.  You may obtain a copy of the License at
  8.  *
  9.  *      http://www.apache.org/licenses/LICENSE-2.0
  10.  *
  11.  * Unless required by applicable law or agreed to in writing, software
  12.  * distributed under the License is distributed on an "AS IS" BASIS,
  13.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14.  * See the License for the specific language governing permissions and
  15.  * limitations under the License.
  16.  */
  17. package org.apache.commons.collections4.trie.analyzer;

  18. import org.apache.commons.collections4.trie.KeyAnalyzer;

  19. /**
  20.  * An {@link KeyAnalyzer} for {@link String}s.
  21.  * <p>
  22.  * This class is stateless.
  23.  * </p>
  24.  * @since 4.0
  25.  */
  26. public class StringKeyAnalyzer extends KeyAnalyzer<String> {

  27.     private static final long serialVersionUID = -7032449491269434877L;

  28.     /** A singleton instance of {@link StringKeyAnalyzer}. */
  29.     public static final StringKeyAnalyzer INSTANCE = new StringKeyAnalyzer();

  30.     /** The number of bits per {@link Character}. */
  31.     public static final int LENGTH = Character.SIZE;

  32.     /** A bit mask where the first bit is 1 and the others are zero. */
  33.     private static final int MSB = 0x8000;

  34.     /** Returns a bit mask where the given bit is set. */
  35.     private static int mask(final int bit) {
  36.         return MSB >>> bit;
  37.     }

  38.     /**
  39.      * Constructs a new instance.
  40.      *
  41.      * @deprecated Use {@link #INSTANCE}.
  42.      */
  43.     @Deprecated
  44.     public StringKeyAnalyzer() {
  45.         // empty
  46.     }

  47.     @Override
  48.     public int bitIndex(final String key, final int offsetInBits, final int lengthInBits,
  49.                         final String other, final int otherOffsetInBits, final int otherLengthInBits) {

  50.         boolean allNull = true;

  51.         if (offsetInBits % LENGTH != 0 || otherOffsetInBits % LENGTH != 0
  52.                 || lengthInBits % LENGTH != 0 || otherLengthInBits % LENGTH != 0) {
  53.             throw new IllegalArgumentException("The offsets and lengths must be at Character boundaries");
  54.         }

  55.         final int beginIndex1 = offsetInBits / LENGTH;
  56.         final int beginIndex2 = otherOffsetInBits / LENGTH;

  57.         final int endIndex1 = beginIndex1 + lengthInBits / LENGTH;
  58.         final int endIndex2 = beginIndex2 + otherLengthInBits / LENGTH;

  59.         final int length = Math.max(endIndex1, endIndex2);

  60.         // Look at each character, and if they're different
  61.         // then figure out which bit makes the difference
  62.         // and return it.
  63.         char k = 0;
  64.         char f = 0;
  65.         for (int i = 0; i < length; i++) {
  66.             final int index1 = beginIndex1 + i;
  67.             final int index2 = beginIndex2 + i;

  68.             if (index1 >= endIndex1) {
  69.                 k = 0;
  70.             } else {
  71.                 k = key.charAt(index1);
  72.             }

  73.             if (other == null || index2 >= endIndex2) {
  74.                 f = 0;
  75.             } else {
  76.                 f = other.charAt(index2);
  77.             }

  78.             if (k != f) {
  79.                 final int x = k ^ f;
  80.                 return i * LENGTH + Integer.numberOfLeadingZeros(x) - LENGTH;
  81.             }

  82.             if (k != 0) {
  83.                 allNull = false;
  84.             }
  85.         }

  86.         // All bits are 0
  87.         if (allNull) {
  88.             return NULL_BIT_KEY;
  89.         }

  90.         // Both keys are equal
  91.         return EQUAL_BIT_KEY;
  92.     }

  93.     @Override
  94.     public int bitsPerElement() {
  95.         return LENGTH;
  96.     }

  97.     @Override
  98.     public boolean isBitSet(final String key, final int bitIndex, final int lengthInBits) {
  99.         if (key == null || bitIndex >= lengthInBits) {
  100.             return false;
  101.         }

  102.         final int index = bitIndex / LENGTH;
  103.         final int bit = bitIndex % LENGTH;

  104.         return (key.charAt(index) & mask(bit)) != 0;
  105.     }

  106.     @Override
  107.     public boolean isPrefix(final String prefix, final int offsetInBits,
  108.                             final int lengthInBits, final String key) {
  109.         if (offsetInBits % LENGTH != 0 || lengthInBits % LENGTH != 0) {
  110.             throw new IllegalArgumentException(
  111.                     "Cannot determine prefix outside of Character boundaries");
  112.         }

  113.         final String s1 = prefix.substring(offsetInBits / LENGTH, lengthInBits / LENGTH);
  114.         return key.startsWith(s1);
  115.     }

  116.     @Override
  117.     public int lengthInBits(final String key) {
  118.         return key != null ? key.length() * LENGTH : 0;
  119.     }
  120. }