/**
 * Copyright (c) 2013 Source Auditor Inc.
 * Copyright (c) 2013 Black Duck Software Inc.
 *
 *   Licensed 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.spdx.compare;

import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

import org.spdx.rdfparser.InvalidSPDXAnalysisException;
import org.spdx.rdfparser.SPDXCreatorInformation;
import org.spdx.rdfparser.SPDXReview;
import org.spdx.rdfparser.SpdxPackageVerificationCode;
import org.spdx.rdfparser.license.AnyLicenseInfo;
import org.spdx.rdfparser.license.ExtractedLicenseInfo;
import org.spdx.rdfparser.model.Annotation;
import org.spdx.rdfparser.model.Checksum;
import org.spdx.rdfparser.model.ExternalDocumentRef;
import org.spdx.rdfparser.model.RdfModelObject;
import org.spdx.rdfparser.model.Relationship;
import org.spdx.rdfparser.model.SpdxDocument;
import org.spdx.rdfparser.model.SpdxElement;
import org.spdx.rdfparser.model.SpdxFile;
import org.spdx.rdfparser.model.SpdxItem;
import org.spdx.rdfparser.model.SpdxPackage;
import org.spdx.rdfparser.model.SpdxSnippet;

import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
import com.google.common.collect.Sets;

/**
 * Performs a comparison between two or more SPDX documents and holds the results of the comparison
 * The main function to perform the comparison is <code>compare(spdxdoc1, spdxdoc2)</code>
 *
 * For reviewers, the comparison results are separated into unique reviewers for a give document
 * which can be obtained by the method <code>getUniqueReviewers(index1, index2)</code>.  The
 * uniqueness is determined by the reviewer name.  If two documents contain reviewers with the
 * same name but different dates or comments, the reviews are considered to be the same review
 * with different data.  The differences for these reviews can be obtained through the method
 * <code>getReviewerDifferences(index1, index2)</code>
 *
 * For files, the comparison results are separated into unique files based on the file names
 * which can be obtained by the method <code>getUniqueFiles(index1, index2)</code>.  If two
 * documents contain files with the same name, but different data, the differences for these
 * files can be obtained through the method <code>getFileDifferences(index1, index2)</code>
 *
 * Multi-threading considerations: This class is "mostly" threadsafe in that the calls to
 * perform the comparison are synchronized and a flag is used to throw an error for any
 * calls to getters when a compare is in progress.  There is a small theoretical window in the
 * getters where the compare operation is started in the middle of a get operation.
 *
 * @author Gary O'Neall
 *
 */
public class SpdxComparer {

	/**
	 * Contains the results of a comparison between two SPDXReviews where
	 * the reviewer name is the same but there is a difference in the
	 * reviewer comment or the reviewer date
	 * @author Gary O'Neall
	 *
	 */
	public static class SPDXReviewDifference {

		boolean commentsEqual;
		boolean datesEqual;
		String comment1;
		String comment2;
		String date1;
		String date2;
		String reviewer;

		/**
		 * @param spdxReview
		 * @param spdxReview2
		 */
		public SPDXReviewDifference(SPDXReview spdxReview,
				SPDXReview spdxReview2) {
			commentsEqual = spdxReview.getComment().trim().equals(spdxReview2.getComment().trim());
			datesEqual = spdxReview.getReviewDate().equals(spdxReview2.getReviewDate());
			this.comment1 = spdxReview.getComment();
			this.comment2 = spdxReview2.getComment();
			this.date1 = spdxReview.getReviewDate();
			this.date2 = spdxReview2.getReviewDate();
			this.reviewer = spdxReview.getReviewer();
		}

		/**
		 * @return true of the dates are equal
		 */
		public boolean isDateEqual() {
			return this.datesEqual;
		}

		/**
		 * @return
		 */
		public String getReviewer() {
			return this.reviewer;
		}

		/**
		 * Get the reviewer date for one of the two reviews compared
		 * @param i if 0, the review date of the first reviewer, if 1, it is the second reviewer
		 * @return
		 * @throws SpdxCompareException
		 */
		public String getDate(int i) throws SpdxCompareException {
			if (i == 0) {
				return this.date1;
			} else if (i == 1) {
				return this.date2;
			} else {
				throw(new SpdxCompareException("Invalid index for get reviewer date"));
			}
		}

		/**
		 * @return true if comments are equal
		 */
		public boolean isCommentEqual() {
			return this.commentsEqual;
		}

