/*
 * $Id: ClusternAverage.java,v 1.5 2006/08/10 15:24:10 marbobo Exp $
 *
 * Copyright (c) Siemens AG 2008 
 *           (c) Universität Paderborn 2008 
 * Licensed under EUPL 1.1. 
 *
 * $Log: ClusternAverage.java,v $
 * Revision 1.5  2006/08/10 15:24:10  marbobo
 * + Bugfix (einige Dokumente wurden nicht angezeigt)
 *
 * Revision 1.4  2006/07/31 07:21:16  lawern
 * Überarbeitung
 *
 */
package vkc.clusterer;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import vkc.db.entities.VKCCategory;

public class ClusternAverage extends Clustern {
    
    public ClusternAverage(VKCCategory category, int weightMode, Integer maxKeywords, boolean termIntersection) {
        super(category, weightMode, maxKeywords, termIntersection);
    }
   
    protected void pairCluster(HeapEntry entry)  {
        Integer  idClusterLeft = entry.getClusterA();
        Integer  idClusterRight = entry.getClusterB();
        
        
        ClusteringItem leftClusteringItem = new ClusteringItem();
        ClusteringItem rightClusteringItem = new ClusteringItem();
        
        //Hole beide ClusterItems aus allCluster
        leftClusteringItem  = (ClusteringItem)allCluster.get(idClusterLeft);
        rightClusteringItem = (ClusteringItem)allCluster.get(idClusterRight);
        
        
	    ClusteringItem newClusteringItem = null;

	    //*******************************************************************************************
        // 								Vereinigung im Dendogram
        //*******************************************************************************************
	    // Füge Cluster im Dendogram zusammen, falls Schnittmenge der Dokumententerme nicht leer 
        HashSet lc = new HashSet( Arrays.asList(leftClusteringItem.getTerms().toArray(new TermEntry[0])));
        HashSet rc = new HashSet( Arrays.asList(rightClusteringItem.getTerms().toArray(new TermEntry[0])));
        lc.retainAll(Arrays.asList(rc.toArray(new TermEntry[0])));
        
        boolean executeClustering = true;
        
        if (CLUSTER_WITH_TERM_INTERSECTION) {
            executeClustering = !lc.isEmpty();
        } else {
            executeClustering = true;
        }
        
        if (executeClustering) {
	        ///////////
	        // Fall-1:  Beide Cluster haben keine SubCluster und mindestens ein Cluster ist Ein-Documentig
	        /////////// 
		    if (rightClusteringItem.isMultipleDocumentWithoutSubcluster() && leftClusteringItem.isSingleDocumentWithoutSubcluster() ||
		        rightClusteringItem.isSingleDocumentWithoutSubcluster() && leftClusteringItem.isMultipleDocumentWithoutSubcluster() ||
		        rightClusteringItem.isSingleDocumentWithoutSubcluster() && leftClusteringItem.isSingleDocumentWithoutSubcluster()) {
		        
		        // Das rechte Cluster stammt aus der Menge Unclustered 
	            if ((leftClusteringItem.getParentID().intValue() == -1 || leftClusteringItem.getParentID().intValue() == 0) && rightClusteringItem.getParentID().intValue() == 0) {
	                
	                // hole vater-Knoten
	                ClusteringItem parent = (ClusteringItem)allCluster.get(rightClusteringItem.getParentID());
	                
	                if (leftClusteringItem.getParentID().intValue() == 0) {
		                // aktualisiere Betrag getRecursivDocCounts von Parent
		                parent.setRecursivDocCounts(parent.getRecursivDocCounts() - (leftClusteringItem.getRecursivDocCounts() + rightClusteringItem.getRecursivDocCounts()));
		                parent.getRecursivDocumentIds().removeAll(leftClusteringItem.getRecursivDocumentIds());
		                parent.getRecursivDocumentIds().removeAll(rightClusteringItem.getRecursivDocumentIds());
	                } else {
		                // aktualisiere Betrag getRecursivDocCounts von Parent
		                parent.setRecursivDocCounts(parent.getRecursivDocCounts() - rightClusteringItem.getRecursivDocCounts());
		                parent.getRecursivDocumentIds().removeAll(rightClusteringItem.getRecursivDocumentIds());
	                }
	                
	                // Lösche beide Knote aus de Liste der SubCluster
	                parent.getSubCluster().remove(leftClusteringItem.getClusterID());
	                parent.getSubCluster().remove(rightClusteringItem.getClusterID());
	                
	                //füge DocumentIds von clusterRight an clusterLeft
			        leftClusteringItem.getDocumentIds().addAll(rightClusteringItem.getDocumentIds());

			        //füge recursivDocumentIds von clusterRight an clusterLeft
			        leftClusteringItem.getRecursivDocumentIds().addAll(rightClusteringItem.getRecursivDocumentIds());
			        
			        //hänge Dokumente von clusterRight an clusterLeft 
			        leftClusteringItem.getDocuments().addAll(rightClusteringItem.getDocuments());
			        
			        // aktualisiere die Anzahl der Dokumente von clusterLeft
		            leftClusteringItem.setRecursivDocCounts(leftClusteringItem.getRecursivDocCounts() + rightClusteringItem.getRecursivDocCounts());
		            
		            //Bilde Schnittmenge der Terme
		            HashSet a = leftClusteringItem.getTerms();
		            HashSet b = rightClusteringItem.getTerms();
		            a.retainAll(Arrays.asList(b.toArray(new TermEntry[0])));
		                   
		            // Lösche clusterRight
			        allCluster.remove(rightClusteringItem.getClusterID());
		            
			        // hänger ItemLeft an die Wurzel  
			        leftClusteringItem.setParentID(new Integer(-1));
			        
			        ClusteringItem root = (ClusteringItem)allCluster.get(leftClusteringItem.getParentID());
		            root.getSubCluster().add(leftClusteringItem.getClusterID());
		            
	            } else if (leftClusteringItem.getParentID().intValue() == 0 && rightClusteringItem.getParentID().intValue() == -1) {
	                
	                // Vertausche itemLeft und itemRight
	                ClusteringItem temp = leftClusteringItem;
	                leftClusteringItem = rightClusteringItem;
	                rightClusteringItem = temp;
	                
	                ClusteringItem parent = (ClusteringItem)allCluster.get(rightClusteringItem.getParentID());
	                
	                // aktualisiere Betrag getRecursivDocCounts von Parent
		            parent.setRecursivDocCounts(parent.getRecursivDocCounts() - rightClusteringItem.getRecursivDocCounts());
	                
		            parent.getRecursivDocumentIds().removeAll(rightClusteringItem.getRecursivDocumentIds());
	                
	                // Lösche beide Knote aus de Liste der SubCluster
	                parent.getSubCluster().remove(leftClusteringItem.getClusterID());
	                parent.getSubCluster().remove(rightClusteringItem.getClusterID());
	                
	                //füge DocumentIds von clusterRight an clusterLeft
			        leftClusteringItem.getDocumentIds().addAll(rightClusteringItem.getDocumentIds());
			        
			        //füge recursivDocumentIds von clusterRight an clusterLeft
			        leftClusteringItem.getRecursivDocumentIds().addAll(rightClusteringItem.getRecursivDocumentIds());

			        //hänge Dokumente von clusterRight an clusterLeft 
			        leftClusteringItem.getDocuments().addAll(rightClusteringItem.getDocuments());
			        
			        // aktualisiere die Anzahl der Dokumente von clusterLeft
		            leftClusteringItem.setRecursivDocCounts(leftClusteringItem.getRecursivDocCounts() + rightClusteringItem.getRecursivDocCounts());
		            
		            // Bilde Schnittmenge der Terme
		            HashSet al = leftClusteringItem.getTerms();
		            HashSet br = rightClusteringItem.getTerms();
		            al.retainAll(Arrays.asList(br.toArray(new TermEntry[0])));
		                       
		            // Lösche clusterRight
			        allCluster.remove(rightClusteringItem.getClusterID());
		            
			        // hänger ItemLeft an die Wurzel  
			        leftClusteringItem.setParentID(new Integer(-1));
			        
			        ClusteringItem root = (ClusteringItem)allCluster.get(leftClusteringItem.getParentID());
		            root.getSubCluster().add(leftClusteringItem.getClusterID());
	            }
	        //////////
		    // Fall-2:Cluster A ist EinDokumentig und ohne Subcluster
		    ///////// Cluster B ist MehrDokumentig und/oder hat Subcluster 
		    ///////// => Füge Inhalt Cluster A zu Cluster B und lösche Cluster A
	        /////////
	        } else if (rightClusteringItem.isSingleDocumentWithoutSubcluster() || leftClusteringItem.isSingleDocumentWithoutSubcluster()) {
	        	if (rightClusteringItem.isSingleDocumentWithoutSubcluster()) {
				    newClusteringItem = leftClusteringItem;
	        	} else {
				    newClusteringItem = rightClusteringItem;
	        	}

		        //füge recursivDocumentIds von clusterRight an clusterLeft
		        newClusteringItem.getRecursivDocumentIds().addAll(leftClusteringItem.getRecursivDocumentIds());
		        newClusteringItem.getRecursivDocumentIds().addAll(rightClusteringItem.getRecursivDocumentIds());

		        // Anzahl der Dokumente im neuen Cluster= Summe der Anzahl der Dokumente beider Kinder
			    newClusteringItem.setRecursivDocCounts(leftClusteringItem.getRecursivDocCounts() + rightClusteringItem.getRecursivDocCounts());
			    
			    newClusteringItem.getDocumentIds().addAll(leftClusteringItem.getDocumentIds());
			    newClusteringItem.getDocumentIds().addAll(rightClusteringItem.getDocumentIds());
			    
			    newClusteringItem.getDocuments().addAll(leftClusteringItem.getDocuments());
			    newClusteringItem.getDocuments().addAll(rightClusteringItem.getDocuments());

		        //Entferne EinDokumentiges Cluster A und aktualisiere Elterncluster entsprechend
			    //Beim ElternCluster A verringere Dokumentenanzahl um Cluster A wenn ElternCluster A != Root
			    //Beim ElternCluster B erhöhe Dokumentanzahl um Cluster A wenn ElternCluster B != Root
	        	if (rightClusteringItem.isSingleDocumentWithoutSubcluster()) {
				    ClusteringItem parentOfItemRight = (ClusteringItem)allCluster.get(rightClusteringItem.getParentID());
		            
				    if (parentOfItemRight.getClusterID().intValue() != -1) {
					    parentOfItemRight.setRecursivDocCounts(parentOfItemRight.getRecursivDocCounts() - rightClusteringItem.getRecursivDocCounts());
				    }
				    
				    parentOfItemRight.getSubCluster().remove(rightClusteringItem.getClusterID());
		            
		            ClusteringItem parentOfItemLeft = (ClusteringItem)allCluster.get(leftClusteringItem.getParentID());

		            if (parentOfItemLeft.getClusterID().intValue() != -1) {
		                parentOfItemLeft.setRecursivDocCounts(parentOfItemLeft.getRecursivDocCounts() + rightClusteringItem.getRecursivDocCounts());
				    }
	        	//Gespiegelter Fall
	        	} else {
				    ClusteringItem parentOfItemLeft = (ClusteringItem)allCluster.get(leftClusteringItem.getParentID());
		            
				    if (parentOfItemLeft.getClusterID().intValue() != -1) {
					    parentOfItemLeft.setRecursivDocCounts(parentOfItemLeft.getRecursivDocCounts() - leftClusteringItem.getRecursivDocCounts());
				    }
				    
				    parentOfItemLeft.getSubCluster().remove(leftClusteringItem.getClusterID());
		            
		            ClusteringItem parentOfItemRight = (ClusteringItem)allCluster.get(rightClusteringItem.getParentID());

		            if (parentOfItemRight.getClusterID().intValue() != -1) {
		                parentOfItemRight.setRecursivDocCounts(parentOfItemRight.getRecursivDocCounts() + leftClusteringItem.getRecursivDocCounts());
				    }
	        	}

	            // Bilde Schnittmenge der Terme
		        HashSet al = new HashSet(Arrays.asList(leftClusteringItem.getTerms().toArray(new TermEntry[0])));
		        HashSet br = new HashSet(Arrays.asList(rightClusteringItem.getTerms().toArray(new TermEntry[0])));
		        al.retainAll(Arrays.asList(br.toArray(new TermEntry[0])));
	            newClusteringItem.getTerms().addAll(Arrays.asList(al.toArray(new TermEntry[0])));
		    //////////
			// Fall-3:beide Cluster sind MehrDocumentig und/ oder haben Subcluster => Erzeuge neune Knoten im Dendogram
		    /////////
	        } else {
	            // erzeuge neuen Knoten mit neuem ID
			    newClusteringItem = new ClusteringItem();
			    
			    // vergebe neuen Cluster-ID
			    newClusteringItem.setClusterID(new Integer(unique_ID++));
			    
			    // neuer Knoten bekommt HeapID vom linken Kind 
			    newClusteringItem.setHeapID(leftClusteringItem.getHeapID());
			    
			    // Setze linkes und rechtes Kind 
			    newClusteringItem.addSubCluster(leftClusteringItem.getClusterID());
			    newClusteringItem.addSubCluster(rightClusteringItem.getClusterID());
			    
			    // Hänge neuen Knoten an root mit ID == -1
			    newClusteringItem.setParentID(new Integer(-1));
			    
		        //füge recursivDocumentIds von clusterRight an clusterLeft
		        newClusteringItem.getRecursivDocumentIds().addAll(leftClusteringItem.getRecursivDocumentIds());
		        newClusteringItem.getRecursivDocumentIds().addAll(rightClusteringItem.getRecursivDocumentIds());

		        // Anzahl der Dokumente im neuen Cluster= Summe der Anzahl der Dokumente beider Kinder
			    newClusteringItem.setRecursivDocCounts(leftClusteringItem.getRecursivDocCounts() + rightClusteringItem.getRecursivDocCounts());

			    ClusteringItem parentOfItemRight = (ClusteringItem)allCluster.get(rightClusteringItem.getParentID());
	            
			    if (parentOfItemRight.getClusterID().intValue() != -1) {
				    parentOfItemRight.setRecursivDocCounts(parentOfItemRight.getRecursivDocCounts() - rightClusteringItem.getRecursivDocCounts());
			    }

			    parentOfItemRight.getSubCluster().remove(rightClusteringItem.getClusterID());
	            
	            ClusteringItem parentOfItemLeft = (ClusteringItem)allCluster.get(leftClusteringItem.getParentID());

	            if (parentOfItemLeft.getClusterID().intValue() != -1) {
	                parentOfItemLeft.setRecursivDocCounts(parentOfItemLeft.getRecursivDocCounts() - leftClusteringItem.getRecursivDocCounts());
			    }

	            parentOfItemLeft.getSubCluster().remove(leftClusteringItem.getClusterID());
	            
	            ClusteringItem root = (ClusteringItem)allCluster.get(newClusteringItem.getParentID());
	            root.getSubCluster().add(newClusteringItem.getClusterID());
			    
	            leftClusteringItem.setParentID(newClusteringItem.getClusterID());
			    rightClusteringItem.setParentID(newClusteringItem.getClusterID());
	
	            // Bilde Schnittmenge der Terme
		        HashSet al = new HashSet( Arrays.asList(leftClusteringItem.getTerms().toArray(new TermEntry[0])));
		        HashSet br = new HashSet( Arrays.asList(rightClusteringItem.getTerms().toArray(new TermEntry[0])));
		        al.retainAll(Arrays.asList(br.toArray(new TermEntry[0])));
			    //newClusteringItem.getTerms().retainAll(Arrays.asList(rightClusteringItem.getTerms().toArray(new TermEntry[0])));
	            newClusteringItem.getTerms().addAll(Arrays.asList(al.toArray(new TermEntry[0])));
	          
	            allCluster.put(newClusteringItem.getClusterID(), newClusteringItem);
	    	    heapIds.add(newClusteringItem.getClusterID());
	        }
	    } 
	    
	    //*******************************************************************************************
        // 								AvarageLink Algorithmus
        //*******************************************************************************************
	   
	    // heapIds verwaltet Id's der Cluster, die für Clustering zur Verfügung stehen
    	for (Iterator it = heapIds.iterator(); it.hasNext();) {
    	    Integer index = (Integer)it.next();
    	   
    	    // Der index darf weder mit dem rechten noch mit dem linken Cluster-ID übereinstimmen
    	    if (!idClusterLeft.equals(index) && !idClusterRight.equals(index)){
	            
	            // Berechne HeapIndex für beide Entries (itemLeft,index) und (itemRight,Index)
	    	    int idxHeapEntry1 = this.getHeapIndex(leftClusteringItem.getHeapID().intValue(), index.intValue());
	    	    int idxHeapEntry2 = this.getHeapIndex(rightClusteringItem.getHeapID().intValue(), index.intValue());
	            
	            // beide Elemente müssen im Heap vorhanden sein
	            if (indexedHeap.isMapped(idxHeapEntry1) && indexedHeap.isMapped(idxHeapEntry2)) {
	                HeapEntry entry1 = (HeapEntry) indexedHeap.get(idxHeapEntry1) ;
	                HeapEntry entry2 = (HeapEntry) indexedHeap.get(idxHeapEntry2) ;
	            
	                double sim1 = entry1.getSim() ;
	                double sim2 = entry2.getSim();
	                int sizeRight = rightClusteringItem.getRecursivDocCounts();
	                int sizeLeft = leftClusteringItem.getRecursivDocCounts();
	                
	                //UPGMA
	                //double sim =  ((sizeLeft* sim1)/(sizeLeft + sizeRight)) +  ((sizeRight * sim2)/(sizeLeft + sizeRight)); 
	                double sim =  ((sizeRight* sim1)/(sizeLeft + sizeRight)) +  ((sizeRight * sim2)/(sizeLeft + sizeRight));	                
	                // c1 ist ClusterID
	                Integer c1 = entry1.getClusterA().equals(leftClusteringItem.getClusterID()) ? entry1.getClusterB() : entry1.getClusterA();
	                
	                if (newClusteringItem != null) {
	                    // actualisiere Heap HeapIds,ClusterIDs und Similarity
	                    indexedHeap.update(idxHeapEntry1, new HeapEntry(newClusteringItem.getHeapID(), index, newClusteringItem.getClusterID(), c1, sim));
	                } else {
	                    indexedHeap.update(idxHeapEntry1, new HeapEntry(leftClusteringItem.getHeapID(), index, leftClusteringItem.getClusterID(), c1, sim));
	                }
	                
	                indexedHeap.delete(idxHeapEntry2);
	            } 
    	    }
    	}

    	heapIds.remove(rightClusteringItem.getHeapID());
    }
}