/*
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 2 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with this program; if not, write to the Free Software
 *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

/*
 * Sequence.java
 * Copyright (C) 2007 Sebastian Beer
 *
 */

package weka.associations.gsp;

import weka.core.FastVector;
import weka.core.Instances;
import weka.core.RevisionHandler;
import weka.core.RevisionUtils;

import java.io.Serializable;
import java.util.Enumeration;

/**
 * Class representing a sequence of elements/itemsets.
 * 
 * @author  Sebastian Beer
 * @version $Revision: 1.2 $
 */
public class Sequence
  implements Cloneable, Serializable, RevisionHandler {

  /** for serialization */
  private static final long serialVersionUID = -5001018056339156390L;

  /** the support count of the Sequence */
  protected int m_SupportCount;
  
  /** ordered list of the comprised elements/itemsets */
  protected FastVector m_Elements;

  /**
   * Constructor.
   */
  public Sequence() {
    m_SupportCount = 0;
    m_Elements = new FastVector();
  }

  /**
   * Constructor accepting a set of elements as parameter.
   * 
   * @param elements 		the Elements of the Sequence
   */
  public Sequence(FastVector elements) {
    m_SupportCount = 0;
    m_Elements = elements;
  }

  /**
   * Constructor accepting an int value as parameter to set the support count.
   * 
   * @param supportCount 	the support count to set
   */
  public Sequence(int supportCount) {
    m_SupportCount = supportCount;
    m_Elements = new FastVector();
  }

  /**
   * Generates all possible candidate k-Sequences and prunes the ones that 
   * contain an infrequent (k-1)-Sequence.
   * 
   * @param kMinusOneSequences 	the set of (k-1)-Sequences, used for verification
   * @return 			the generated set of k-candidates
   * @throws CloneNotSupportedException
   */
  public static FastVector aprioriGen(FastVector kMinusOneSequences) throws CloneNotSupportedException {
    FastVector allCandidates = generateKCandidates(kMinusOneSequences);
    FastVector prunedCandidates = pruneCadidates(allCandidates, kMinusOneSequences);

    return prunedCandidates;
  }

  /**
   * Deletes Sequences of a given set which don't meet the minimum support 
   * count threshold.
   * 
   * @param sequences 		the set Sequences to be checked
   * @param minSupportCount 	the minimum support count
   * @return 			the set of Sequences after deleting
   */
  public static FastVector deleteInfrequentSequences(FastVector sequences, long minSupportCount) {
    FastVector deletedSequences = new FastVector();
    Enumeration seqEnum = sequences.elements();

    while (seqEnum.hasMoreElements()) {
      Sequence currentSeq = (Sequence) seqEnum.nextElement();
      long curSupportCount = currentSeq.getSupportCount();

      if (curSupportCount >= minSupportCount) {
	deletedSequences.addElement(currentSeq);
      }
    }
    return deletedSequences;
  }

  /**
   * Generates candidate k-Sequences on the basis of a given (k-1)-Sequence set.
   * 
   * @param kMinusOneSequences 	the set of (k-1)-Sequences
   * @return 			the set of candidate k-Sequences
   * @throws CloneNotSupportedException
   */
  protected static FastVector generateKCandidates(FastVector kMinusOneSequences) throws CloneNotSupportedException {
    FastVector candidates = new FastVector();
    FastVector mergeResult = new FastVector();

    for (int i = 0; i < kMinusOneSequences.size(); i++) {
      for (int j = 0; j < kMinusOneSequences.size(); j++) {
	Sequence originalSeq1 = (Sequence) kMinusOneSequences.elementAt(i);
	Sequence seq1 = originalSeq1.clone();
	Sequence originalSeq2 = (Sequence) kMinusOneSequences.elementAt(j);
	Sequence seq2 = originalSeq2.clone();
	Sequence subseq1 = seq1.deleteEvent("first");
	Sequence subseq2 = seq2.deleteEvent("last");

	if (subseq1.equals(subseq2)) {
	  //seq1 and seq2 are 1-sequences
	  if ((subseq1.getElements().size() == 0) && (subseq2.getElements().size() == 0)) {
	    if (i >= j) {
	      mergeResult = merge(seq1, seq2, true, true);
	    } else {
	      mergeResult = merge(seq1, seq2, true, false);
	    }
	    //seq1 and seq2 are k-sequences
	  } else {
	    mergeResult = merge(seq1, seq2, false, false);
	  }
	  candidates.appendElements(mergeResult);
	}
      }
    }
    return candidates;
  }

  /**
   * Merges two Sequences in the course of candidate generation. Differentiates 
   * between merging 1-Sequences and k-Sequences, k > 1.
   * 
   * @param seq1 		Sequence at first position
   * @param seq2 		Sequence at second position
   * @param oneElements 	true, if 1-Elements should be merged, else false
   * @param mergeElements 	true, if two 1-Elements were not already merged 
   * 				(regardless of their position), else false
   * @return 			set of resulting Sequences
   */
  protected static FastVector merge(Sequence seq1, Sequence seq2, boolean oneElements, boolean mergeElements) {
    FastVector mergeResult = new FastVector();

    //merge 1-sequences
    if (oneElements) {
      Element element1 = (Element) seq1.getElements().firstElement();
      Element element2 = (Element) seq2.getElements().firstElement();
      Element element3 = null;
      if (mergeElements) {
	for (int i = 0; i < element1.getEvents().length; i++) {
	  if (element1.getEvents()[i] > -1) {
	    if (element2.getEvents()[i] > -1) {
	      break;
	    } else {
	      element3 = Element.merge(element1, element2);
	    }
	  }
	}
      }
      FastVector newElements1 = new FastVector();
      //generate <{x}{y}>
      newElements1.addElement(element1);
      newElements1.addElement(element2);
      mergeResult.addElement(new Sequence(newElements1));
      //generate <{x,y}>
      if (element3 != null) {
	FastVector newElements2 = new FastVector();
	newElements2.addElement(element3);
	mergeResult.addElement(new Sequence(newElements2));
      }

      return mergeResult;
      //merge k-sequences, k > 1
    } else {
      Element lastElementSeq1 = (Element) seq1.getElements().lastElement();
      Element lastElementSeq2 = (Element) seq2.getElements().lastElement();
      Sequence resultSeq = new Sequence();
      FastVector resultSeqElements = resultSeq.getElements();

      //if last two events/items belong to the same element/itemset
      if (lastElementSeq2.containsOverOneEvent()) {
	for (int i = 0; i < (seq1.getElements().size()-1); i++) {
	  resultSeqElements.addElement(seq1.getElements().elementAt(i));
	}
	resultSeqElements.addElement(Element.merge(lastElementSeq1, lastElementSeq2));
	mergeResult.addElement(resultSeq);

	return mergeResult;
	//if last two events/items belong to different elements/itemsets
      } else {
	for (int i = 0; i < (seq1.getElements().size()); i++) {
	  resultSeqElements.addElement(seq1.getElements().elementAt(i));
	}
	resultSeqElements.addElement(lastElementSeq2);
	mergeResult.addElement(resultSeq);

	return mergeResult;
      }
    }
  }

  /**
   * Converts a set of 1-Elements into a set of 1-Sequences.
   * 
   * @param elements 		the set of 1-Elements
   * @return 			the set of 1-Sequences
   */
  public static FastVector oneElementsToSequences(FastVector elements) {
    FastVector sequences = new FastVector();
    Enumeration elementEnum = elements.elements();

    while (elementEnum.hasMoreElements()) {
      Sequence seq = new Sequence();
      FastVector seqElements = seq.getElements();
      seqElements.addElement(elementEnum.nextElement());
      sequences.addElement(seq);
    }
    return sequences;
  }

  /**
   * Prints a set of Sequences as String output.
   * 
   * @param setOfSequences	the set of sequences
   */
  public static void printSetOfSequences(FastVector setOfSequences) {
    Enumeration seqEnum = setOfSequences.elements();
    int i = 1;

    while(seqEnum.hasMoreElements()) {
      Sequence seq = (Sequence) seqEnum.nextElement();
      System.out.print("[" + i++ + "]" + " " + seq.toString());
    }
  }

  /**
   * Prunes a k-Sequence of a given candidate set if one of its (k-1)-Sequences 
   * is infrequent.
   * 
   * @param allCandidates 	the set of all potential k-Sequences
   * @param kMinusOneSequences 	the set of (k-1)-Sequences for verification
   * @return 			the set of the pruned candidates
   */
  protected static FastVector pruneCadidates(FastVector allCandidates, FastVector kMinusOneSequences) {
    FastVector prunedCandidates = new FastVector();
    boolean isFrequent;
    //for each candidate
    for (int i = 0; i < allCandidates.size(); i++) {
      Sequence candidate = (Sequence) allCandidates.elementAt(i);
      isFrequent = true;
      FastVector canElements = candidate.getElements();
      //generate each possible (k-1)-sequence and verify if it's frequent
      for (int j = 0; j < canElements.size(); j++) {
	if(isFrequent) {
	  Element origElement = (Element) canElements.elementAt(j);
	  int[] origEvents = origElement.getEvents();

	  for (int k = 0; k < origEvents.length; k++) {
	    if (origEvents[k] > -1) {
	      int helpEvent = origEvents[k];
	      origEvents[k] = -1;

	      if (origElement.isEmpty()) {
		canElements.removeElementAt(j);
		//check if the (k-1)-sequence is contained in the set of kMinusOneSequences
		int containedAt = kMinusOneSequences.indexOf(candidate);
		if (containedAt != -1) {
		  origEvents[k] = helpEvent;
		  canElements.insertElementAt(origElement, j);
		  break;
		} else {
		  isFrequent = false;
		  break;
		}
	      } else {
		//check if the (k-1)-sequence is contained in the set of kMinusOneSequences
		int containedAt = kMinusOneSequences.indexOf(candidate);
		if (containedAt != -1) {
		  origEvents[k] = helpEvent;
		  continue;
		} else {
		  isFrequent = false;
		  break;
		}
	      }
	    }
	  }
	} else {
	  break;
	}
      }
      if (isFrequent) {
	prunedCandidates.addElement(candidate);
      }
    }
    return prunedCandidates;
  }

  /**
   * Returns a String representation of a set of Sequences where the numeric 
   * value of each event/item is represented by its respective nominal value.
   * 
   * @param setOfSequences 	the set of Sequences
   * @param dataSet 		the corresponding data set containing the header 
   * 				information
   * @param filterAttributes	the attributes to filter out
   * @return 			the String representation
   */
  public static String setOfSequencesToString(FastVector setOfSequences, Instances dataSet, FastVector filterAttributes) {
    StringBuffer resString = new StringBuffer();
    Enumeration SequencesEnum = setOfSequences.elements();
    int i = 1;
    boolean printSeq;

    while(SequencesEnum.hasMoreElements()) {
      Sequence seq = (Sequence) SequencesEnum.nextElement();
      Integer filterAttr = (Integer) filterAttributes.elementAt(0);
      printSeq = true;

      if (filterAttr.intValue() != -1) {
	for (int j=0; j < filterAttributes.size(); j++) {
	  filterAttr = (Integer) filterAttributes.elementAt(j);
	  FastVector seqElements = seq.getElements();

	  if (printSeq) {
	    for (int k=0; k < seqElements.size(); k++) {
	      Element currentElement = (Element) seqElements.elementAt(k);
	      int[] currentEvents = currentElement.getEvents();

	      if (currentEvents[filterAttr.intValue()] != -1) {
		continue;
	      } else {
		printSeq = false;
		break;
	      }
	    }
	  }
	}
      }
      if (printSeq) {
	resString.append("[" + i++ + "]" + " " + seq.toNominalString(dataSet));
      }
    }
    return resString.toString();
  }

  /**
   * Updates the support count of a set of Sequence candidates according to a 
   * given set of data sequences.
   * 
   * @param candidates 		the set of candidates
   * @param dataSequences 	the set of data sequences
   */
  public static void updateSupportCount(FastVector candidates, FastVector dataSequences) {
    Enumeration canEnumeration = candidates.elements();

    while(canEnumeration.hasMoreElements()){
      Enumeration dataSeqEnumeration = dataSequences.elements();
      Sequence candidate = (Sequence) canEnumeration.nextElement();

      while(dataSeqEnumeration.hasMoreElements()) {
	Instances dataSequence = (Instances) dataSeqEnumeration.nextElement();

	if (candidate.isSubsequenceOf(dataSequence)) {
	  candidate.setSupportCount(candidate.getSupportCount() + 1);
	}
      }
    }
  }

  /**
   * Returns a deep clone of a Sequence.
   * 
   * @return 		the cloned Sequence
   */
  public Sequence clone() {
    try {
      Sequence clone = (Sequence) super.clone();

      clone.setSupportCount(m_SupportCount);
      FastVector cloneElements = new FastVector(m_Elements.size());

      for (int i = 0; i < m_Elements.size(); i++) {
	Element helpElement = (Element) m_Elements.elementAt(i);
	cloneElements.addElement(helpElement.clone());
      }
      clone.setElements(cloneElements);

      return clone;
    } catch (CloneNotSupportedException exc) {
      exc.printStackTrace();
    }
    return null;
  }

  /**
   * Deletes either the first or the last event/item of a Sequence. If the 
   * deleted event/item is the only value in the Element, it is removed, as well.
   * 
   * @param position 		the position of the event/item (first or last)
   * @return 			the Sequence with either the first or the last 
   * 				event/item deleted
   */
  protected Sequence deleteEvent(String position) {
    Sequence cloneSeq = clone();

    if (position.equals("first")) {
      Element element = (Element) cloneSeq.getElements().firstElement();
      element.deleteEvent("first");
      if (element.isEmpty()) {
	cloneSeq.getElements().removeElementAt(0);
      }
      return cloneSeq;
    }
    if (position.equals("last")) {
      Element element = (Element) cloneSeq.getElements().lastElement();
      element.deleteEvent("last");
      if (element.isEmpty()) {
	cloneSeq.getElements().removeElementAt(m_Elements.size()-1);
      }
      return cloneSeq;
    }
    return null;
  }

  /**
   * Checks if two Sequences are equal.
   * 
   * @return 			true, if the two Sequences are equal, else false
   */
  public boolean equals(Object obj) {
    Sequence seq2 = (Sequence) obj;
    FastVector seq2Elements = seq2.getElements();

    for (int i = 0; i < m_Elements.size(); i++) {
      Element thisElement = (Element) m_Elements.elementAt(i);
      Element seq2Element = (Element) seq2Elements.elementAt(i);
      if (!thisElement.equals(seq2Element)) {
	return false;
      }
    }
    return true;
  }

  /**
   * Returns the Elements of the Sequence.
   * 
   * @return 			the Elements
   */
  protected FastVector getElements() {
    return m_Elements;
  }

  /**
   * Returns the support count of the Sequence.
   * 
   * @return 			the support count
   */
  protected int getSupportCount() {
    return m_SupportCount;
  }

  /**
   * Checks if the Sequence is subsequence of a given data sequence.
   * 
   * @param dataSequence 	the data sequence to verify against
   * @return 			true, if the Sequnce is subsequence of the data 
   * 				sequence, else false
   */
  protected boolean isSubsequenceOf(Instances dataSequence) {
    FastVector elements = getElements();
    Enumeration elementEnum = elements.elements();
    Element curElement = (Element) elementEnum.nextElement();

    for (int i = 0; i < dataSequence.numInstances(); i++) {
      if (curElement.isContainedBy(dataSequence.instance(i))) {
	if (!elementEnum.hasMoreElements()) {
	  return true;
	} else {
	  curElement = (Element) elementEnum.nextElement();
	  continue;
	}
      }
    }
    return false;
  }

  /**
   * Sets the Elements of the Sequence.
   * 
   * @param elements 		the Elements to set
   */
  protected void setElements(FastVector elements) {
    m_Elements = elements;
  }

  /**
   * Sets the support count of the Sequence.
   * 
   * @param supportCount 	the support count to set
   */
  protected void setSupportCount(int supportCount) {
    m_SupportCount = supportCount;
  }

  /**
   * Returns a String representation of a Sequences where the numeric value 
   * of each event/item is represented by its respective nominal value.
   * 
   * @param dataSet 		the corresponding data set containing the header 
   * 				information
   * @return 			the String representation
   */
  public String toNominalString(Instances dataSet) {
    String result = "";

    result += "<";

    for (int i = 0; i < m_Elements.size(); i++) {
      Element element = (Element) m_Elements.elementAt(i);
      result += element.toNominalString(dataSet);
    }
    result += "> (" + getSupportCount() + ")\n";

    return result;
  }

  /**
   * Returns a String representation of a Sequence.
   * 
   * @return 			the String representation
   */
  public String toString() {
    String result = "";

    result += "Sequence Output\n";
    result += "------------------------------\n";
    result += "Support Count: " + getSupportCount() + "\n";
    result += "contained elements/itemsets:\n";

    for (int i = 0; i < m_Elements.size(); i++) {
      Element element = (Element) m_Elements.elementAt(i);
      result += element.toString();
    }
    result += "\n\n";

    return result;
  }
  
  /**
   * Returns the revision string.
   * 
   * @return		the revision
   */
  public String getRevision() {
    return RevisionUtils.extract("$Revision: 1.2 $");
  }
}
