partition/src/main/java/net/sf/taverna/t2/partition/Partition.java

/*******************************************************************************
 * Copyright (C) 2007 The University of Manchester   
 * 
 *  Modifications to the initial code base are copyright of their
 *  respective authors, or their employers as appropriate.
 * 
 *  This program is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public License
 *  as published by the Free Software Foundation; either version 2.1 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
 *  Lesser General Public License for more details.
 *    
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
 ******************************************************************************/
package net.sf.taverna.t2.partition;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

import javax.swing.event.TreeModelEvent;
import javax.swing.tree.TreePath;

/**
 * A partition represents a set of items which can be exclusively classified
 * into one or more distinct subsets along with the algorithm to perform this
 * subset operation.
 * 
 * @author Tom Oinn
 * 
 * @param <ItemType>
 *            all items in the underlying set of which this is a subset are
 *            instances of this type or can be cast to it according to
 *            conventional java language rules.
 * @param <PartitionValueType>
 *            the partition value type used by the parent partition algorithm to
 *            create this partition object. As an example, if this partition
 *            object represented all those entries with a particular host
 *            institution this would be a String or possibly URL.
 * @param <ChildPartitionValueType>
 *            the partition value type used by this partition's partition
 *            algorithm to create sub-partitions, it's used in the signature
 *            here because ordering of children is done based on these values.
 *            Any child partition will have a getPartitionValue return type
 *            cast-able to this type.
 */
public class Partition<ItemType extends Comparable, PartitionValueType, ChildPartitionValueType> {

	// A comparator operating over the value type of the child partitions and
	// used to order them as created or to re-order on a change of this property
	private Comparator<ChildPartitionValueType> childPartitionOrder = null;

	// Back reference to the root partition of which this is a direct or
	// indirect sub-partition. If this *is* the root partition this points to
	// self
	protected RootPartition<ItemType> root;

	// A subset of the parent's member set containing items which have been
	// allocated to this partition by the parent's partition algorithm. The
	// partition is specified by the partitionValue field.
	private List<ItemType> members;

	// The parent partition of which this is a subset
	private Partition<ItemType, ?, PartitionValueType> parent;

	// Specification of the partition in terms of the parent's partitioning
	// algorithm
	private PartitionValueType partitionValue;

	// List of partitioning algorithms to be applied to this subset to create
	// further partitions, the algorithm at index 0 is the one used for this
	// partition, all others are passed in to the constructors for
	// sub-partitions
	protected List<PartitionAlgorithm<?>> partitionAlgorithms;

	// An initially empty list of sub-partitions created by the head element of
	// the partition algorithm list
	protected List<Partition<ItemType, ChildPartitionValueType, ?>> children;

	// Path from this node back to the root, initialised on first access and
	// cached
	private List<Partition<ItemType, ?, ?>> partitionPath = null;

	// For leaf partitions this is equal to the number of items in the member
	// set, for all other partitions it is the sum of the item count of all
	// child partitions
	protected int itemCount = 0;

	/**
	 * Construct a new Partition, this is used by the RootPartition and by this
	 * class to construct the recursively sub-divided partition structure based
	 * on the rules encapsulated by the partition algorithm list.
	 * 
	 * @param parent
	 *            parent partition of which this is a subset
	 * @param pa
	 *            partition algorithm list, with the algorithm used to create
	 *            child partitions of this one at position 0, if this list is
	 *            empty this is a leaf partition.
	 * @param root
	 *            reference to the RootPartition acting as the externally
	 *            visible front-end to this structure
	 * @param pv
	 *            the value which the parent's partition algorithm has assigned
	 *            to this partition. This must be interpreted in the context of
	 *            the parent's first partition algorithm for display and other
	 *            purposes
	 */
	protected Partition(Partition<ItemType, ?, PartitionValueType> parent,
			List<PartitionAlgorithm<?>> pa, RootPartition<ItemType> root,
			PartitionValueType pv) {
		this.root = root;
		this.members = new ArrayList<ItemType>();
		this.parent = parent;
		this.partitionValue = pv;
		this.partitionAlgorithms = pa;
		this.children = new ArrayList<Partition<ItemType, ChildPartitionValueType, ?>>();
	}

	/**
	 * Return the number of items below this node in the partition tree; in the
	 * case of leaf partitions this is the number of items in the member set,
	 * for non-leaf partitions it is the sum of the item count for all immediate
	 * child partitions.
	 */
	public int getItemCount() {
		return this.itemCount;
	}

	/**
	 * Sub-partitions of this partition are ordered based on a comparator over
	 * the child partition value type.
	 * 
	 * @return a comparator over child partition value types, or null if no
	 *         comparator has been specified (by default this returns null)
	 */
	public Comparator<ChildPartitionValueType> getChildPartitionOrder() {
		return this.childPartitionOrder;
	}

