path: root/org.eclipse.help/src/org/eclipse/help/internal/util/SequenceResolver.java

/*******************************************************************************
 * Copyright (c) 2006 IBM Corporation and others.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     IBM Corporation - initial API and implementation
 *******************************************************************************/
package org.eclipse.help.internal.util;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.Set;

/*
 * Provides an algorithm for determining a recommended sequence of items that
 * satisfies a primary sequence and as many secondary sequences as possible.
 *
 * For example, this is used to determine the display order of books on the tocs
 * based on the active product's preferred order as well as all other products'
 * preferred orders.
 */
public class SequenceResolver {

	private List primaryList;
	private List[] secondaryLists;
	private ListIterator primaryIter;
	private ListIterator[] secondaryIters;
	private Set processedItems;

	/*
	 * Merges the given primary and secondary orderings such that all ordering
	 * conditions from the primary are satisfied, and as many secondary ordering
	 * conditions as reasonably possible are also satisfied. An ordering condition
	 * is a pair of adjacent items in any ordering.
	 *
	 * For example:
	 *
	 *    primary =             {b, d, f}
	 *    secondary[0] =        {c, d, e}
	 *    secondary[1] =        {a, b, c}
	 *    -------------------------------
	 *    result =     {a, b, c, d, e, f}
	 *
	 * The algorithm works in iterations, where at each iteration we determine
	 * the next element in the recommended sequence. We maintain a pointer for
	 * each ordering to keep track of what we've already ordered.
	 *
	 * To determine the next item, we locate the current element in each ordering.
	 * These are the candidates for the next item as the next item can only be
	 * one of these.
	 *
	 * The top candidates are selected from the list of candidates, where a top
	 * candidate is one that has the lowest rank (there can be many). Rank is
	 * determined by how many other candidates appear before that candidate
	 * item in all the orderings. That is, we find out how many items
	 * the orderings list before each candidate.
	 *
	 * If a candidate has no other candidates listed before it, it will be
	 * the next item. If there are many, the first one is selected. If one of
	 * the top candidates is from the primary ordering (can only be one), it is
	 * automatically selected.
	 *
	 * Using the top rank ensures that if there are conflicts, and that
	 * as many orderings as possible are satisfied. For example, if most orderings
	 * want x before y, but a few want the opposite, x will be placed before y.
	 */
	public List getSequence(List primary, List[] secondary) {
		primaryList = primary;
		secondaryLists = secondary;
		prepareDataStructures();
		List order = new ArrayList();
		Object item;
		while ((item = getNextItem()) != null) {
			processedItems.add(item);
			advanceIterator(primaryIter);
			for (int i=0;i<secondaryIters.length;++i) {
				advanceIterator(secondaryIters[i]);
			}
			order.add(item);
		}
		return order;
	}

	/*
	 * Create the data structures necessary for later operations.
	 */
	private void prepareDataStructures() {
		primaryIter = primaryList.listIterator();
		secondaryIters = new ListIterator[secondaryLists.length];
		for (int i=0;i<secondaryLists.length;++i) {
			secondaryIters[i] = secondaryLists[i].listIterator();
		}
		processedItems = new HashSet();
	}

	/*
	 * Determine the next item in the sequence based on the top
	 * candidate items.
	 */
	private Object getNextItem() {
		Candidate[] candidates = getTopCandidates();
		switch(candidates.length) {
		case 0:
			return null;
		case 1:
			return candidates[0].item;
		default:
			for (int i=0;i<candidates.length;++i) {
				if (candidates[i].isPrimary) {
					return candidates[i].item;
				}
			}
			return candidates[0].item;
		}
	}

	/*
	 * Retrieves the top candidates from all the available next item candidates.
	 * These are the candidates that have the lowest rank
	 */
	private Candidate[] getTopCandidates() {
		Candidate[] candidates = getEligibleCandidates();
		rankCandidates(candidates);
		if (candidates.length > 0) {
			int topRank = candidates[0].rank;
			for (int i=1;i<candidates.length;++i) {
				if (candidates[i].rank < topRank) {
					topRank = candidates[i].rank;
				}
			}
			List topCandidates = new ArrayList();
			for (int i=0;i<candidates.length;++i) {
				if (candidates[i].rank == topRank) {
					topCandidates.add(candidates[i]);
				}
			}
			return (Candidate[])topCandidates.toArray(new Candidate[topCandidates.size()]);
		}
		return candidates;
	}

