-
-
Notifications
You must be signed in to change notification settings - Fork 33
/
HierarhyId.cs
451 lines (396 loc) · 18.7 KB
/
HierarhyId.cs
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
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.Linq;
namespace Microsoft.SqlServer.Types.SqlHierarchy
{
/// <summary>
/// Represents hierarchical data.
/// </summary>
[Serializable]
internal struct HierarchyId : IComparable
{
private readonly string _hierarchyId;
private readonly long[][] _nodes;
static readonly long[][] __RootNodes = new long[0][];
internal long[][] GetNodes() => _nodes ?? __RootNodes;
/// <summary>
/// The Path separator character
/// </summary>
public const string PathSeparator = "/";
private const string InvalidHierarchyIdExceptionMessage =
"The input string '{0}' is not a valid string representation of a HierarchyId node.";
private const string GetReparentedValueOldRootExceptionMessage =
"HierarchyId.GetReparentedValue failed because 'oldRoot' was not an ancestor node of 'this'. 'oldRoot' was '{0}', and 'this' was '{1}'.";
private const string GetDescendantMostBeChildExceptionMessage =
"HierarchyId.GetDescendant failed because '{0}' must be a child of 'this'. '{0}' was '{1}' and 'this' was '{2}'.";
private const string GetDescendantChild1MustLessThanChild2ExceptionMessage =
"HierarchyId.GetDescendant failed because 'child1' must be less than 'child2'. 'child1' was '{0}' and 'child2' was '{1}'.";
internal HierarchyId(long[][] nodes)
{
if (nodes == null)
throw new ArgumentNullException(nameof(nodes));
this._nodes = nodes;
this._hierarchyId = nodes == null || nodes.Length == 0 ? PathSeparator :
(PathSeparator + string.Join(PathSeparator, nodes.Select(LongArrayToString)) + PathSeparator);
}
/// <summary>
/// Constructs an HierarchyId with the given canonical string representation value.
/// </summary>
/// <returns>Hierarchyid value.</returns>
/// <param name="hierarchyId">Canonical string representation</param>
public HierarchyId(string hierarchyId)
{
_hierarchyId = hierarchyId ?? throw new ArgumentNullException(nameof(hierarchyId));
if (hierarchyId == "/")
{
_nodes = __RootNodes;
}
else
{
var nodesStr = hierarchyId.Split('/');
if (!string.IsNullOrEmpty(nodesStr[0]) || !string.IsNullOrEmpty(nodesStr[nodesStr.Length - 1]))
throw new HierarchyIdException(string.Format(CultureInfo.InvariantCulture, InvalidHierarchyIdExceptionMessage, hierarchyId));
int nodesCount = nodesStr.Length - 2;
var nodes = new long[nodesCount][];
for (int i = 0; i < nodesCount; i++)
{
string node = nodesStr[i + 1];
var intsStr = node.Split('.');
var ints = new long[intsStr.Length];
for (int j = 0; j < intsStr.Length; j++)
{
if (!long.TryParse(intsStr[j], out long num))
throw new HierarchyIdException(string.Format(CultureInfo.InvariantCulture, InvalidHierarchyIdExceptionMessage, hierarchyId));
ints[j] = num;
}
nodes[i] = ints;
}
_nodes = nodes;
}
}
/// <summary>
/// Returns a hierarchyid representing the nth ancestor of this.
/// </summary>
/// <returns>A hierarchyid representing the nth ancestor of this.</returns>
/// <param name="n">n</param>
[SuppressMessage("Microsoft.Naming", "CA1704:IdentifiersShouldBeSpelledCorrectly", MessageId = "n")]
public HierarchyId GetAncestor(int n)
{
if (GetLevel() == n)
return new HierarchyId(__RootNodes);
if (GetLevel() < n)
throw new ArgumentException(nameof(n));
string hierarchyStr = PathSeparator + string.Join(PathSeparator, GetNodes().Take(GetLevel() - n).Select(LongArrayToString)) + PathSeparator;
return new HierarchyId(hierarchyStr);
}
/// <summary>
/// Returns a child node of the parent.
/// </summary>
/// <param name="child1"> null or the hierarchyid of a child of the current node. </param>
/// <param name="child2"> null or the hierarchyid of a child of the current node. </param>
/// <returns>
/// Returns one child node that is a descendant of the parent.
/// If both child1 and child2 are null, returns a child of parent.
/// If child1 is not null, and child2 is null, returns a child of parent greater than child1.
/// If child2 is not null and child1 is null, returns a child of parent less than child2.
/// If child1 and child2 are not null, returns a child of parent greater than child1 and less than child2.
/// If child1 is not null and not a child of parent, an exception is raised.
/// If child2 is not null and not a child of parent, an exception is raised.
/// If child1 >= child2, an exception is raised.
/// </returns>
public HierarchyId GetDescendant(HierarchyId? child1, HierarchyId? child2)
{
if (child1 != null && (child1.Value.GetLevel() != GetLevel() + 1 || !child1.Value.IsDescendantOf(this)))
throw new HierarchyIdException(string.Format(CultureInfo.InvariantCulture, GetDescendantMostBeChildExceptionMessage, "child1", child1, ToString()));
if (child2 != null && (child2.Value.GetLevel() != GetLevel() + 1 || !child2.Value.IsDescendantOf(this)))
throw new HierarchyIdException(string.Format(CultureInfo.InvariantCulture, GetDescendantMostBeChildExceptionMessage, "child2", child1, ToString()));
if (child1 == null && child2 == null)
return new HierarchyId(ToString() + 1 + PathSeparator);
string hierarchyStr;
if (child1 == null)
{
var result = new HierarchyId(child2.ToString());
var lastNode = result.GetNodes().Last();
//decrease the last part of the last node of the 1nd child
lastNode[lastNode.Length - 1]--;
hierarchyStr = PathSeparator + string.Join(PathSeparator, result.GetNodes().Select(LongArrayToString)) + PathSeparator;
return new HierarchyId(hierarchyStr);
}
if (child2 == null)
{
var result = new HierarchyId(child1.ToString());
var lastNode = result.GetNodes().Last();
//increase the last part of the last node of the 2nd child
lastNode[lastNode.Length - 1]++;
hierarchyStr = PathSeparator + string.Join(PathSeparator, result.GetNodes().Select(LongArrayToString)) + PathSeparator;
return new HierarchyId(hierarchyStr);
}
var child1LastNode = child1.Value.GetNodes().Last();
var child2LastNode = child2.Value.GetNodes().Last();
var cmp = CompareLongArrays(child1LastNode, child2LastNode);
if (cmp >= 0)
{
throw new HierarchyIdException( string.Format(CultureInfo.InvariantCulture, GetDescendantChild1MustLessThanChild2ExceptionMessage, child1, child2));
}
var newNode = GetBetween(child1LastNode, child2LastNode);
var nodesToJoin = GetNodes().Select(LongArrayToString).Concat(new[] {LongArrayToString(newNode)});
return new HierarchyId(PathSeparator + string.Join(PathSeparator, nodesToJoin) + PathSeparator);
}
static long[] GetBetween(long[] node1, long[] node2)
{
int i = 0;
for (; i < node1.Length; i++)
{
if (node1[i] < node2[i])
{
break;
}
}
if (i == node1.Length)
i--;
var result = node1.Take(i + 1).ToArray();
if (result[i] + 1 < node2[i])
{
result[i]++;
return result;
}
else if (node1.Length > i + 1)
{
return result.Concat(new[] { node1[i + 1] + 1 }).ToArray();
}
else if (node2.Length > i + 1)
{
return result.Concat(new[] { node2[i + 1] - 1 }).ToArray();
}
else if (node2.Length >= i + 1)
{
return result.Concat(new[] { 1L }).ToArray();
}
return result;
}
/// <summary>
/// Returns an integer that represents the depth of the node this in the tree.
/// </summary>
/// <returns>An integer that represents the depth of the node this in the tree.</returns>
public short GetLevel()
{
return (short)GetNodes().Length;
}
/// <summary>
/// Returns the root of the hierarchy tree.
/// </summary>
/// <returns>The root of the hierarchy tree.</returns>
[SuppressMessage("Microsoft.Design", "CA1024:UsePropertiesWhereAppropriate")]
public static HierarchyId GetRoot()
{
return new HierarchyId("/");
}
/// <summary>
/// Returns true if this is a descendant of parent.
/// </summary>
/// <returns>True if this is a descendant of parent.</returns>
/// <param name="parent">parent</param>
public bool IsDescendantOf(HierarchyId parent)
{
if (parent.GetLevel() > GetLevel())
{
return false;
}
for (int i = 0; i < parent.GetLevel(); i++)
{
int cmp = CompareLongArrays(GetNodes()[i], parent.GetNodes()[i]);
if (cmp != 0)
{
return false;
}
}
return true;
}
/// <summary>
/// Returns a node whose path from the root is the path to newRoot, followed by the path from oldRoot to this.
/// </summary>
/// <returns>Hierarchyid value.</returns>
/// <param name="oldRoot">oldRoot</param>
/// <param name="newRoot">newRoot</param>
[SuppressMessage("Microsoft.Naming", "CA1704:IdentifiersShouldBeSpelledCorrectly", MessageId = "Reparented")]
public HierarchyId GetReparentedValue(HierarchyId oldRoot, HierarchyId newRoot)
{
if (!IsDescendantOf(oldRoot))
{
throw new ArgumentException(
string.Format(CultureInfo.InvariantCulture, GetReparentedValueOldRootExceptionMessage, oldRoot, ToString()), "oldRoot");
}
StringBuilder sb = new StringBuilder();
sb.Append(PathSeparator);
foreach (var node in newRoot.GetNodes())
{
sb.Append(LongArrayToString(node));
sb.Append(PathSeparator);
}
foreach (var node in GetNodes().Skip(oldRoot.GetLevel()))
{
sb.Append(LongArrayToString(node));
sb.Append(PathSeparator);
}
return new HierarchyId(sb.ToString());
}
/// <summary>
/// Converts the canonical string representation of a hierarchyid to a hierarchyid value.
/// </summary>
/// <returns>Hierarchyid value.</returns>
/// <param name="input">input</param>
public static HierarchyId Parse(string input)
{
return new HierarchyId(input);
}
private static string LongArrayToString(IEnumerable<long> array)
{
return string.Join(".", array);
}
private static int CompareLongArrays(long[] array1, long[] array2)
{
int count = Math.Min(array1.Length, array2.Length);
for (int i = 0; i < count; i++)
{
long item1 = array1[i];
long item2 = array2[i];
if (item1 < item2)
return -1;
if (item1 > item2)
return 1;
}
if (array1.Length > count)
return 1;
if (array2.Length > count)
return -1;
return 0;
}
/// <summary>
/// Compares two HierarchyIds by their values.
/// </summary>
/// <param name="hid1"> a HierarchyId to compare </param>
/// <param name="hid2"> a HierarchyId to compare </param>
/// <returns>
/// A 32-bit signed integer that indicates the lexical relationship between the two comparands.
/// Value Condition Less than zero: hid1 is less than hid2.
/// Zero: hid1 equals hid2.
/// Greater than zero: hid1 is greater than hid2.
/// </returns>
public static int Compare(HierarchyId hid1, HierarchyId hid2)
{
var nodes1 = hid1.GetNodes();
var nodes2 = hid2.GetNodes();
int count = Math.Min(nodes1.Length, nodes2.Length);
for (int i = 0; i < count; i++)
{
var node1 = nodes1[i];
var node2 = nodes2[i];
int cmp = CompareLongArrays(node1, node2);
if (cmp != 0)
return cmp;
}
if (nodes1.Length > count)
return 1;
if (nodes2.Length > count)
return -1;
return 0;
}
/// <summary>
/// Compares two HierarchyIds by their values.
/// </summary>
/// <param name="hid1"> a HierarchyId to compare </param>
/// <param name="hid2"> a HierarchyId to compare </param>
/// <returns>
/// true if the the first parameter is less than the second parameter, false otherwise
/// </returns>
public static bool operator <(HierarchyId hid1, HierarchyId hid2) => Compare(hid1, hid2) < 0;
/// <summary>
/// Compares two HierarchyIds by their values.
/// </summary>
/// <param name="hid1"> a HierarchyId to compare </param>
/// <param name="hid2"> a HierarchyId to compare </param>
/// <returns>
/// true if the the first parameter is greater than the second parameter, false otherwise
/// </returns>
public static bool operator >(HierarchyId hid1, HierarchyId hid2) => Compare(hid1, hid2) > 0;
/// <summary>
/// Compares two HierarchyIds by their values.
/// </summary>
/// <param name="hid1"> a HierarchyId to compare </param>
/// <param name="hid2"> a HierarchyId to compare </param>
/// <returns>
/// true if the the first parameter is less or equal than the second parameter, false otherwise
/// </returns>
public static bool operator <=(HierarchyId hid1, HierarchyId hid2) => Compare(hid1, hid2) <= 0;
/// <summary>
/// Compares two HierarchyIds by their values.
/// </summary>
/// <param name="hid1"> a HierarchyId to compare </param>
/// <param name="hid2"> a HierarchyId to compare </param>
/// <returns>
/// true if the the first parameter is greater or equal than the second parameter, false otherwise
/// </returns>
public static bool operator >=(HierarchyId hid1, HierarchyId hid2) => Compare(hid1, hid2) >= 0;
/// <summary>
/// Compares two HierarchyIds by their values.
/// </summary>
/// <param name="hid1"> a HierarchyId to compare </param>
/// <param name="hid2"> a HierarchyId to compare </param>
/// <returns> true if the two HierarchyIds are equal, false otherwise </returns>
public static bool operator ==(HierarchyId hid1, HierarchyId hid2) => Compare(hid1, hid2) == 0;
/// <summary>
/// Compares two HierarchyIds by their values.
/// </summary>
/// <param name="hid1"> a HierarchyId to compare </param>
/// <param name="hid2"> a HierarchyId to compare </param>
/// <returns> true if the two HierarchyIds are not equal, false otherwise </returns>
public static bool operator !=(HierarchyId hid1, HierarchyId hid2) => Compare(hid1, hid2) != 0;
/// <summary>
/// Compares this instance to a given HierarchyId by their values.
/// </summary>
/// <param name="other"> the HierarchyId to compare against this instance </param>
/// <returns> true if this instance is equal to the given HierarchyId, and false otherwise </returns>
public bool Equals(HierarchyId other) => Compare(this, other) == 0;
/// <summary>
/// Returns a value-based hash code, to allow HierarchyId to be used in hash tables.
/// </summary>
/// <returns> the hash value of this HierarchyId </returns>
public override int GetHashCode()
{
return ToString().GetHashCode();
}
/// <summary>
/// Compares this instance to a given HierarchyId by their values.
/// </summary>
/// <param name="obj"> the HierarchyId to compare against this instance </param>
/// <returns> true if this instance is equal to the given HierarchyId, and false otherwise </returns>
public override bool Equals(object obj)
{
return Equals((HierarchyId)obj);
}
/// <summary>
/// Returns a string representation of the hierarchyid value.
/// </summary>
/// <returns>A string representation of the hierarchyid value.</returns>
public override string ToString()
{
return _hierarchyId ?? "NULL";
}
public bool IsNull => _hierarchyId == null;
/// <summary>
/// Implementation of IComparable.CompareTo()
/// </summary>
/// <param name="obj"> The object to compare to </param>
/// <returns> 0 if the HierarchyIds are "equal" (i.e., have the same _hierarchyId value) </returns>
public int CompareTo(object obj)
{
if (obj is HierarchyId h)
{
return Compare(this, h);
}
Debug.Assert(false, "object is not a HierarchyId");
return -1;
}
}
}