package org.unicode.cldr.unittest;

import org.unicode.cldr.util.CollationMapMaker;
import org.unicode.cldr.util.CollationStringByteConverter;
import org.unicode.cldr.util.Dictionary;
import org.unicode.cldr.util.IntMap;
import org.unicode.cldr.util.ReferenceStringSearch;
import org.unicode.cldr.util.StateDictionary;
import org.unicode.cldr.util.StateDictionaryBuilder;
import org.unicode.cldr.util.Utf8StringByteConverter;
import org.unicode.cldr.util.Timer;
import org.unicode.cldr.util.CldrUtility;
import org.unicode.cldr.util.Dictionary.DictionaryCharList;
import org.unicode.cldr.util.Dictionary.Matcher;
import org.unicode.cldr.util.Dictionary.Matcher.Status;
import org.unicode.cldr.util.ReferenceStringSearch.ExtendedRange;
import org.unicode.cldr.util.ReferenceStringSearch.Range;

import com.ibm.icu.impl.Utility;
import com.ibm.icu.text.BreakIterator;
import com.ibm.icu.text.Collator;
import com.ibm.icu.text.NumberFormat;
import com.ibm.icu.text.RuleBasedCollator;
import com.ibm.icu.text.StringCharacterIterator;
import com.ibm.icu.text.StringSearch;
import com.ibm.icu.util.ULocale;

import java.text.CharacterIterator;
import java.util.Map;
import java.util.TreeMap;

public class TestReferenceStringSearch {
  /****************** SIMPLE TESTING ***************/
  
  /**
   * for simple testing of this class.
   * @param args
   */
  public static final void main(String[] args) {
    checkTestCases();
    checkAgainstStringSearch();
  }
  
  static final RuleBasedCollator TEST_COLLATOR = (RuleBasedCollator) Collator
  .getInstance(ULocale.ENGLISH);
  static {
    TEST_COLLATOR.setStrength(TEST_COLLATOR.PRIMARY);
    TEST_COLLATOR.setAlternateHandlingShifted(true); // ignore puncuation
  }
  
  static final BreakIterator TEST_BREAKER = BreakIterator.getCharacterInstance();
  
  
  private static void checkTestCases() {
    String[][] testCases = { 
        { "abc", "ABCABC" },
        { "abc", "abc" },
        { "e\u00DF", " ess e\u00DF ESS\u0300 " },
        { "a!a", "b.a.a.a.b" },
        { "\u03BA\u03B1\u03B9", "\u03BA\u03B1\u1FBE"},
    };
    
    ReferenceStringSearch refSearch = new ReferenceStringSearch()
    .setCollator(TEST_COLLATOR)
    .setBreaker(TEST_BREAKER);
    ExtendedRange extendedRange = new ExtendedRange();
    Range range = new Range();
    
    for (int i = 0; i < testCases.length; ++i) {
      String key = testCases[i][0];
      String target = testCases[i][1];
      refSearch.setKey(key).setTarget(target);
      
      System.out.println("Raw Positions of '" + key + "' in '" + target + "'");
      int count = 0;
      while (refSearch.searchForwards(extendedRange)) {
        //System.out.println(extendedRange); // for the numeric offsets
        System.out.println("\t" + extendedRange.toString(key, target));
        ++count;
      }
      System.out.println("  Count: " + count);
      
      refSearch.setNativeOffset(0);
      System.out.println("Positions of '" + key + "' in '" + target + "'");
      count = 0;
      while (refSearch.searchForwards(range)) {
        //System.out.println(range); // for the numeric offsets
        System.out.println("\t" + range.toString(key, target));
        ++count;
      }
      System.out.println("  Count: " + count);
      System.out.println();
    }
  }
  
