8000 Add binary_search_by and binary_search methods to Deque by PingGuoMiaoMiao · Pull Request #2359 · moonbitlang/core · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

Add binary_search_by and binary_search methods to Deque #2359

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 4 commits into from
Jul 1, 2025
Merged

Add binary_search_by and binary_search methods to Deque #2359

merged 4 commits into from
Jul 1, 2025

Conversation

PingGuoMiaoMiao
Copy link
Contributor

PR Overview

Summary

This PR adds binary_search_by and binary_search methods to the Deque implementation, providing efficient O(log n) searching capability for sorted deques.

Changes

  • Added binary_search_by method that accepts a comparator function
  • Added binary_search convenience method for types implementing Compare
  • Implemented proper ring buffer index handling
  • Added comprehensive unit tests covering:
    • Empty deque cases
    • Single and multiple element deques
    • Wrapped around buffer cases
    • Duplicate elements
    • Custom comparators

@coveralls
Copy link
Collaborator
8000 coveralls commented Jun 26, 2025 •
edited
Loading

Pull Request Test Coverage Report for Build 160

Details

  • 0 of 0 changed or added relevant lines in 0 files are covered.
  • No unchanged relevant lines lost coverage.
  • Overall coverage remained the same at 89.386%
Totals Coverage Status
Change from base Build 154: 0.0%
Covered Lines: 3453
Relevant Lines: 3863
💛 - Coveralls

@FlyCloudC
Copy link
Contributor

Missing tests for handling wrapped around cases. For example

///|
test "binary_search when wrapped around" {
  let dq = @deque.of([5, 7, 9])
  dq..push_front(3)..push_front(1)

  let found_first = dq.binary_search(1)
  inspect(found_first, content="Ok(0)")

  let found_middle = dq.binary_search(5)
  inspect(found_middle, content="Ok(2)")

  let found_last = dq.binary_search(9)
  inspect(found_last, content="Ok(4)")
}

peter-jerry-ye
peter-jerry-ye reviewed Jun 27, 2025
View reviewed changes
@FlyCloudC
Copy link
Contributor
FlyCloudC commented Jun 27, 2025 •
edited
Loading

If you don't plan to specifically optimize for the wrap-around case and just use i % self.buf.length(), you can refer to the logic in ​​array.mbt​​ here:

core/builtin/array.mbt

Lines 992 to 1013 in fbb9e83

pub fn[T : Compare] Array::binary_search(
self : Array[T],
value : T
) -> Result[Int, Int] {
let len = self.length()
for i = 0, j = len; i < j; {
let h = i + (j - i) / 2
// Note even if self[h] == value, we still continue the search
// because we want to find the leftmost match
if self.unsafe_get(h) < value {
continue h + 1, j
} else {
continue i, h
}
} else {
if i < len && self.unsafe_get(i) == value {
Ok(i)
} else {
Err(i)
}
}
}

< 10000 input type="hidden" name="_method" value="put" autocomplete="off" />

@peter-jerry-ye-code-review peter-jerry-ye code review
Copy link
Potential unsafe memory access in binary_search methods

Category
Correctness
Code Snippet
Lines 1375, 1378, 1416, 1447: self.buf[physical_index]
Recommendation
Add bounds checking or use safe accessor methods like get() that return Option types, or verify that the deque implementation guarantees initialized slots up to len
Reasoning
The code directly accesses buffer elements without checking if they are initialized. While the comment says 'Safe access to elements (assuming initialized)', this assumption should be verified or made explicit through safer access patterns.

Code duplication between binary_search_by and binary_search methods

Category
Maintainability
Code Snippet
Lines 1363-1390 and 1434-1461 contain nearly identical binary search logic
Recommendation
Refactor binary_search to call binary_search_by with a comparison function: self.binary_search_by(fn(x) { x.compare(value) })
Reasoning
The two methods implement the same algorithm with only the comparison logic differing. This duplication increases maintenance burden and risk of bugs when one method is updated but not the other.

Redundant test cases with identical functionality

Category
Maintainability
Code Snippet
Lines 1065-1147 and 1199-1279 contain duplicate test scenarios
Recommendation
Remove the duplicate test functions deque_binary_search_empty, deque_binary_search_single_element, deque_binary_search_multiple_elements, and deque_binary_search_duplicates as they test identical scenarios to the earlier tests
Reasoning
Having duplicate tests increases maintenance overhead without adding value. The earlier test functions already provide comprehensive coverage for the same scenarios.

peter-jerry-ye
peter-jerry-ye reviewed Jun 30, 2025
View reviewed changes
@PingGuoMiaoMiao
modified: deque/deque.mbt
ec40504 
	modified:   deque/deque.mbti
	modified:   deque/deque_test.mbt
@peter-jerry-ye
Copy link
Collaborator

Thanks.

@peter-jerry-ye peter-jerry-ye merged commit 2fc0766 into moonbitlang:main Jul 1, 2025
10 checks passed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@peter-jerry-ye peter-jerry-ye Awaiting requested review from peter-jerry-ye

Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
4 participants
@PingGuoMiaoMiao @coveralls @FlyCloudC @peter-jerry-ye
0