	/**
	 * Set a comparator for child partition ordering - if the supplied
	 * comparator is different to the current one this will also trigger a
	 * re-order of all child partitions and corresponding events in the root
	 * partition's tree view. In the current implementation this is the very
	 * broad 'tree structure changed' event for this node in the tree view.
	 * 
	 * @param order
	 *            a new comparator to order child partitions
	 */
	public void setChildPartitionOrder(Comparator<ChildPartitionValueType> order) {
		if (!order.equals(childPartitionOrder)) {
			childPartitionOrder = order;
			sortChildPartitions();
		}
	}

	/**
	 * Return the parent partition of which this is a sub-partition, or null if
	 * this is the root partition.
	 */
	public Partition<ItemType, ?, PartitionValueType> getParent() {
		return this.parent;
	}

	/**
	 * The parent partition created this partition based on a particular value
	 * of a property of the members of the sub-partition. This returns that
	 * value, and is the result returned from the parent partition's first
	 * partition algorithm when run on all members of this partition or its
	 * direct or indirect sub-partitions.
	 */
	public PartitionValueType getPartitionValue() {
		return this.partitionValue;
	}

	@Override
	public String toString() {
		if (getParent() != null) {
			// query type
			String string = this.getParent().getPartitionAlgorithms().get(0)
					.toString();
			// result of query
			String string2 = this.partitionValue.toString();
			return string2 + " (" + getItemCount() + ")";
		} else {
			// This is for a root partition, loop through its children to return
			// the correct number when running a new query
			int items = 0;
			for (Partition child : children) {
				items = items + child.getItemCount();
			}
			String queryType = getPartitionAlgorithms().get(0).toString();
			// return "Activities which match query = " + getItemCount();
			return "Available activities (" + items + ")";
			//+ ", query by "
				//	+ queryType;
		}
	}

	/**
	 * Return a list of Partition objects from the root (at index 0) to this
	 * node at the final position in the list. Computes the first time then
	 * caches, as it should be impossible for this to be modified without
	 * recreation of the entire structure from scratch.
	 */
	public synchronized List<Partition<ItemType, ?, ?>> getPartitionPath() {
		if (partitionPath == null) {
			List<Partition<ItemType, ?, ?>> al = new ArrayList<Partition<ItemType, ?, ?>>();
			Partition<ItemType, ?, ?> activePartition = this;
			al.add(activePartition);
			while (activePartition.getParent() != null) {
				al.add(0, activePartition.getParent());
				activePartition = activePartition.getParent();
			}
			partitionPath = al;
		}
		return partitionPath;
	}

	/**
	 * If this is a leaf partition, defined as one with an empty list of
	 * partition algorithms, then this method returns the set of all items which
	 * have been classified as belonging to this leaf partition. For non-leaf
	 * partitions it will return an empty set.
	 */
	public final List<ItemType> getMembers() {
		return Collections.unmodifiableList(this.members);
	}

	/**
	 * The list of partition algorithms applicable to this node (at index 0) and
	 * subsequent downstream sub-partitions of it. If this is empty then the
	 * partition is a leaf partition.
	 */
	public final List<PartitionAlgorithm<?>> getPartitionAlgorithms() {
		return Collections.unmodifiableList(partitionAlgorithms);
	}

	/**
	 * Sub-partitions of this partition defined by the partition algorithm at
	 * index 0 of the list. If this is a leaf partition this will always be
	 * empty.
	 */
	public final List<Partition<ItemType, ChildPartitionValueType, ?>> getChildren() {
		return Collections.unmodifiableList(children);
	}

