1
|
/*
|
2
|
Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft
|
3
|
Permission is hereby granted, free of charge, to any person obtaining a copy
|
4
|
of this software and associated documentation files (the "Software"), to deal
|
5
|
in the Software without restriction, including without limitation the rights
|
6
|
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
|
7
|
copies of the Software, and to permit persons to whom the Software is
|
8
|
furnished to do so, subject to the following conditions:
|
9
|
|
10
|
The above copyright notice and this permission notice shall be included in
|
11
|
all copies or substantial portions of the Software.
|
12
|
|
13
|
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
|
14
|
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
|
15
|
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
|
16
|
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
|
17
|
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
|
18
|
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
|
19
|
SOFTWARE.
|
20
|
*/
|
21
|
|
22
|
// C5 example: Views 2004-12-29 OBSOLETE
|
23
|
|
24
|
// Compile with
|
25
|
// csc /r:C5.dll Views.cs
|
26
|
|
27
|
using System;
|
28
|
using C5;
|
29
|
using SCG = System.Collections.Generic;
|
30
|
|
31
|
namespace Views {
|
32
|
class Views {
|
33
|
public static void Main(String[] args) {
|
34
|
IList<char> lst = new LinkedList<char>();
|
35
|
lst.AddAll<char>(new char[] { 'a', 'b', 'c', 'd' });
|
36
|
IList<char>
|
37
|
A = lst.View(0, 2),
|
38
|
B = lst.View(2, 0),
|
39
|
C = lst.View(2, 1),
|
40
|
D = lst.View(3, 1),
|
41
|
E = lst.View(4, 0),
|
42
|
F = lst.View(1, 2),
|
43
|
G = lst.View(0, 4);
|
44
|
IList<char>[] views = { A, B, C, D, E, F, G };
|
45
|
Console.WriteLine("ABCDEFG overlaps with:");
|
46
|
foreach (IList<char> u in views) {
|
47
|
foreach (IList<char> w in views)
|
48
|
Console.Write(Overlap(u, w) ? '+' : '-');
|
49
|
Console.WriteLine();
|
50
|
}
|
51
|
Console.WriteLine("ABCDEFG overlap length:");
|
52
|
foreach (IList<char> u in views) {
|
53
|
foreach (IList<char> w in views) {
|
54
|
int len = OverlapLength(u, w);
|
55
|
Console.Write(len >= 0 ? String.Format("{0}", len) : " ");
|
56
|
}
|
57
|
Console.WriteLine();
|
58
|
}
|
59
|
Console.WriteLine("ABCDEFG contained in:");
|
60
|
foreach (IList<char> u in views) {
|
61
|
foreach (IList<char> w in views)
|
62
|
Console.Write(ContainsView(u, w) ? '+' : '-');
|
63
|
Console.WriteLine();
|
64
|
}
|
65
|
}
|
66
|
|
67
|
public static int LeftEndIndex<T>(IList<T> u) {
|
68
|
return u.Offset;
|
69
|
}
|
70
|
|
71
|
public static int RightEndIndex<T>(IList<T> u) {
|
72
|
return u.Offset+u.Count;
|
73
|
}
|
74
|
|
75
|
public static bool Overlap<T>(IList<T> u, IList<T> w) {
|
76
|
if (u.Underlying == null || u.Underlying != w.Underlying)
|
77
|
throw new ArgumentException("views must have same underlying list");
|
78
|
else
|
79
|
return u.Offset < w.Offset+w.Count && w.Offset < u.Offset+u.Count;
|
80
|
}
|
81
|
|
82
|
public static int OverlapLength<T>(IList<T> u, IList<T> w) {
|
83
|
if (Overlap(u, w))
|
84
|
return Math.Min(u.Offset+u.Count, w.Offset+w.Count)
|
85
|
- Math.Max(u.Offset, w.Offset);
|
86
|
else
|
87
|
return -1; // No overlap
|
88
|
}
|
89
|
|
90
|
public static bool ContainsView<T>(IList<T> u, IList<T> w) {
|
91
|
if (u.Underlying == null || u.Underlying != w.Underlying)
|
92
|
throw new ArgumentException("views must have same underlying list");
|
93
|
else
|
94
|
if (w.Count > 0)
|
95
|
return u.Offset <= w.Offset && w.Offset+w.Count <= u.Offset+u.Count;
|
96
|
else
|
97
|
return u.Offset < w.Offset && w.Offset < u.Offset+u.Count;
|
98
|
}
|
99
|
|
100
|
public static bool SameUnderlying<T>(IList<T> u, IList<T> w) {
|
101
|
return (u.Underlying ?? u) == (w.Underlying ?? w);
|
102
|
}
|
103
|
|
104
|
// Replace the first occurrence of each x from xs by y in list:
|
105
|
|
106
|
public static void ReplaceXsByY<T>(HashedLinkedList<T> list, T[] xs, T y) {
|
107
|
foreach (T x in xs) {
|
108
|
using (IList<T> view = list.ViewOf(x)) {
|
109
|
if (view != null) {
|
110
|
view.Remove();
|
111
|
view.Add(y);
|
112
|
}
|
113
|
}
|
114
|
}
|
115
|
}
|
116
|
|
117
|
// Find first item that satisfies p
|
118
|
|
119
|
public static bool Find<T>(IList<T> list, Fun<T,bool> p, out T res) {
|
120
|
IList<T> view = list.View(0, 0);
|
121
|
while (view.Offset < list.Count) {
|
122
|
view.Slide(+1, 1);
|
123
|
if (p(view.First)) {
|
124
|
res = view.First;
|
125
|
return true;
|
126
|
}
|
127
|
}
|
128
|
res = default(T);
|
129
|
return false;
|
130
|
}
|
131
|
|
132
|
// Or, using that the list is enumerable:
|
133
|
|
134
|
public static bool Find1<T>(IList<T> list, Fun<T,bool> p, out T res) {
|
135
|
foreach (T x in list) {
|
136
|
if (p(x)) {
|
137
|
res = x;
|
138
|
return true;
|
139
|
}
|
140
|
}
|
141
|
res = default(T);
|
142
|
return false;
|
143
|
}
|
144
|
|
145
|
// Find last item that satisfies p
|
146
|
|
147
|
public static bool FindLast<T>(IList<T> list, Fun<T,bool> p, out T res) {
|
148
|
IList<T> view = list.View(list.Count, 0);
|
149
|
while (view.Offset > 0) {
|
150
|
view.Slide(-1, 1);
|
151
|
if (p(view.First)) {
|
152
|
res = view.First;
|
153
|
return true;
|
154
|
}
|
155
|
}
|
156
|
res = default(T);
|
157
|
return false;
|
158
|
}
|
159
|
}
|
160
|
}
|