/*
 * 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://www.apache.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.
*/

package org.apache.uima.ruta.textruler.learner.rapier;

import java.util.ArrayList;
import java.util.Iterator;

import org.apache.uima.ruta.textruler.core.TextRulerRuleItem;
import org.apache.uima.ruta.textruler.core.TextRulerRulePattern;
import org.apache.uima.ruta.textruler.core.TextRulerToolkit;
import org.apache.uima.ruta.textruler.core.TextRulerWordConstraint;

public class RapierGeneralizationHelper {

  // ----------------------------------------------------------------------------------------------------------------------------------------
  // --- ITEM(s) GENERALIZATION
  // -------------------------------------------------------------------------------------------------------------
  // ----------------------------------------------------------------------------------------------------------------------------------------
  private static ArrayList<TextRulerRuleItem> getGeneralizationsForRuleItems(
          TextRulerRuleItem item1, TextRulerRuleItem item2) {
    ArrayList<TextRulerRuleItem> item1List = new ArrayList<TextRulerRuleItem>();
    ArrayList<TextRulerRuleItem> item2List = new ArrayList<TextRulerRuleItem>();
    if (item1 != null)
      item1List.add(item1);
    if (item2 != null)
      item2List.add(item2);
    return getGeneralizationsForRuleItemLists(item1List, item2List);
  }