  private static void checkAgainstStringSearch() {
    int maxCount = (int)Math.pow(2,12);
    Timer icuTimer = new Timer();
    Timer newTimer = new Timer();
    Timer directTimer = new Timer();
    
    for (int count = 1; count <= maxCount; count *= 2) {
      String bigText = Utility.repeat("The quick brown fox jumped over the L\u00E3zy dog. ", count);
      int[] icuPos = new int[count*2];
      int[] newPos = new int[count*2];
      int[] directPos = new int[count*2];
      
      int oldCount = checkOld("lazy", bigText, icuPos, icuTimer);
      int newCount = checkNew("lazy", bigText, newPos, newTimer, icuTimer);
      int directCount = checkNew("lazy", bigText, directPos, directTimer, icuTimer);
      
      int diff = findDifference(icuPos, newPos, oldCount, newCount);
      if (diff >= 0) {
        System.out.println("\tDifference at " + diff + ", " + icuPos[diff] + ", " + newPos[diff]);
      } else {
        System.out.println("\tNo Difference in results: icu vs new");
      }
      diff = findDifference(icuPos, directPos, oldCount, directCount);
      if (diff >= 0) {
        System.out.println("\tDifference at " + diff + ", " + icuPos[diff] + ", " + directPos[diff]);
      } else {
        System.out.println("\tNo Difference in results: icu vs direct");
      }

      System.out.println();
      System.out.flush();
    }
  }
  
  
  private static int checkNew(String key, String bigText, int[] newPos, Timer newTimer, Timer icuTimer) {
    int count;
    
    long time, delta;
    count = 0;
    Range range = new Range();
    ReferenceStringSearch rss = new ReferenceStringSearch().setCollator(TEST_COLLATOR).setBreaker(TEST_BREAKER).setKey(key).setTarget(bigText);
    
    rss.searchForwards(range);
    newPos[count++] = range.start;
    newPos[count++] = range.limit;
    
    newTimer.start();
    
    while (rss.searchForwards(range)) {
      newPos[count++] = range.start;
      newPos[count++] = range.limit;
    }
    
    newTimer.stop();
    System.out.println("New: " + nf.format(count) + ", Time: " + newTimer.toString(icuTimer));
    
    return count;
  }
  
  static DirectStringSearch rss = new DirectStringSearch().setCollator(TEST_COLLATOR).setBreaker(TEST_BREAKER);
  
  private static int checkDirect(String key, String bigText, int[] newPos, Timer newTimer, Timer icuTimer) {
    int count;
    
    long time, delta;
    count = 0;
    Range range = new Range();
    rss.setKey(key).setTarget(bigText);
    
    rss.searchForwards(range);
    newPos[count++] = range.start;
    newPos[count++] = range.limit;
    
    newTimer.start();
    
    while (rss.searchForwards(range)) {
      newPos[count++] = range.start;
      newPos[count++] = range.limit;
    }
    
    newTimer.stop();
    System.out.println("New: " + nf.format(count) + ", Time: " + newTimer.toString(icuTimer));
    
    return count;
  }
  
  static class DirectStringSearch {
    
    private DictionaryCharList textToSearchIn;
    private DictionaryCharList key;
    
    private BreakIterator breaker;
    int textPosition = 0;

    private StateDictionary<String> dictionary;
    private int keyLength;
    
    public DirectStringSearch setCollator(RuleBasedCollator collation) {
      Map<CharSequence,String> map = new TreeMap<CharSequence,String>(Dictionary.CHAR_SEQUENCE_COMPARATOR);
      new CollationMapMaker().generateCollatorFolding(collation, map);
      // for compactness, we'd use .setIntMapFactory(new IntMap.CompactStringIntMapFactory())
      dictionary = new StateDictionaryBuilder<String>().setByteConverter(new Utf8StringByteConverter()).make(map);
      return this;
    }
    
    public boolean searchForwards(Range range) {
      main:
      for (; textToSearchIn.hasCharAt(textPosition + keyLength - 1); ++textPosition) {
        // see if we match at position
        for (int i = 0; i < keyLength; ++i) {
          if (key.charAt(i) != textToSearchIn.charAt(textPosition + i)) {
            continue main;
          }
        }
        // we have a match, so return the values
        final int start = textToSearchIn.toSourceOffset(textPosition);
        // TODO get boundaries
//        position.start = getBoundary(breaker, internalPosition.minStart, internalPosition.maxStart, !widestStart);
//        if (position.start == -1) continue; // failed to find the right boundary
        final int limit = textToSearchIn.toSourceOffset(textPosition + keyLength);
        range.start = start;
        range.limit = limit;
        return true;
      }
      return true;
    }
    
