← Back to branch summary

~ubuntu-branches/ubuntu/oneiric/monodevelop/oneiric

« back to all changes in this revision

Viewing changes to contrib/NGit/NGit.Revplot/PlotCommitList.cs

  • Committer: Bazaar Package Importer
  • Author(s): Jo Shields
  • Date: 2011-06-27 17:03:13 UTC
  • mto: (1.8.1 upstream)
  • mto: This revision was merged to the branch mainline in revision 54.
  • Revision ID: james.westby@ubuntu.com-20110627170313-6cvz3s19x6e9hqe9
Import upstream version 2.5.92+dfsg

Show diffs side-by-side

added added

removed removed

Lines of Context:
contrib/NGit/NGit.Revplot/PlotCommitList.cs
 
1
/*
 
2
This code is derived from jgit (http://eclipse.org/jgit).
 
3
Copyright owners are documented in jgit's IP log.
 
4
 
 
5
This program and the accompanying materials are made available
 
6
under the terms of the Eclipse Distribution License v1.0 which
 
7
accompanies this distribution, is reproduced below, and is
 
8
available at http://www.eclipse.org/org/documents/edl-v10.php
 
9
 
 
10
All rights reserved.
 
11
 
 
12
Redistribution and use in source and binary forms, with or
 
13
without modification, are permitted provided that the following
 
14
conditions are met:
 
15
 
 
16
- Redistributions of source code must retain the above copyright
 
17
  notice, this list of conditions and the following disclaimer.
 
18
 
 
19
- Redistributions in binary form must reproduce the above
 
20
  copyright notice, this list of conditions and the following
 
21
  disclaimer in the documentation and/or other materials provided
 
22
  with the distribution.
 
23
 
 
24
- Neither the name of the Eclipse Foundation, Inc. nor the
 
25
  names of its contributors may be used to endorse or promote
 
26
  products derived from this software without specific prior
 
27
  written permission.
 
28
 
 
29
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
 
30
CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
 
31
INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 
32
OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 
33
ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
 
34
CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 
35
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 
36
NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 
37
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
 
38
CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 
39
STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 
40
ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 
41
ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
42
*/
 
43
 
 
44
using System;
 
45
using System.Collections.Generic;
 
46
using NGit;
 
47
using NGit.Revplot;
 
48
using NGit.Revwalk;
 
49
using Sharpen;
 
50
 
 
51
namespace NGit.Revplot
 