  // generalize two given pattern elements or pattern element lists and return
  // all possible generalizations as
  // TextRulerRuleItem objects
  private static ArrayList<TextRulerRuleItem> getGeneralizationsForRuleItemLists(
          ArrayList<TextRulerRuleItem> item1List, ArrayList<TextRulerRuleItem> item2List) {
    ArrayList<RapierRuleItem> proposedWordConstraints = new ArrayList<RapierRuleItem>();
    ArrayList<RapierRuleItem> proposedTagConstraints = new ArrayList<RapierRuleItem>();
    ArrayList<RapierRuleItem> proposedClassConstraints = new ArrayList<RapierRuleItem>();
    ArrayList<TextRulerRuleItem> result = new ArrayList<TextRulerRuleItem>();

    int resultListLen1 = 0;
    int resultListLen2 = 0;
    boolean oneListIsEmpty = false;

    if (item1List.size() == 0 && item2List.size() == 0) {
      TextRulerToolkit.log("ERROR !");
    }
    if (item1List.size() == 0 || item2List.size() == 0) {
      // TextRulerToolkit.log("SPECIAL CASE WITH ONE LIST OF ZERO SIZE");
      oneListIsEmpty = true;
    }

    boolean hasEmptyWordList = false;
    int maxWordCount = 0;
    boolean hasEmptyTagList = false;
    int maxTagCount = 0;
    for (TextRulerRuleItem rt : item2List) {
      RapierRuleItem t = (RapierRuleItem) rt;
      resultListLen2 += t.isListItem() ? t.listLen() : 1;
      if (t.getWordConstraints().size() > maxWordCount)
        maxWordCount = t.getWordConstraints().size();
      if (t.getWordConstraints().size() == 0)
        hasEmptyWordList = true;
      if (t.getTagConstraints().size() > maxTagCount)
        maxTagCount = t.getTagConstraints().size();
      if (t.getTagConstraints().size() == 0)
        hasEmptyTagList = true;
    }
    for (TextRulerRuleItem rt : item1List) {
      RapierRuleItem t = (RapierRuleItem) rt;
      resultListLen1 += t.isListItem() ? t.listLen() : 1;
      if (t.getWordConstraints().size() > maxWordCount)
        maxWordCount = t.getWordConstraints().size();
      if (t.getWordConstraints().size() == 0)
        hasEmptyWordList = true;
      if (t.getTagConstraints().size() > maxTagCount)
        maxTagCount = t.getTagConstraints().size();
      if (t.getTagConstraints().size() == 0)
        hasEmptyTagList = true;
    }
    int resultListLen = resultListLen1 > resultListLen2 ? resultListLen1 : resultListLen2; // take
    // the
    // bigger
    // of
    // both
    if (resultListLen == 1 && !oneListIsEmpty)
      resultListLen = 0; // lists with a length of 1 can only occur when
    // one itemList is empty! THAT CANNOT HAPPEN
    // HERE!

    // generalize word constraints:
    if (hasEmptyWordList) // at least one constraint of both is empty
    {
      // do nothing here, proposed.wordItems stays empty
      proposedWordConstraints.add(new RapierRuleItem());
    } else // create union of both constraints AND (if both constraints
    // weren't the same) drop constraint
    {
      RapierRuleItem proposed = new RapierRuleItem();
      for (TextRulerRuleItem t : item1List)
        proposed.addWordConstraints(((RapierRuleItem) t).getWordConstraints());
      for (TextRulerRuleItem t : item2List)
        proposed.addWordConstraints(((RapierRuleItem) t).getWordConstraints());

      proposedWordConstraints.add(proposed);

      // if the union of both constraints is a real union (one does not
      // subsume the other completely),
      // we have to add the DROPPING OF THE CONSTRAINT as a second
      // proposed word constraint
      if (maxWordCount != proposed.getWordConstraints().size()) // the
      // union
      // is a
      // real
      // bigger
      // set
      // than
      {
        proposedWordConstraints.add(new RapierRuleItem());
      }
    }

    if (hasEmptyTagList) // at least one constraint of both is empty
    {
      // do nothing here, proposed.tagItems stays empty
      proposedTagConstraints.add(new RapierRuleItem());
    } else // create union of both constraints AND (if both constraints
    // weren't the same) drop constraint
    {
      RapierRuleItem proposed = new RapierRuleItem();
      for (TextRulerRuleItem t : item1List)
        proposed.addTagConstraints(((RapierRuleItem) t).getTagConstraints());
      for (TextRulerRuleItem t : item2List)
        proposed.addTagConstraints(((RapierRuleItem) t).getTagConstraints());

      proposedTagConstraints.add(proposed);

      // if the union of both constraints is a real union (one does not
      // subsume the other completely),
      // we have to add the DROPPING OF THE CONSTRAINT as a second
      // proposed tag constraint
      if (maxTagCount != proposed.getTagConstraints().size()) // the union
      // is a real
      // bigger
      // set than
      {
        proposedTagConstraints.add(new RapierRuleItem());
      }
    }

    // TODO semantic class generalization
    proposedClassConstraints.add(new RapierRuleItem()); // add only NO
    // class
    // constraint
    // version for
    // now!

    // finally, create all combinations of the above proposed items
    for (RapierRuleItem wt : proposedWordConstraints) {
      for (RapierRuleItem tt : proposedTagConstraints) {
        for (RapierRuleItem ct : proposedClassConstraints) {
          RapierRuleItem newItem = new RapierRuleItem();
          for (TextRulerWordConstraint wi : wt.getWordConstraints())
            newItem.addWordConstraint(wi.copy());
          for (String ti : tt.getTagConstraints())
            newItem.addTagConstraint(ti);
          for (String tc : ct.getClassConstraints())
            newItem.addClassConstraint(tc);
          newItem.setListLen(resultListLen);
          newItem.setListBeginsAtZero(oneListIsEmpty && resultListLen > 0);
          result.add(newItem);
        }
      }
    }
    return result;
  }

