/
SortedIndexedArray.cs
119 lines (93 loc) · 2.78 KB
/
SortedIndexedArray.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
using System;
using System.Collections.Generic;
using System.Linq;
using CollectionTest.Model;
namespace CollectionTest.Collection
{
public class SortedIndexedArray<T>: List<T> where T : IDated
{
private int[] indexer;
public void BuildIndex()
{
var length = base[Count - 1].Date;
indexer = new int[length];
var num = 0;
var last = base[0].Date;
for (int i = 0; i < length; i++)
{
if (i > last)
{
num++;
last = base[num].Date;
}
indexer[i] = num;
}
}
public void AddToIndex()
{
if (indexer == null || indexer.Count() <= 1)
{
BuildIndex();
return;
}
var lastIndex = indexer[indexer.Length - 1];
var index = indexer.Length;
if (Count - 1 == indexer[indexer.Length - 1]) //indexer is not dirty
return;
var newIndexer = new int[base[Count - 1].Date];
Array.Copy(indexer, newIndexer, indexer.Length);
while(index < base[Count - 1].Date)
{
for (int j = 0; j < base[lastIndex + 1].Date - base[lastIndex].Date; j++)
{
newIndexer[index] = lastIndex + 1;
index++;
}
lastIndex++;
}
indexer = newIndexer;
}
public T Right(int date)
{
if (date >= base[Count - 1].Date)
return default(T);
var index = indexer[date];
if (base[index].Date == date)
index++;
return base[index];
}
public IEnumerable<T> RangeFromTo(int from, int to)
{
var fromIndex = GetIndex(from);
if (fromIndex < 0)
return new List<T>();
var toIndex = GetIndex(to);
int length;
if (toIndex < 0)
length = Count - fromIndex;
else
{
length = toIndex - fromIndex;
if (base[toIndex].Date == to)
length++;
}
return this.Skip(fromIndex).Take(length);
}
private int GetIndex(int date)
{
if (date > indexer.Length - 1)
return -1;
return indexer[date];
}
public new void Add(T obj)
{
base.Add(obj);
if(indexer != null)
AddToIndex();
}
public new void AddRange(IEnumerable<T> collection)
{
throw new NotSupportedException();
}
}
}