52
{
 
53
        /// <summary>
 
54
        /// An ordered list of
 
55
        /// <see cref="PlotCommit{L}">PlotCommit&lt;L&gt;</see>
 
56
        /// subclasses.
 
57
        /// <p>
 
58
        /// Commits are allocated into lanes as they enter the list, based upon their
 
59
        /// connections between descendant (child) commits and ancestor (parent) commits.
 
60
        /// <p>
 
61
        /// The source of the list must be a
 
62
        /// <see cref="PlotWalk">PlotWalk</see>
 
63
        /// and
 
64
        /// <see cref="NGit.Revwalk.RevCommitList{E}.FillTo(int)">NGit.Revwalk.RevCommitList&lt;E&gt;.FillTo(int)
 
65
        ///     </see>
 
66
        /// must be used to populate the list.
 
67
        /// </summary>
 
68
        /// <?></?>
 
69
        public class PlotCommitList<L> : RevCommitList<PlotCommit<L>> where L:PlotLane
 
70
        {
 
71
                internal const int MAX_LENGTH = 25;
 
72
 
 
73
                private int positionsAllocated;
 
74
 
 
75
                private readonly TreeSet<int> freePositions = new TreeSet<int>();
 
76
 
 
77
                private readonly HashSet<PlotLane> activeLanes = new HashSet<PlotLane>();
 
78
 
 
79
                public override void Clear()
 
80
                {
 
81
                        base.Clear();
 
82
                        positionsAllocated = 0;
 
83
                        freePositions.Clear();
 
84
                        activeLanes.Clear();
 
85
                }
 
86
 
 
87
                public override void Source(RevWalk w)
 
88
                {
 
89
                        if (!(w is PlotWalk))
 
90
                        {
 
91
                                throw new InvalidCastException(MessageFormat.Format(JGitText.Get().classCastNotA, 
 
92
                                        typeof(PlotWalk).FullName));
 
93
                        }
 
94
                        base.Source(w);
 
95
                }
 
96
 
 
97
                /// <summary>Find the set of lanes passing through a commit's row.</summary>
 
98
                /// <remarks>
 
99
                /// Find the set of lanes passing through a commit's row.
 
100
                /// <p>
 
101
                /// Lanes passing through a commit are lanes that the commit is not directly
 
102
                /// on, but that need to travel through this commit to connect a descendant
 
103
                /// (child) commit to an ancestor (parent) commit. Typically these lanes will
 
104
                /// be drawn as lines in the passed commit's box, and the passed commit won't
 
105
                /// appear to be connected to those lines.
 
106
                /// <p>
 
107
                /// This method modifies the passed collection by adding the lanes in any
 
108
                /// order.
 
109
                /// </remarks>
 
110
                /// <param name="currCommit">the commit the caller needs to get the lanes from.</param>
 
111
                /// <param name="result">collection to add the passing lanes into.</param>
 
112
                public virtual void FindPassingThrough(PlotCommit<L> currCommit, ICollection<L> result
 
113
                        )
 
114
                {
 
115
                        foreach (PlotLane p in currCommit.passingLanes)
 
116
                        {
 
117
                                result.AddItem((L)p);
 
118
                        }
 
119
                }
 
120
 
 
121
                protected internal override void Enter(int index, PlotCommit<L> currCommit)
 
122
                {
 
123
                        SetupChildren(currCommit);
 
124
                        int nChildren = currCommit.GetChildCount();
 
125
                        if (nChildren == 0)
 
126
                        {
 
127
                                return;
 
128
                        }
 
129
                        if (nChildren == 1 && currCommit.children[0].ParentCount < 2)
 
130
                        {
 
131
                                // Only one child, child has only us as their parent.
 
132
                                // Stay in the same lane as the child.
 
133
                                //
 
134
                                PlotCommit c = currCommit.children[0];
 
135
                                if (c.lane == null)
 
136
                                {
 
137
                                        // Hmmph. This child must be the first along this lane.
 
138
                                        //
 
139
                                        c.lane = NextFreeLane();
 
140
                                        activeLanes.AddItem(c.lane);
 
141
                                }
 
142
                                for (int r = index - 1; r >= 0; r--)
 
143
                                {
 
144
                                        PlotCommit rObj = this[r];
 
145
                                        if (rObj == c)
 
146
                                        {
 
147
                                                break;
 
148
                                        }
 
149
                                        rObj.AddPassingLane(c.lane);
 
150
                                }
 
151
                                currCommit.lane = c.lane;
 
152
                        }
 
153
                        else
 
154
                        {
 
155
                                // More than one child, or our child is a merge.
 
156
                                // Use a different lane.
 
157
                                //
 
158
                                // Process all our children. Especially important when there is more
 
159
                                // than one child (e.g. a commit is processed where other branches
 
160
                                // fork out). For each child the following is done
 
161
                                // 1. If no lane was assigned to the child a new lane is created and
 
162
                                // assigned
 
163
                                // 2. The lane of the child is closed. If this frees a position,
 
164
                                // this position will be added freePositions list.
 
165
                                // If we have multiple children which where previously not on a lane
 
166
                                // each such child will get his own new lane but all those new lanes
 
167
                                // will be on the same position. We have to take care that not
 
168
                                // multiple newly created (in step 1) lanes occupy that position on
 
169
                                // which the
 
170
                                // parent's lane will be on. Therefore we delay closing the lane
 
171
                                // with the parents position until all children are processed.
 
172
                                // The lane on that position the current commit will be on
 
173
                                PlotLane reservedLane = null;
 
174
                                for (int i = 0; i < nChildren; i++)
 
175
                                {
 
176
                                        PlotCommit c = currCommit.children[i];
 
177
                                        // don't forget to position all of your children if they are
 
178
                                        // not already positioned.
 
179
                                        if (c.lane == null)
 
180
                                        {
 
181
                                                c.lane = NextFreeLane();
 
182
                                                activeLanes.AddItem(c.lane);
 
183
                                                if (reservedLane != null)
 
184
                                                {
 
185
                                                        CloseLane(c.lane);
 
186
                                                }
 
187
                                                else
 
188
                                                {
 
189
                                                        reservedLane = c.lane;
 
190
                                                }
 
191
                                        }
 
192
                                        else
 
193
                                        {
 
194
                                                if (reservedLane == null && activeLanes.Contains(c.lane))
 
195
                                                {
 
196
                                                        reservedLane = c.lane;
 
197
                                                }
 
198
                                                else
 
199
                                                {
 
200
                                                        CloseLane(c.lane);
 
201
                                                }
 
202
                                        }
 
203
                                }
 
204
                                // finally all children are processed. We can close the lane on that
 
205
                                // position our current commit will be on.
 
206
                                if (reservedLane != null)
 
207
                                {
 
208
                                        CloseLane(reservedLane);
 
209
                                }
 
210
                                currCommit.lane = NextFreeLane();
 
211
                                activeLanes.AddItem(currCommit.lane);
 
212
                                // take care: when connecting yourself to your child make sure that
 
213
                                // you will not be located on a lane on which a passed commit is
 
214
                                // located on. Otherwise we would have to draw a line through a
 
215
                                // commit.
 
216
                                int remaining = nChildren;
 
217
                                BitSet blockedPositions = new BitSet();
 
218
                                for (int r = index - 1; r >= 0; r--)
 
219
                                {
 
220
                                        PlotCommit rObj = this[r];
 
221
                                        if (currCommit.IsChild(rObj))
 
222
                                        {
 
223
                                                if (--remaining == 0)
 
224
                                                {
 
225
                                                        break;
 
226
                                                }
 
227
                                        }
 
228
                                        if (rObj != null)
 
229
                                        {
 
230
                                                PlotLane lane = rObj.GetLane();
 
231
                                                if (lane != null)
 
232
                                                {
 
233
                                                        blockedPositions.Set(lane.GetPosition());
 
234
                                                }
 
235
                                                rObj.AddPassingLane(currCommit.lane);
 
236
                                        }
 
237
                                }
 
238
                                // Now let's check whether we have to reposition the lane
 
239
                                if (blockedPositions.Get(currCommit.lane.GetPosition()))
 
240
                                {
 
241
                                        int newPos = -1;
 
242
                                        foreach (int pos in freePositions)
 
243
                                        {
 
244
                                                if (!blockedPositions.Get(pos))
 
245
                                                {
 
246
                                                        newPos = pos;
 
247
                                                        break;
 
248
                                                }
 
249
                                        }
 
250
                                        if (newPos == -1)
 
251
                                        {
 
252
                                                newPos = positionsAllocated++;
 
253
                                        }
 
254
                                        freePositions.AddItem(currCommit.lane.GetPosition());
 
255
                                        currCommit.lane.position = newPos;
 
256
                                }
 
257
                        }
 
258
                }
 
259
 
 
260
                private void CloseLane(PlotLane lane)
 
261
                {
 
262
                        RecycleLane((L)lane);
 
263
                        if (activeLanes.Remove(lane))
 
264
                        {
 
265
                                freePositions.AddItem(Sharpen.Extensions.ValueOf(lane.GetPosition()));
 
266
                        }
 
267
                }
 
268
 
 
269
                private void SetupChildren(PlotCommit<L> currCommit)
 
270
                {
 
271
                        int nParents = currCommit.ParentCount;
 
272
                        for (int i = 0; i < nParents; i++)
 
273
                        {
 
274
                                ((PlotCommit)currCommit.GetParent(i)).AddChild(currCommit);
 
275
                        }
 
276
                }
 
277
 
 
278
                private PlotLane NextFreeLane()
 
279
                {
 
280
                        PlotLane p = CreateLane();
 
281
                        if (freePositions.IsEmpty())
 
282
                        {
 
283
                                p.position = positionsAllocated++;
 
284
                        }
 
285
                        else
 
286
                        {
 
287
                                int min = freePositions.First();
 
288
                                p.position = min;
 
289
                                freePositions.Remove(min);
 
290
                        }
 
291
                        return p;
 
292
                }
 
293
 
 
294
                /// <returns>a new Lane appropriate for this particular PlotList.</returns>
 
295
                protected internal virtual L CreateLane()
 
296
                {
 
297
                        return (L)new PlotLane();
 
298
                }
 
299
 
 
300
                /// <summary>
 
301
                /// Return colors and other reusable information to the plotter when a lane
 
302
                /// is no longer needed.
 
303
                /// </summary>
 
304
                /// <remarks>
 
305
                /// Return colors and other reusable information to the plotter when a lane
 
306
                /// is no longer needed.
 
307
                /// </remarks>
 
308
                /// <param name="lane"></param>
 
309
                protected internal virtual void RecycleLane(L lane)
 
310
                {
 
311
                }
 
312
                // Nothing.
 
313
        }
 
314
}