  // ----------------------------------------------------------------------------------------------------------------------------------------
  // --- EQUAL SIZE PATTERN GENERALIZATION
  // --------------------------------------------------------------------------------------------------
  // ----------------------------------------------------------------------------------------------------------------------------------------
  private static ArrayList<TextRulerRulePattern> getGeneralizationsForRuleItemPatternsOfEqualSize(
          TextRulerRulePattern pattern1, TextRulerRulePattern pattern2) {
    ArrayList<TextRulerRulePattern> resultList = new ArrayList<TextRulerRulePattern>();

    ArrayList<ArrayList<TextRulerRuleItem>> generalizationTable = new ArrayList<ArrayList<TextRulerRuleItem>>();
    Iterator<TextRulerRuleItem> it2 = pattern2.iterator();
    if (pattern1.size() != pattern2.size()) {
      TextRulerToolkit.log("ERROR!");
    }
    for (TextRulerRuleItem item1 : pattern1) {
      TextRulerRuleItem item2 = it2.next();
      // get all possible LGGs of the current two elements and save them
      // into the matrix
      ArrayList<TextRulerRuleItem> allLGGs = getGeneralizationsForRuleItems(item1, item2);
      generalizationTable.add(allLGGs);
      // TextRulerToolkit.log("--- GET GENERALISATIONS FOR TWO TERMS:  --"+t1+"--   --"+t2+"--");
      // ArrayList<MLRapierRuleTerm> allLGGs =
      // this.getGeneralizationsForRuleTerms(t1, t2);
      // for (MLRapierRuleTerm term : allLGGs)
      // TextRulerToolkit.log("--- "+term);
      // TextRulerToolkit.log("--- END");
    }

    // now we have patternSize lists of possible generalizations, one list
    // per original pattern item pair of
    // pattern1 and pattern2. we now have to build all possible
    // combinations. Each combination is a
    // new pattern
    recursiveBuildAllRuleItemCombinations(generalizationTable, 0, new TextRulerRulePattern(),
            resultList);
    return resultList;
  }

  private static void recursiveBuildAllRuleItemCombinations(
          ArrayList<ArrayList<TextRulerRuleItem>> table, int curIndex,
          TextRulerRulePattern currentPattern, ArrayList<TextRulerRulePattern> resultPatterns) {
    if (curIndex >= table.size()) {
      // make a deep copy of the current pattern:
      TextRulerRulePattern copy = new TextRulerRulePattern();
      for (TextRulerRuleItem item : currentPattern)
        copy.add(item.copy());
      resultPatterns.add(copy);
    } else {
      for (TextRulerRuleItem item : table.get(curIndex)) {
        currentPattern.add(item);
        recursiveBuildAllRuleItemCombinations(table, curIndex + 1, currentPattern, resultPatterns);
        currentPattern.remove(currentPattern.size() - 1);
      }
    }
  }

  // ----------------------------------------------------------------------------------------------------------------------------------------
  // --- DISTINCT SIZE PATTERN GENERALIZATION
  // -----------------------------------------------------------------------------------------------
  // ----------------------------------------------------------------------------------------------------------------------------------------

