/*
 * The_xmloperator_project Software License, Version 1.7
 *
 * Copyright (c) 2000 - 2003 The_xmloperator_project.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * 3. The end-user documentation included with the redistribution,
 *    if any, must include the following acknowledgment:
 *      "This product includes or uses software developped
 *       by The_xmloperator_project (http://www.xmloperator.net/)."
 *    Alternately, this acknowledgment may appear in the software itself,
 *    if and wherever such third-party acknowledgments normally appear.
 *
 * 4. Products derived from this software may not be called "xmloperator",
 *    nor may "xmloperator" appear in their name, without prior written
 *    permission. For written permission, please contact
 *    the xmloperator project administrator.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED.  IN NO EVENT SHALL THE_XMLOPERATOR_PROJECT OR
 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 * ====================================================================
 *
 * Further information can be found on the project's site
 * (http://www.xmloperator.net/).
 */
package xmltorng.i2s.impl;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Collections;
import java.util.Set;
import java.util.HashSet;
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;

import xmltorng.framework.document.relaxng.Name;
import xmltorng.framework.document.relaxng.Pattern;
import xmltorng.framework.document.relaxng.NonEmptyPattern;
import xmltorng.i2s.framework.RepeatableName;
import xmltorng.i2s.framework.PatternCategory;
import xmltorng.i2s.framework.ChoicePatternCategory;
import xmltorng.i2s.framework.GroupPatternCategory;
import xmltorng.i2s.framework.AttributesPatternCategory;
import xmltorng.i2s.util.PatternFactory;
import xmltorng.i2s.util.NNIntMatrix;
import xmltorng.i2s.impl.OptionalRepeatableElementPatternCategory;
import xmltorng.i2s.impl.AttributesPatternCategoryImpl;

/**
 * A group pattern category is a pattern category for group patterns
 *   whose child patterns are supported by the choice pattern category
 *   or choice patterns whose child patterns are such group patterns.
 * May also contain attributes and/or text.
 *
 * Formally :
 * attribute ::= <attribute name="QName"> <text/> </attribute>
 * attributes ::= attribute | (<group> attribute+ </group>)
 * element ::= <element name="QName"> any </element>
 * oneOrMoreElement ::= element | (<oneOrMore> element </oneOrMore>)
 *   | (<choice> (element* & (<oneOrMore> element </oneOrMore>)+) </choice>)
 * zerorOrMoreElement ::= oneOrMoreElement
 *   | (<optional> oneOrMoreElement </optional>)
 * group ::= zeroOrMoreElement | (<group> zeroOrMoreElement+ </group>)
 * choice ::= group | (<choice> group+ </choice>)
 * elementsAndText ::= choice | (<interleave> choice <text/> </interleave>)
 * content ::= elementsAndText
 *   | (<group> attributes elementsAndText </group>)
 *
 * Additional constraint : an element with a given name may appear at most in
 *   one child pattern.
 */
public final class GroupPatternCategoryImpl implements GroupPatternCategory {
  private static final boolean DEBUG = false;
  private AttributesPatternCategory attributesPatternCategory;
  private boolean hasText = false;
  private int patternCount = 0;
  private final Map fromElementNameToElementUsage = new HashMap();
  private final List elementNameList = new ArrayList();
  private final NNIntMatrix constraintMatrix = new NNIntMatrix();

  static private final class ElementUsage {
    public boolean isRepeatable = false;
    public int usageCount = 0;
      // The element is optional if and only if usageCount < patternCount.
  }

  public GroupPatternCategoryImpl() {
    attributesPatternCategory = new AttributesPatternCategoryImpl();
  }

  public GroupPatternCategoryImpl(
      AttributesPatternCategory attributesPatternCategory, boolean hasText) {
    this.attributesPatternCategory = attributesPatternCategory;
    this.hasText = hasText;
  }

  public GroupPatternCategoryImpl(
      ChoicePatternCategory patternCategory,
      AttributesPatternCategory attributesPatternCategory, boolean hasText) {
    Map fromElementNameToRepeatable =
        patternCategory.fromElementNameToRepeatable();
    this.addNames(fromElementNameToRepeatable,
                  patternCategory.isPatternOptional());
    this.patternCount += fromElementNameToRepeatable.size();
    this.attributesPatternCategory = attributesPatternCategory;
    this.hasText = hasText;
  }

  private void addNames(Map fromElementNameToRepeatable, boolean isOptional) {
    Iterator iterator = fromElementNameToRepeatable.keySet().iterator();
    while (iterator.hasNext()) {
      Name name = (Name)iterator.next();
      ElementUsage elementUsage =
          (ElementUsage)this.fromElementNameToElementUsage.get(name);
      if (elementUsage == null)
        elementUsage = this.addElementName(name);
      if (!isOptional)
        elementUsage.usageCount++;
      if (((Boolean)fromElementNameToRepeatable.get(name)).booleanValue())
        elementUsage.isRepeatable = true;
    }
  }