		/**
		 * Get the reviewer comment for one of the two reviews compared
		 * @param i if 0, the review date of the first reviewer, if 1, it is the second reviewer
		 * @return
		 * @throws SpdxCompareException
		 */
		public String getComment(int i) throws SpdxCompareException {
			if (i == 0) {
				return this.comment1;
			} else if (i == 1) {
				return this.comment2;
			} else {
				throw(new SpdxCompareException("Invalid index for get reviewer date"));
			}
		}

	}



	private SpdxDocument[] spdxDocs = null;
	private boolean differenceFound = false;
	private boolean compareInProgress = false;

	// Document level results
	private boolean spdxVersionsEqual = true;
	private boolean documentCommentsEqual = true;
	private boolean dataLicenseEqual = true;
	private boolean licenseListVersionEquals = true;
	private boolean documentContentsEquals = true;

	// Reviewer results
	/**
	 * Holds a map of all SPDX documents which have reviewers unique relative to other SPDX document
	 * based on the reviewer name.  The results of the map is another map of all SPDX documents in
	 * the comparison which do not contain some of the reviewers in the key document.  See the
	 * implementation of compareReviewers for details
	 */
	private Map<SpdxDocument, Map<SpdxDocument, SPDXReview[]>> uniqueReviews = Maps.newHashMap();

	/**
	 * Holds a map of any SPDX documents which have reviewer differenes.  A reviewer difference
	 * is an SPDXReview with the same reviewer name but a different reviewer date or comment
	 */
	private Map<SpdxDocument, Map<SpdxDocument, SPDXReviewDifference[]>> reviewerDifferences = Maps.newHashMap();

	// Extracted Licensing Info results
	/**
	 * Holds a map of all SPDX documents which have extracted license infos unique relative to other SPDX document
	 * based on the reviewer name.  The results of the map is another map of all SPDX documents in
	 * the comparison which do not contain some of the reviewers in the key document.  See the
	 * implementation of compareReviewers for details
	 */
	private Map<SpdxDocument, Map<SpdxDocument, ExtractedLicenseInfo[]>> uniqueExtractedLicenses = Maps.newHashMap();
	/**
	 * Map of any SPDX documents that have extraced license infos with equivalent text but different comments, id's or other fields
	 */
	private Map<SpdxDocument, Map<SpdxDocument, SpdxLicenseDifference[]>> licenseDifferences = Maps.newHashMap();
	/**
	 * Maps the license ID's for the extracted license infos of the documents being compared.  License ID's are mapped based on the text
	 * being equivalent
	 */
	private Map<SpdxDocument, Map<SpdxDocument, Map<String, String>>> extractedLicenseIdMap = Maps.newHashMap();

	private boolean creatorInformationEquals;

	private Map<SpdxDocument, Map<SpdxDocument, String[]>> uniqueCreators = Maps.newHashMap();

	// file compare results
	/**
	 * Holds a map of all SPDX documents which have files unique relative to other SPDX document
	 * based on the file name.  The results of the map is another map of all SPDX documents in
	 * the comparison which do not contain some of the files in the key document.  See the
	 * implementation of compareFiles for details
	 */
	private Map<SpdxDocument, Map<SpdxDocument, SpdxFile[]>> uniqueFiles = Maps.newHashMap();

	/**
	 * Holds a map of any SPDX documents which have file differences.  A file difference
	 * is an SPDXReview with the same filename name but a different file property
	 */
	private Map<SpdxDocument, Map<SpdxDocument, SpdxFileDifference[]>> fileDifferences = Maps.newHashMap();

	// Package compare results
	/**
	 * Holds a map of all SPDX documents which have packages unique relative to other SPDX document
	 * based on the package name and package version.  The results of the map is another map of all SPDX documents in
	 * the comparison which do not contain some of the packages in the key document.  See the
	 * implementation of comparePackages for details
	 */
	private Map<SpdxDocument, Map<SpdxDocument, SpdxPackage[]>> uniquePackages = Maps.newHashMap();

	/**
	 * Map of package names to package comparisons
	 */
	private Map<String, SpdxPackageComparer> packageComparers = Maps.newHashMap();

	// Annotation comparison results
	private Map<SpdxDocument, Map<SpdxDocument, Annotation[]>> uniqueDocumentAnnotations = Maps.newHashMap();

	// Document Relationships comparison results
	private Map<SpdxDocument, Map<SpdxDocument, Relationship[]>> uniqueDocumentRelationships = Maps.newHashMap();

	// External Document References comparison results
	private Map<SpdxDocument, Map<SpdxDocument, ExternalDocumentRef[]>> uniqueExternalDocumentRefs = Maps.newHashMap();