  // this is the low level version for patterns of distinct sizes! it creates
  // ALL possible combinations how to pair/map pattern items
  // of the shorter with those of the longer pattern. the optimizing version
  // (getOptimizedGeneralizationsForRuleItemPatternsOfDistinctSize)
  // uses this method for its pattern segments! (see below)
  private static ArrayList<TextRulerRulePattern> getGeneralizationsForRuleItemPatternsOfDistinctSize(
          TextRulerRulePattern pattern1, TextRulerRulePattern pattern2) {
    ArrayList<TextRulerRulePattern> resultList = new ArrayList<TextRulerRulePattern>();
    if (pattern1.size() == pattern2.size()) {
      TextRulerToolkit.log("ERROR! CALL getGeneralizationsForRuleItemPatternsOfEqualSize instead!");
      if (TextRulerToolkit.DEBUG)
        return null;
    }

    TextRulerRulePattern longerPattern = pattern1;
    TextRulerRulePattern shorterPattern = pattern2;
    if (pattern2.size() > pattern1.size()) {
      longerPattern = pattern2;
      shorterPattern = pattern1;
    }

    if (longerPattern.size() <= 1 || shorterPattern.size() <= 1) {
      // Special case 1: one of the pattern terms list is empty AND
      // special case 2: one has only ONE element
      if (longerPattern.size() + shorterPattern.size() == 0) {
        TextRulerToolkit.log("ERROR !! BOTH PATTERNS ARE EMPTY!");
        if (TextRulerToolkit.DEBUG)
          return null;
      }

      // get all possible generalizations of the two patterns. result of
      // each generalization is ONE rule item, so we
      // don't use TextRulerRulePattern here since this IS NOT a rule
      // pattern! it's a list of possible generalizations:
      ArrayList<TextRulerRuleItem> generalizations = getGeneralizationsForRuleItemLists(
              longerPattern, shorterPattern);
      // create a one element result pattern for each:
      for (TextRulerRuleItem item : generalizations) {
        TextRulerRulePattern p = new TextRulerRulePattern();
        p.add(item);
        resultList.add(p);
      }
    }
    // else SPECIAL CASE 3 // TODO make those values configurable ?
    else if (((longerPattern.size() - shorterPattern.size()) > 6) || (longerPattern.size() > 10)) {
      int resultListLen1 = 0;
      for (TextRulerRuleItem rt : shorterPattern)
        resultListLen1 += ((RapierRuleItem) rt).isListItem() ? ((RapierRuleItem) rt).listLen() : 1;
      int resultListLen2 = 0;
      for (TextRulerRuleItem rt : longerPattern)
        resultListLen2 += ((RapierRuleItem) rt).isListItem() ? ((RapierRuleItem) rt).listLen() : 1;

      RapierRuleItem singleItem = new RapierRuleItem();
      singleItem.setListLen(resultListLen1 > resultListLen2 ? resultListLen1 : resultListLen2);
      TextRulerRulePattern singleItemPattern = new TextRulerRulePattern();
      singleItemPattern.add(singleItem);
      resultList.add(singleItemPattern);
    } else { // sizes are different and both > 1
      // create all possible generalization combinations, that is: how can
      // we map elements of the shorter pattern
      // to the ones of the longer pattern and then generalize each
      // mapping (each group) of items?
      ArrayList<ArrayList<RapierPatternItemMapping>> combinationList = new ArrayList<ArrayList<RapierPatternItemMapping>>();

      recursiveBuildAllPossiblePatternMappingSequences(longerPattern, shorterPattern,
              new ArrayList<RapierPatternItemMapping>(), combinationList);

      for (ArrayList<RapierPatternItemMapping> mappingSequence : combinationList) {
        resultList.addAll(getGeneralizationsForPatternMappingSequence(mappingSequence));
      }
    }
    return resultList;
  }

  // creates all possible combinations how to pair together items from the
  // longer and the shorter source pattern, e.g.
  // 1 2 3 4 5 vs. 1 2 3 = 1/1+2+3 2/4 3/5, ...
  private static void recursiveBuildAllPossiblePatternMappingSequences(
          TextRulerRulePattern longerPattern, TextRulerRulePattern shorterPattern,
          ArrayList<RapierPatternItemMapping> currentMappingSequence,
          ArrayList<ArrayList<RapierPatternItemMapping>> resultList) {
    int windowSize = longerPattern.size() - shorterPattern.size() + 1;

    if (shorterPattern.size() > longerPattern.size()) {
      TextRulerToolkit.log("ERROR: SHORTER > LONGER !!");
    }
    if (longerPattern.size() == 0 || shorterPattern.size() == 0) {
      TextRulerToolkit.log("ERROR: SHORTER == LONGER == 0!");
    } else {
      // if the remaining (sub-)patterns are of equal size or one has only
      // one element left, create one last item mapping and
      // a final result mapping sequence:
      if (shorterPattern.size() == 1 || (longerPattern.size() == shorterPattern.size())) {
        RapierPatternItemMapping lastMapping = new RapierPatternItemMapping();
        lastMapping.shorterPattern.addAll(shorterPattern);
        lastMapping.longerPattern.addAll(longerPattern);
        ArrayList<RapierPatternItemMapping> newMappingSequence = new ArrayList<RapierPatternItemMapping>();
        newMappingSequence.addAll(currentMappingSequence);
        newMappingSequence.add(lastMapping);
        resultList.add(newMappingSequence);
      } else { // otherwise we have to create all possible combinations of
        // the longer and shorter remaining pattern:
        TextRulerRuleItem firstItem = shorterPattern.get(0);
        // combine with 0, 0/1, ... 0/1/2/.../windowSize-1
        for (int maxi = 0; maxi < windowSize; maxi++) {
          RapierPatternItemMapping newMapping = new RapierPatternItemMapping();
          newMapping.shorterPattern.add(firstItem);
          for (int li = 0; li <= maxi; li++)
            newMapping.longerPattern.add(longerPattern.get(li));
          currentMappingSequence.add(newMapping);
          TextRulerRulePattern restLongerPattern = new TextRulerRulePattern();
          TextRulerRulePattern restShorterPattern = new TextRulerRulePattern();
          for (int i = 1; i < shorterPattern.size(); i++)
            restShorterPattern.add(shorterPattern.get(i));
          for (int i = maxi + 1; i < longerPattern.size(); i++)
            restLongerPattern.add(longerPattern.get(i));

          // recurse:
          recursiveBuildAllPossiblePatternMappingSequences(restLongerPattern, restShorterPattern,
                  currentMappingSequence, resultList);

          // remove last segment to get back to the same state as
          // before the recursion:
          currentMappingSequence.remove(currentMappingSequence.size() - 1);
        }
      }
    }
  }

