Mercurial > repos > rhope

comparison list.rhope @ 126:85f8012b6938

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Simplify and speed up List by removing support for sparse Lists
author Mike Pavone <pavone@retrodev.com>
date Thu, 28 Oct 2010 21:39:17 -0400
parents f4fc0a98088a
children
comparison
equal deleted inserted replaced
125:e556416e9c91 126:85f8012b6938
9 out, not found <- [[list]Buffer >>]Index[index] 9 out, not found <- [[list]Buffer >>]Index[index]
10 } 10 }
11 11
12 Set@List Leaf[list,index,value:out,invalid index] 12 Set@List Leaf[list,index,value:out,invalid index]
13 { 13 {
14 If[[index] < [0]] 14
15 { 15 len <- [[list]Buffer >>]Length
16 rev index <- [[[list]Buffer >>]Length]+[index] 16
17 invalid index <- If[[rev index] < [0]] {} 17 If[[[index] > [7]] And [[index] >= [len]]]
18 {
19 out,invalid index <- [list]Set[rev index, value]
20 }
21
22 }{
23 len <- [[list]Buffer >>]Length
24 If[[index] > [len]]
25 {
26 makeleft <- Yes
27 }{
28 If[[[index] > [7]] And [[index] >= [len]]]
29 {
30 makeleft <- Yes
31 }{
32 out <- [list]Buffer <<[ [[list]Buffer >>]Set[index, value] ]
33 }
34 }
35 }
36
37 Val[makeleft]
38 { 18 {
39 out <- [[[[[[Build[List()] 19 out <- [[[[[[Build[List()]
40 ]Buffer << [[Array[]]Append[value]] 20 ]Buffer << [Array[]]
41 ]Left << [list] 21 ]Left << [list]
42 ]Right << [List[]] 22 ]Right << [List[]]
43 ]Offset << [index] 23 ]Offset << [8i32]
44 ]Right Offset <<[[index]+[8i32]] 24 ]Length << [[list]Length]
45 ]Length << [ [[list]Length]+[1] ] 25 ]Set[index, value]
46 } 26 }{
47 } 27 out <- [list]Buffer <<[ [[list]Buffer >>]Set[index, value] ]
48
49 _Right Set@List Leaf[list,index,val:out,didn't set]
50 {
51 len <- [[list]Buffer >>]Length
52 do it <- If[[index] < [len]] {}
53 {
54 ,didn't set <- If[[index]=[len]]
55 {
56 didn't set,do it <- If[[index]>[7]]
57 }
58 }
59 Val[do it]
60 {
61 out <- [list]Set[index,val]
62 } 28 }
63 } 29 }
64 30
65 Length@List Leaf[list:out] 31 Length@List Leaf[list:out]
66 { 32 {
104 { 70 {
105 Buffer 71 Buffer
106 Left 72 Left
107 Right 73 Right
108 Offset(Int32,Naked) 74 Offset(Int32,Naked)
109 Right Offset(Int32,Naked)
110 Length(Int32,Naked) 75 Length(Int32,Naked)
111 } 76 }
112 77
113 List[:out(List)] 78 List[:out(List)]
114 { 79 {
115 out <- [Build[List Leaf()]]Buffer <<[Array[]] 80 out <- [Build[List Leaf()]]Buffer <<[Array[]]
116 } 81 }
117 82
118 Index@List[list,index:out,not found] 83 Index@List[list,index:out,not found]
119 { 84 {
120 If[[index]<[[list]Offset >>]] 85 offset <- [list]Offset >>
86 If[[index]<[offset]]
121 { 87 {
122 out, not found <- [[list]Left >>]Index[index] 88 out, not found <- [[list]Left >>]Index[index]
123 }{ 89 }{
124 If[[index] < [[list]Right Offset >>]] 90 right offset <- [offset]+[8i32]
91 If[[index] < [right offset]]
125 { 92 {
126 out, not found <- [[list]Buffer >>]Index[[index]-[[list]Offset >>]] 93 out, not found <- [[list]Buffer >>]Index[[index]-[[list]Offset >>]]
127 }{ 94 }{
128 out, not found <- [[list]Right >>]Index[[index]-[[list]Right Offset >>]] 95 out, not found <- [[list]Right >>]Index[[index]-[right offset]]
129 } 96 }
130 } 97 }
131 } 98 }
132 99
133 Length@List[list:out] 100 Length@List[list:out]
135 out <- [list]Length >> 102 out <- [list]Length >>
136 } 103 }
137 104
138 Set@List[list,index,val:out,invalid index] 105 Set@List[list,index,val:out,invalid index]
139 { 106 {
140 If[[index] < [0]] 107 If[[index]>[[list]Length]]
141 { 108 {
142 , invalid index <- [list]Last 109 out <- [[list]Set[[index]-[1], val]
143 { rev index <- [[~]+[1]]+[index] } 110 ]Set[index, val]
144 invalid index <- If[[rev index] < [0]] {} 111 }{
145 { out,invalid index <- [list]Set[rev index, val] } 112 offset <- [list]Offset >>
146 113 If[[index]<[offset]]
147 }{
148 If[[index]<[[list]Offset >>]]
149 { 114 {
150 lsize <- [[list]Left >>]Length 115 lsize <- [[list]Left >>]Length
151 [[list]Left >>]Set[index, val] 116 ,invalid <- [[list]Left >>]Set[index, val]
152 { 117 {
153 out <- [[list]Left <<[~] 118 out <- [[list]Left <<[~]
154 ]Length <<[ [[list]Length >>]+[[[~]Length]-[lsize]] ] 119 ]Length <<[ [[list]Length >>]+[[[~]Length]-[lsize]] ]
155 } 120 }
156 }{ 121 }{
157 122 right offset <- [offset]+[8]
158 If[[index]<[[list]Right Offset >>]] 123 If[[index]<[right offset]]
159 { 124 {
160 off index <- [index]-[[list]Offset >>] 125 off index <- [index]-[[list]Offset >>]
161 bsize <- [[list]Buffer >>]Length 126 bsize <- [[list]Buffer >>]Length
162 If[[off index]>[bsize]] 127 [[list]Buffer >>]Set[off index, val]
163 { 128 {
164 If[[[list]Right >>]Length] 129 out <- [[list]Buffer <<[~]
165 { 130 ]Length <<[ [[list]Length >>]+[[[~]Length >>]-[bsize]] ]
166 my end <- [[list]Offset >>]+[[[list]Buffer >>]Length]
167 nroffset <- [[[index]-[my end]]/[2]]+[my end]
168 nright <- out <- [[[[[[Build[List()]
169 ]Buffer << [[Array[]]Append[val]]
170 ]Left << [List[]]
171 ]Right << [[list]Right >>]
172 ]Offset << [[index]-[nroffset]]
173 ]Right Offset <<[ [[list]Right Offset>>]-[nroffset] ]
174 ]Length << [ [[[list]Right >>]Length]+[1] ]
175
176 out <- [[[list]Right <<[nright]
177 ]Length <<[ [[list]Length >>]+[1] ]
178 ]Right Offset <<[nroffset]
179 }{
180 out <- [[[list]Right <<[ [[list]Right >>]Set[0, val] ]
181 ]Right Offset <<[index]
182 ]Length <<[ [[list]Length >>]+[1] ]
183 }
184 }{
185 [[list]Buffer >>]Set[off index, val]
186 {
187 out <- [[list]Buffer <<[~]
188 ]Length <<[ [[list]Length >>]+[[[~]Length >>]-[bsize]] ]
189 }
190 } 131 }
191 }{ 132 }{
192 rsize <- [[list]Right>>]Length 133 rsize <- [[list]Right>>]Length
193 adj ind <- [index]-[[list]Right Offset>>] 134 adj ind <- [index]-[right offset]
194 If[[[[list]Left>>]Length] > [rsize]] 135 If[[[[list]Left>>]Length] > [rsize]]
195 { 136 {
196 [[list]Right >>]Set[adj ind, val] 137 [[list]Right >>]Set[adj ind, val]
197 { 138 {
198 out <- [[list]Right <<[~] 139 out <- [[list]Right <<[~]
199 ]Length <<[ [[list]Length >>]+[[[~]Length]-[rsize]] ] 140 ]Length <<[ [[list]Length >>]+[[[~]Length]-[rsize]] ]
200 } 141 }
201 }{ 142 }{
202 [[list]Right >>]_Right Set[adj ind, val] 143 out <- [[[[[Build[List()]
203 { 144 ]Buffer << [[Array[]]Append[val]]
204 out <- [[list]Right <<[~] 145 ]Left << [list]
205 ]Length <<[ [[list]Length >>]+[[[~]Length]-[rsize]] ] 146 ]Right << [List[]]
206 }{ 147 ]Offset << [index]
207 out <- [[[[[[Build[List()] 148 ]Length << [ [[list]Length]+[1] ]
208 ]Buffer << [[Array[]]Append[val]]
209 ]Left << [list]
210 ]Right << [List[]]
211 ]Offset << [index]
212 ]Right Offset <<[[index]+[8i32]]
213 ]Length << [ [[list]Length]+[1] ]
214 }
215 } 149 }
216 } 150 }
217 } 151 }
218 } 152 }
219 } 153 }
220 154
221 _Right Set@List[list,index,val:out,didn't set]
222 {
223 If[[[list]Right Offset >>]>[index]]
224 {
225 out <- [list]Set[index, val]
226 }{
227 ,didn't set <- [[list]Right >>]_Right Set[[index]-[[list]Right Offset >>], val]
228 { out <- [list]Right <<[~] }
229 }
230 }
231
232 Last@List[list:out,none] 155 Last@List[list:out,none]
233 { 156 {
234 [[list]Right >>]Last 157 out <- [[list]Length]-[1]
235 { out <- [~]+[[list]Right Offset >>] }
236 { out <- [[[[list]Buffer >>]Length]-[1]]+[[list]Offset >>] }
237 } 158 }
238 159
239 Append@List[list,val:out] 160 Append@List[list,val:out]
240 { 161 {
241 [list]Last 162 [list]Last
254 } 175 }
255 } 176 }
256 177
257 Next@List[list,index:next,none] 178 Next@List[list,index:next,none]
258 { 179 {
259 If[[index] < [[[list]Offset >>]-[1]]] 180 pos next <- [index]+[1]
260 { 181 ,none <- If[[pos next] < [[list]Length]]
261 next <- [[list]Left >>]Next[index] {} 182 {
262 { next <- Offset >>[list] } 183 next <- Val[pos next]
263 }{
264 If[[index] < [[list]Right Offset >>]]
265 {
266 pos next <- [index]+[1]
267 If[[pos next] < [[[[list]Buffer >>]Length]+[[list]Offset >>]]]
268 {
269 next <- Val[pos next]
270 }{
271 ,none <- [[list]Right >>]First
272 { next <- [~]+[[list]Right Offset >>] }
273 }
274 }{
275 ,none <- [[list]Right >>]Next[[index]-[[list]Right Offset >>]]
276 { next <- [~]+[[list]Right Offset >>] }
277 }
278 } 184 }
279 } 185 }
280 186
281 New Like@List[in:out] 187 New Like@List[in:out]
282 { 188 {
329 Print@List[list:out] 235 Print@List[list:out]
330 { 236 {
331 Print["List"] 237 Print["List"]
332 { out <- _Print Seq[list, [list]First] } 238 { out <- _Print Seq[list, [list]First] }
333 } 239 }
334
335 240
336 Peek@List[list:out,empty] 241 Peek@List[list:out,empty]
337 { 242 {
338 [list]Last 243 [list]Last
339 { 244 {
385 290
386 =@List[a,b:out] 291 =@List[a,b:out]
387 { 292 {
388 out <- _=List[a,b] 293 out <- _=List[a,b]
389 } 294 }
295