	// Snippet references comparison results
	private Map<SpdxDocument, Map<SpdxDocument, SpdxSnippet[]>> uniqueSnippets = Maps.newHashMap();
	private Map<String, SpdxSnippetComparer>  snippetComparers = Maps.newHashMap();

	public SpdxComparer() {

	}

	/**
	 * Compares 2 SPDX documents
	 * @param spdxDoc1
	 * @param spdxDoc2
	 * @throws InvalidSPDXAnalysisException
	 * @throws SpdxCompareException
	 */
	public void compare(SpdxDocument spdxDoc1, SpdxDocument spdxDoc2) throws InvalidSPDXAnalysisException, SpdxCompareException {
		compare(new SpdxDocument[] {spdxDoc1, spdxDoc2});
	}

	/**
	 * Compares multiple SPDX documents
	 * @param spdxDocuments
	 * @throws SpdxCompareException
	 * @throws InvalidSPDXAnalysisException
	 */
	public synchronized void compare(SpdxDocument[] spdxDocuments) throws InvalidSPDXAnalysisException, SpdxCompareException {
		//TODO: Add a monitor function which allows for cancel
		clearCompareResults();
		this.spdxDocs = spdxDocuments;
		differenceFound = false;
		performCompare();
	}

	/**
	 * @throws InvalidSPDXAnalysisException
	 * @throws SpdxCompareException
	 *
	 */
	private void performCompare() throws InvalidSPDXAnalysisException, SpdxCompareException {
		compareInProgress = true;
		differenceFound = false;
		compareExtractedLicenseInfos();	// note - this must be done first to build the translation map of IDs
		compareDocumentFields();
		compareSnippets();
		compareFiles();
		comparePackages();
		compareReviewers();
		compareCreators();
		compareDocumentAnnotations();
		compareDocumentRelationships();
		compareExternalDocumentRefs();
		compareInProgress = false;
	}

	/**
	 * Compare the snippets in the documents
	 * @throws SpdxCompareException
	 */
	private void compareSnippets() throws SpdxCompareException {
		// This will be a complete NXN comparison of all documents filling in the uniqueSnippets map
		if (this.spdxDocs == null || this.spdxDocs.length < 1) {
			return;
		}
		this.uniqueSnippets.clear();
		this.snippetComparers.clear();
		// N x N comparison of all snippets
		for (int i = 0; i < spdxDocs.length; i++) {
			List<SpdxSnippet> snippetsA;
			try {
				snippetsA = spdxDocs[i].getDocumentContainer().findAllSnippets();
			} catch (InvalidSPDXAnalysisException e) {
				throw(new SpdxCompareException("Error collecting snippets from SPDX document "+spdxDocs[i].getName(), e));
			}
			// note - the snippet arrays MUST be sorted for the comparator methods to work
			Collections.sort(snippetsA);
			addSnippetComparers(spdxDocs[i], snippetsA, this.extractedLicenseIdMap);
			Map<SpdxDocument, SpdxSnippet[]> uniqueAMap = this.uniqueSnippets.get(spdxDocs[i]);
			if (uniqueAMap == null) {
				uniqueAMap = Maps.newHashMap();
			}
			for (int j = 0; j < spdxDocs.length; j++) {
				if (j == i) {
					continue;
				}
				List<SpdxSnippet> snippetsB;
				try {
					snippetsB = spdxDocs[j].getDocumentContainer().findAllSnippets();
				} catch (InvalidSPDXAnalysisException e) {
					throw(new SpdxCompareException("Error collecting snippets from SPDX document "+spdxDocs[i].getName(), e));
				}
				//Note that the files arrays must be sorted for the find methods to work
				Collections.sort(snippetsB);
				SpdxSnippet[] uniqueAB = findUniqueSnippets(snippetsA, snippetsB);
				if (uniqueAB != null && uniqueAB.length > 0) {
					uniqueAMap.put(spdxDocs[j], uniqueAB);
				}
			}
			if (!uniqueAMap.isEmpty()) {
				this.uniqueSnippets.put(spdxDocs[i], uniqueAMap);
			}
		}
		if (!_isSnippetsEqualsNoCheck()) {
			this.differenceFound = true;
		}
	}

