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