  // here the input is called a MAPPING instead of a pattern segmentation in
  // order to distinguish between the two levels of
  // dividing the problem: a pattern segmentation is a special mapping of
  // equal items in the two to generalize source patterns;
  // the segments that result through that segmentation still need to be
  // generalized (see getGeneralizationsForPatternSegmentation)
  // if sucha semgent has subpattersn of different size,
  // getGeneralizationsForRuleItemPatternsOfDistinctSize is used to
  // generalize it, which uses THIS METHOD HERE to get all generalizations for
  // a special MAPPING. a mapping (in comparison to the
  // segmentation!) is a mapping between the longer and shorter pattern items
  // which then get directly generalized here!
  // in order to show this difference, we use the (inernally exactly the
  // same!) class RapierPatternItemMapping instead of
  // RapierPatternSegment!)
  private static ArrayList<TextRulerRulePattern> getGeneralizationsForPatternMappingSequence(
          ArrayList<RapierPatternItemMapping> patternMappingSequence) {
    ArrayList<TextRulerRulePattern> resultList = new ArrayList<TextRulerRulePattern>();
    ArrayList<ArrayList<TextRulerRuleItem>> generalizationTable = new ArrayList<ArrayList<TextRulerRuleItem>>();

    // every mapping has several possible generalizations, so we store all
    // of them in that generalizationTable, one list of
    // generalizations for each mapping:
    for (RapierPatternItemMapping mapping : patternMappingSequence) {
      ArrayList<TextRulerRuleItem> lggList = getGeneralizationsForRuleItemLists(
              mapping.shorterPattern, mapping.longerPattern);
      generalizationTable.add(lggList);
    }

    // afterwards we have again to create all possible combinations of those
    // lists (like in the equalSizeGeneralization):
    // Each combination is a new pattern
    recursiveBuildAllRuleItemCombinations(generalizationTable, 0, new TextRulerRulePattern(),
            resultList);
    return resultList;
  }

  // ----------------------------------------------------------------------------------------------------------------------------------------
  // --- FIND MATCHINGS BETWEEN PATTERNS FOR GENERALIZATION
  // -----------------------------------------------------------------------------------------------
  // ----------------------------------------------------------------------------------------------------------------------------------------