	/**
	 * @param snippetsA
	 * @param snippetsB
	 * @return
	 */
	private SpdxSnippet[] findUniqueSnippets(List<SpdxSnippet> snippetsA,
			List<SpdxSnippet> snippetsB) {
		int bIndex = 0;
		int aIndex = 0;
		List<SpdxSnippet> alRetval = Lists.newArrayList();
		while (aIndex < snippetsA.size()) {
			if (bIndex >= snippetsB.size()) {
				alRetval.add(snippetsA.get(aIndex));
				aIndex++;
			} else {
				int compareVal = snippetsA.get(aIndex).compareTo(snippetsB.get(bIndex));
				if (compareVal == 0) {
					// snippets are equal
					aIndex++;
					bIndex++;
				} else if (compareVal > 0) {
					// snippetsA is greater than snippetsB
					bIndex++;
				} else {
					// snippetsB is greater than snippetsA
					alRetval.add(snippetsA.get(aIndex));
					aIndex++;
				}
			}
		}
		return alRetval.toArray(new SpdxSnippet[alRetval.size()]);
	}

	/**
	 * @param spdxDocument
	 * @param snippets
	 * @param extractedLicenseIdMap2
	 * @throws SpdxCompareException
	 */
	private void addSnippetComparers(
			SpdxDocument spdxDocument,
			List<SpdxSnippet> snippets,
			Map<SpdxDocument, Map<SpdxDocument, Map<String, String>>> extractedLicenseIdMap2) throws SpdxCompareException {
		for (SpdxSnippet snippet:snippets) {
			SpdxSnippetComparer comparer = this.snippetComparers.get(snippet.toString());
			if (comparer == null) {
				comparer = new SpdxSnippetComparer(extractedLicenseIdMap);
				this.snippetComparers.put(snippet.toString(), comparer);
			}
			comparer.addDocumentSnippet(spdxDocument, snippet);
		}
	}

	/**
	 * @throws InvalidSPDXAnalysisException
	 *
	 */
	private void compareExternalDocumentRefs() throws InvalidSPDXAnalysisException {
		// this will be a N x N comparison of all external document relationships to fill the
		// hashmap uniqueExternalDocumentRefs
		for (int i = 0; i < spdxDocs.length; i++) {
			ExternalDocumentRef[] externalDocRefsA = spdxDocs[i].getExternalDocumentRefs();
			Map<SpdxDocument, ExternalDocumentRef[]> uniqueAMap = uniqueExternalDocumentRefs.get(spdxDocs[i]);
			if (uniqueAMap == null) {
				uniqueAMap = Maps.newHashMap();
				// We will put this into the hashmap at the end of this method if it is not empty
			}
			for (int j = 0; j < spdxDocs.length; j++) {
				if (j == i) {
					continue;	// skip comparing to ourself
				}
				ExternalDocumentRef[] externalDocRefsB = spdxDocs[j].getExternalDocumentRefs();

				// find any external refs in A that are not in B
				ExternalDocumentRef[] uniqueA = findUniqueExternalDocumentRefs(externalDocRefsA, externalDocRefsB);
				if (uniqueA != null && uniqueA.length > 0) {
					uniqueAMap.put(spdxDocs[j], uniqueA);
				}
			}
			if (uniqueAMap.keySet().size() > 0) {
				this.uniqueExternalDocumentRefs.put(spdxDocs[i], uniqueAMap);
			}
		}
		if (!this._isExternalDcoumentRefsEqualsNoCheck()) {
			this.differenceFound = true;
		}
	}

	/**
	 * Compare all of the document level relationships
	 */
	private void compareDocumentRelationships() {
		// this will be a N x N comparison of all document level relationships to fill the
		// hashmap uniqueDocumentRelationships
		for (int i = 0; i < spdxDocs.length; i++) {
			Relationship[] relationshipsA = spdxDocs[i].getRelationships();
			Map<SpdxDocument, Relationship[]> uniqueAMap = uniqueDocumentRelationships.get(spdxDocs[i]);
			if (uniqueAMap == null) {
				uniqueAMap = Maps.newHashMap();
				// We will put this into the hashmap at the end of this method if it is not empty
			}
			for (int j = 0; j < spdxDocs.length; j++) {
				if (j == i) {
					continue;	// skip comparing to ourself
				}
				Relationship[] relationshipsB = spdxDocs[j].getRelationships();

				// find any creators in A that are not in B
				Relationship[] uniqueA = findUniqueRelationships(relationshipsA, relationshipsB);
				if (uniqueA != null && uniqueA.length > 0) {
					uniqueAMap.put(spdxDocs[j], uniqueA);
				}
			}
			if (uniqueAMap.keySet().size() > 0) {
				this.uniqueDocumentRelationships.put(spdxDocs[i], uniqueAMap);
			}
		}
		if (!this._isDocumentRelationshipsEqualsNoCheck()) {
			this.differenceFound = true;
		}
	}