    public DirectStringSearch setTarget(String textToSearchIn) {
      this.textToSearchIn = new DictionaryCharList(dictionary, textToSearchIn);
      if (breaker != null) {
        breaker.setText(textToSearchIn);
      }
      return this;
    }
    
    public DirectStringSearch setKey(String key) {
      this.key = new DictionaryCharList(dictionary, key);
      keyLength = key.length();
      return this;
    }
    
    public DirectStringSearch setBreaker(BreakIterator breaker) {
      this.breaker = breaker;
      return this;
    }
    
//    char[] convert(String text) {
//      StringBuilder result = new StringBuilder();
//      keyMatcher.setText(text); // reset the matcher to the start
//      while (true) {
//        CharSequence value = next(keyMatcher);
//        if (value == null) {
//          break;
//        }
//        result.append(value);
//      }
//      // convert to char array
//      char[] tempResult = new char[result.length()];
//      result.getChars(0, tempResult.length, tempResult, 0);
//      return tempResult;
//    }
    
//    /**
//     * Get the next sequence of chars from the matcher, and move the cursor past it.
//     * @param matcher
//     * @param result
//     * @param resultOffset
//     * @return
//     */
//    static <T extends CharSequence> CharSequence next(Matcher<T> matcher) {
//      if (!matcher.hasMore()) {
//        return null;
//      }
//      Status status = matcher.next(Matcher.Filter.LONGEST_MATCH);
//      if (status == Status.MATCH) {
//          matcher.setOffset(matcher.getMatchEnd());
//          return matcher.getMatchValue();
//      } else {
//        // needs optimization
//          final int offset = matcher.getOffset();
//          matcher.setOffset(offset + 1);
//          return matcher.getText().subSequence(offset, offset+1);
//      }
//    }
  }
//  
//  static class CircularBuffer<T> {
//    private T[] buffer;
//    private int start = 0;
//    private int limit = 0;
//    // invariants: 
//    // both < buffer.length;
//    // limit == start means it is empty. So any non-empty buffer has different values
//    
//    public CircularBuffer(T[] buffer) {
//      this.buffer = buffer;
//    }
//
//    /**
//     * Get the total capacity of the buffer.
//     */
//    public int capacity() {
//      return buffer.length - 1;
//    }
//    
//    /**
//     * Remove from the front of the queue
//     * @return
//     */
//    public T remove() {
//      if (start == limit) {
//        throw new ArrayIndexOutOfBoundsException();
//      }
//      T value = buffer[start];
//      ++start;
//      if (start == buffer.length) {
//        start = 0;
//      }
//      return value;
//    }
//    
//    /**
//     * Add to the end of the queue
//     * @param item
//     */
//    public void add(T item) {
//      int oldLimit = limit;
//      if (limit + 1 == start || start == 0 && limit + 1 == buffer.length) {
//        throw new ArrayIndexOutOfBoundsException();
//      }
//      ++ limit;
//      if (limit == buffer.length) {
//        limit = 0;
//      }
//      if (limit == start) {
//        limit = oldLimit;
//        throw new ArrayIndexOutOfBoundsException();
//      }
//      buffer[oldLimit] = item;
//    }
//    
//    /**
//     * Get the number of items in the queue
//     * @return
//     */
//    int length() {
//      int len = limit - start;
//      return len >= 0 ? len : buffer.length - len;
//      // buffer.length-start  +  limit-0;
//    }
//    
//    /**
//     * Compare the contents to some other list of values
//     * @param key
//     * @return
//     */
//    boolean matchesAt(T[] key) {
//      int j = start;
//      int i = 0;
//      while (true) {
//        // fail if no match
//        if (key[i] != buffer[j]) {
//          return false;
//        }
//        // succeed if at end of key
//        ++i;
//        if (i == key.length) {
//          return true;
//        }
//        // fail if end of buffer
//        ++j;
//        if (j == limit) {
//          return false;
//        }
//        // wrap around if needed
//        if (j == buffer.length) {
//          j = 0;
//        }
//      }
//    }
//  }
//  
//  
//  static class CharCircularBuffer {
//    private char[] buffer;
//    private int start = 0;
//    private int limit = 0;
//    // invariants: 
//    // both < buffer.length;
//    // limit == start means it is empty. So any non-empty buffer has different values
//    
//    public void set(char[] buffer) {
//      this.buffer = buffer;
//      start = limit = 0;
//    }
//
//    /**
//     * Get the total capacity of the buffer.
//     */
//    public int capacity() {
//      return buffer.length - 1;
//    }
//    
//    /**
//     * Remove from the front of the queue
//     * @return
//     */
//    public char remove() {
//      if (start == limit) {
//        throw new ArrayIndexOutOfBoundsException();
//      }
//      char value = buffer[start];
//      ++start;
//      if (start == buffer.length) {
//        start = 0;
//      }
//      return value;
//    }
//    
//    /**
//     * Add to the end of the queue
//     * @param item
//     */
//    public void add(char item) {
//      int oldLimit = limit;
//      if (limit + 1 == start || start == 0 && limit + 1 == buffer.length) {
//        throw new ArrayIndexOutOfBoundsException();
//      }
//      ++ limit;
//      if (limit == buffer.length) {
//        limit = 0;
//      }
//      if (limit == start) {
//        limit = oldLimit;
//        throw new ArrayIndexOutOfBoundsException();
//      }
//      buffer[oldLimit] = item;
//    }
//    
//    /**
//     * Get the number of items in the queue
//     * @return
//     */
//    int length() {
//      int len = limit - start;
//      return len >= 0 ? len : buffer.length - len;
//      // buffer.length-start  +  limit-0;
//    }
//    
//    /**
//     * Compare the contents to some other list of values
//     * @param key
//     * @return
//     */
//    boolean matchesAt(char[] key) {
//      int j = start;
//      int i = 0;
//      while (true) {
//        // fail if no match
//        if (key[i] != buffer[j]) {
//          return false;
//        }
//        // succeed if at end of key
//        ++i;
//        if (i == key.length) {
//          return true;
//        }
//        // fail if end of buffer
//        ++j;
//        if (j == limit) {
//          return false;
//        }
//        // wrap around if needed
//        if (j == buffer.length) {
//          j = 0;
//        }
//      }
//    }
//  }
//  
  private static int checkOld(String key, String bigText, int[] icuPos, Timer icuTimer) {
    int count = 0;
    long time;
    CharacterIterator ci = new StringCharacterIterator(bigText);
    StringSearch foo = new StringSearch("lazy", ci, TEST_COLLATOR, TEST_BREAKER);
    
    foo.next();
    icuPos[count++] = foo.getMatchStart();
    icuPos[count++] = foo.getMatchStart() + foo.getMatchLength();
    
    icuTimer.start();
    
    while (foo.next() != foo.DONE) {
      icuPos[count++] = foo.getMatchStart();
      icuPos[count++] = foo.getMatchStart() + foo.getMatchLength();
    }
    
    icuTimer.stop();
    System.out.println("ICU: " + nf.format(count) + ", Time: " + icuTimer.toString());
    return count;
  }
  
  static NumberFormat nf = NumberFormat.getNumberInstance();
  
  private static int findDifference(int[] icuPos, int[] newPos, int oldCount, int newCount) {
    int count = Math.min(oldCount, newCount);
    for (int i = 0; i < count; ++i) {
      if (icuPos[i] != newPos[i]) {
        return i;
      }
    }
    if (oldCount != newCount) {
      return count;
    }
    return -1;
  }
  
  
}