  // find matches in two patterns by comparing the items of the patterns and
  // return all possible segmentations of those two patterns.
  private static void recursiveFindPatternSegmentsByMatchingPatternItems(
          TextRulerRulePattern longerPattern, TextRulerRulePattern shorterPattern,
          ArrayList<RapierPatternSegment> currentSegmentation,
          ArrayList<ArrayList<RapierPatternSegment>> resultList) {
    int cmpWindowSize = longerPattern.size() - shorterPattern.size() + 1;

    // is one
    // (rest-)pattern
    // empty ?
    if (longerPattern.size() == 0 || shorterPattern.size() == 0) {
      // create result segmentation
      ArrayList<RapierPatternSegment> newSegmentation = new ArrayList<RapierPatternSegment>();
      newSegmentation.addAll(currentSegmentation); // add current
      // add rest if
      // recursive state
      // anything is
      // left one of
      // the
      // patterns
      if (longerPattern.size() + shorterPattern.size() > 0) {
        RapierPatternSegment lastSegment = new RapierPatternSegment();
        for (TextRulerRuleItem i : shorterPattern)
          lastSegment.shorterPattern.add(i);
        for (TextRulerRuleItem i : longerPattern)
          lastSegment.longerPattern.add(i);
        newSegmentation.add(lastSegment);
      }
      resultList.add(newSegmentation);
    } else {
      boolean matched = false;
      for (int si = 0; si < shorterPattern.size(); si++) {
        // compare element si with si, si+1, ... si+cmpWindowSize-1
        for (int li = si; li < si + cmpWindowSize; li++) {
          if (longerPattern.get(li).equals(shorterPattern.get(si))) {
            // matched pair found!
            matched = true;
            // --> calculate pattern segments, add them to the
            // current one and pass the rest of the
            // patterns to the next recursion level:
            RapierPatternSegment newSegment = new RapierPatternSegment();
            for (int i = 0; i < si; i++)
              newSegment.shorterPattern.add(shorterPattern.get(i));
            for (int i = 0; i < li; i++)
              newSegment.longerPattern.add(longerPattern.get(i));

            boolean addedLeftSegmentation = false;
            if (newSegment.longerPattern.size() > 0 || newSegment.shorterPattern.size() > 0) {
              // only add if the segmentation is not empty!
              currentSegmentation.add(newSegment);
              addedLeftSegmentation = true;
            }

            RapierPatternSegment matchedSegment = new RapierPatternSegment();
            matchedSegment.shorterPattern.add(shorterPattern.get(si));
            matchedSegment.longerPattern.add(longerPattern.get(li));
            currentSegmentation.add(matchedSegment);

            // the rest is now the rest to the right of both (so
            // li+1 and si+1 to the ends...)
            TextRulerRulePattern restLongerPattern = new TextRulerRulePattern();
            TextRulerRulePattern restShorterPattern = new TextRulerRulePattern();
            for (int i = li + 1; i < longerPattern.size(); i++)
              restLongerPattern.add(longerPattern.get(i));
            for (int i = si + 1; i < shorterPattern.size(); i++)
              restShorterPattern.add(shorterPattern.get(i));

            // recurse...
            if (restLongerPattern.size() > restShorterPattern.size())
              recursiveFindPatternSegmentsByMatchingPatternItems(restLongerPattern,
                      restShorterPattern, currentSegmentation, resultList);
            else
              recursiveFindPatternSegmentsByMatchingPatternItems(restShorterPattern,
                      restLongerPattern, currentSegmentation, resultList);

            // remove added segments so that we are in the same
            // state as before the recursion:
            if (addedLeftSegmentation)
              currentSegmentation.remove(currentSegmentation.size() - 1); // remove the left side
            // segment
            currentSegmentation.remove(currentSegmentation.size() - 1); // remove
            // the
            // matched
            // segment
          }
        }
      }
      if (!matched) // add remaining items of both lists in one pattern
      // segment
      {
        ArrayList<RapierPatternSegment> newSegmentation = new ArrayList<RapierPatternSegment>();
        newSegmentation.addAll(currentSegmentation);

        RapierPatternSegment lastSegment = new RapierPatternSegment();
        for (TextRulerRuleItem i : shorterPattern)
          lastSegment.shorterPattern.add(i);
        for (TextRulerRuleItem i : longerPattern)
          lastSegment.longerPattern.add(i);
        newSegmentation.add(lastSegment);
        resultList.add(newSegmentation);
      }
    }
  }