  private ElementUsage addElementName(Name elementName) {
    ElementUsage elementUsage = new ElementUsage();
    this.fromElementNameToElementUsage.put(elementName, elementUsage);
    this.elementNameList.add(elementName);
    this.constraintMatrix.setDimension(this.elementNameList.size());
    return elementUsage;
  }

  public AttributesPatternCategory attributesPatternCategory() {
    return attributesPatternCategory;
  }

  public boolean hasText() {
    return hasText;
  }

  /////////////////////////////////
  // PatternCategory implementation
  /////////////////////////////////

  public Pattern fullPattern(Map fromNameToElementDefinition) {
    int nameCount = this.elementNameList.size();
    if (nameCount == 0)
      return null;
    int[] groupIndexes = new int[nameCount];
    int groupCount =
        this.constraintMatrix.collectConnectedElements(groupIndexes);
    if (DEBUG) {
      for (int k = 0; k < nameCount; k++) {
        System.out.print(" ");
        System.out.print(((Name)this.elementNameList.get(k)).getName());
      }
      System.out.println();
      for (int k1 = 0; k1 < nameCount; k1++) {
        for (int k2 = 0; k2 < nameCount; k2++) {
          System.out.print(" ");
          System.out.print(this.constraintMatrix.get(k1, k2));
        }
        System.out.println();
      }
      System.out.print("groups:");
      for (int k = 0; k < groupIndexes.length; k++) {
        System.out.print(' ');
        System.out.print(groupIndexes[k]);
      }
      System.out.println();
    }
    NonEmptyPattern[] groupPatterns = new NonEmptyPattern[groupCount];
    int elementNameIndex = 0;
    for (int groupIndex = 1; groupIndex <= groupCount; groupIndex++) {
      while (groupIndexes[elementNameIndex] == 0)
        elementNameIndex++;
      // Build a ChoicePatternCategory list
      List choicePatternCategoryList = new ArrayList();
      if (!this.completeChoicePatternCategoryList(
          choicePatternCategoryList, groupIndexes, elementNameIndex))
        return null; // Contradictory constraint.
      // Build the group pattern.
      List patternList = new ArrayList();
      if (DEBUG)
        System.out.print('(');
      for (int k = 0; k < choicePatternCategoryList.size(); k++) {
        ChoicePatternCategory choicePatternCategory =
                   (ChoicePatternCategory)choicePatternCategoryList.get(k);
        if (DEBUG) {
          if (k != 0)
            System.out.print(" , ");
          System.out.print(choicePatternCategory);
        }
        NonEmptyPattern childPattern =
            (NonEmptyPattern)choicePatternCategory.fullPattern(
            fromNameToElementDefinition);
        if (childPattern == null)
          throw new RuntimeException("Null full pattern");
        patternList.add(childPattern);
      }
      if (DEBUG)
        System.out.println(')');
      NonEmptyPattern groupPattern;
      int patternCount = patternList.size();
      if (patternCount == 1)
        groupPattern = (NonEmptyPattern)patternList.get(0);
      else {
        NonEmptyPattern[] patterns = new NonEmptyPattern[patternCount];
        patternList.toArray(patterns);
        groupPattern = PatternFactory.group(patterns);
      }
      groupPatterns[groupIndex - 1] = groupPattern;
    }
    NonEmptyPattern pattern = groupCount == 1 ? groupPatterns[0] :
        PatternFactory.choice(groupPatterns, false);
    if (this.hasText)
      pattern = PatternFactory.interleave(
          new NonEmptyPattern[] {pattern, PatternFactory.textPattern()});
    Pattern attributesPattern = this.attributesPatternCategory.fullPattern();
    return attributesPattern.isEmpty() ? pattern :
        PatternFactory.group(
        new NonEmptyPattern[] {(NonEmptyPattern)attributesPattern, pattern});
  }

