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.common.collections;
023
024import java.util.ArrayList;
025import java.util.Arrays;
026import java.util.Collection;
027import java.util.HashMap;
028import java.util.HashSet;
029import java.util.Iterator;
030import java.util.List;
031import java.util.Map;
032import java.util.Set;
033
034/**
035 * @author <a href="mailto:bs@nuxeo.com">Bogdan Stefanescu</a>
036 */
037// TODO handle dependencies cycles.
038@SuppressWarnings({ "ClassWithoutToString" })
039public class DependencyTree<K, T> implements Iterable<DependencyTree.Entry<K, T>> {
040
041    private final Map<K, Entry<K, T>> registry;
042
043    // the sorted list of resolved entries.
044    // given an element e from that list it is ensured that any element at the left
045    // of 'e' doesn't depends on it
046    private final List<Entry<K, T>> resolved;
047
048    private EventHandler<T> eventHandler;
049
050    public DependencyTree() {
051        registry = new HashMap<K, Entry<K, T>>();
052        resolved = new ArrayList<Entry<K, T>>();
053    }
054
055    public Iterator<Entry<K, T>> iterator() {
056        return registry.values().iterator();
057    }
058
059    public void add(K key, T object, K... requires) {
060        add(key, object, Arrays.asList(requires));
061    }
062
063    public void 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;
073        }
074        updateDependencies(entry, requires);
075        notifyRegistered(entry);
076        // resolve it if no pending requirements
077        if (entry.isResolved()) {
078            resolve(entry);
079        }
080    }
081
082    public void add(K key, T object) {
083        add(key, object, (Collection<K>) null);
084    }
085
086    public void remove(K key) {
087        Entry<K, T> entry = registry.remove(key);
088        if (entry != null) {
089            unregister(entry);
090        }
091    }
092
093    public void unregister(Entry<K, T> entry) {
094        if (entry.isResolved()) {
095            unresolve(entry);
096        }
097        notifyUnregistered(entry);
098    }
099
100    public Entry<K, T> getEntry(K key) {
101        return registry.get(key);
102    }
103
104    public T get(K key) {
105        Entry<K, T> entry = registry.get(key);
106        return entry != null ? entry.object : null;
107    }
108
109    public void resolve(Entry<K, T> entry) {
110        resolved.add(entry);
111        // notify listener
112        notifyResolved(entry);
113        // resolve any dependent entry if they are waiting only for me
114        Set<Entry<K, T>> deps = entry.getDependsOnMe();
115        if (deps != null) {
116            for (Entry<K, T> dep : deps) {
117                dep.removeWaitingFor(entry);
118                if (dep.isResolved()) {
119                    resolve(dep); // resolve the dependent entry
120                }
121            }
122        }
123    }
124
125    public void unresolve(Entry<K, T> entry) {
126        // unresolve any dependent object
127        Set<Entry<K, T>> deps = entry.getDependsOnMe();
128        if (deps != null) {
129            for (Entry<K, T> dep : deps) {
130                dep.addWaitingFor(entry);
131                if (!dep.isResolved()) {
132                    unresolve(dep); // unresolve the dependent entry
133                }
134            }
135        }
136        resolved.remove(entry);
137        notifyUnresolved(entry);
138    }
139
140    public boolean isRegistered(K key) {
141        Entry<K, T> entry = registry.get(key);
142        return entry != null && entry.object != null;
143    }
144
145    public boolean isResolved(K key) {
146        Entry<K, T> entry = registry.get(key);
147        return entry != null && entry.isResolved();
148    }
149
150    public void setEventHandler(EventHandler<T> eventHandler) {
151        this.eventHandler = eventHandler;
152    }
153
154    public Collection<Entry<K, T>> getEntries() {
155        return registry.values();
156    }
157
158    public List<Entry<K, T>> getPendingEntries() {
159        List<Entry<K, T>> result = new ArrayList<Entry<K, T>>();
160        for (Map.Entry<K, Entry<K, T>> entry : registry.entrySet()) {
161            Entry<K, T> val = entry.getValue();
162            if (!val.isResolved()) {
163                result.add(val);
164            }
165        }
166        return result;
167    }
168
169    public List<T> getPendingObjects() {
170        List<T> list = new ArrayList<T>();
171        List<Entry<K, T>> entries = getPendingEntries();
172        for (Entry<K, T> entry : entries) {
173            list.add(entry.object);
174        }
175        return list;
176    }
177
178    public List<Entry<K, T>> getMissingRequirements() {
179        List<Entry<K, T>> result = new ArrayList<Entry<K, T>>();
180        for (Map.Entry<K, Entry<K, T>> entry : registry.entrySet()) {
181            Entry<K, T> val = entry.getValue();
182            if (!val.isRegistered()) {
183                result.add(val);
184            }
185        }
186        return result;
187    }
188
189    /**
190     * Entries are sorted so an entry never depends on entries on its right.
191     */
192    public List<Entry<K, T>> getResolvedEntries() {
193        return resolved;
194    }
195
196    public List<T> getResolvedObjects() {
197        List<T> list = new ArrayList<T>();
198        List<Entry<K, T>> entries = resolved;
199        for (Entry<K, T> entry : entries) {
200            list.add(entry.object);
201        }
202        return list;
203    }
204
205    public void clear() {
206        for (Entry<K, T> entry : resolved) {
207            entry = registry.remove(entry.key);
208            if (entry != null) {
209                notifyUnresolved(entry);
210                notifyUnregistered(entry);
211            }
212        }
213        resolved.clear();
214        Iterator<Entry<K, T>> it = registry.values().iterator();
215        while (it.hasNext()) {
216            Entry<K, T> entry = it.next();
217            it.remove();
218            if (entry.isRegistered()) {
219                notifyUnregistered(entry);
220            }
221        }
222    }
223
224    protected void updateDependencies(Entry<K, T> entry, Collection<K> requires) {
225        if (requires != null) {
226            for (K req : requires) {
227                Entry<K, T> reqEntry = registry.get(req);
228                if (reqEntry != null) {
229                    if (reqEntry.isResolved()) {
230                        // requirement satisfied -> continue
231                        reqEntry.addDependsOnMe(entry);
232                        continue;
233                    }
234                } else {
235                    reqEntry = new Entry<K, T>(req, null);
236                    registry.put(req, reqEntry);
237                }
238                // dependencies not satisfied
239                reqEntry.addDependsOnMe(entry);
240                entry.addWaitingFor(reqEntry);
241            }
242        }
243    }
244
245    private void notifyRegistered(Entry<K, T> entry) {
246        if (eventHandler != null) {
247            eventHandler.registered(entry.object);
248        }
249    }
250
251    private void notifyUnregistered(Entry<K, T> entry) {
252        if (eventHandler != null) {
253            eventHandler.unregistered(entry.object);
254        }
255    }
256
257    private void notifyResolved(Entry<K, T> entry) {
258        if (eventHandler != null) {
259            eventHandler.resolved(entry.object);
260        }
261    }
262
263    private void notifyUnresolved(Entry<K, T> entry) {
264        if (eventHandler != null) {
265            eventHandler.unresolved(entry.object);
266        }
267    }
268
269    public static class Entry<K, T> {
270        private final K key;
271
272        private T object;
273
274        private Set<Entry<K, T>> waitsFor;
275
276        private Set<Entry<K, T>> dependsOnMe;
277
278        public Entry(K key, T object) {
279            this.key = key;
280            this.object = object;
281        }
282
283        public final boolean isRegistered() {
284            return object != null;
285        }
286
287        public final boolean isResolved() {
288            return object != null && waitsFor == null;
289        }
290
291        public final void addWaitingFor(Entry<K, T> entry) {
292            if (waitsFor == null) {
293                waitsFor = new HashSet<Entry<K, T>>();
294            }
295            waitsFor.add(entry);
296        }
297
298        public final void removeWaitingFor(Entry<K, T> key) {
299            if (waitsFor != null) {
300                waitsFor.remove(key);
301                if (waitsFor.isEmpty()) {
302                    waitsFor = null;
303                }
304            }
305        }
306
307        public final void addDependsOnMe(Entry<K, T> entry) {
308            if (dependsOnMe == null) {
309                dependsOnMe = new HashSet<Entry<K, T>>();
310            }
311            dependsOnMe.add(entry);
312        }
313
314        public Set<Entry<K, T>> getDependsOnMe() {
315            return dependsOnMe;
316        }
317
318        /**
319         * @return Returns the waitsFor.
320         */
321        public Set<Entry<K, T>> getWaitsFor() {
322            return waitsFor;
323        }
324
325        public final T get() {
326            return object;
327        }
328
329        /**
330         * @return Returns the key.
331         */
332        public K getKey() {
333            return key;
334        }
335
336        @Override
337        public String toString() {
338            return key.toString();
339        }
340
341        @Override
342        public boolean equals(Object obj) {
343            if (obj == this) {
344                return true;
345            }
346            if (!(obj instanceof Entry)) {
347                return false;
348            }
349            return key.equals(((Entry) obj).key);
350        }
351
352        @Override
353        public int hashCode() {
354            return key.hashCode();
355        }
356    }
357
358    interface EventHandler<T> {
359
360        void registered(T object);
361
362        void unregistered(T object);
363
364        void resolved(T object);
365
366        void unresolved(T object);
367
368    }
369
370}