File size: 8,521 Bytes
18a519f | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 | using System;
using System.Collections.Generic;
namespace UnityEngine.Timeline
{
interface IInterval
{
Int64 intervalStart { get; }
Int64 intervalEnd { get; }
}
struct IntervalTreeNode // interval node,
{
public Int64 center; // midpoint for this node
public int first; // index of first element of this node in m_Entries
public int last; // index of the last element of this node in m_Entries
public int left; // index in m_Nodes of the left subnode
public int right; // index in m_Nodes of the right subnode
}
class IntervalTree<T> where T : IInterval
{
internal struct Entry
{
public Int64 intervalStart;
public Int64 intervalEnd;
public T item;
}
const int kMinNodeSize = 10; // the minimum number of entries to have subnodes
const int kInvalidNode = -1;
const Int64 kCenterUnknown = Int64.MaxValue; // center hasn't been calculated. indicates no children
readonly List<Entry> m_Entries = new List<Entry>();
readonly List<IntervalTreeNode> m_Nodes = new List<IntervalTreeNode>();
/// <summary>
/// Whether the tree will be rebuilt on the next query
/// </summary>
public bool dirty { get; internal set; }
/// <summary>
/// Add an IInterval to the tree
/// </summary>
public void Add(T item)
{
if (item == null)
return;
m_Entries.Add(
new Entry()
{
intervalStart = item.intervalStart,
intervalEnd = item.intervalEnd,
item = item
}
);
dirty = true;
}
/// <summary>
/// Query the tree at a particular time
/// </summary>
/// <param name="value"></param>
/// <param name="results"></param>
public void IntersectsWith(Int64 value, List<T> results)
{
if (m_Entries.Count == 0)
return;
if (dirty)
{
Rebuild();
dirty = false;
}
if (m_Nodes.Count > 0)
Query(m_Nodes[0], value, results);
}
/// <summary>
/// Query the tree at a particular range of time
/// </summary>
/// <param name="start"></param>
/// <param name="end"></param>
/// <param name="results"></param>
public void IntersectsWithRange(Int64 start, Int64 end, List<T> results)
{
if (start > end)
return;
if (m_Entries.Count == 0)
return;
if (dirty)
{
Rebuild();
dirty = false;
}
if (m_Nodes.Count > 0)
QueryRange(m_Nodes[0], start, end, results);
}
/// <summary>
/// Updates the intervals from their source. Use this to detect if the data in the tree
/// has changed.
/// </summary>
public void UpdateIntervals()
{
bool isDirty = false;
for (int i = 0; i < m_Entries.Count; i++)
{
var n = m_Entries[i];
var s = n.item.intervalStart;
var e = n.item.intervalEnd;
isDirty |= n.intervalStart != s;
isDirty |= n.intervalEnd != e;
m_Entries[i] = new Entry()
{
intervalStart = s,
intervalEnd = e,
item = n.item
};
}
dirty |= isDirty;
}
private void Query(IntervalTreeNode intervalTreeNode, Int64 value, List<T> results)
{
for (int i = intervalTreeNode.first; i <= intervalTreeNode.last; i++)
{
var entry = m_Entries[i];
if (value >= entry.intervalStart && value < entry.intervalEnd)
{
results.Add(entry.item);
}
}
if (intervalTreeNode.center == kCenterUnknown)
return;
if (intervalTreeNode.left != kInvalidNode && value < intervalTreeNode.center)
Query(m_Nodes[intervalTreeNode.left], value, results);
if (intervalTreeNode.right != kInvalidNode && value > intervalTreeNode.center)
Query(m_Nodes[intervalTreeNode.right], value, results);
}
private void QueryRange(IntervalTreeNode intervalTreeNode, Int64 start, Int64 end, List<T> results)
{
for (int i = intervalTreeNode.first; i <= intervalTreeNode.last; i++)
{
var entry = m_Entries[i];
if (end >= entry.intervalStart && start < entry.intervalEnd)
{
results.Add(entry.item);
}
}
if (intervalTreeNode.center == kCenterUnknown)
return;
if (intervalTreeNode.left != kInvalidNode && start < intervalTreeNode.center)
QueryRange(m_Nodes[intervalTreeNode.left], start, end, results);
if (intervalTreeNode.right != kInvalidNode && end > intervalTreeNode.center)
QueryRange(m_Nodes[intervalTreeNode.right], start, end, results);
}
private void Rebuild()
{
m_Nodes.Clear();
m_Nodes.Capacity = m_Entries.Capacity;
Rebuild(0, m_Entries.Count - 1);
}
private int Rebuild(int start, int end)
{
IntervalTreeNode intervalTreeNode = new IntervalTreeNode();
// minimum size, don't subdivide
int count = end - start + 1;
if (count < kMinNodeSize)
{
intervalTreeNode = new IntervalTreeNode() { center = kCenterUnknown, first = start, last = end, left = kInvalidNode, right = kInvalidNode };
m_Nodes.Add(intervalTreeNode);
return m_Nodes.Count - 1;
}
var min = Int64.MaxValue;
var max = Int64.MinValue;
for (int i = start; i <= end; i++)
{
var o = m_Entries[i];
min = Math.Min(min, o.intervalStart);
max = Math.Max(max, o.intervalEnd);
}
var center = (max + min) / 2;
intervalTreeNode.center = center;
// first pass, put every thing left of center, left
int x = start;
int y = end;
while (true)
{
while (x <= end && m_Entries[x].intervalEnd < center)
x++;
while (y >= start && m_Entries[y].intervalEnd >= center)
y--;
if (x > y)
break;
var nodeX = m_Entries[x];
var nodeY = m_Entries[y];
m_Entries[y] = nodeX;
m_Entries[x] = nodeY;
}
intervalTreeNode.first = x;
// second pass, put every start passed the center right
y = end;
while (true)
{
while (x <= end && m_Entries[x].intervalStart <= center)
x++;
while (y >= start && m_Entries[y].intervalStart > center)
y--;
if (x > y)
break;
var nodeX = m_Entries[x];
var nodeY = m_Entries[y];
m_Entries[y] = nodeX;
m_Entries[x] = nodeY;
}
intervalTreeNode.last = y;
// reserve a place
m_Nodes.Add(new IntervalTreeNode());
int index = m_Nodes.Count - 1;
intervalTreeNode.left = kInvalidNode;
intervalTreeNode.right = kInvalidNode;
if (start < intervalTreeNode.first)
intervalTreeNode.left = Rebuild(start, intervalTreeNode.first - 1);
if (end > intervalTreeNode.last)
intervalTreeNode.right = Rebuild(intervalTreeNode.last + 1, end);
m_Nodes[index] = intervalTreeNode;
return index;
}
public void Clear()
{
m_Entries.Clear();
m_Nodes.Clear();
}
}
}
|