  private boolean completeChoicePatternCategoryList(
      List choicePatternCategoryList, int[] groupIndexes, int elementNameIndex) {
    groupIndexes[elementNameIndex] = 0;
    Name elementName = (Name)elementNameList.get(elementNameIndex);
    ElementUsage elementUsage =
        (ElementUsage)this.fromElementNameToElementUsage.get(elementName);
    int index1 = -1;
    int index2 = choicePatternCategoryList.size();
    for (int k = 0; k < elementNameList.size(); k++) {
      // name could be added to choicePatternCategoryList.get(index)
      //   with index1 < index < index2
      int constraint = this.constraintMatrix.get(elementNameIndex, k);
      if (constraint != 0) {
        Name comparedName = (Name)elementNameList.get(k);
        int index =
            choicePatternCategoryIndex(choicePatternCategoryList, comparedName);
        if (index >= 0) {
          if (constraint < 0) {
            // name > comparedName
            if (index > index1)
              index1 = index;
          }
          else if (constraint > 0) {
            // name < comparedName
            if (index < index2)
              index2 = index;
          }
        }
      }
    }
    if (DEBUG)
      System.out.println("Limit indexes for \"" + elementName.getName() + "\": "
    + index1 + " " + index2);
    if (index1 >= index2)
      return false; // Contradictory constraint.
    if (index1 + 1 == index2) {
      // A new ChoicePatternCategory must be inserted between
      //   choicePatternCategoryList.get(index1) and
      //   choicePatternCategoryList.get(index2)
      choicePatternCategoryList.add(
          index2,
          new OptionalRepeatableElementPatternCategory(
          elementName, elementUsage.isRepeatable,
          elementUsage.usageCount != this.patternCount));
    }
    else {
      // name can be added to choicePatternCategoryList.get(index)
      //   with index1 < index < index2
      index1++;
      index2--;
      boolean isOptional = elementUsage.usageCount != this.patternCount;
      int index =  choicePatternCategoryIndex(
          choicePatternCategoryList, index1, index2, isOptional);
      if (index < 0)
        index =  choicePatternCategoryIndex(
            choicePatternCategoryList, index1, index2, !isOptional);
      OptionalRepeatableElementPatternCategory choicePatternCategory =
          (OptionalRepeatableElementPatternCategory)
          choicePatternCategoryList.get(index);
      choicePatternCategory.addElementName(
          elementName, elementUsage.isRepeatable);
      if (isOptional)
        choicePatternCategory.setPatternOptional(true);
    }
    for (int k = 0; k < this.elementNameList.size(); k++)
      if (groupIndexes[k] != 0
        && this.constraintMatrix.get(elementNameIndex, k) != 0
        && !this.completeChoicePatternCategoryList(
        choicePatternCategoryList, groupIndexes, k))
      return false;
    return true;
  }

  private static final int choicePatternCategoryIndex(
      List choicePatternCategoryList, Name elementName) {
    for (int k = 0; k < choicePatternCategoryList.size(); k++)
      if (((ChoicePatternCategory)choicePatternCategoryList.get(k)).
          fromElementNameToRepeatable().get(elementName) != null)
        return k;
    return -1;
  }

  private static final int choicePatternCategoryIndex(
      List choicePatternCategoryList, int index1, int index2,
      boolean isOptional) {
    for (int k = index1; k <= index2; k++)
      if (((ChoicePatternCategory)choicePatternCategoryList.get(k)).
          isPatternOptional() == isOptional)
        return k;
    return -1;
  }

  public boolean addPattern(
      Name[] attributeNames, boolean hasText,
      RepeatableName[] repeatableElementNames) {
    Set nameSet = new HashSet();
    int previousIndex = -1;
    for (int k = 0; k < repeatableElementNames.length; k++) {
      RepeatableName repeatableElementName = repeatableElementNames[k];
      Name elementName = repeatableElementName.getName();
      if (!nameSet.add(elementName))
        return false; // Circuit.
      int index;
      ElementUsage elementUsage =
          (ElementUsage)this.fromElementNameToElementUsage.get(elementName);
      if (elementUsage == null) {
        index = this.elementNameList.size();
        elementUsage = this.addElementName(elementName);
      }
      else
        index = this.elementNameList.indexOf(elementName);
      elementUsage.usageCount++;
      if (repeatableElementName.isRepeatable())
        elementUsage.isRepeatable = true;
      if (previousIndex >= 0) {
        if (this.constraintMatrix.get(previousIndex, index) < 0)
          return false; // Contradictory constraint.
        this.constraintMatrix.setAntisymetricaly(previousIndex, index, +1);
      }
      previousIndex = index;
    }
    this.patternCount++;
    if (hasText)
      this.hasText = true;
    this.attributesPatternCategory.addAttributeNames(attributeNames);
    return true;
  }

  //////////////////////////////////////
  // GroupPatternCategory implementation
  //////////////////////////////////////

  public Set elementNameSet() {
    return Collections.unmodifiableSet(
        this.fromElementNameToElementUsage.keySet());
  }

  public boolean isRepeatable(Name elementName) {
    return ((ElementUsage)this.fromElementNameToElementUsage.get(elementName)).
        isRepeatable;
  }

  public boolean isOptional(Name elementName) {
    return ((ElementUsage)this.fromElementNameToElementUsage.get(elementName)).
        usageCount < this.patternCount;
  }
}
