/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at legal-notices/CDDLv1_0.txt
 * or http://forgerock.org/license/CDDLv1.0.html.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at legal-notices/CDDLv1_0.txt.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information:
 *      Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 *
 *
 *      Copyright 2006-2009 Sun Microsystems, Inc.
 *      Portions Copyright 2014 ForgeRock AS
 */
package org.opends.server.api;

import java.util.Collection;
import java.util.LinkedList;
import java.util.List;
import java.util.TreeSet;

import org.forgerock.opendj.ldap.Assertion;
import org.forgerock.opendj.ldap.ByteSequence;
import org.forgerock.opendj.ldap.ByteString;
import org.forgerock.opendj.ldap.ByteStringBuilder;
import org.forgerock.opendj.ldap.ConditionResult;
import org.forgerock.opendj.ldap.DecodeException;
import org.forgerock.opendj.ldap.spi.IndexQueryFactory;

/**
 * This class defines the set of methods and structures that must be
 * implemented by a Directory Server module that implements a matching
 * rule used for substring matching.
 */
@org.opends.server.types.PublicAPI(
     stability=org.opends.server.types.StabilityLevel.VOLATILE,
     mayInstantiate=false,
     mayExtend=true,
     mayInvoke=false)
public abstract class SubstringMatchingRule
        extends AbstractMatchingRule
        implements MatchingRule
{
  /**
   * Normalizes the provided value fragment into a form that can be
   * used to efficiently compare values.
   *
   * @param  substring  The value fragment to be normalized.
   *
   * @return  The normalized form of the value fragment.
   *
   * @throws  DecodeException  If the provided value fragment is
   *                              not acceptable according to the
   *                              associated syntax.
   */
  public abstract ByteString normalizeSubstring(
      ByteSequence substring) throws DecodeException;



  /**
   * Determines whether the provided value matches the given substring
   * filter components.  Note that any of the substring filter
   * components may be {@code null} but at least one of them must be
   * non-{@code null}.
   *
   * @param  value           The normalized value against which to
   *                         compare the substring components.
   * @param  subInitial      The normalized substring value fragment
   *                         that should appear at the beginning of
   *                         the target value.
   * @param  subAnyElements  The normalized substring value fragments
   *                         that should appear in the middle of the
   *                         target value.
   * @param  subFinal        The normalized substring value fragment
   *                         that should appear at the end of the
   *                         target value.
   *
   * @return  {@code true} if the provided value does match the given
   *          substring components, or {@code false} if not.
   */
  public boolean valueMatchesSubstring(ByteSequence value,
                                    ByteSequence subInitial,
                                    List<ByteSequence> subAnyElements,
                                    ByteSequence subFinal)
  {
    int valueLength = value.length();

    int pos = 0;
    if (subInitial != null)
    {
      int initialLength = subInitial.length();
      if (initialLength > valueLength)
      {
        return false;
      }

      for (; pos < initialLength; pos++)
      {
        if (subInitial.byteAt(pos) != value.byteAt(pos))
        {
          return false;
        }
      }
    }


    if ((subAnyElements != null) && (! subAnyElements.isEmpty()))
    {
      for (ByteSequence element : subAnyElements)
      {
        int anyLength = element.length();
        if(anyLength == 0)
            continue;
        int end = valueLength - anyLength;
        boolean match = false;
        for (; pos <= end; pos++)
        {
          if (element.byteAt(0) == value.byteAt(pos))
          {
            boolean subMatch = true;
            for (int i=1; i < anyLength; i++)
            {
              if (element.byteAt(i) != value.byteAt(pos+i))
              {
                subMatch = false;
                break;
              }
            }

            if (subMatch)
            {
              match = subMatch;
              break;
            }
          }
        }

        if (match)
        {
          pos += anyLength;
        }
        else
        {
          return false;
        }
      }
    }


    if (subFinal != null)
    {
      int finalLength = subFinal.length();

      if ((valueLength - finalLength) < pos)
      {
        return false;
      }

      pos = valueLength - finalLength;
      for (int i=0; i < finalLength; i++,pos++)
      {
        if (subFinal.byteAt(i) != value.byteAt(pos))
        {
          return false;
        }
      }
    }


    return true;
  }

  /**
   * Default assertion implementation for substring matching rules.
   * For example, with the assertion value "initial*any1*any2*any3*final",
   * the assertion will be decomposed like this:
   * <ul>
   * <li>normInitial will contain "initial"</li>
   * <li>normAnys will contain [ "any1", "any2", "any3" ]</li>
   * <li>normFinal will contain "final"</li>
   * </ul>
   */
  static final class DefaultSubstringAssertion implements Assertion {
      /** Normalized substring for the text before the first '*' character. */
      private final ByteString normInitial;
      /** Normalized substrings for all text chunks in between '*' characters. */
      private final ByteString[] normAnys;
      /** Normalized substring for the text after the last '*' character. */
      private final ByteString normFinal;

      private DefaultSubstringAssertion(final ByteString normInitial,
              final ByteString[] normAnys, final ByteString normFinal) {
          this.normInitial = normInitial;
          this.normAnys = normAnys;
          this.normFinal = normFinal;
      }

      /** {@inheritDoc} */
      @Override
      public ConditionResult matches(final ByteSequence normalizedAttributeValue) {
          final int valueLength = normalizedAttributeValue.length();

          int pos = 0;
          if (normInitial != null) {
              final int initialLength = normInitial.length();
              if (initialLength > valueLength) {
                  return ConditionResult.FALSE;
              }

              for (; pos < initialLength; pos++) {
                  if (normInitial.byteAt(pos) != normalizedAttributeValue.byteAt(pos)) {
                      return ConditionResult.FALSE;
                  }
              }
          }

          if (normAnys != null) {
          matchEachSubstring:
              for (final ByteSequence element : normAnys) {
                  final int anyLength = element.length();
                  final int end = valueLength - anyLength;
              matchCurrentSubstring:
                  for (; pos <= end; pos++) {
                      // Try to match all characters from the substring
                      for (int i = 0; i < anyLength; i++) {
                          if (element.byteAt(i) != normalizedAttributeValue.byteAt(pos + i)) {
                              // not a match,
                              // try to find a match in the rest of this value
                              continue matchCurrentSubstring;
                          }
                      }
                      // we just matched current substring,
                      // go try to match the next substring
                      pos += anyLength;
                      continue matchEachSubstring;
                  }
                  // Could not match current substring
                  return ConditionResult.FALSE;
              }
          }

          if (normFinal != null) {
              final int finalLength = normFinal.length();

              if (valueLength - finalLength < pos) {
                  return ConditionResult.FALSE;
              }

              pos = valueLength - finalLength;
              for (int i = 0; i < finalLength; i++, pos++) {
                  if (normFinal.byteAt(i) != normalizedAttributeValue.byteAt(pos)) {
                      return ConditionResult.FALSE;
                  }
              }
          }

          return ConditionResult.TRUE;
      }

      /** {@inheritDoc} */
      @Override
      public <T> T createIndexQuery(IndexQueryFactory<T> factory) throws DecodeException {
          final Collection<T> subqueries = new LinkedList<T>();
          if (normInitial != null) {
              // relies on the fact that equality indexes are also ordered
              subqueries.add(rangeMatch(factory, "equality", normInitial));
          }
          if (normAnys != null) {
              for (ByteString normAny : normAnys) {
                  substringMatch(factory, normAny, subqueries);
              }
          }
          if (normFinal != null) {
              substringMatch(factory, normFinal, subqueries);
          }
          if (normInitial != null) {
              // Add this one last to minimize the risk to run the same search twice
              // (possible overlapping with the use of equality index at the start of this method)
              substringMatch(factory, normInitial, subqueries);
          }
          return factory.createIntersectionQuery(subqueries);
      }

      private <T> T rangeMatch(IndexQueryFactory<T> factory, String indexID, ByteSequence lower) {
          // Iterate through all the keys that have this value as the prefix.

          // Set the upper bound for a range search.
          // We need a key for the upper bound that is of equal length
          // but slightly greater than the lower bound.
          final ByteStringBuilder upper = new ByteStringBuilder(lower);

          for (int i = upper.length() - 1; i >= 0; i--) {
              if (upper.byteAt(i) == (byte) 0xFF) {
                  // We have to carry the overflow to the more significant byte.
                  upper.setByte(i, (byte) 0);
              } else {
                  // No overflow, we can stop.
                  upper.setByte(i, (byte) (upper.byteAt(i) + 1));
                  break;
              }
          }

          // Read the range: lower <= keys < upper.
          return factory.createRangeMatchQuery(indexID, lower, upper, true, false);
      }

      private <T> void substringMatch(final IndexQueryFactory<T> factory, final ByteString normSubstring,
              final Collection<T> subqueries) {
          int substrLength = factory.getIndexingOptions().substringKeySize();

          // There are two cases, depending on whether the user-provided
          // substring is smaller than the configured index substring length or not.
          if (normSubstring.length() < substrLength) {
              subqueries.add(rangeMatch(factory, "substring", normSubstring));
          } else {
              // Break the value up into fragments of length equal to the
              // index substring length, and read those keys.

              // Eliminate duplicates by putting the keys into a set.
              final TreeSet<ByteSequence> substringKeys = new TreeSet<ByteSequence>();

              // Example: The value is ABCDE and the substring length is 3.
              // We produce the keys ABC BCD CDE.
              for (int first = 0, last = substrLength;
                   last <= normSubstring.length(); first++, last++) {
                  substringKeys.add(normSubstring.subSequence(first, first + substrLength));
              }

              for (ByteSequence key : substringKeys) {
                  subqueries.add(factory.createExactMatchQuery("substring", key));
              }
          }
      }

  }

  /** {@inheritDoc} */
  @Override
  public Assertion getSubstringAssertion(ByteSequence subInitial,
      List<? extends ByteSequence> subAnyElements, ByteSequence subFinal)
      throws DecodeException
  {
    final ByteString normInitial = subInitial == null ? null : normalizeSubstring(subInitial);

    ByteString[] normAnys = null;
    if (subAnyElements != null && !subAnyElements.isEmpty())
    {
      normAnys = new ByteString[subAnyElements.size()];
      for (int i = 0; i < subAnyElements.size(); i++)
      {
        normAnys[i] = normalizeSubstring(subAnyElements.get(i));
      }
    }
    final ByteString normFinal = subFinal == null ? null : normalizeSubstring(subFinal);

    return new DefaultSubstringAssertion(normInitial, normAnys, normFinal);
  }

}