  private static ArrayList<TextRulerRulePattern> getGeneralizationsForPatternSegmentation(
          ArrayList<RapierPatternSegment> patternSegmentation) {
    // for creating those, we need a table:
    // each segment of the patternSegmentation creates a bunch of possible
    // new generalized sub patterns (that's the inner
    // ArrayList<TextRulerRulePattern>)
    // since we have a whole sequence of pattern semgents (a whole
    // segmentation), we need the outer ArrayList to collect
    // all generalizations of all pattern segments:
    ArrayList<ArrayList<TextRulerRulePattern>> generalizationTable = new ArrayList<ArrayList<TextRulerRulePattern>>();

    // now, we create all generalizations of each pattern segment and
    // collect them in that table:
    for (RapierPatternSegment pSeg : patternSegmentation) {
      ArrayList<TextRulerRulePattern> pSegGeneralizations;

      if (pSeg.longerPattern.size() == pSeg.shorterPattern.size())
        pSegGeneralizations = getGeneralizationsForRuleItemPatternsOfEqualSize(pSeg.longerPattern,
                pSeg.shorterPattern);
      else
        pSegGeneralizations = getGeneralizationsForRuleItemPatternsOfDistinctSize(
                pSeg.longerPattern, pSeg.shorterPattern);

      generalizationTable.add(pSegGeneralizations);
    }

    // finally, we have to build all combinations of them in form of
    // MLRulePatterns:
    ArrayList<TextRulerRulePattern> resultList = new ArrayList<TextRulerRulePattern>(); // the
    // result
    // is
    // a
    // list
    // of
    // new
    // generalized
    // patterns

    recursiveBuildAllRuleItemCombinationsFromPatterns(generalizationTable, 0,
            new TextRulerRulePattern(), resultList);

    return resultList;
  }

  private static void recursiveBuildAllRuleItemCombinationsFromPatterns(
          ArrayList<ArrayList<TextRulerRulePattern>> table, int curIndex,
          TextRulerRulePattern currentPattern, ArrayList<TextRulerRulePattern> resultPatterns) {
    if (curIndex >= table.size()) {
      // make a deep copy of the current pattern:
      TextRulerRulePattern copy = new TextRulerRulePattern();
      for (TextRulerRuleItem item : currentPattern)
        copy.add(item.copy());
      resultPatterns.add(copy);
    } else {
      for (TextRulerRulePattern pattern : table.get(curIndex)) {
        currentPattern.addAll(pattern);
        recursiveBuildAllRuleItemCombinationsFromPatterns(table, curIndex + 1, currentPattern,
                resultPatterns);
        for (int i = 0; i < pattern.size(); i++)
          currentPattern.remove(currentPattern.size() - 1);
      }
    }
  }

  // ----------------------------------------------------------------------------------------------------------------------------------------
  // --- WORKING ON PATTERNS OF DISTINCT LENGTH - OPTIMIZED
  // ---------------------------------------------------------------------------------
  // ----------------------------------------------------------------------------------------------------------------------------------------

