import java.util.*;

public class APriori {
  // Umsetzung zwischen Produktnamen <-> Nummern
  private HashMap<String, Integer> product2id;
  private HashMap<Integer, String> id2product;
  // Anzahl der bisher bekannten Produkte
  private int productCount = 0; 

  // Die Verkaufstransaktionen -- Jede Transaktion ist ein sortiertes int-Array!
  private LinkedList<int[]> transactions = new LinkedList<int[]>();

  // Die frequent itemsets -- Die einzelnen int-Arrays sind sortiert!
  // Die Variable frequentItemsets speichert die frequent itemsets
  // gruppiert in LinkedLists nach der Anzahl der Einträge. 
  private LinkedList<LinkedList<int[]>> frequentItemsets = 
    new LinkedList<LinkedList<int[]>>();

  // Konstruktor mit Angabe der Schätzung der Anzahl der verschiedenen
  // Produkte
  public APriori(int numberProducts) {
    product2id = new HashMap<String, Integer>(numberProducts);
    id2product = new HashMap<Integer, String>(numberProducts);
  }

  // Umsetzen von einem Produkt in eine Zahl; ist ein Produkt bisher
  // nicht bekannt, bekommt es eine neue Nummer.
  private int getMapping(String productName) {
    if (product2id.containsKey(productName))
      return product2id.get(productName);
    else {
      product2id.put(productName, productCount);
      id2product.put(productCount, productName);
      productCount++;
      return productCount-1;
    } 
  }

  // Umsetzen von einer Zahl in ein Produkt
  private String getMapping(int id) {
    return id2product.get(id);
  }

  // Hinzufügen einer Verkaufstransaktion -- wir gehen davon aus, 
  // dass die Daten schon gereinigt sind und keine Duplikate vorkommen!
  public void addTransaction(String... products) {
    int[] transaction = new int[products.length];
    int i = 0;

    // Konvertieren der Liste von Produkten in ein int-Array
    for (String product : products)
      transaction[i++] = getMapping(product);

    Arrays.sort(transaction);
    transactions.add(transaction);
  }
  
  // Berechnen der frequent itemsets
  public void calculateFrequentItemsets(int minsupp) {
    // Die Liste der frequent itemsets der aktuellen Iteration
    LinkedList<int[]> currentItemset = new LinkedList<int[]>();
    frequentItemsets.add(currentItemset);

    // Zuerst die einelementigen frequent itemsets bestimmen
    int[] support = new int[productCount];

    // Alle Produkte aller Transaktionen durchlaufen und entsprechenden 
    // Support inkrementieren.
    for (int[] transaction : transactions)
      for (int product : transaction)
        support[product]++;

    // Die frequent items suchen und in currentItemset einfügen.
    for (int i = 0; i < productCount; i++)
      if (support[i] >= minsupp)
        currentItemset.add(new int[]{i});
    
    // Iterieren, bis keine neuen frequent itemsets mehr gefunden werden.
    do {
      // Die frequent itemsets der letzten Iteration jeweils um ein
      // frequent item erweitern.
      currentItemset = expandItemsets(currentItemset);
      frequentItemsets.add(currentItemset);

      // Für jedes frequent itemset einen Zähler anlegen.
      support = new int[currentItemset.size()];
      int[] itemset = null;

      // Für jede Transaktion überprüfen, welche frequent itemsets
      // sie enthält und die entsprechenden Zähler inkrementieren.
      for (int[] transaction : transactions) {
        int pos = -1;
        for (Iterator itr = currentItemset.iterator(); itr.hasNext(); ) {
          itemset = (int[])itr.next(); pos++;
          if (contains(transaction, itemset)) {
            support[pos]++;
          }
        }
      }

      // Die frequent itemsets der aktuellen Iteration durchlaufen und
      // alle, die minsupp nicht erfüllen, verwerfen.
      int pos = -1;
      for (Iterator itr = currentItemset.iterator(); itr.hasNext(); ) {
        itemset = (int[])itr.next(); pos++;
        if (support[pos] < minsupp)
          itr.remove();
      }
    } while (!currentItemset.isEmpty());
  }

  // Bestimmt, ob das sortierte Array a1 die Elemente des sortierten Arrays a2
  // beinhaltet. Vorgehensweise ähnlich zu Merge-Join.
  private boolean contains(int[] a1, int[] a2) {
    int pos_a1 = 0;
    int pos_a2 = 0;

    if (a1.length < a2.length)
      return false;

    do {
      if (a1[pos_a1] < a2[pos_a2]) {
        pos_a1++;
      } else {
        if (a1[pos_a1] == a2[pos_a2]) {
          pos_a1++; pos_a2++;
        } else {
          return false;
        }
      }
    } while (pos_a2 != a2.length && pos_a1 != a1.length);

    if (pos_a2 == a2.length)
      return true;
    else
      return false;
  }

  // Generiert aus den frequent itemsets mit k Elementen die mit k+1 Elementen
  private LinkedList<int[]> expandItemsets(LinkedList<int[]> oldItemsets) {
    LinkedList<int[]> newItemsets = new LinkedList<int[]>();
    LinkedList<int[]> frequentItems = frequentItemsets.get(0);
    int[] newItemset = null;

    // Bilde aus alten itemsets mit k Elementen die neuen itemsets mit k+1 Elementen
    for (int[] itemset : oldItemsets) {
      // Für jedes alte itemset mit k Elementen überprüfen, mit welchen einelementigen 
      // itemsets es erweitert werden kann.
      for (int [] item : frequentItems) {
        // Item zu itemset nur hinzufügen, wenn das item größer ist, als
        // alle Elemente des itemsets. Da dies sortiert ist, ist das letzte Element
        // das größte. Diese Vorgehensweise verhindert die Generierung von
        // Duplikaten bei den itemsets.
        if (itemset[itemset.length-1] < item[0]) {
          newItemset = new int[itemset.length + 1];
          System.arraycopy(itemset, 0, newItemset, 0, itemset.length);
          newItemset[itemset.length] = item[0];
          newItemsets.add(newItemset);
        }
      }
    }

    return newItemsets;
  }
  
  // Ausgabe der frequent itemsets
  public void printFrequentItemsets() {
    StringBuffer buf = new StringBuffer();

    for (LinkedList<int[]> iteration : frequentItemsets) {
      for (int[] itemset : iteration) {
        for (int item : itemset) {
          buf.append(getMapping(item) + ", ");
        }
        // das letzte Komma wieder löschen ;-)
        buf.delete(buf.length()-2, buf.length());
        buf.append("\n");
      }
      buf.append("------------------------------\n");
    }
    
    System.out.println(buf);
  }

  // Testroutine
  public static void main(String[] args) {
    APriori ap = new APriori(20);
    
    ap.addTransaction("Drucker", "Papier", "PC", "Toner");
    ap.addTransaction("PC", "Scanner");
    ap.addTransaction("Drucker", "Papier", "Toner");
    ap.addTransaction("Drucker", "PC");
    ap.addTransaction("Drucker", "Papier", "PC", "Scanner", "Toner");
    ap.calculateFrequentItemsets(3);
    ap.printFrequentItemsets();
  } 
  
}