	/**
	 * Compare all of the Document level annotations
	 */
	private void compareDocumentAnnotations() {
		// this will be a N x N comparison of all document level annotations to fill the
		// hashmap uniqueAnnotations
		for (int i = 0; i < spdxDocs.length; i++) {
			Annotation[] annotationsA = spdxDocs[i].getAnnotations();
			Map<SpdxDocument, Annotation[]> uniqueAMap = uniqueDocumentAnnotations.get(spdxDocs[i]);
			if (uniqueAMap == null) {
				uniqueAMap = Maps.newHashMap();
				// We will put this into the hashmap at the end of this method if it is not empty
			}
			for (int j = 0; j < spdxDocs.length; j++) {
				if (j == i) {
					continue;	// skip comparing to ourself
				}
				Annotation[] annotationsB = spdxDocs[j].getAnnotations();

				// find any creators in A that are not in B
				Annotation[] uniqueA = findUniqueAnnotations(annotationsA, annotationsB);
				if (uniqueA != null && uniqueA.length > 0) {
					uniqueAMap.put(spdxDocs[j], uniqueA);
				}
			}
			if (uniqueAMap.keySet().size() > 0) {
				this.uniqueDocumentAnnotations.put(spdxDocs[i], uniqueAMap);
			}
		}
		if (!this._isDocumentAnnotationsEqualsNoCheck()) {
			this.differenceFound = true;
		}
	}

	/**
	 * @throws InvalidSPDXAnalysisException
	 * @throws SpdxCompareException
	 *
	 */
	private void compareFiles() throws InvalidSPDXAnalysisException, SpdxCompareException {
		this.uniqueFiles.clear();
		this.fileDifferences.clear();
		// N x N comparison of all files
		for (int i = 0; i < spdxDocs.length; i++) {
			SpdxFile[] filesA = collectAllFiles(spdxDocs[i]);
			// note - the file arrays MUST be sorted for the comparator methods to work
			Arrays.sort(filesA);
			Map<SpdxDocument, SpdxFile[]> uniqueAMap = this.uniqueFiles.get(spdxDocs[i]);
			if (uniqueAMap == null) {
				uniqueAMap = Maps.newHashMap();
			}
			// this map will be added to uniqueFiles at the end if we find anything
			Map<SpdxDocument, SpdxFileDifference[]> diffMap = this.fileDifferences.get(spdxDocs[i]);
			if (diffMap == null) {
				diffMap = Maps.newHashMap();
			}
			for (int j = 0; j < spdxDocs.length; j++) {
				if (j == i) {
					continue;
				}
				SpdxFile[] filesB = collectAllFiles(spdxDocs[j]);
				//Note that the files arrays must be sorted for the find methods to work
				Arrays.sort(filesB);
				SpdxFile[] uniqueAB = findUniqueFiles(filesA, filesB);
				if (uniqueAB != null && uniqueAB.length > 0) {
					uniqueAMap.put(spdxDocs[j], uniqueAB);
				}
				SpdxFileDifference[] differences = findFileDifferences(spdxDocs[i], spdxDocs[j], filesA, filesB, this.extractedLicenseIdMap);
				if (differences != null && differences.length > 0) {
					diffMap.put(spdxDocs[j], differences);
				}
			}
			if (!uniqueAMap.isEmpty()) {
				this.uniqueFiles.put(spdxDocs[i], uniqueAMap);
			}
			if (!diffMap.isEmpty()) {
				this.fileDifferences.put(spdxDocs[i], diffMap);
			}
		}
		if (!_isFilesEqualsNoCheck()) {
			this.differenceFound = true;
		}
	}

	/**
	 * Add all files found in the related elements (including descendant related elements)
	 * @param element
	 * @param files
	 * @throws InvalidSPDXAnalysisException
	 */
	private void addAllRelatedFiles(SpdxElement element, Set<SpdxFile> files,
			Set<SpdxElement> visitedElements) throws InvalidSPDXAnalysisException {
		if (element == null || visitedElements.contains(element)) {
			return;
		}
		visitedElements.add(element);
		Relationship[] relationships = element.getRelationships();
		if (relationships != null) {
			for (int j = 0; j < relationships.length; j++) {
				if (relationships[j] != null &&
						relationships[j].getRelatedSpdxElement() instanceof SpdxFile &&
						!files.contains(relationships[j].getRelatedSpdxElement())) {
					files.add((SpdxFile)(relationships[j].getRelatedSpdxElement()));
				} else if (relationships[j] != null &&
						relationships[j].getRelatedSpdxElement() instanceof SpdxPackage) {
					SpdxFile[] pkgFiles = ((SpdxPackage)(relationships[j].getRelatedSpdxElement())).getFiles();
					if (pkgFiles != null) {
						for (int k = 0; k < pkgFiles.length; k++) {
							files.add(pkgFiles[k]);
						}
					}
				}
				// recursively add all of the related files to this relationships
				addAllRelatedFiles(relationships[j].getRelatedSpdxElement(), files, visitedElements);
			}
		}
	}

