001/*
002 * Copyright 2006 - 2013
003 *     Stefan Balev     <stefan.balev@graphstream-project.org>
004 *     Julien Baudry    <julien.baudry@graphstream-project.org>
005 *     Antoine Dutot    <antoine.dutot@graphstream-project.org>
006 *     Yoann Pigné      <yoann.pigne@graphstream-project.org>
007 *     Guilhelm Savin   <guilhelm.savin@graphstream-project.org>
008 * 
009 * This file is part of GraphStream <http://graphstream-project.org>.
010 * 
011 * GraphStream is a library whose purpose is to handle static or dynamic
012 * graph, create them from scratch, file or any source and display them.
013 * 
014 * This program is free software distributed under the terms of two licenses, the
015 * CeCILL-C license that fits European law, and the GNU Lesser General Public
016 * License. You can  use, modify and/ or redistribute the software under the terms
017 * of the CeCILL-C license as circulated by CEA, CNRS and INRIA at the following
018 * URL <http://www.cecill.info> or under the terms of the GNU LGPL as published by
019 * the Free Software Foundation, either version 3 of the License, or (at your
020 * option) any later version.
021 * 
022 * This program is distributed in the hope that it will be useful, but WITHOUT ANY
023 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
024 * PARTICULAR PURPOSE.  See the GNU Lesser General Public License for more details.
025 * 
026 * You should have received a copy of the GNU Lesser General Public License
027 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
028 * 
029 * The fact that you are presently reading this means that you have had
030 * knowledge of the CeCILL-C and LGPL licenses and that you accept their terms.
031 */
032package org.graphstream.stream;
033
034import java.util.Iterator;
035import java.util.LinkedList;
036
037import org.graphstream.graph.Edge;
038import org.graphstream.graph.Graph;
039import org.graphstream.graph.Node;
040import org.graphstream.graph.implementations.AdjacencyListGraph;
041import org.graphstream.graph.implementations.Graphs;
042import org.graphstream.util.GraphDiff;
043import org.graphstream.util.VerboseSink;
044
045public class Timeline implements Source, Replayable, Iterable<Graph> {
046
047        public static final String TIME_PREFIX = "time";
048
049        private class StepDiff {
050                double step;
051                GraphDiff diff;
052
053                StepDiff(double step, GraphDiff diff) {
054                        this.step = step;
055                        this.diff = diff;
056                }
057        }
058
059        LinkedList<StepDiff> diffs;
060
061        protected boolean changed;
062        protected Graph initialGraph, currentGraph;
063        protected GraphDiff currentDiff;
064        protected Connector connector;
065        protected PipeBase pipe;
066        protected int seeker;
067
068        public Timeline() {
069                this.diffs = new LinkedList<StepDiff>();
070                this.changed = false;
071                this.connector = new Connector();
072                this.currentDiff = null;
073                this.pipe = new PipeBase();
074        }
075
076        public void reset() {
077
078        }
079
080        public void play(double from, double to) {
081                play(from, to, pipe);
082        }
083
084        public void play(double from, double to, Sink sink) {
085                if (diffs.size() == 0)
086                        return;
087
088                if (from > to) {
089                        int i = diffs.size() - 1, j;
090
091                        while (i > 0 && diffs.get(i).step > from)
092                                i--;
093
094                        j = i;
095
096                        while (j > 0 && diffs.get(j).step >= to)
097                                j--;
098
099                        for (int k = i; k >= j; k--)
100                                diffs.get(k).diff.reverse(sink);
101                } else {
102                        int i = 0, j;
103
104                        while (i < diffs.size() - 1 && diffs.get(i).step < from)
105                                i++;
106
107                        j = i;
108
109                        while (j < diffs.size() - 1 && diffs.get(j).step <= to)
110                                j++;
111
112                        for (int k = i; k <= j; k++)
113                                diffs.get(k).diff.apply(sink);
114                }
115        }
116
117        public void play() {
118                play(initialGraph.getStep(), currentGraph.getStep());
119        }
120
121        public void play(Sink sink) {
122                play(initialGraph.getStep(), currentGraph.getStep(), sink);
123        }
124
125        public void playback() {
126                play(currentGraph.getStep(), initialGraph.getStep());
127        }
128
129        public void playback(Sink sink) {
130                play(currentGraph.getStep(), initialGraph.getStep(), sink);
131        }
132
133        public void seek(int i) {
134                seeker = i;
135        }
136
137        public void seekStart() {
138                seeker = 0;
139        }
140
141        public void seekEnd() {
142                seeker = diffs.size();
143        }
144
145        public boolean hasNext() {
146                return seeker < diffs.size();
147        }
148
149        public void next() {
150                if (seeker >= diffs.size())
151                        return;
152
153                diffs.get(seeker++).diff.apply(pipe);
154        }
155
156        public boolean hasPrevious() {
157                return seeker > 0;
158        }
159
160        public void previous() {
161                if (seeker <= 0)
162                        return;
163
164                diffs.get(--seeker).diff.reverse(pipe);
165        }
166
167        /**
168         * 
169         * @param source
170         */
171        public void begin(Source source) {
172                initialGraph = new AdjacencyListGraph("initial");
173                currentGraph = new AdjacencyListGraph("initial");
174                begin();
175        }
176
177        /**
178         * 
179         * @param source
180         */
181        public void begin(Graph source) {
182                initialGraph = Graphs.clone(source);
183                currentGraph = source;
184                begin();
185        }
186
187        protected void begin() {
188                currentGraph.addSink(connector);
189                pushDiff();
190        }
191
192        /**
193         * 
194         */
195        public void end() {
196                if (currentDiff != null) {
197                        currentDiff.end();
198                        diffs.add(new StepDiff(currentGraph.getStep(), currentDiff));
199                }
200
201                currentGraph.removeSink(connector);
202                currentGraph = Graphs.clone(currentGraph);
203        }
204
205        protected void pushDiff() {
206                if (currentDiff != null) {
207                        currentDiff.end();
208                        diffs.add(new StepDiff(currentGraph.getStep(), currentDiff));
209                }
210
211                currentDiff = new GraphDiff();
212                currentDiff.start(currentGraph);
213        }
214
215        /*
216         * (non-Javadoc)
217         * 
218         * @see java.lang.Iterable#iterator()
219         */
220        public Iterator<Graph> iterator() {
221                return new TimelineIterator();
222        }
223
224        /*
225         * (non-Javadoc)
226         * 
227         * @see org.graphstream.stream.Replayable#getReplayController()
228         */
229        public Controller getReplayController() {
230                return new TimelineReplayController();
231        }
232
233        protected class Connector extends SinkAdapter {
234                @Override
235                public void stepBegins(String sourceId, long timeId, double step) {
236                        Timeline.this.pushDiff();
237                }
238        }
239
240        protected class TimelineReplayController extends PipeBase implements
241                        Controller {
242                public void replay() {
243                        play(this);
244                }
245
246                public void replay(String sourceId) {
247                        String tmp = this.sourceId;
248                        this.sourceId = sourceId;
249                        play(this);
250                        this.sourceId = tmp;
251                }
252        }
253
254        protected class TimelineIterator implements Iterator<Graph> {
255                Graph current;
256                int idx;
257
258                public TimelineIterator() {
259                        current = Graphs.clone(initialGraph);
260                        idx = 0;
261                }
262
263                /*
264                 * (non-Javadoc)
265                 * 
266                 * @see java.util.Iterator#hasNext()
267                 */
268                public boolean hasNext() {
269                        return idx < diffs.size();
270                }
271
272                /*
273                 * (non-Javadoc)
274                 * 
275                 * @see java.util.Iterator#next()
276                 */
277                public Graph next() {
278                        if (idx >= diffs.size())
279                                return null;
280
281                        diffs.get(idx++).diff.apply(current);
282                        return Graphs.clone(current);
283                }
284
285                /*
286                 * (non-Javadoc)
287                 * 
288                 * @see java.util.Iterator#remove()
289                 */
290                public void remove() {
291                }
292
293        }
294
295        /*
296         * (non-Javadoc)
297         * 
298         * @see org.graphstream.stream.Source#addSink(org.graphstream.stream.Sink)
299         */
300        public void addSink(Sink sink) {
301                pipe.addSink(sink);
302        }
303
304        /*
305         * (non-Javadoc)
306         * 
307         * @see
308         * org.graphstream.stream.Source#removeSink(org.graphstream.stream.Sink)
309         */
310        public void removeSink(Sink sink) {
311                pipe.removeSink(sink);
312        }
313
314        /*
315         * (non-Javadoc)
316         * 
317         * @see
318         * org.graphstream.stream.Source#addAttributeSink(org.graphstream.stream
319         * .AttributeSink)
320         */
321        public void addAttributeSink(AttributeSink sink) {
322                pipe.addAttributeSink(sink);
323        }
324
325        /*
326         * (non-Javadoc)
327         * 
328         * @see
329         * org.graphstream.stream.Source#removeAttributeSink(org.graphstream.stream
330         * .AttributeSink)
331         */
332        public void removeAttributeSink(AttributeSink sink) {
333                pipe.removeAttributeSink(sink);
334        }
335
336        /*
337         * (non-Javadoc)
338         * 
339         * @see org.graphstream.stream.Source#addElementSink(org.graphstream.stream.
340         * ElementSink)
341         */
342        public void addElementSink(ElementSink sink) {
343                pipe.addElementSink(sink);
344        }
345
346        /*
347         * (non-Javadoc)
348         * 
349         * @see
350         * org.graphstream.stream.Source#removeElementSink(org.graphstream.stream
351         * .ElementSink)
352         */
353        public void removeElementSink(ElementSink sink) {
354                pipe.removeElementSink(sink);
355        }
356
357        /*
358         * (non-Javadoc)
359         * 
360         * @see org.graphstream.stream.Source#clearElementSinks()
361         */
362        public void clearElementSinks() {
363                pipe.clearElementSinks();
364        }
365
366        /*
367         * (non-Javadoc)
368         * 
369         * @see org.graphstream.stream.Source#clearAttributeSinks()
370         */
371        public void clearAttributeSinks() {
372                pipe.clearAttributeSinks();
373        }
374
375        /*
376         * (non-Javadoc)
377         * 
378         * @see org.graphstream.stream.Source#clearSinks()
379         */
380        public void clearSinks() {
381                pipe.clearSinks();
382        }
383
384        public static void main(String... strings) throws Exception {
385                Graph g = new AdjacencyListGraph("g");
386                Timeline timeline = new Timeline();
387                timeline.addSink(new VerboseSink());
388
389                timeline.begin(g);
390
391                g.stepBegins(0.0);
392                g.addNode("A");
393                g.addNode("B");
394                g.stepBegins(1.0);
395                g.addNode("C");
396
397                timeline.end();
398
399                System.out.printf("############\n");
400                System.out.printf("# Play :\n");
401                timeline.play();
402                System.out.printf("############\n");
403                System.out.printf("# Playback :\n");
404                timeline.playback();
405                System.out.printf("############\n");
406                System.out.printf("# Sequence :\n");
407                int i = 0;
408                for (Graph it : timeline) {
409                        System.out.printf(" Graph#%d %s\n", i, toString(it));
410                }
411                System.out.printf("############\n");
412        }
413
414        private static String toString(Graph g) {
415                StringBuilder buffer = new StringBuilder();
416                buffer.append("id=\"").append(g.getId()).append("\" node={");
417
418                for (Node n : g)
419                        buffer.append("\"").append(n.getId()).append("\", ");
420                buffer.append("}, edges={");
421                for (Edge e : g.getEachEdge())
422                        buffer.append("\"").append(e.getId()).append("\":\"")
423                                        .append(e.getSourceNode().getId()).append("\"--\"")
424                                        .append(e.getTargetNode().getId()).append("\", ");
425                buffer.append("}");
426
427                return buffer.toString();
428        }
429}