<commit_before>package org.smoothbuild.fs.match;

import static com.google.common.base.Preconditions.checkArgument;
import static org.smoothbuild.fs.match.Constants.SINGLE_STAR;

import org.smoothbuild.fs.base.Path;

import com.google.common.base.Predicate;
import com.google.common.collect.ImmutableList;

/**
 * Matches file/directory name against given pattern.
 * 
 * <pre>
 * Each star '*' in pattern matches zero or more characters.
 * Double stars "**" are forbidden.
 * </pre>
 */
public class NameMatcher implements Predicate<Path> {
  private final ImmutableList<String> patternParts;

  public NameMatcher(NamePattern pattern) {
    checkArgument(!pattern.isDoubleStar());
    this.patternParts = pattern.parts();
  }

  @Override
  public boolean apply(Path path) {
    String string = path.value();
    // TODO use 'array = string.toCharArray();' to improve speed

    // matching leftmost characters to first '*'

    int pLeft = 0;
    int sLeft = 0;

    while (pLeft < patternParts.size()) {
      String part = patternParts.get(pLeft);
      if (part.equals(SINGLE_STAR)) {
        break;
      } else if (string.substring(sLeft).startsWith(part)) {
        sLeft += part.length();
        pLeft++;
      } else {
        return false;
      }
    }

    if (pLeft == patternParts.size()) {
      return sLeft == string.length();
    }

    // matching rightmost characters to last '*'

    int pRight = patternParts.size() - 1;
    int sRight = string.length();

    while (pLeft < pRight) {
      String part = patternParts.get(pRight);
      if (part.equals(SINGLE_STAR)) {
        break;
      } else if (string.substring(0, sRight).endsWith(part)) {
        sRight -= part.length();
        pRight--;
      } else {
        return false;
      }
    }

    /*
     * At this point pLeft and pRight points to parts that contain SINGLE_STAR.
     * If they both point to the same part then we've matched the whole pattern
     * - matching is successful if sRight and sLeft haven't overlapped. All
     * these cases are checked inside 'while' clause below.
     */

    int stillToMatch = minimumCharactersNeeded(pLeft + 1, pRight - 1);
    int stillAvailable = sRight - sLeft;

    while (true) {
      if (stillAvailable < stillToMatch) {
        return false;
      }
      if (pLeft == pRight) {
        return true;
      }
      pLeft++;
      String part = patternParts.get(pLeft);
      int steps = stillAvailable - part.length() + 1;

      // TODO use Boyer-Moore algorithm instead
      // http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm
      boolean found = false;
      for (int i = 0; i < steps; i++) {
        if (string.substring(sLeft + i).startsWith(part)) {
          pLeft++;
          sLeft += part.length() + i;
          found = true;
          break;
        }
      }
      if (!found) {
        return false;
      }
    }
  }

  private int minimumCharactersNeeded(int pLeft, int pRight) {
    int result = 0;
    for (int i = pLeft; i <= pRight; i++) {
      String part = patternParts.get(i);<commit_msg>removed speed TODOs from NameMatcher - no need to implement them until performance bottlenecks are measured<commit_after>package org.smoothbuild.fs.match;

import static com.google.common.base.Preconditions.checkArgument;
import static org.smoothbuild.fs.match.Constants.SINGLE_STAR;

import org.smoothbuild.fs.base.Path;

import com.google.common.base.Predicate;
import com.google.common.collect.ImmutableList;

/**
 * Matches file/directory name against given pattern.
 * 
 * <pre>
 * Each star '*' in pattern matches zero or more characters.
 * Double stars "**" are forbidden.
 * </pre>
 */
public class NameMatcher implements Predicate<Path> {
  private final ImmutableList<String> patternParts;

  public NameMatcher(NamePattern pattern) {
    checkArgument(!pattern.isDoubleStar());
    this.patternParts = pattern.parts();
  }

  @Override
  public boolean apply(Path path) {
    String string = path.value();

    // matching leftmost characters to first '*'

    int pLeft = 0;
    int sLeft = 0;

    while (pLeft < patternParts.size()) {
      String part = patternParts.get(pLeft);
      if (part.equals(SINGLE_STAR)) {
        break;
      } else if (string.substring(sLeft).startsWith(part)) {
        sLeft += part.length();
        pLeft++;
      } else {
        return false;
      }
    }

    if (pLeft == patternParts.size()) {
      return sLeft == string.length();
    }

    // matching rightmost characters to last '*'

    int pRight = patternParts.size() - 1;
    int sRight = string.length();

    while (pLeft < pRight) {
      String part = patternParts.get(pRight);
      if (part.equals(SINGLE_STAR)) {
        break;
      } else if (string.substring(0, sRight).endsWith(part)) {
        sRight -= part.length();
        pRight--;
      } else {
        return false;
      }
    }

    /*
     * At this point pLeft and pRight points to parts that contain SINGLE_STAR.
     * If they both point to the same part then we've matched the whole pattern
     * - matching is successful if sRight and sLeft haven't overlapped. All
     * these cases are checked inside 'while' clause below.
     */

    int stillToMatch = minimumCharactersNeeded(pLeft + 1, pRight - 1);
    int stillAvailable = sRight - sLeft;

    while (true) {
      if (stillAvailable < stillToMatch) {
        return false;
      }
      if (pLeft == pRight) {
        return true;
      }
      pLeft++;
      String part = patternParts.get(pLeft);
      int steps = stillAvailable - part.length() + 1;

      boolean found = false;
      for (int i = 0; i < steps; i++) {
        if (string.substring(sLeft + i).startsWith(part)) {
          pLeft++;
          sLeft += part.length() + i;
          found = true;
          break;
        }
      }
      if (!found) {
        return false;
      }
    }
  }

  private int minimumCharactersNeeded(int pLeft, int pRight) {
    int result = 0;
    for (int i = pLeft; i <= pRight; i++) {
      String part = patternParts.get(i);
{'fraction_non_alphanumeric': 0.11598746081504702, 'fraction_numerical': 0.0037947533410328327, 'mean_word_length': 2.432616081540204, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '524044', 'n_tokens_mistral': 1857, 'n_tokens_neox': 1789, 'n_words': 510}