SequenceResolver


1   /*******************************************************************************
2    * Copyright (c) 2006 IBM Corporation and others.
3    * All rights reserved. This program and the accompanying materials
4    * are made available under the terms of the Eclipse Public License v1.0
5    * which accompanies this distribution, and is available at
6    * http://www.eclipse.org/legal/epl-v10.html
7    *
8    * Contributors:
9    *     IBM Corporation - initial API and implementation
10   *******************************************************************************/
11  package org.eclipse.help.internal.util;
12  
13  import java.util.ArrayList  ;
14  import java.util.Collections  ;
15  import java.util.HashSet  ;
16  import java.util.Iterator  ;
17  import java.util.List  ;
18  import java.util.ListIterator  ;
19  import java.util.Set  ;
20  
21  /*
22   * Provides an algorithm for determining a recommended sequence of items that
23   * satisfies a primary sequence and as many secondary sequences as possible.
24   * 
25   * For example, this is used to determine the display order of books on the tocs
26   * based on the active product's preferred order as well as all other products'
27   * preferred orders.
28   */
29  public class SequenceResolver {
30  
31      private List   primaryList;
32      private List  [] secondaryLists;
33      private ListIterator   primaryIter;
34      private ListIterator  [] secondaryIters;
35      private Set   processedItems;
36      
37      /*
38       * Merges the given primary and secondary orderings such that all ordering
39       * conditions from the primary are satisfied, and as many secondary ordering
40       * conditions as reasonably possible are also satisfied. An ordering condition
41       * is a pair of adjacent items in any ordering.
42       * 
43       * For example:
44       * 
45       *    primary =             {b, d, f}
46       *    secondary[0] =        {c, d, e}
47       *    secondary[1] =        {a, b, c}
48       *    -------------------------------
49       *    result =     {a, b, c, d, e, f}
50       *
51       * The algorithm works in iterations, where at each iteration we determine
52       * the next element in the recommended sequence. We maintain a pointer for
53       * each ordering to keep track of what we've already ordered.
54       * 
55       * To determine the next item, we locate the current element in each ordering.
56       * These are the candidates for the next item as the next item can only be
57       * one of these.
58       * 
59       * The top candidates are selected from the list of candidates, where a top
60       * candidate is one that has the lowest rank (there can be many). Rank is
61       * determined by how many other candidates appear before that candidate
62       * item in all the orderings. That is, we find out how many items
63       * the orderings list before each candidate.
64       * 
65       * If a candidate has no other candidates listed before it, it will be
66       * the next item. If there are many, the first one is selected. If one of
67       * the top candidates is from the primary ordering (can only be one), it is
68       * automatically selected.
69       * 
70       * Using the top rank ensures that if there are conflicts, and that
71       * as many orderings as possible are satisfied. For example, if most orderings
72       * want x before y, but a few want the opposite, x will be placed before y.
73       */
74      public List   getSequence(List   primary, List  [] secondary) {
75          primaryList = primary;
76          secondaryLists = secondary;
77          prepareDataStructures();
78          List   order = new ArrayList  ();
79          Object   item;
80          while ((item = getNextItem()) != null) {
81              processedItems.add(item);
82              advanceIterator(primaryIter);
83              for (int i=0;i<secondaryIters.length;++i) {
84                  advanceIterator(secondaryIters[i]);
85              }
86              order.add(item);
87          }
88          return order;
89      }
90  
91      /*
92       * Create the data structures necessary for later operations.
93       */
94      private void prepareDataStructures() {
95          primaryIter = primaryList.listIterator();
96          secondaryIters = new ListIterator  [secondaryLists.length];
97          for (int i=0;i<secondaryLists.length;++i) {
98              secondaryIters[i] = secondaryLists[i].listIterator();
99          }
100         processedItems = new HashSet  ();
101     }
102     
103     /*
104      * Determine the next item in the sequence based on the top
105      * candidate items.
106      */
107     private Object   getNextItem() {
108         Candidate[] candidates = getTopCandidates();
109         switch(candidates.length) {
110         case 0:
111             return null;
112         case 1:
113             return candidates[0].item;
114         default:
115             for (int i=0;i<candidates.length;++i) {
116                 if (candidates[i].isPrimary) {
117                     return candidates[i].item;
118                 }
119             }
120             return candidates[0].item;
121         }
122     }
123     
124     /*
125      * Retrieves the top candidates from all the available next item candidates.
126      * These are the candidates that have the lowest rank 
127      */
128     private Candidate[] getTopCandidates() {
129         Candidate[] candidates = getEligibleCandidates();
130         rankCandidates(candidates);
131         if (candidates.length > 0) {
132             int topRank = candidates[0].rank;
133             for (int i=1;i<candidates.length;++i) {
134                 if (candidates[i].rank < topRank) {
135                     topRank = candidates[i].rank;
136                 }
137             }
138             List   topCandidates = new ArrayList  ();
139             for (int i=0;i<candidates.length;++i) {
140                 if (candidates[i].rank == topRank) {
141                     topCandidates.add(candidates[i]);
142                 }
143             }
144             return (Candidate[])topCandidates.toArray(new Candidate[topCandidates.size()]);
145         }
146         return candidates;
147     }
148     
149     /*
150      * Returns all eligible candidates. A candidate is eligible if it does not
151      * conflict with the primary candidate. That is, if the primary candidate's list
152      * has that candidate after the primary candidate, it is contradicting the primary
153      * sequence and is not eligible.
154      */
155     private Candidate[] getEligibleCandidates() {
156         Candidate[] allCandidates = getAllCandidates();
157         Candidate primary = null;
158         for (int i=0;i<allCandidates.length;++i) {
159             if (allCandidates[i].isPrimary) {
160                 primary = allCandidates[i];
161                 break;
162             }
163         }
164         // if we have no primary candidate then they're all eligible
165         if (primary != null) {
166             List   eligibleCandidates = new ArrayList  (allCandidates.length);
167             // primary candidate is always eligible
168             eligibleCandidates.add(primary);
169             Set   primarySet = Collections.singleton(primary.item);
170             for (int i=0;i<allCandidates.length;++i) {
171                 Candidate c = allCandidates[i];
172                 if (c != primary) {
173                     // does it contradict the primary sequence? if not, it is eligible
174                     if (countPrecedingItems(c.item, primary.src, primarySet) == 0) {
175                         eligibleCandidates.add(c);
176                     }
177                 }
178             }
179             return (Candidate[])eligibleCandidates.toArray(new Candidate[eligibleCandidates.size()]);
180         }
181         return allCandidates;
182     }
183     
184     /*
185      * Retrieve all the candidates for the next item in sequence, with
186      * no duplicates.
187      */
188     private Candidate[] getAllCandidates() {
189         List   candidates = new ArrayList  ();
190         Object   item = getNextItem(primaryIter);
191         if (item != null) {
192             Candidate c = new Candidate();
193             c.item = item;
194             c.isPrimary = true;
195             c.src = primaryList;
196             candidates.add(c);
197         }
198         for (int i=0;i<secondaryIters.length;++i) {
199             item = getNextItem(secondaryIters[i]);
200             if (item != null) {
201                 Candidate c = new Candidate();
202                 c.item = item;
203                 c.isPrimary = false;
204                 c.src = secondaryLists[i];
205                 if (!candidates.contains(c)) {
206                     candidates.add(c);
207                 }
208             }
209         }
210         return (Candidate[])candidates.toArray(new Candidate[candidates.size()]);
211     }
212 
213     /*
214      * Assign a rank to each of the given candidates. Rank is determined by
215      * how many preceding candidates appear before that candidate in the orderings.
216      * This essentially means how far back this item should be in the final
217      * sequence.
218      */
219     private void rankCandidates(Candidate[] candidates) {
220         // for quick lookup
221         Set   candidateItems = new HashSet  ();
222         for (int i=0;i<candidates.length;++i) {
223             candidateItems.add(candidates[i].item);
224         }
225         for (int i=0;i<candidates.length;++i) {
226             Candidate c = candidates[i];
227             for (int j=0;j<candidates.length;++j) {
228                 c.rank += countPrecedingItems(c.item, candidates[j].src, candidateItems);
229             }
230         }
231     }
232 
233     /*
234      * Counts the number of elements from the given set that come before
235      * the given item in the given list.
236      */
237     private int countPrecedingItems(Object   item, List   list, Set   set) {
238         int count = 0;
239         Iterator   iter = list.iterator();
240         while (iter.hasNext()) {
241             Object   next = iter.next();
242             if (next.equals(item)) {
243                 return count;
244             }
245             if (set.contains(next)) {
246                 ++count;
247             }
248         }
249         return 0;
250     }
251     
252     /*
253      * Returns the next item available to this iterator, without moving it
254      * forward.
255      */
256     private Object   getNextItem(ListIterator   iter) {
257         if (iter.hasNext()) {
258             Object   next = iter.next();
259             iter.previous();
260             return next;
261         }
262         return null;
263     }
264 
265     /*
266      * Advances the given iterator to the next item in its
267      * sequence that we haven't yet processed.
268      */
269     private void advanceIterator(ListIterator   iter) {
270         while (iter.hasNext()) {
271             Object   item = iter.next();
272             if (!processedItems.contains(item)) {
273                 iter.previous();
274                 break;
275             }
276         }
277     }
278 
279     /*
280      * A candidate item; one that could potentially be the next one in the final
281      * sequence.
282      */
283     private static class Candidate {
284         public Object   item;
285         public boolean isPrimary;
286         public int rank;
287         public List   src;
288         
289         public boolean equals(Object   obj) {
290             return item.equals(obj);
291         }
292         
293         public int hashCode() {
294             return item.hashCode();
295         }
296     }
297 }
298
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags