keii.dev
A game framework written with osu! in mind.
1// Copyright (c) ppy Pty Ltd <contact@ppy.sh>. Licensed under the MIT Licence.
2// See the LICENCE file in the repository root for full licence text.
3
4using System;
5using System.Collections.Generic;
6using System.Diagnostics;
7using System.Linq;
8using osu.Framework.Lists;
9
10namespace osu.Framework.Graphics.Transforms
11{
12 /// <summary>
13 /// Tracks the lifetime of transforms for one specified target member.
14 /// </summary>
15 internal class TargetGroupingTransformTracker
16 {
17 /// <summary>
18 /// A list of <see cref="Transform"/>s associated with the <see cref="TargetGrouping"/>.
19 /// </summary>
20 public IReadOnlyList<Transform> Transforms => transforms;
21
22 /// <summary>
23 /// The member this instance is tracking.
24 /// </summary>
25 public readonly string TargetGrouping;
26
27 private readonly SortedList<Transform> transforms = new SortedList<Transform>(Transform.COMPARER);
28
29 private readonly Transformable transformable;
30
31 private readonly Queue<(ITransformSequence sequence, Action<ITransformSequence> action)> removalActions = new Queue<(ITransformSequence, Action<ITransformSequence>)>();
32
33 /// <summary>
34 /// Used to assign a monotonically increasing ID to <see cref="Transform"/>s as they are added. This member is
35 /// incremented whenever a <see cref="Transform"/> is added.
36 /// </summary>
37 private ulong currentTransformID;
38
39 /// <summary>
40 /// The index of the last transform in <see cref="transforms"/> to be applied to completion.
41 /// </summary>
42 private readonly Dictionary<string, int> lastAppliedTransformIndices = new Dictionary<string, int>();
43
44 /// <summary>
45 /// All <see cref="Transform.TargetMember"/>s which are handled by this tracker.
46 /// </summary>
47 public IEnumerable<string> TargetMembers => targetMembers;
48
49 private readonly HashSet<string> targetMembers = new HashSet<string>();
50
51 public TargetGroupingTransformTracker(Transformable transformable, string targetGrouping)
52 {
53 TargetGrouping = targetGrouping;
54 this.transformable = transformable;
55 }
56
57 public void UpdateTransforms(in double time, bool rewinding)
58 {
59 if (rewinding && !transformable.RemoveCompletedTransforms)
60 {
61 resetLastAppliedCache();
62
63 var appliedToEndReverts = new List<string>();
64
65 // Under the case that completed transforms are not removed, reversing the clock is permitted.
66 // We need to first look back through all the transforms and apply the start values of the ones that were previously
67 // applied, but now exist in the future relative to the current time.
68 for (int i = transforms.Count - 1; i >= 0; i--)
69 {
70 var t = transforms[i];
71
72 // rewind logic needs to only run on transforms which have been applied at least once.
73 if (!t.Applied)
74 continue;
75
76 // some specific transforms can be marked as non-rewindable.
77 if (!t.Rewindable)
78 continue;
79
80 if (time >= t.StartTime)
81 {
82 // we are in the middle of this transform, so we want to mark as not-completely-applied.
83 // note that we should only do this for the last transform of each TargetMember to avoid incorrect application order.
84 // the actual application will be in the main loop below now that AppliedToEnd is false.
85 if (!appliedToEndReverts.Contains(t.TargetMember))
86 {
87 t.AppliedToEnd = false;
88 appliedToEndReverts.Add(t.TargetMember);
89 }
90 }
91 else
92 {
93 // we are before the start time of this transform, so we want to eagerly apply the value at current time and mark as not-yet-applied.
94 // this transform will not be applied again unless we play forward in the future.
95 t.Apply(time);
96 t.Applied = false;
97 t.AppliedToEnd = false;
98 }
99 }
100 }
101
102 for (int i = getLastAppliedIndex(); i < transforms.Count; ++i)
103 {
104 var t = transforms[i];
105
106 var tCanRewind = !transformable.RemoveCompletedTransforms && t.Rewindable;
107
108 bool flushAppliedCache = false;
109
110 if (time < t.StartTime)
111 break;
112
113 if (!t.Applied)
114 {
115 // This is the first time we are updating this transform.
116 // We will find other still active transforms which act on the same target member and remove them.
117 // Since following transforms acting on the same target member are immediately removed when a
118 // new one is added, we can be sure that previous transforms were added before this one and can
119 // be safely removed.
120 for (int j = getLastAppliedIndex(t.TargetMember); j < i; ++j)
121 {
122 var u = transforms[j];
123 if (u.TargetMember != t.TargetMember) continue;
124
125 if (!u.AppliedToEnd)
126 // we may have applied the existing transforms too far into the future.
127 // we want to prepare to potentially read into the newly activated transform's StartTime,
128 // so we should re-apply using its StartTime as a basis.
129 u.Apply(t.StartTime);
130
131 if (!tCanRewind)
132 {
133 transforms.RemoveAt(j--);
134 flushAppliedCache = true;
135 i--;
136
137 if (u.AbortTargetSequence != null)
138 removalActions.Enqueue((u.AbortTargetSequence, s => s.TransformAborted()));
139 }
140 else
141 u.AppliedToEnd = true;
142 }
143 }
144
145 if (!t.HasStartValue)
146 {
147 t.ReadIntoStartValue();
148 t.HasStartValue = true;
149 }
150
151 if (!t.AppliedToEnd)
152 {
153 t.Apply(time);
154
155 t.AppliedToEnd = time >= t.EndTime;
156
157 if (t.AppliedToEnd)
158 {
159 if (!tCanRewind)
160 {
161 transforms.RemoveAt(i--);
162 flushAppliedCache = true;
163 }
164
165 if (t.IsLooping)
166 {
167 if (tCanRewind)
168 {
169 t.IsLooping = false;
170 t = t.Clone();
171 }
172
173 t.AppliedToEnd = false;
174 t.Applied = false;
175 t.HasStartValue = false;
176
177 t.IsLooping = true;
178
179 t.StartTime += t.LoopDelay;
180 t.EndTime += t.LoopDelay;
181
182 // this could be added back at a lower index than where we are currently iterating, but
183 // running the same transform twice isn't a huge deal.
184 transforms.Add(t);
185 flushAppliedCache = true;
186 }
187 else if (t.CompletionTargetSequence != null)
188 removalActions.Enqueue((t.CompletionTargetSequence, s => s.TransformCompleted()));
189 }
190 }
191
192 if (flushAppliedCache)
193 resetLastAppliedCache();
194 // if this transform is applied to end, we can be sure that all previous transforms have been completed.
195 else if (t.AppliedToEnd)
196 setLastAppliedIndex(t.TargetMember, i + 1);
197 }
198
199 invokePendingRemovalActions();
200 }
201
202 /// <summary>
203 /// Adds to this object a <see cref="Transform"/> which was previously populated using this object via
204 /// <see cref="TransformableExtensions.PopulateTransform{TValue, TEasing, TThis}"/>.
205 /// Added <see cref="Transform"/>s are immediately applied, and therefore have an immediate effect on this object if the current time of this
206 /// object falls within <see cref="Transform.StartTime"/> and <see cref="Transform.EndTime"/>.
207 /// If <see cref="Transformable.Clock"/> is null, e.g. because this object has just been constructed, then the given transform will be finished instantaneously.
208 /// </summary>
209 /// <param name="transform">The <see cref="Transform"/> to be added.</param>
210 /// <param name="customTransformID">When not null, the <see cref="Transform.TransformID"/> to assign for ordering.</param>
211 public void AddTransform(Transform transform, ulong? customTransformID = null)
212 {
213 Debug.Assert(!(transform.TransformID == 0 && transforms.Contains(transform)), $"Zero-id {nameof(Transform)}s should never be contained already.");
214
215 if (transform.TargetGrouping != TargetGrouping)
216 throw new ArgumentException($"Target grouping \"{transform.TargetGrouping}\" does not match this tracker's grouping \"{TargetGrouping}\".", nameof(transform));
217
218 targetMembers.Add(transform.TargetMember);
219
220 // This contains check may be optimized away in the future, should it become a bottleneck
221 if (transform.TransformID != 0 && transforms.Contains(transform))
222 throw new InvalidOperationException($"{nameof(Transformable)} may not contain the same {nameof(Transform)} more than once.");
223
224 transform.TransformID = customTransformID ?? ++currentTransformID;
225 int insertionIndex = transforms.Add(transform);
226 resetLastAppliedCache();
227
228 // Remove all existing following transforms touching the same property as this one.
229 for (int i = insertionIndex + 1; i < transforms.Count; ++i)
230 {
231 var t = transforms[i];
232
233 if (t.TargetMember == transform.TargetMember)
234 {
235 transforms.RemoveAt(i--);
236 if (t.AbortTargetSequence != null)
237 removalActions.Enqueue((t.AbortTargetSequence, s => s.TransformAborted()));
238 }
239 }
240
241 invokePendingRemovalActions();
242 }
243
244 /// <summary>
245 /// Removes a <see cref="Transform"/>.
246 /// </summary>
247 /// <param name="toRemove">The <see cref="Transform"/> to remove.</param>
248 public void RemoveTransform(Transform toRemove)
249 {
250 transforms.Remove(toRemove);
251 resetLastAppliedCache();
252 }
253
254 /// <summary>
255 /// Removes <see cref="Transform"/>s that start after <paramref name="time"/>.
256 /// </summary>
257 /// <param name="time">The time to clear <see cref="Transform"/>s after.</param>
258 /// <param name="targetMember">
259 /// An optional <see cref="Transform.TargetMember"/> name of <see cref="Transform"/>s to clear.
260 /// Null for clearing all <see cref="Transform"/>s.
261 /// </param>
262 public virtual void ClearTransformsAfter(double time, string targetMember = null)
263 {
264 resetLastAppliedCache();
265
266 if (targetMember == null)
267 {
268 for (int i = 0; i < transforms.Count; i++)
269 {
270 var t = transforms[i];
271
272 if (t.StartTime >= time)
273 {
274 transforms.RemoveAt(i--);
275 if (t.AbortTargetSequence != null)
276 removalActions.Enqueue((t.AbortTargetSequence, s => s.TransformAborted()));
277 }
278 }
279 }
280 else
281 {
282 for (int i = 0; i < transforms.Count; i++)
283 {
284 var t = transforms[i];
285
286 if (t.TargetMember == targetMember && t.StartTime >= time)
287 {
288 transforms.RemoveAt(i--);
289 if (t.AbortTargetSequence != null)
290 removalActions.Enqueue((t.AbortTargetSequence, s => s.TransformAborted()));
291 }
292 }
293 }
294
295 invokePendingRemovalActions();
296 }
297
298 /// <summary>
299 /// Finishes specified <see cref="Transform"/>s, using their <see cref="Transform{TValue}.EndValue"/>.
300 /// </summary>
301 /// <param name="targetMember">
302 /// An optional <see cref="Transform.TargetMember"/> name of <see cref="Transform"/>s to finish.
303 /// Null for finishing all <see cref="Transform"/>s.
304 /// </param>
305 public virtual void FinishTransforms(string targetMember = null)
306 {
307 Func<Transform, bool> toFlushPredicate;
308 if (targetMember == null)
309 toFlushPredicate = t => !t.IsLooping;
310 else
311 toFlushPredicate = t => !t.IsLooping && t.TargetMember == targetMember;
312
313 // Flush is undefined for endlessly looping transforms
314 var toFlush = transforms.Where(toFlushPredicate).ToArray();
315
316 transforms.RemoveAll(t => toFlushPredicate(t));
317 resetLastAppliedCache();
318
319 foreach (Transform t in toFlush)
320 {
321 if (!t.HasStartValue)
322 {
323 t.ReadIntoStartValue();
324 t.HasStartValue = true;
325 }
326
327 t.Apply(t.EndTime);
328 t.TriggerComplete();
329 }
330 }
331
332 private void invokePendingRemovalActions()
333 {
334 while (removalActions.TryDequeue(out var item))
335 item.action(item.sequence);
336 }
337
338 /// <summary>
339 /// Retrieve the last transform index that was <see cref="Transform.AppliedToEnd"/>.
340 /// </summary>
341 /// <param name="targetMember">An optional target member. If null, the lowest common last application is returned.</param>
342 private int getLastAppliedIndex(string targetMember = null)
343 {
344 if (targetMember == null)
345 {
346 int min = int.MaxValue;
347
348 foreach (int i in lastAppliedTransformIndices.Values)
349 {
350 if (i < min)
351 min = i;
352 }
353
354 return min;
355 }
356
357 if (lastAppliedTransformIndices.TryGetValue(targetMember, out int val))
358 return val;
359
360 return 0;
361 }
362
363 /// <summary>
364 /// Set the last transform index that was <see cref="Transform.AppliedToEnd"/> for a specific target member.
365 /// </summary>
366 /// <param name="targetMember">The target member to set the index of.</param>
367 /// <param name="index">The index of the transform in <see cref="transforms"/>.</param>
368 private void setLastAppliedIndex(string targetMember, int index)
369 {
370 lastAppliedTransformIndices[targetMember] = index;
371 }
372
373 /// <summary>
374 /// Reset the last applied index cache completely.
375 /// </summary>
376 private void resetLastAppliedCache()
377 {
378 foreach (var tracked in targetMembers)
379 lastAppliedTransformIndices[tracked] = 0;
380 }
381 }
382}