  // "optimized", because this method uses the pattern item matching
  // optimization (search for equal items and make a segmentation, etc.)
  private static ArrayList<TextRulerRulePattern> getOptimizedGeneralizationsForRuleItemPatternsOfDistinctSize(
          TextRulerRulePattern pattern1, TextRulerRulePattern pattern2) {
    ArrayList<ArrayList<RapierPatternSegment>> matchedCombinationList = new ArrayList<ArrayList<RapierPatternSegment>>();

    // in order to reduce the amount of possible combinations how to combine
    // the elements of the shorter pattern with the
    // elements of the longer pattern, we first search for equal pattern
    // items in both patterns. those equal patterns get hardwired
    // in the combination and the left and right remaining subpatterns stay
    // as a "divided smaller problem" that needs to be conquered...
    // the result of the search is a list of possible segmentations of the
    // patterns. all semgementations are those "smaller"
    // left problems that we then need to generalize in the original manner.
    // if no equal items are found, one segmentation with only one segment
    // (the orignal longer and shoter pattern) is returned and
    // has to be generalized.
    if (pattern1.size() > pattern2.size())
      recursiveFindPatternSegmentsByMatchingPatternItems(pattern1, pattern2,
              new ArrayList<RapierPatternSegment>(), matchedCombinationList);
    else
      recursiveFindPatternSegmentsByMatchingPatternItems(pattern2, pattern1,
              new ArrayList<RapierPatternSegment>(), matchedCombinationList);

    // if (TextRulerToolkit.DEBUG && matchedCombinationList.size() > 1)
    // {
    // TextRulerToolkit.log("PATTERN SEQUENCES FOUND: "+matchedCombinationList.size());
    // for (ArrayList<RapierPatternSegment> patternSequence :
    // matchedCombinationList)
    // {
    // TextRulerToolkit.log("\tNEXT SEQUENCE");
    // for (RapierPatternSegment pSeg : patternSequence)
    // {
    // TextRulerToolkit.log("\t\t"+pSeg.longerPattern);
    // TextRulerToolkit.log("\t\t"+pSeg.shorterPattern);
    // }
    // }
    // }

    ArrayList<TextRulerRulePattern> resultList = new ArrayList<TextRulerRulePattern>();

    for (ArrayList<RapierPatternSegment> patternSegmentation : matchedCombinationList) {
      // TODO filter out possible duplicates ?
      resultList.addAll(getGeneralizationsForPatternSegmentation(patternSegmentation));
    }
    return resultList;
  }

  // ----------------------------------------------------------------------------------------------------------------------------------------
  // --- THE FINAL RESULT: a genarlization method
  // -------------------------------------------------------------------------------------------
  // ----------------------------------------------------------------------------------------------------------------------------------------

  // input: two sequences of rule items (=patterns) that shall be
  // generalized... matchings are searched for a optimized search
  // and to get a not too big count of generalizations...
  // result: a (probably very large!) list of possible generalizations, e.g.
  // used for all slotfiller generalizations of two rules...
  public static ArrayList<TextRulerRulePattern> getGeneralizationsForRuleItemPatterns(
          TextRulerRulePattern pattern1, TextRulerRulePattern pattern2) {
    ArrayList<TextRulerRulePattern> result = new ArrayList<TextRulerRulePattern>();

    // if (TextRulerToolkit.DEBUG)
    // {
    // TextRulerToolkit.log("\tgetGeneralizationsForRuleItemPatterns:");
    // TextRulerToolkit.log("\tPattern1:"+pattern1);
    // TextRulerToolkit.log("\tPattern2:"+pattern2);
    // }

    if (pattern1.size() == 0 && pattern2.size() == 0) {
      return result; // return empty list
    } else if (pattern1.size() == pattern2.size()) // both have the same
    // pattern item count
    {
      // generalizing is easy then: simply generalize each pair of items:
      result = getGeneralizationsForRuleItemPatternsOfEqualSize(pattern1, pattern2);
    } else {
      // TextRulerToolkit.logIf(TextRulerToolkit.DEBUG && pattern1.size()
      // == 0 || pattern2.size() == 0, "SpecialCaseWithZeroLength");
      result = getOptimizedGeneralizationsForRuleItemPatternsOfDistinctSize(pattern1, pattern2);
    }

    // if (TextRulerToolkit.DEBUG)
    // {
    // TextRulerToolkit.log("\t\tGeneralizations: "+result.size());
    // for (TextRulerRulePattern lggPattern : result)
    // TextRulerToolkit.log("\t\t\t"+lggPattern);
    // }

    return result;
  }

}