	/**
	 * Add all packages found in the related elements (including descendant related elements)
	 * @param element
	 * @param pkgs
	 * @throws InvalidSPDXAnalysisException
	 */
	private void addAllRelatedPackages(SpdxElement element,
			Set<SpdxPackage> pkgs,
			Set<SpdxElement> visitedElements) throws InvalidSPDXAnalysisException {
		if (element == null || visitedElements.contains(element)) {
			return;
		}
		visitedElements.add(element);
		Relationship[] relationships = element.getRelationships();
		if (relationships != null) {
			for (int j = 0; j < relationships.length; j++) {
				if (relationships[j] != null &&
						relationships[j].getRelatedSpdxElement() instanceof SpdxPackage &&
						!pkgs.contains(relationships[j].getRelatedSpdxElement())) {
					pkgs.add((SpdxPackage)(relationships[j].getRelatedSpdxElement()));
				}
				// recursively add all of the related files to this relationships
				addAllRelatedPackages(relationships[j].getRelatedSpdxElement(),
						pkgs, visitedElements);
			}
		}
	}

	/**
	 * Collect all of the packages present in the SPDX document including packages
	 * embedded in other relationships within documents
	 * @param spdxDocument
	 * @return
	 * @throws InvalidSPDXAnalysisException
	 */
	protected SpdxPackage[] collectAllPackages(SpdxDocument spdxDocument) throws InvalidSPDXAnalysisException {
		Set<SpdxPackage> retval = Sets.newHashSet();
		SpdxItem[] items = spdxDocument.getDocumentDescribes();
		for (int i = 0; i < items.length; i++) {
			if (items[i] instanceof SpdxPackage) {
				retval.add((SpdxPackage)items[i]);
			}
			addAllRelatedPackages(items[i], retval, Sets.<SpdxElement>newHashSet());
		}
		return retval.toArray(new SpdxPackage[retval.size()]);
	}

	/**
	 * Collect all of the files present in the SPDX document including files within documents
	 * and files embedded in packages
	 * @param spdxDocument
	 * @return
	 * @throws InvalidSPDXAnalysisException
	 */
	protected SpdxFile[] collectAllFiles(SpdxDocument spdxDocument) throws InvalidSPDXAnalysisException {
		Set<SpdxFile> retval = Sets.newHashSet();
		SpdxItem[] items = spdxDocument.getDocumentDescribes();
		for (int i = 0; i < items.length; i++) {
			if (items[i] instanceof SpdxFile) {
				retval.add((SpdxFile)items[i]);
			} else if (items[i] instanceof SpdxPackage) {
				SpdxFile[] pkgFiles = ((SpdxPackage)items[i]).getFiles();
				for (int j = 0; j < pkgFiles.length; j++) {
					retval.add(pkgFiles[j]);
				}
			}
			addAllRelatedFiles(items[i], retval, Sets.<SpdxElement>newHashSet());
		}
		return retval.toArray(new SpdxFile[retval.size()]);
	}

	/**
	 * Returns an array of files differences between A and B where the names
	 * are the same, but one or more properties are different for that file
	 * @param filesA
	 * @param filesB
	 * @return
	 * @throws SpdxCompareException
	 */
	static SpdxFileDifference[] findFileDifferences(SpdxDocument docA, SpdxDocument docB,
			SpdxFile[] filesA, SpdxFile[] filesB,
			Map<SpdxDocument, Map<SpdxDocument, Map<String, String>>> licenseIdXlationMap) throws SpdxCompareException {

		List<SpdxFileDifference> alRetval = Lists.newArrayList();
		int aIndex = 0;
		int bIndex = 0;
		while (aIndex < filesA.length && bIndex < filesB.length) {
			int compare = filesA[aIndex].getName().compareTo(filesB[bIndex].getName());
			if (compare == 0) {
				SpdxFileComparer fileComparer = new SpdxFileComparer(licenseIdXlationMap);
				fileComparer.addDocumentFile(docA, filesA[aIndex]);
				fileComparer.addDocumentFile(docB, filesB[bIndex]);
				if (fileComparer.isDifferenceFound()) {
					alRetval.add(fileComparer.getFileDifference(docA, docB));
				}
				aIndex++;
				bIndex++;
			} else if (compare > 0) {
				// fileA is greater than fileB
				bIndex++;
			} else {
				// fileB is greater than fileA
				aIndex++;
			}
		}
		SpdxFileDifference[] retval = alRetval.toArray(new SpdxFileDifference[alRetval.size()]);
		return retval;
	}

