Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitc574e8f

Browse files
dsymeKevinRansom
authored andcommitted
[RFC FS-1050] TryGetValue on map (dotnet#4827)
* TryGetValue on map* TryGetValue on map* fix baselines* Build find/tryFind on trGetValue
1 parentbbe06d5 commitc574e8f

File tree

5 files changed

+59
-38
lines changed

5 files changed

+59
-38
lines changed

‎src/fsharp/FSharp.Core/map.fs‎

Lines changed: 43 additions & 38 deletions
Original file line numberDiff line numberDiff line change
@@ -64,17 +64,18 @@ namespace Microsoft.FSharp.Collections
6464

6565
letempty= MapEmpty
6666

67-
letheight=function
67+
letheight(m:MapTree<'Key,'Value>)=
68+
match mwith
6869
| MapEmpty->0
6970
| MapOne_->1
7071
| MapNode(_,_,_,_,h)-> h
7172

72-
letisEmptym=
73+
letisEmpty(m:MapTree<'Key,'Value>)=
7374
match mwith
7475
| MapEmpty->true
7576
|_->false
7677

77-
letmk l k v r=
78+
letmk l k v r:MapTree<'Key,'Value>=
7879
match l,rwith
7980
| MapEmpty,MapEmpty-> MapOne(k,v)
8081
|_->
@@ -83,7 +84,7 @@ namespace Microsoft.FSharp.Collections
8384
letm=if hl< hrthen hrelse hl
8485
MapNode(k,v,l,r,m+1)
8586

86-
letrebalance t1k v t2=
87+
letrebalance t1(k:'Key)(v:'Value)t2=
8788
lett1h= height t1
8889
lett2h= height t2
8990
if t2h> t1h+2then(* right is heavier than left*)
@@ -114,7 +115,7 @@ namespace Microsoft.FSharp.Collections
114115
|_-> failwith"rebalance"
115116
else mk t1 k v t2
116117

117-
let recadd(comparer:IComparer<'Value>)kv m=
118+
let recadd(comparer:IComparer<'Key>)k(v:'Value)(m:MapTree<'Key,'Value>)=
118119
match mwith
119120
| MapEmpty-> MapOne(k,v)
120121
| MapOne(k2,_)->
@@ -128,36 +129,37 @@ namespace Microsoft.FSharp.Collections
128129
elif c=0then MapNode(k,v,l,r,h)
129130
else rebalance l k2 v2(add comparer k v r)
130131

131-
let recfind(comparer:IComparer<'Value>)km=
132+
let rectryGetValue(comparer:IComparer<'Key>)k(v:byref<'Value>)(m:MapTree<'Key,'Value>)=
132133
match mwith
133-
| MapEmpty->raise(KeyNotFoundException())
134+
| MapEmpty->false
134135
| MapOne(k2,v2)->
135136
letc= comparer.Compare(k,k2)
136-
if c=0thenv2
137-
elseraise(KeyNotFoundException())
137+
if c=0thenv<- v2;true
138+
elsefalse
138139
| MapNode(k2,v2,l,r,_)->
139140
letc= comparer.Compare(k,k2)
140-
if c<0then find comparer k l
141-
elif c=0then v2
142-
else find comparer k r
141+
if c<0then tryGetValue comparer k&v l
142+
elif c=0then v<- v2;true
143+
else tryGetValue comparer k&v r
144+
145+
letfind(comparer:IComparer<'Key>)k(m:MapTree<'Key,'Value>)=
146+
let mutablev= Unchecked.defaultof<'Value>
147+
if tryGetValue comparer k&v mthen
148+
v
149+
else
150+
raise(KeyNotFoundException())
143151

144-
let rectryFind(comparer:IComparer<'Value>)k m=
145-
match mwith
146-
| MapEmpty-> None
147-
| MapOne(k2,v2)->
148-
letc= comparer.Compare(k,k2)
149-
if c=0then Some v2
150-
else None
151-
| MapNode(k2,v2,l,r,_)->
152-
letc= comparer.Compare(k,k2)
153-
if c<0then tryFind comparer k l
154-
elif c=0then Some v2
155-
else tryFind comparer k r
152+
lettryFind(comparer:IComparer<'Key>)k(m:MapTree<'Key,'Value>)=
153+
let mutablev= Unchecked.defaultof<'Value>
154+
if tryGetValue comparer k&v mthen
155+
Some v
156+
else
157+
None
156158

157-
letpartition1(comparer:IComparer<'Value>)(f:OptimizedClosures.FSharpFunc<_,_,_>)k v(acc1,acc2)=
159+
letpartition1(comparer:IComparer<'Key>)(f:OptimizedClosures.FSharpFunc<_,_,_>)k v(acc1,acc2)=
158160
if f.Invoke(k, v)then(add comparer k v acc1,acc2)else(acc1,add comparer k v acc2)
159161

160-
let recpartitionAux(comparer:IComparer<'Value>)(f:OptimizedClosures.FSharpFunc<_,_,_>)s acc=
162+
let recpartitionAux(comparer:IComparer<'Key>)(f:OptimizedClosures.FSharpFunc<_,_,_>)s acc=
161163
match swith
162164
| MapEmpty-> acc
163165
| MapOne(k,v)-> partition1 comparer f k v acc
@@ -166,11 +168,11 @@ namespace Microsoft.FSharp.Collections
166168
letacc= partition1 comparer f k v acc
167169
partitionAux comparer f l acc
168170

169-
letpartition(comparer:IComparer<'Value>)f s= partitionAux comparer(OptimizedClosures.FSharpFunc<_,_,_>.Adapt(f)) s(empty,empty)
171+
letpartition(comparer:IComparer<'Key>)f s= partitionAux comparer(OptimizedClosures.FSharpFunc<_,_,_>.Adapt(f)) s(empty,empty)
170172

171-
letfilter1(comparer:IComparer<'Value>)(f:OptimizedClosures.FSharpFunc<_,_,_>)k v acc=if f.Invoke(k, v)then add comparer k v accelse acc
173+
letfilter1(comparer:IComparer<'Key>)(f:OptimizedClosures.FSharpFunc<_,_,_>)k v acc=if f.Invoke(k, v)then add comparer k v accelse acc
172174

173-
let recfilterAux(comparer:IComparer<'Value>)(f:OptimizedClosures.FSharpFunc<_,_,_>)s acc=
175+
let recfilterAux(comparer:IComparer<'Key>)(f:OptimizedClosures.FSharpFunc<_,_,_>)s acc=
174176
match swith
175177
| MapEmpty-> acc
176178
| MapOne(k,v)-> filter1 comparer f k v acc
@@ -179,9 +181,9 @@ namespace Microsoft.FSharp.Collections
179181
letacc= filter1 comparer f k v acc
180182
filterAux comparer f r acc
181183

182-
letfilter(comparer:IComparer<'Value>)f s= filterAux comparer(OptimizedClosures.FSharpFunc<_,_,_>.Adapt(f)) s empty
184+
letfilter(comparer:IComparer<'Key>)f s= filterAux comparer(OptimizedClosures.FSharpFunc<_,_,_>.Adapt(f)) s empty
183185

184-
let recspliceOutSuccessorm=
186+
let recspliceOutSuccessor(m:MapTree<'Key,'Value>)=
185187
match mwith
186188
| MapEmpty-> failwith"internal error: Map.spliceOutSuccessor"
187189
| MapOne(k2,v2)-> k2,v2,MapEmpty
@@ -190,7 +192,7 @@ namespace Microsoft.FSharp.Collections
190192
| MapEmpty-> k2,v2,r
191193
|_->letk3,v3,l'= spliceOutSuccessor lin k3,v3,mk l' k2 v2 r
192194

193-
let recremove(comparer:IComparer<'Value>)km=
195+
let recremove(comparer:IComparer<'Key>)k(m:MapTree<'Key,'Value>)=
194196
match mwith
195197
| MapEmpty-> empty
196198
| MapOne(k2,_)->
@@ -208,7 +210,7 @@ namespace Microsoft.FSharp.Collections
208210
mk l sk sv r'
209211
else rebalance l k2 v2(remove comparer k r)
210212

211-
let recmem(comparer:IComparer<'Value>)km=
213+
let recmem(comparer:IComparer<'Key>)k(m:MapTree<'Key,'Value>)=
212214
match mwith
213215
| MapEmpty->false
214216
| MapOne(k2,_)->(comparer.Compare(k,k2)=0)
@@ -217,7 +219,7 @@ namespace Microsoft.FSharp.Collections
217219
if c<0then mem comparer k l
218220
else(c=0|| mem comparer k r)
219221

220-
let reciterOpt(f:OptimizedClosures.FSharpFunc<_,_,_>)m=
222+
let reciterOpt(f:OptimizedClosures.FSharpFunc<_,_,_>)(m:MapTree<'Key,'Value>)=
221223
match mwith
222224
| MapEmpty->()
223225
| MapOne(k2,v2)-> f.Invoke(k2, v2)
@@ -300,7 +302,7 @@ namespace Microsoft.FSharp.Collections
300302

301303
letfold f x m= foldOpt(OptimizedClosures.FSharpFunc<_,_,_,_>.Adapt(f)) x m
302304

303-
letfoldSectionOpt(comparer:IComparer<'Value>)lo hi(f:OptimizedClosures.FSharpFunc<_,_,_,_>)m x=
305+
letfoldSectionOpt(comparer:IComparer<'Key>)lo hi(f:OptimizedClosures.FSharpFunc<_,_,_,_>)m x=
304306
let recfoldFromTo(f:OptimizedClosures.FSharpFunc<_,_,_,_>)m x=
305307
match mwith
306308
| MapEmpty-> x
@@ -319,7 +321,7 @@ namespace Microsoft.FSharp.Collections
319321

320322
if comparer.Compare(lo,hi)=1then xelse foldFromTo f m x
321323

322-
letfoldSection(comparer:IComparer<'Value>)lo hi f m x=
324+
letfoldSection(comparer:IComparer<'Key>)lo hi f m x=
323325
foldSectionOpt comparer lo hi(OptimizedClosures.FSharpFunc<_,_,_,_>.Adapt(f)) m x
324326

325327
lettoList m=
@@ -531,6 +533,9 @@ namespace Microsoft.FSharp.Collections
531533
memberm.Remove(key):Map<'Key,'Value>=
532534
new Map<'Key,'Value>(comparer,MapTree.remove comparer key tree)
533535

536+
memberm.TryGetValue(key,[<System.Runtime.InteropServices.Out>]value:byref<'Value>)=
537+
MapTree.tryGetValue comparer key&value tree
538+
534539
memberm.TryFind(key)=
535540
#if TRACE_SETS_AND_MAPS
536541
MapTree.report()
@@ -588,7 +593,7 @@ namespace Microsoft.FSharp.Collections
588593

589594
members.Add(k,v)= ignore(k,v); raise(NotSupportedException(SR.GetString(SR.mapCannotBeMutated)))
590595
members.ContainsKey(k)= s.ContainsKey(k)
591-
members.TryGetValue(k,r)=if s.ContainsKey(k)then(r<- s.[k];true)elsefalse
596+
members.TryGetValue(k,r)=s.TryGetValue(k,&r)
592597
members.Remove(k:'Key)= ignore(k);(raise(NotSupportedException(SR.GetString(SR.mapCannotBeMutated))): bool)
593598

594599
interface ICollection<KeyValuePair<'Key, 'Value>>with
@@ -618,7 +623,7 @@ namespace Microsoft.FSharp.Collections
618623
interface IReadOnlyDictionary<'Key, 'Value>with
619624
members.Itemwith get(key)= s.[key]
620625
members.Keys=seq{for kvpin s-> kvp.Key}
621-
members.TryGetValue(key,value)=if s.ContainsKey(key)then(value<- s.[key];true)elsefalse
626+
members.TryGetValue(key,value:byref<'Value>)=s.TryGetValue(key,&value)
622627
members.Values=seq{for kvpin s-> kvp.Value}
623628
members.ContainsKey key= s.ContainsKey key
624629

‎src/fsharp/FSharp.Core/map.fsi‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -56,6 +56,13 @@ namespace Microsoft.FSharp.Collections
5656
/// <returns>The mapped value, or None if the key is not in the map.</returns>
5757
memberTryFind:key:'Key->'Value option
5858

59+
/// <summary>Lookup an element in the map, assigning to <c>value</c> if the element is in the domain
60+
/// of the map and returning <c>false</c> if not.</summary>
61+
/// <param name="key">The input key.</param>
62+
/// <param name="value">A reference to the output value.</param>
63+
/// <returns><c>true</c> if the value is present, <c>false</c> if not.</returns>
64+
memberTryGetValue:key:'Key*[<System.Runtime.InteropServices.Out>] value:byref<'Value>-> bool
65+
5966
interface IDictionary<'Key, 'Value>
6067
interface ICollection<KeyValuePair<'Key, 'Value>>
6168
interface IEnumerable<KeyValuePair<'Key, 'Value>>

‎tests/FSharp.Core.UnitTests/SurfaceArea.coreclr.fs‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -258,6 +258,7 @@ Microsoft.FSharp.Collections.FSharpMap`2[TKey,TValue]: Int32 get_Count()
258258
Microsoft.FSharp.Collections.FSharpMap`2[TKey,TValue]: Microsoft.FSharp.Collections.FSharpMap`2[TKey,TValue] Add(TKey, TValue)
259259
Microsoft.FSharp.Collections.FSharpMap`2[TKey,TValue]: Microsoft.FSharp.Collections.FSharpMap`2[TKey,TValue] Remove(TKey)
260260
Microsoft.FSharp.Collections.FSharpMap`2[TKey,TValue]: Microsoft.FSharp.Core.FSharpOption`1[TValue] TryFind(TKey)
261+
Microsoft.FSharp.Collections.FSharpMap`2[TKey,TValue]: Boolean TryGetValue(TKey, TValue ByRef)
261262
Microsoft.FSharp.Collections.FSharpMap`2[TKey,TValue]: System.String ToString()
262263
Microsoft.FSharp.Collections.FSharpMap`2[TKey,TValue]: System.Type GetType()
263264
Microsoft.FSharp.Collections.FSharpMap`2[TKey,TValue]: TValue Item [TKey]

‎tests/FSharp.Core.UnitTests/SurfaceArea.net40.fs‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -245,6 +245,7 @@ Microsoft.FSharp.Collections.FSharpMap`2[TKey,TValue]: Int32 get_Count()
245245
Microsoft.FSharp.Collections.FSharpMap`2[TKey,TValue]: Microsoft.FSharp.Collections.FSharpMap`2[TKey,TValue] Add(TKey, TValue)
246246
Microsoft.FSharp.Collections.FSharpMap`2[TKey,TValue]: Microsoft.FSharp.Collections.FSharpMap`2[TKey,TValue] Remove(TKey)
247247
Microsoft.FSharp.Collections.FSharpMap`2[TKey,TValue]: Microsoft.FSharp.Core.FSharpOption`1[TValue] TryFind(TKey)
248+
Microsoft.FSharp.Collections.FSharpMap`2[TKey,TValue]: Boolean TryGetValue(TKey, TValue ByRef)
248249
Microsoft.FSharp.Collections.FSharpMap`2[TKey,TValue]: System.String ToString()
249250
Microsoft.FSharp.Collections.FSharpMap`2[TKey,TValue]: System.Type GetType()
250251
Microsoft.FSharp.Collections.FSharpMap`2[TKey,TValue]: TValue Item [TKey]

‎tests/fsharp/core/map/test.fsx‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -24,9 +24,16 @@ let test_eq_range n m x =
2424
done;
2525
for i= nto mdo
2626
test"ew9wef"(Map.tryFind i x= Some(i*100));
27+
test"ew9wef"(x.TryGetValue(i)=(true,(i*100)));
28+
let mutableres=0
29+
test"ew9wef"(x.TryGetValue(i,&res)=true);
30+
test"ew9wef"(res=(i*100));
2731
done;
2832
for i= m+1to m+100do
2933
test"ew9wef"(Map.tryFind i x= None);
34+
test"ew9wef"(x.TryGetValue(i)=(false,0));
35+
let mutableres=0
36+
test"ew9wef"(x.TryGetValue(i,&res)=false);
3037
done;
3138
for i= m+1to m+5do
3239
test"ew9cwef"((try Some(Map.find i x)with:? System.Collections.Generic.KeyNotFoundException-> None)= None);

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp