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

Commit70df7d1

Browse files
authored
Merge pull request#9 from mgorvat/development
Methods for finding lower and ceiling keys in the sorted dictionary.
2 parents6c21025 +147be4c commit70df7d1

File tree

3 files changed

+116
-0
lines changed

3 files changed

+116
-0
lines changed

‎Sources/RedBlackTree.swift‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -348,6 +348,24 @@ public struct RedBlackTree<Key: Comparable, Value>: Probable, Collection, Bidire
348348
returninternalFindNodeForKey(key).value
349349
}
350350

351+
/**
352+
:name: findLowerValue
353+
:description: Finds instance with key that is lower or equal input key
354+
- returns: Value?
355+
*/
356+
publicfunc findLowerValue(for key:Key)->Value?{
357+
returninternalFindLowerForKey(key).value
358+
}
359+
360+
/**
361+
:name: findCeilingValue
362+
:description: Finds instance with key that is larger or equal input key
363+
- returns: Value?
364+
*/
365+
publicfunc findCeilingValue(for key:Key)->Value?{
366+
returninternalFindCeilingForKey(key).value
367+
}
368+
351369
/**
352370
Returns the Key value at a given position.
353371
- Parameter position: An Int.
@@ -395,6 +413,48 @@ public struct RedBlackTree<Key: Comparable, Value>: Probable, Collection, Bidire
395413
}
396414
}
397415

416+
/**
417+
:name: internalFindLowerForKey
418+
:description: Finds a node with a key that is equal or less that given.
419+
- returns: RedBlackNode<Key, Value>
420+
*/
421+
privatefunc internalFindLowerForKey(_ key:Key)->RedBlackNode<Key,Value>{
422+
varz= root
423+
varmax= sentinel
424+
425+
while z!== sentinel{
426+
if key> z.key{
427+
max= z
428+
}
429+
if key== z.key{
430+
return z
431+
}
432+
z= key< z.keyasKey? z.left: z.right
433+
}
434+
return max
435+
}
436+
437+
/**
438+
:name: internalFindCeilingForKey
439+
:description: Finds a node with a key that is equal or larger that given.
440+
- returns: RedBlackNode<Key, Value>
441+
*/
442+
privatefunc internalFindCeilingForKey(_ key:Key)->RedBlackNode<Key,Value>{
443+
varz= root
444+
varmin= sentinel
445+
446+
while z!== sentinel{
447+
if key< z.key{
448+
min= z
449+
}
450+
if key== z.key{
451+
return z
452+
}
453+
z= key< z.keyasKey? z.left: z.right
454+
}
455+
return min
456+
}
457+
398458
/**
399459
:name:indexOf
400460
:description:Returns the Index of a given member, or nil if the member is not present in the set.

‎Sources/SortedDictionary.swift‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -309,6 +309,24 @@ public struct SortedDictionary<Key: Comparable & Hashable, Value>: Probable, Col
309309
return tree.findValue(for: key)
310310
}
311311

312+
/**
313+
Finds the value for a key which is less or equal given.
314+
- Parameter for key: A Key type.
315+
- Returns: An optional Value type.
316+
*/
317+
publicfunc findLowerEntry(for key:Key)->Value?{
318+
return tree.findLowerValue(for: key)
319+
}
320+
321+
/**
322+
Finds the value for a key which is larger or equal given.
323+
- Parameter for key: A Key type.
324+
- Returns: An optional Value type.
325+
*/
326+
publicfunc findCeilingEntry(for key:Key)->Value?{
327+
return tree.findCeilingValue(for: key)
328+
}
329+
312330
/**
313331
Searches for given keys in the SortedDictionary.
314332
- Parameter for keys: A list of Key types.

‎Tests/SortedDictionaryTests.swift‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -121,4 +121,42 @@ class SortedDictionaryTests: XCTestCase {
121121
letvalues=[1,2,3,4]
122122
XCTAssert(values== s.values,"Test failed.")
123123
}
124+
125+
func testLowerEntry(){
126+
lets=SortedDictionary<Int,Int>(elements:(1,1),(2,2),(3,3),(5,5),(8,8),(13,13),(21,21),(34,34))
127+
128+
XCTAssert(s.findLowerEntry(for:-15)==nil,"Test failed.")
129+
XCTAssert(s.findLowerEntry(for:0)==nil,"Test failed.")
130+
XCTAssert(s.findLowerEntry(for:1)==1,"Test failed.")
131+
XCTAssert(s.findLowerEntry(for:2)==2,"Test failed.")
132+
XCTAssert(s.findLowerEntry(for:3)==3,"Test failed.")
133+
XCTAssert(s.findLowerEntry(for:4)==3,"Test failed.")
134+
XCTAssert(s.findLowerEntry(for:5)==5,"Test failed.")
135+
XCTAssert(s.findLowerEntry(for:6)==5,"Test failed.")
136+
XCTAssert(s.findLowerEntry(for:7)==5,"Test failed.")
137+
XCTAssert(s.findLowerEntry(for:8)==8,"Test failed.")
138+
XCTAssert(s.findLowerEntry(for:9)==8,"Test failed.")
139+
XCTAssert(s.findLowerEntry(for:10)==8,"Test failed.")
140+
XCTAssert(s.findLowerEntry(for:40)==34,"Test failed.")
141+
XCTAssert(s.findLowerEntry(for:50)==34,"Test failed.")
142+
}
143+
144+
func testCeilingEntry(){
145+
lets=SortedDictionary<Int,Int>(elements:(1,1),(2,2),(3,3),(5,5),(8,8),(13,13),(21,21),(34,34))
146+
147+
XCTAssert(s.findCeilingEntry(for:-15)==1,"Test failed.")
148+
XCTAssert(s.findCeilingEntry(for:0)==1,"Test failed.")
149+
XCTAssert(s.findCeilingEntry(for:1)==1,"Test failed.")
150+
XCTAssert(s.findCeilingEntry(for:2)==2,"Test failed.")
151+
XCTAssert(s.findCeilingEntry(for:3)==3,"Test failed.")
152+
XCTAssert(s.findCeilingEntry(for:4)==5,"Test failed.")
153+
XCTAssert(s.findCeilingEntry(for:5)==5,"Test failed.")
154+
XCTAssert(s.findCeilingEntry(for:6)==8,"Test failed.")
155+
XCTAssert(s.findCeilingEntry(for:7)==8,"Test failed.")
156+
XCTAssert(s.findCeilingEntry(for:8)==8,"Test failed.")
157+
XCTAssert(s.findCeilingEntry(for:9)==13,"Test failed.")
158+
XCTAssert(s.findCeilingEntry(for:10)==13,"Test failed.")
159+
XCTAssert(s.findCeilingEntry(for:40)==nil,"Test failed.")
160+
XCTAssert(s.findCeilingEntry(for:50)==nil,"Test failed.")
161+
}
124162
}

0 commit comments

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