	/**
	 * Inject an item into this partition, if there are partition algorithms in
	 * the partition algorithm list (i.e. this is not a leaf) this will
	 * recursively call the same method on child partitions or create new
	 * partitions where there are none that match the value from the partition
	 * algorithm. If this is a leaf partition the item is added to the member
	 * set. The list is sorted when adding an item and it is inserted in the
	 * appropriate place
	 * 
	 * @param item
	 *            the item to add to the partition structure.
	 */
	@SuppressWarnings("unchecked")
	protected synchronized void addItem(ItemType item) {
		if (partitionAlgorithms.isEmpty()) {
			// itemCount = 0;
			// Allocate directly to member set, no further partitioning
			members.add(item);
			Collections.sort(members);
			int indexOf = members.indexOf(item);
			// root.treeNodesInserted(new TreeModelEvent(this, getTreePath(),
			// new int[] { members.size() - 1 }, new Object[] { item }));
			root.treeNodesInserted(new TreeModelEvent(this, getTreePath(),
					new int[] { indexOf }, new Object[] { item }));
			// Increment item count for all partitions in the partition path
			for (Partition<ItemType, ?, ?> p : getPartitionPath()) {
				synchronized (p) {
					p.itemCount++;
					root.treeNodesChanged(new TreeModelEvent(this, p
							.getTreePath()));
				}
			}

			// Cache the storage of this item to this partition in the root
			// partition for more efficient removal if required (saves having to
			// search the entire partition tree, although that wouldn't be too
			// painful if it was required this is faster at the cost of a few
			// bytes of memory)
			root.itemStoredAt(item, this);
			// TODO - when the tree model covers items on the leaf nodes we'll
			// want to message it here as well.
		} else {
			PartitionAlgorithm<ChildPartitionValueType> pa;
			pa = (PartitionAlgorithm<ChildPartitionValueType>) partitionAlgorithms
					.get(0);
			ChildPartitionValueType pvalue = pa.allocate(item, root
					.getPropertyExtractorRegistry());
			// FIXME not sure how to do this since you seem to have to add the
			// items to the partition if you want to then search them again,
			// maybe you need a non-showing partition or something?
			// //if it is a failed search then don't bother adding to the
			// partition
			// if (pvalue.toString().equalsIgnoreCase("No match")) {
			// return;
			// }
			// See if there's a partition with this value already in the child
			// partition list
			for (Partition<ItemType, ChildPartitionValueType, ?> potentialChild : children) {
				if (potentialChild.getPartitionValue().equals(pvalue)) {
					potentialChild.addItem(item);
					return;
				}
			}
			// If not we have to create a new sub-partition
			List<PartitionAlgorithm<?>> tail = new ArrayList<PartitionAlgorithm<?>>();
			for (int i = 1; i < partitionAlgorithms.size(); i++) {
				tail.add(partitionAlgorithms.get(i));
			}
			Partition<ItemType, ChildPartitionValueType, ?> newPartition = new Partition(
					this, tail, this.root, pvalue);
			// Insert the new partition in the correct place according to the
			// comparator currently installed, or at the end if none exists or
			// the list is empty
			if (childPartitionOrder == null || children.isEmpty()) {
				children.add(newPartition);
				root.treeNodesInserted(new TreeModelEvent(this, getTreePath(),
						new int[] { children.indexOf(newPartition) },
						new Object[] { newPartition }));
			} else {
				boolean foundIndex = false;
				for (int i = 0; i < children.size(); i++) {
					ChildPartitionValueType existingPartitionValue = children
							.get(i).getPartitionValue();
					if (childPartitionOrder.compare(pvalue,
							existingPartitionValue) < 0) {
						children.add(i, newPartition);
						root.treeNodesInserted(new TreeModelEvent(this,
								getTreePath(), new int[] { i },
								new Object[] { newPartition }));
						if (i != 0) {
							root.treeStructureChanged(new TreeModelEvent(this,
									getTreePath()));
						}
						foundIndex = true;
						break;
					}
				}
				if (!foundIndex) {
					// Fallen off the end of the array without finding something
					// with greater index than the new partition so we add it at
					// the
					// end (by definition this is the largest value according to
					// the
					// comparator)
					children.add(newPartition);
					root.treeNodesInserted(new TreeModelEvent(this,
							getTreePath(), new int[] { children
									.indexOf(newPartition) },
							new Object[] { newPartition }));
				}
			}
			// Add the item to the new partition to trigger creation of any
			// sub-partitions required
			newPartition.addItem(item);
		}
	}

	/**
	 * Remove an item from the member set
	 * 
	 * @param item
	 *            the item to remove
	 */
	protected void removeMember(ItemType item) {
		this.members.remove(item);
	}

	/**
	 * Re-order the child partitions based on the comparator, if no comparator
	 * has been defined this method does nothing. Tree structure changed
	 * messages are fired from this node in the tree view if the comparator is
	 * defined even if no nodes have been changed (lazy but not too much of an
	 * issue I suspect)
	 */
	protected synchronized final void sortChildPartitions() {
		if (this.childPartitionOrder == null) {
			// Can't do anything unless the comparator is set appropriately
			return;
		}
		Comparator<Partition<ItemType, ChildPartitionValueType, ?>> comparator = new Comparator<Partition<ItemType, ChildPartitionValueType, ?>>() {
			public int compare(
					Partition<ItemType, ChildPartitionValueType, ?> o1,
					Partition<ItemType, ChildPartitionValueType, ?> o2) {
				// FIXME is this really safe to do? It's fairly specific to our
				// case. Doesn't seem very generic
				if (o1.getPartitionValue().toString().equalsIgnoreCase(
						"no value")) {
					// No value so put it to the end
					return 1;
				}
				return childPartitionOrder.compare(o1.getPartitionValue(), o2
						.getPartitionValue());
			}
		};
		Collections.<Partition<ItemType, ChildPartitionValueType, ?>> sort(
				children, comparator);
		// Message the root that the node structure under this node has changed
		// (this is a bit lazy and we could almost certainly be more clever here
		// as the nodes have been removed and added to re-order them)
		root.treeStructureChanged(new TreeModelEvent(this, getTreePath()));
	}

	/**
	 * Return a TreePath object with this node as the final entry in the path
	 */
	protected final synchronized TreePath getTreePath() {
		return new TreePath(getPartitionPath().toArray());
	}

	// public void sortItems() {
	// System.out.println("sorting the items");
	// synchronized (members) {
	// List<ItemType> oldOrder = new ArrayList<ItemType>(members);
	// Collections.sort(oldOrder);
	//
	// for (ItemType item : oldOrder) {
	// removeMember(item);
	// }
	// for (ItemType item : oldOrder) {
	// addItem(item);
	// }
	// }
	//
	// }

}