import java.util.Map;
import java.util.HashMap;
import java.util.Set;
import java.util.HashSet;
import java.util.ArrayList;
import java.util.regex.Pattern;
import java.util.regex.Matcher;

class Main {
  private final String input;
  private final String expected;
  private final String[] search = new String[] { "foo", "bar", };
  private final String[] replace = new String[] { "bar", "foo" };

  private Main() {
    StringBuilder sb = new StringBuilder();
    StringBuilder expectedSb = new StringBuilder();
    for (int i = 0; i < 320000; i++) {
              sb.append("ffffffffffoo baz quux bar");
      expectedSb.append("fffffffffbar baz quux foo");
    }
    this.input = sb.toString();
    this.expected = expectedSb.toString();
    System.out.printf("Input size: %d chars%n", this.input.length());
  }

  public static void main(String[] args) {
  	Solution[] solutions = new Solution[] {
  	  new RecursiveSolution(),
  	  new JanosSolution(),
  	  new ArshajiiSolution(),
  	  new BoannSolution(),
  	  new JeroenSolution(),
  	  new ApacheSolution()
  	};

    Main main = new Main();
    for (int i = 0; i < 2; i++) {
      for (Solution solution : solutions) {
      	main.timeSolution(solution);
      }
    }
  }

  private void timeSolution(Solution solution) {
    long start = System.nanoTime();
    String actual = solution.replaceAll(input, search, replace);
    long now = System.nanoTime();
    System.out.printf("%20s: %12d. Equals expected: %b%n", solution.getName(), now - start, actual.equals(this.expected));
  }

  private interface Solution {
    String getName();
    String replaceAll(final String input, final String[] search, final String[] replace);
  }

  private static class RecursiveSolution implements Solution {
    public String getName() {
      return "Recursive";
    }

    public String replaceAll(String input, String[] search, String[] replace) {
      StringBuilder sb = new StringBuilder();
      replaceAll(sb, input, 0, input.length(), search, replace, 0);
      return sb.toString();
    }

    private static void replaceAll(StringBuilder sb, String input, int start, int end, String[] search, String[] replace, int i) {
      while (i < search.length && start < end) {
        int j = indexOf(input, search[i], start, end);
        if (j == -1) {
          i++;
        } else {
          replaceAll(sb, input, start, j, search, replace, i + 1);
          sb.append(replace[i]);
          start = j + search[i].length();
        }
      }
      sb.append(input, start, end);
    }

    private static int indexOf(final String source, final String target, final int start, final int end) {
      int len = target.length();
      if (len == 0) {
        return start;
      }
      if (len > source.length()) {
        return -1;
      }
      if (len == source.length()) {
        return source.equals(target) ? 0 : -1;
      }
      int max = end - len;
      char first = target.charAt(0);
      for (int i = start; i <= max; i++) {
        if (source.charAt(i) != first) {
          while (++i <= max && source.charAt(i) != first);
        }
        if (i <= max) {
          int j = i + 1;
          int e = j + len - 1;
          for (int k = 1; j < e && source.charAt(j) == target.charAt(k); j++, k++);
          if (j == e) {
            return i;
          }
        }
      }
      return -1;
    }
  }

  private static class JeroenSolution implements Solution {
    public String getName() {
      return "Jeroen";
    }

    public String replaceAll(String subject, String[] search, String[] replace) {
      subject = subject.replace("foo", "\uE000");
      subject = subject.replace("bar", "foo");
      subject = subject.replace("\uE000", "bar");
      return subject;
    }
  }

  private static class JanosSolution implements Solution {
  	public String getName() {
  	  return "Janos";
  	}
  	