	/*
	 * Returns all eligible candidates. A candidate is eligible if it does not
	 * conflict with the primary candidate. That is, if the primary candidate's list
	 * has that candidate after the primary candidate, it is contradicting the primary
	 * sequence and is not eligible.
	 */
	private Candidate[] getEligibleCandidates() {
		Candidate[] allCandidates = getAllCandidates();
		Candidate primary = null;
		for (int i=0;i<allCandidates.length;++i) {
			if (allCandidates[i].isPrimary) {
				primary = allCandidates[i];
				break;
			}
		}
		// if we have no primary candidate then they're all eligible
		if (primary != null) {
			List eligibleCandidates = new ArrayList(allCandidates.length);
			// primary candidate is always eligible
			eligibleCandidates.add(primary);
			Set primarySet = Collections.singleton(primary.item);
			for (int i=0;i<allCandidates.length;++i) {
				Candidate c = allCandidates[i];
				if (c != primary) {
					// does it contradict the primary sequence? if not, it is eligible
					if (countPrecedingItems(c.item, primary.src, primarySet) == 0) {
						eligibleCandidates.add(c);
					}
				}
			}
			return (Candidate[])eligibleCandidates.toArray(new Candidate[eligibleCandidates.size()]);
		}
		return allCandidates;
	}

	/*
	 * Retrieve all the candidates for the next item in sequence, with
	 * no duplicates.
	 */
	private Candidate[] getAllCandidates() {
		List candidates = new ArrayList();
		Object item = getNextItem(primaryIter);
		if (item != null) {
			Candidate c = new Candidate();
			c.item = item;
			c.isPrimary = true;
			c.src = primaryList;
			candidates.add(c);
		}
		for (int i=0;i<secondaryIters.length;++i) {
			item = getNextItem(secondaryIters[i]);
			if (item != null) {
				Candidate c = new Candidate();
				c.item = item;
				c.isPrimary = false;
				c.src = secondaryLists[i];
				if (!candidates.contains(c)) {
					candidates.add(c);
				}
			}
		}
		return (Candidate[])candidates.toArray(new Candidate[candidates.size()]);
	}

	/*
	 * Assign a rank to each of the given candidates. Rank is determined by
	 * how many preceding candidates appear before that candidate in the orderings.
	 * This essentially means how far back this item should be in the final
	 * sequence.
	 */
	private void rankCandidates(Candidate[] candidates) {
		// for quick lookup
		Set candidateItems = new HashSet();
		for (int i=0;i<candidates.length;++i) {
			candidateItems.add(candidates[i].item);
		}
		for (int i=0;i<candidates.length;++i) {
			Candidate c = candidates[i];
			for (int j=0;j<candidates.length;++j) {
				c.rank += countPrecedingItems(c.item, candidates[j].src, candidateItems);
			}
		}
	}

	/*
	 * Counts the number of elements from the given set that come before
	 * the given item in the given list.
	 */
	private int countPrecedingItems(Object item, List list, Set set) {
		int count = 0;
		Iterator iter = list.iterator();
		while (iter.hasNext()) {
			Object next = iter.next();
			if (next.equals(item)) {
				return count;
			}
			if (set.contains(next)) {
				++count;
			}
		}
		return 0;
	}

	/*
	 * Returns the next item available to this iterator, without moving it
	 * forward.
	 */
	private Object getNextItem(ListIterator iter) {
		if (iter.hasNext()) {
			Object next = iter.next();
			iter.previous();
			return next;
		}
		return null;
	}

	/*
	 * Advances the given iterator to the next item in its
	 * sequence that we haven't yet processed.
	 */
	private void advanceIterator(ListIterator iter) {
		while (iter.hasNext()) {
			Object item = iter.next();
			if (!processedItems.contains(item)) {
				iter.previous();
				break;
			}
		}
	}

	/*
	 * A candidate item; one that could potentially be the next one in the final
	 * sequence.
	 */
	private static class Candidate {
		public Object item;
		public boolean isPrimary;
		public int rank;
		public List src;

		@Override
		public boolean equals(Object obj) {
			return item.equals(obj);
		}

		@Override
		public int hashCode() {
			return item.hashCode();
		}
	}
}