	/**
	 * finds any packages in A that are not in B.  Packages are considered the
	 * same if they have the same package name and the same package version.
	 * NOTE: The arrays must be sorted by file name
	 * @param pkgsA
	 * @param pkgsB
	 * @return
	 */
	static SpdxPackage[] findUniquePackages(SpdxPackage[] pkgsA, SpdxPackage[] pkgsB) {
		int bIndex = 0;
		int aIndex = 0;
		List<SpdxPackage> alRetval = Lists.newArrayList();
		while (aIndex < pkgsA.length) {
			if (bIndex >= pkgsB.length) {
				alRetval.add(pkgsA[aIndex]);
				aIndex++;
			} else {
				int compareVal = pkgsA[aIndex].compareTo(pkgsB[bIndex]);
				if (compareVal == 0) {
					// packages are equal
					aIndex++;
					bIndex++;
				} else if (compareVal > 0) {
					// pkgA is greater than pkgB
					bIndex++;
				} else {
					// pkgB is greater than pkgA
					alRetval.add(pkgsA[aIndex]);
					aIndex++;
				}
			}
		}
		SpdxPackage[] retval = alRetval.toArray(new SpdxPackage[alRetval.size()]);
		return retval;
	}
	/**
	 * finds any files in A that are not in B.  NOTE: The arrays must be sorted by file name
	 * @param filesA
	 * @param filesB
	 * @return
	 */
	static SpdxFile[] findUniqueFiles(SpdxFile[] filesA, SpdxFile[] filesB) {
		int bIndex = 0;
		int aIndex = 0;
		List<SpdxFile> alRetval = Lists.newArrayList();
		while (aIndex < filesA.length) {
			if (bIndex >= filesB.length) {
				alRetval.add(filesA[aIndex]);
				aIndex++;
			} else {
				int compareVal = filesA[aIndex].getName().compareTo(filesB[bIndex].getName());
				if (compareVal == 0) {
					// files are equal
					aIndex++;
					bIndex++;
				} else if (compareVal > 0) {
					// fileA is greater than fileB
					bIndex++;
				} else {
					// fileB is greater tha fileA
					alRetval.add(filesA[aIndex]);
					aIndex++;
				}
			}
		}
		SpdxFile[] retval = alRetval.toArray(new SpdxFile[alRetval.size()]);
		return retval;
	}

	/**
	 * @throws InvalidSPDXAnalysisException
	 *
	 */
	private void compareCreators() throws InvalidSPDXAnalysisException {
		this.creatorInformationEquals = true;
		this.licenseListVersionEquals = true;
		// this will be a N x N comparison of all creators to fill the
		// hashmap uniqueCreators
		for (int i = 0; i < spdxDocs.length; i++) {
			SPDXCreatorInformation creatorInfoA = spdxDocs[i].getCreationInfo();
			String[] creatorsA = creatorInfoA.getCreators();
			Map<SpdxDocument, String[]> uniqueAMap = uniqueCreators.get(spdxDocs[i]);
			if (uniqueAMap == null) {
				uniqueAMap = Maps.newHashMap();
				// We will put this into the hashmap at the end of this method if it is not empty
			}
			for (int j = 0; j < spdxDocs.length; j++) {
				if (j == i) {
					continue;	// skip comparing to ourself
				}
				SPDXCreatorInformation creatorInfoB = spdxDocs[j].getCreationInfo();
				String[] creatorsB = creatorInfoB.getCreators();

				// find any creators in A that are not in B
				String[] uniqueA = findUniqueString(creatorsA, creatorsB);
				if (uniqueA != null && uniqueA.length > 0) {
					uniqueAMap.put(spdxDocs[j], uniqueA);
				}
				// compare creator comments
				if (!stringsEqual(creatorInfoA.getComment(), creatorInfoB.getComment())) {
					this.creatorInformationEquals = false;
				}
				// compare creation dates
				if (!stringsEqual(creatorInfoA.getCreated(), creatorInfoB.getCreated())) {
					this.creatorInformationEquals = false;
				}
				// compare license list versions
				if (!stringsEqual(creatorInfoA.getLicenseListVersion(), creatorInfoB.getLicenseListVersion())) {
					this.creatorInformationEquals = false;
					this.licenseListVersionEquals = false;
				}
			}
			if (uniqueAMap.keySet().size() > 0) {
				this.uniqueCreators.put(spdxDocs[i], uniqueAMap);
				this.creatorInformationEquals = false;
			}
		}
		if (!this.creatorInformationEquals) {
			this.differenceFound = true;
		}
	}