    public String replaceAll(String text, String[] searchList, String[] replacementList) {
      // TODO: throw new IllegalArgumentException() if any param doesn't make sense
      //validateParams(text, searchList, replacementList);

      SearchTracker tracker = new SearchTracker(text, searchList, replacementList);
      if (!tracker.hasNextMatch(0)) {
        return text;
      }

      StringBuilder buf = new StringBuilder(text.length() * 2);
      int start = 0;

      do {
        SearchTracker.MatchInfo matchInfo = tracker.matchInfo;
        int textIndex = matchInfo.textIndex;
        String pattern = matchInfo.pattern;
        String replacement = matchInfo.replacement;

        buf.append(text.substring(start, textIndex));
        buf.append(replacement);

        start = textIndex + pattern.length();
      } while (tracker.hasNextMatch(start));

      return buf.append(text.substring(start)).toString();
    }

    private static class SearchTracker {

      private final String text;

      private final Map<String, String> patternToReplacement = new HashMap<>();
      private final Set<String> pendingPatterns = new HashSet<>();

      private MatchInfo matchInfo = null;

      private static class MatchInfo {
        private final String pattern;
        private final String replacement;
        private final int textIndex;

        private MatchInfo(String pattern, String replacement, int textIndex) {
          this.pattern = pattern;
          this.replacement = replacement;
          this.textIndex = textIndex;
        }
      }

      private SearchTracker(String text, String[] searchList, String[] replacementList) {
        this.text = text;
        for (int i = 0; i < searchList.length; ++i) {
          String pattern = searchList[i];
          patternToReplacement.put(pattern, replacementList[i]);
          pendingPatterns.add(pattern);
        }
      }

      boolean hasNextMatch(int start) {
        int textIndex = -1;
        String nextPattern = null;

        for (String pattern : new ArrayList<>(pendingPatterns)) {
          int matchIndex = text.indexOf(pattern, start);
          if (matchIndex == -1) {
            pendingPatterns.remove(pattern);
          } else {
            if (textIndex == -1 || matchIndex < textIndex) {
              textIndex = matchIndex;
              nextPattern = pattern;
            }
          }
        }

        if (nextPattern != null) {
          matchInfo = new MatchInfo(nextPattern, patternToReplacement.get(nextPattern), textIndex);
          return true;
        }
        return false;
      }
    }
  }

  private static class ArshajiiSolution implements Solution {
  	public String getName() {
  	  return "arshajii";
  	}
  	
  	public String replaceAll(String input, String[] search, String[] replace) {
  	  Pattern p = Pattern.compile("foo|bar");
      Matcher m = p.matcher(input);
      StringBuffer sb = new StringBuffer();
      while (m.find()) {
        /* do the swap... */
        switch (m.group()) {
        case "foo":
          m.appendReplacement(sb, "bar");
          break;
        case "bar":
          m.appendReplacement(sb, "foo");
          break;
        default:
        /* error */
          break;
      }
    }
    m.appendTail(sb);
    return sb.toString();
  }
}
  
/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You 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://w...content-available-to-author-only...e.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.
 */
 // From http://s...content-available-to-author-only...e.org/viewvc/commons/proper/lang/trunk/src/main/java/org/apache/commons/lang3/StringUtils.java?view=co
  private static class ApacheSolution implements Solution {
    public String getName() {
      return "Apache";
    }

    public String replaceAll(final String text, final String[] searchList, final String[] replacementList) {
        return replaceEach(text, searchList, replacementList, false, 0);
    }

