001/*
002 * Copyright (c) 2006-2011 Nuxeo SA (http://nuxeo.com/) and others.
003 *
004 * All rights reserved. This program and the accompanying materials
005 * are made available under the terms of the Eclipse Public License v1.0
006 * which accompanies this distribution, and is available at
007 * http://www.eclipse.org/legal/epl-v10.html
008 *
009 * Contributors:
010 *     Nuxeo - initial API and implementation
011 *
012 * $Id$
013 */
014
015package org.nuxeo.runtime.deploy;
016
017import java.util.ArrayList;
018import java.util.Arrays;
019import java.util.Collection;
020import java.util.HashSet;
021import java.util.Hashtable;
022import java.util.Iterator;
023import java.util.List;
024import java.util.Map;
025import java.util.Set;
026import java.util.Vector;
027
028/**
029 * @author <a href="mailto:bs@nuxeo.com">Bogdan Stefanescu</a> TODO this was copied from nuxeo.commons and fixed -
030 *         should put it back with all modifs
031 */
032// TODO handle dependencies cycles.
033public class DependencyTree<K, T> implements Iterable<DependencyTree.Entry<K, T>> {
034
035    private final Map<K, Entry<K, T>> registry;
036
037    // the sorted list of resolved entries.
038    // given an element e from that list it is ensured that any element at the left
039    // of 'e' doesn't depends on it
040    private final List<Entry<K, T>> resolved;
041
042    public DependencyTree() {
043        registry = new Hashtable<K, Entry<K, T>>();
044        resolved = new Vector<Entry<K, T>>();
045    }
046
047    @Override
048    public Iterator<Entry<K, T>> iterator() {
049        return registry.values().iterator();
050    }
051
052    public Entry<K, T> add(K key, T object, K... requires) {
053        return add(key, object, Arrays.asList(requires));
054    }
055
056    public Entry<K, T> add(K key, T object, Collection<K> requires) {
057        Entry<K, T> entry = registry.get(key);
058        if (entry == null) {
059            entry = new Entry<K, T>(key, object);
060            registry.put(key, entry);
061        } else if (entry.object == null) {
062            entry.object = object;
063        } else {
064            // TODO object already exists
065            return entry;
066        }
067        updateDependencies(entry, requires);
068        registered(entry);
069        // resolve it if no pending requirements
070        if (entry.canEnterResolvedState()) {
071            resolve(entry);
072        }
073        return entry;
074    }
075
076    public void add(K key, T object) {
077        add(key, object, (Collection<K>) null);
078    }
079
080    public void remove(K key) {
081        Entry<K, T> entry = registry.get(key); // do not remove entry
082        if (entry != null) {
083            unregister(entry);
084            entry.object = null;
085            entry.waitsFor = null;
086        }
087    }
088
089    public void unregister(Entry<K, T> entry) {
090        if (entry.isResolved()) {
091            unresolve(entry);
092        }
093        unregistered(entry);
094    }
095
096    public Entry<K, T> getEntry(K key) {
097        return registry.get(key);
098    }
099
100    public T get(K key) {
101        Entry<K, T> entry = registry.get(key);
102        return entry != null ? entry.object : null;
103    }
104
105    public T getResolved(K key) {
106        Entry<K, T> entry = registry.get(key);
107        return entry != null && entry.isResolved() ? entry.object : null;
108    }
109
110    private void resolveEntry(Entry<K, T> entry) {
111        // synchronize () {
112        resolved.add(entry);
113        entry.isResolved = true;
114        // }
115        // notify listener
116        resolved(entry);
117    }
118
119    private void unresolveEntry(Entry<K, T> entry) {
120        // synchronize () {
121        resolved.remove(entry);
122        entry.isResolved = false;
123        // }
124        unresolved(entry);
125    }
126
127    public void resolve(Entry<K, T> entry) {
128        resolveEntry(entry);
129        // resolve any dependent entry if they are waiting only for me
130        Set<Entry<K, T>> deps = entry.getDependsOnMe();
131        if (deps != null) {
132            for (Entry<K, T> dep : deps) {
133                dep.removeWaitingFor(entry);
134                if (dep.canEnterResolvedState()) {
135                    resolve(dep); // resolve the dependent entry
136                }
137            }
138        }
139    }
140
141    public void unresolve(Entry<K, T> entry) {
142        // unresolve any dependent object
143        Set<Entry<K, T>> deps = entry.getDependsOnMe();
144        if (deps != null) {
145            for (Entry<K, T> dep : deps) {
146                dep.addWaitingFor(entry);
147                if (dep.isResolved()) {
148                    unresolve(dep); // unresolve the dependent entry
149                }
150            }
151        }
152        unresolveEntry(entry);
153    }
154
155    public boolean isPhantom(K key) {
156        Entry<K, T> entry = registry.get(key);
157        return entry != null && entry.isPhantom();
158    }
159
160    public boolean isRegistered(K key) {
161        Entry<K, T> entry = registry.get(key);
162        return entry != null && entry.isRegistered();
163    }
164
165    public boolean isResolved(K key) {
166        Entry<K, T> entry = registry.get(key);
167        return entry != null && entry.isResolved();
168    }
169
170    public Collection<Entry<K, T>> getEntries() {
171        return registry.values();
172    }
173
174    public List<T> getRegisteredObjects() {
175        List<T> list = new ArrayList<T>();
176        Collection<Entry<K, T>> entries = getEntries();
177        for (Entry<K, T> entry : entries) {
178            list.add(entry.object);
179        }
180        return list;
181    }
182
183    public List<Entry<K, T>> getPendingEntries() {
184        List<Entry<K, T>> result = new ArrayList<Entry<K, T>>();
185        for (Map.Entry<K, Entry<K, T>> entry : registry.entrySet()) {
186            Entry<K, T> val = entry.getValue();
187            if (!val.isResolved()) {
188                result.add(val);
189            }
190        }
191        return result;
192    }
193
194    public List<T> getPendingObjects() {
195        List<T> list = new ArrayList<T>();
196        List<Entry<K, T>> entries = getPendingEntries();
197        for (Entry<K, T> entry : entries) {
198            list.add(entry.object);
199        }
200        return list;
201    }
202
203    public List<Entry<K, T>> getMissingRequirements() {
204        List<Entry<K, T>> result = new ArrayList<Entry<K, T>>();
205        for (Map.Entry<K, Entry<K, T>> entry : registry.entrySet()) {
206            Entry<K, T> val = entry.getValue();
207            if (!val.isRegistered()) {
208                result.add(val);
209            }
210        }
211        return result;
212    }
213
214    /**
215     * Entries are sorted so an entry never depends on entries on its right.
216     */
217    public List<Entry<K, T>> getResolvedEntries() {
218        return resolved;
219    }
220
221    public List<T> getResolvedObjects() {
222        List<T> list = new ArrayList<T>();
223        List<Entry<K, T>> entries = resolved;
224        for (Entry<K, T> entry : entries) {
225            list.add(entry.object);
226        }
227        return list;
228    }
229
230    public void clear() {
231        for (Entry<K, T> entry : resolved) {
232            entry = registry.remove(entry.key);
233            if (entry != null) {
234                entry.isResolved = false;
235                unresolved(entry);
236                unregistered(entry);
237            }
238        }
239        resolved.clear();
240        Iterator<Entry<K, T>> it = registry.values().iterator();
241        while (it.hasNext()) {
242            Entry<K, T> entry = it.next();
243            it.remove();
244            if (entry.isRegistered()) {
245                unregistered(entry);
246            }
247        }
248    }
249
250    protected void updateDependencies(Entry<K, T> entry, Collection<K> requires) {
251        if (requires != null) {
252            for (K req : requires) {
253                Entry<K, T> reqEntry = registry.get(req);
254                if (reqEntry != null) {
255                    if (reqEntry.isResolved()) {
256                        // requirement satisfied -> continue
257                        reqEntry.addDependsOnMe(entry);
258                        continue;
259                    }
260                } else {
261                    reqEntry = new Entry<K, T>(req, null); // placeholder entry
262                    registry.put(req, reqEntry);
263                }
264                // dependencies not satisfied
265                reqEntry.addDependsOnMe(entry);
266                entry.addWaitingFor(reqEntry);
267            }
268        }
269    }
270
271    protected void registered(Entry<K, T> entry) {
272    }
273
274    protected void unregistered(Entry<K, T> entry) {
275    }
276
277    protected void resolved(Entry<K, T> entry) {
278    }
279
280    protected void unresolved(Entry<K, T> entry) {
281    }
282
283    public static final int PHANTOM = 0;
284
285    public static final int REGISTERED = 1;
286
287    public static final int RESOLVED = 3;
288
289    public static class Entry<K, T> {
290        private final K key;
291
292        private T object;
293
294        private Set<Entry<K, T>> waitsFor;
295
296        private Set<Entry<K, T>> dependsOnMe;
297
298        private boolean isResolved = false;
299
300        public Entry(K key, T object) {
301            this.key = key;
302            this.object = object;
303        }
304
305        public boolean isPhantom() {
306            return object == null;
307        }
308
309        public boolean isRegistered() {
310            return object != null;
311        }
312
313        public boolean isResolved() {
314            return isResolved;
315        }
316
317        public final boolean canEnterResolvedState() {
318            return !isResolved && object != null && waitsFor == null;
319        }
320
321        public final void addWaitingFor(Entry<K, T> entry) {
322            if (waitsFor == null) {
323                waitsFor = new HashSet<Entry<K, T>>();
324            }
325            waitsFor.add(entry);
326        }
327
328        public final void removeWaitingFor(Entry<K, T> key) {
329            if (waitsFor != null) {
330                waitsFor.remove(key);
331                if (waitsFor.isEmpty()) {
332                    waitsFor = null;
333                }
334            }
335        }
336
337        public final void addDependsOnMe(Entry<K, T> entry) {
338            if (dependsOnMe == null) {
339                dependsOnMe = new HashSet<Entry<K, T>>();
340            }
341            dependsOnMe.add(entry);
342        }
343
344        public Set<Entry<K, T>> getDependsOnMe() {
345            return dependsOnMe;
346        }
347
348        public Set<Entry<K, T>> getWaitsFor() {
349            return waitsFor;
350        }
351
352        public final T get() {
353            return object;
354        }
355
356        public K getKey() {
357            return key;
358        }
359
360        @Override
361        public String toString() {
362            return key.toString();
363        }
364
365        @Override
366        public boolean equals(Object obj) {
367            if (obj == null) {
368                return false;
369            }
370            if (obj == this) {
371                return true;
372            }
373            if (!(obj instanceof Entry)) {
374                return false;
375            }
376            return key.equals(((Entry<?, ?>) obj).key);
377        }
378
379        @Override
380        public int hashCode() {
381            return key.hashCode();
382        }
383    }
384
385}