	/**
	 * Finds any strings which are in A but not in B
	 * @param stringsA
	 * @param stringsB
	 * @return
	 */
	private String[] findUniqueString(String[] stringsA, String[] stringsB) {
		if (stringsA == null) {
			return new String[0];
		}
		if (stringsB == null) {
			return Arrays.copyOf(stringsA, stringsA.length);
		}
		List<String> al = Lists.newArrayList();
		for (int i = 0; i < stringsA.length; i++) {
			boolean found = false;
			for (int j = 0; j < stringsB.length; j++) {
				if (stringsA[i].trim().equals(stringsB[j].trim())) {
					found = true;
					break;
				}
			}
			if (!found) {
				al.add(stringsA[i]);
			}
		}
		return al.toArray(new String[al.size()]);
	}

	/**
	 * Compares the SPDX documents and sets the appropriate flags
	 * @throws SpdxCompareException
	 */
	private void comparePackages() throws SpdxCompareException {
		if (this.spdxDocs == null || this.spdxDocs.length < 1) {
			return;
		}
		this.uniquePackages.clear();
		this.packageComparers.clear();
		// N x N comparison of all files
		for (int i = 0; i < spdxDocs.length; i++) {
			SpdxPackage[] pkgsA;
			try {
				pkgsA = collectAllPackages(spdxDocs[i]);
			} catch (InvalidSPDXAnalysisException e) {
				throw(new SpdxCompareException("Error collecting packages from SPDX document "+spdxDocs[i].getName(), e));
			}
			// note - the package arrays MUST be sorted for the comparator methods to work
			Arrays.sort(pkgsA);
			addPackageComparers(spdxDocs[i], pkgsA, this.extractedLicenseIdMap);
			Map<SpdxDocument, SpdxPackage[]> uniqueAMap = this.uniquePackages.get(spdxDocs[i]);
			if (uniqueAMap == null) {
				uniqueAMap = Maps.newHashMap();
			}
			for (int j = 0; j < spdxDocs.length; j++) {
				if (j == i) {
					continue;
				}
				SpdxPackage[] pkgsB;
				try {
					pkgsB = collectAllPackages(spdxDocs[j]);
				} catch (InvalidSPDXAnalysisException e) {
					throw(new SpdxCompareException("Error collecting packages from SPDX document "+spdxDocs[i].getName(), e));
				}
				//Note that the files arrays must be sorted for the find methods to work
				Arrays.sort(pkgsB);
				SpdxPackage[] uniqueAB = findUniquePackages(pkgsA, pkgsB);
				if (uniqueAB != null && uniqueAB.length > 0) {
					uniqueAMap.put(spdxDocs[j], uniqueAB);
				}
			}
			if (!uniqueAMap.isEmpty()) {
				this.uniquePackages.put(spdxDocs[i], uniqueAMap);
			}
		}
		if (!_isPackagesEqualsNoCheck()) {
			this.differenceFound = true;
		}
	}

	/**
	 * add all the document packages to the multi-comparer
	 * @param spdxDocument
	 * @param pkgs
	 * @param extractedLicenseIdMap
	 * @throws SpdxCompareException
	 */
	private void addPackageComparers(SpdxDocument spdxDocument,
			SpdxPackage[] pkgs, Map<SpdxDocument, Map<SpdxDocument, Map<String, String>>> extractedLicenseIdMap) throws SpdxCompareException {
		for (int i = 0; i < pkgs.length; i++) {
			SpdxPackageComparer mpc = this.packageComparers.get(pkgs[i].getName());
			if (mpc == null) {
				mpc = new SpdxPackageComparer(extractedLicenseIdMap);
				this.packageComparers.put(pkgs[i].getName(), mpc);
			}
			mpc.addDocumentPackage(spdxDocument, pkgs[i]);
		}
	}

	/**
	 * Compares two licenses from two different SPDX documents taking into account
	 * the extracted license infos who's ID's may be different between the two documents
	 * Note: The ExtracedLicenseIDMap must be initialized before this method is invoked
	 * @param doc1 Index of the SPDX document for license1