   private static String replaceEach(
            final String text, final String[] searchList, final String[] replacementList, final boolean repeat, final int timeToLive) {

        // mchyzer Performance note: This creates very few new objects (one major goal)
        // let me know if there are performance requests, we can create a harness to measure

        if (text == null || text.isEmpty() || searchList == null ||
                searchList.length == 0 || replacementList == null || replacementList.length == 0) {
            return text;
        }

        // if recursing, this shouldn't be less than 0
        if (timeToLive < 0) {
            throw new IllegalStateException("Aborting to protect against StackOverflowError - " +
                                            "output of one loop is the input of another");
        }

        final int searchLength = searchList.length;
        final int replacementLength = replacementList.length;

        // make sure lengths are ok, these need to be equal
        if (searchLength != replacementLength) {
            throw new IllegalArgumentException("Search and Replace array lengths don't match: "
                + searchLength
                + " vs "
                + replacementLength);
        }

        // keep track of which still have matches
        final boolean[] noMoreMatchesForReplIndex = new boolean[searchLength];

        // index on index that the match was found
        int textIndex = -1;
        int replaceIndex = -1;
        int tempIndex = -1;

        // index of replace array that will replace the search string found
        // NOTE: logic duplicated below START
        for (int i = 0; i < searchLength; i++) {
            if (noMoreMatchesForReplIndex[i] || searchList[i] == null ||
                    searchList[i].isEmpty() || replacementList[i] == null) {
                continue;
            }
            tempIndex = text.indexOf(searchList[i]);

            // see if we need to keep searching for this
            if (tempIndex == -1) {
                noMoreMatchesForReplIndex[i] = true;
            } else {
                if (textIndex == -1 || tempIndex < textIndex) {
                    textIndex = tempIndex;
                    replaceIndex = i;
                }
            }
        }
        // NOTE: logic mostly below END

        // no search strings found, we are done
        if (textIndex == -1) {
            return text;
        }

        int start = 0;

        // get a good guess on the size of the result buffer so it doesn't have to double if it goes over a bit
        int increase = 0;

        // count the replacement text elements that are larger than their corresponding text being replaced
        for (int i = 0; i < searchList.length; i++) {
            if (searchList[i] == null || replacementList[i] == null) {
                continue;
            }
            final int greater = replacementList[i].length() - searchList[i].length();
            if (greater > 0) {
                increase += 3 * greater; // assume 3 matches
            }
        }
        // have upper-bound at 20% increase, then let Java take over
        increase = Math.min(increase, text.length() / 5);

        final StringBuilder buf = new StringBuilder(text.length() + increase);

        while (textIndex != -1) {

            for (int i = start; i < textIndex; i++) {
                buf.append(text.charAt(i));
            }
            buf.append(replacementList[replaceIndex]);

            start = textIndex + searchList[replaceIndex].length();

            textIndex = -1;
            replaceIndex = -1;
            tempIndex = -1;
            // find the next earliest match
            // NOTE: logic mostly duplicated above START
            for (int i = 0; i < searchLength; i++) {
                if (noMoreMatchesForReplIndex[i] || searchList[i] == null ||
                        searchList[i].isEmpty() || replacementList[i] == null) {
                    continue;
                }
                tempIndex = text.indexOf(searchList[i], start);

                // see if we need to keep searching for this
                if (tempIndex == -1) {
                    noMoreMatchesForReplIndex[i] = true;
                } else {
                    if (textIndex == -1 || tempIndex < textIndex) {
                        textIndex = tempIndex;
                        replaceIndex = i;
                    }
                }
            }
            // NOTE: logic duplicated above END

        }
        final int textLength = text.length();
        for (int i = start; i < textLength; i++) {
            buf.append(text.charAt(i));
        }
        final String result = buf.toString();
        if (!repeat) {
            return result;
        }

        return replaceEach(result, searchList, replacementList, repeat, timeToLive - 1);
    }
  }

  private static class BoannSolution implements Solution {
    public String getName() {
      return "Boann";
    }

    public String replaceAll(String subject, String[] search, String[] replace) {
      if (search.length != replace.length) {
        throw new IllegalArgumentException("Strings to find and replace are not paired.");
      }
      StringBuilder sb = new StringBuilder();
  outer:
      for (int i = 0; i < subject.length(); i++) {
        for (int j = 0; j < search.length; j++) {
          String find = search[j];
          if (subject.regionMatches(i, find, 0, find.length())) {
            sb.append(replace[j]);
            i += find.length() - 1;
            continue outer;
          }
        }
        sb.append(subject.charAt(i));
      }
      return sb.toString();
    }
  }
}