{"action":"created","issue":{"url":"https://api.github.com/repos/rust-lang/rfcs/issues/2184","repository_url":"https://api.github.com/repos/rust-lang/rfcs","labels_url":"https://api.github.com/repos/rust-lang/rfcs/issues/2184/labels{/name}","comments_url":"https://api.github.com/repos/rust-lang/rfcs/issues/2184/comments","events_url":"https://api.github.com/repos/rust-lang/rfcs/issues/2184/events","html_url":"https://github.com/rust-lang/rfcs/issues/2184","id":267156760,"node_id":"MDU6SXNzdWUyNjcxNTY3NjA=","number":2184,"title":"Add `lower_bound`, `upper_bound` and `equal_range` for slices where T: Ord to complement `binary_search`","user":{"login":"alkis","id":265981,"node_id":"MDQ6VXNlcjI2NTk4MQ==","avatar_url":"https://avatars2.githubusercontent.com/u/265981?v=4","gravatar_id":"","url":"https://api.github.com/users/alkis","html_url":"https://github.com/alkis","followers_url":"https://api.github.com/users/alkis/followers","following_url":"https://api.github.com/users/alkis/following{/other_user}","gists_url":"https://api.github.com/users/alkis/gists{/gist_id}","starred_url":"https://api.github.com/users/alkis/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/alkis/subscriptions","organizations_url":"https://api.github.com/users/alkis/orgs","repos_url":"https://api.github.com/users/alkis/repos","events_url":"https://api.github.com/users/alkis/events{/privacy}","received_events_url":"https://api.github.com/users/alkis/received_events","type":"User","site_admin":false},"labels":[{"id":211667901,"node_id":"MDU6TGFiZWwyMTE2Njc5MDE=","url":"https://api.github.com/repos/rust-lang/rfcs/labels/T-libs","name":"T-libs","color":"bfd4f2","default":false}],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":24,"created_at":"2017-10-20T12:16:39Z","updated_at":"2018-07-12T15:17:27Z","closed_at":null,"author_association":"NONE","body":"### Motivation\r\n\r\nFom discussion on https://github.com/rust-lang/rust/pull/45333.\r\n\r\nThere is demand for `lower_bound`, `upper_bound` and `equal_range` especially for sorted sequences of *non-unique* elements. In such sequences the aforementioned operations are more interesting and useful than `binary_search`. The addition of these three ops will complement the support of sorted slices in the standard library.\r\n\r\n### Proposed APIs\r\n\r\n##### `lower_bound`\r\n\r\n```rust\r\n/// Finds the first element in the sorted slice that is _not less_ than `x`.\r\n///\r\n/// Returns the index `a` such that all elements in `self[..a]` are less than `x` and all elements in `self[a..]` are greater or equal to `x`.\r\n///\r\n/// # Examples\r\n/// ```\r\n/// let a = [10, 11, 13, 13, 15];\r\n/// assert_eq!(a.lower_bound(9), 0);\r\n/// assert_eq!(a.lower_bound(10), 0);\r\n/// assert_eq!(a.lower_bound(11), 1);\r\n/// assert_eq!(a.lower_bound(12), 2);\r\n/// assert_eq!(a.lower_bound(13), 2);\r\n/// assert_eq!(a.lower_bound(14), 4);\r\n/// assert_eq!(a.lower_bound(15), 4);\r\n/// assert_eq!(a.lower_bound(16), 5);\r\n/// ```\r\nfn lower_bound(&self, x: &T) -> usize \r\nwhere\r\n    T: Ord;\r\n\r\n/// `lower_bound` with a comparator.\r\nfn lower_bound_by<'a, F>(&'a self, f: F) -> usize\r\nwhere\r\n    F: FnMut(&'a T) -> Ordering;\r\n\r\n/// `lower_bound` with key extraction.\r\nfn lower_bound_by_key<'a, B, F>(&'a self, b: &B, f: F)  -> usize\r\nwhere\r\n    B: Ord,\r\n    F: FnMut(&'a T) -> B\r\n```\r\n\r\n##### `upper_bound`\r\n\r\n```rust\r\n/// Finds the first element in the sorted slice that is _greater_ than `x`.\r\n///\r\n/// Returns the index `a` such that all elements in `self[..a]` are less or equal to `x` and all elements in `self[a..]` are greater than `x`.\r\n///\r\n/// # Examples\r\n/// ```\r\n/// let a = [10, 11, 13, 13, 15];\r\n/// assert_eq!(a.upper_bound(9), 0);\r\n/// assert_eq!(a.upper_bound(10), 1);\r\n/// assert_eq!(a.upper_bound(11), 2);\r\n/// assert_eq!(a.upper_bound(12), 2);\r\n/// assert_eq!(a.upper_bound(13), 4);\r\n/// assert_eq!(a.upper_bound(14), 4);\r\n/// assert_eq!(a.upper_bound(15), 5);\r\n/// assert_eq!(a.upper_bound(16), 5);\r\n/// ```\r\nfn upper_bound(&self, x: &T) -> usize\r\nwhere\r\n    T: Ord;\r\n\r\n/// `upper_bound` with a comparator.\r\nfn upper_bound_by<'a, F>(&'a self, f: F) -> usize\r\nwhere\r\n    F: FnMut(&'a T) -> Ordering;\r\n\r\n/// `upper_bound` with key extraction.\r\nfn upper_bound_by_key<'a, B, F>(&'a self, b: &B, f: F)  -> usize\r\nwhere\r\n    B: Ord,\r\n    F: FnMut(&'a T) -> B\r\n```\r\n\r\n##### `equal_range`\r\n\r\n```rust\r\n/// Finds all elements _equal_ to `x`.\r\n///\r\n/// Returns the `Range` `a..b` such that all elements in `self[..a]` are less than `x`, all elements in `self[a..b]` are equal to `x`, and all elements in `self[b..]` are greater than `x`.\r\n///\r\n/// # Examples\r\n/// ```\r\n/// let a = [10, 11, 13, 13, 15];\r\n///  for i in (9..17) {\r\n///    assert_eq!(a.equal_range(i), (a.lower_bound(i), a.upper_bound(i)));\r\n///  }\r\n/// ```\r\n\r\nfn equal_range(&self, x: &T) -> std::ops::Range<usize> \r\nwhere\r\n    T: Ord;\r\n\r\n/// `equal_range` with a comparator.\r\nfn equal_range_by<'a, F>(&'a self, f: F) -> std::ops::Range<usize> \r\nwhere\r\n    F: FnMut(&'a T) -> Ordering;\r\n\r\n/// `equal_range` with key extraction.\r\nfn equal_range_by_key<'a, B, F>(&'a self, b: &B, f: F)  -> std::ops::Range<usize> \r\nwhere\r\n    B: Ord,\r\n    F: FnMut(&'a T) -> B\r\n```"},"comment":{"url":"https://api.github.com/repos/rust-lang/rfcs/issues/comments/404548629","html_url":"https://github.com/rust-lang/rfcs/issues/2184#issuecomment-404548629","issue_url":"https://api.github.com/repos/rust-lang/rfcs/issues/2184","id":404548629,"node_id":"MDEyOklzc3VlQ29tbWVudDQwNDU0ODYyOQ==","user":{"login":"sicking","id":1831914,"node_id":"MDQ6VXNlcjE4MzE5MTQ=","avatar_url":"https://avatars2.githubusercontent.com/u/1831914?v=4","gravatar_id":"","url":"https://api.github.com/users/sicking","html_url":"https://github.com/sicking","followers_url":"https://api.github.com/users/sicking/followers","following_url":"https://api.github.com/users/sicking/following{/other_user}","gists_url":"https://api.github.com/users/sicking/gists{/gist_id}","starred_url":"https://api.github.com/users/sicking/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sicking/subscriptions","organizations_url":"https://api.github.com/users/sicking/orgs","repos_url":"https://api.github.com/users/sicking/repos","events_url":"https://api.github.com/users/sicking/events{/privacy}","received_events_url":"https://api.github.com/users/sicking/received_events","type":"User","site_admin":false},"created_at":"2018-07-12T15:17:27Z","updated_at":"2018-07-12T15:17:27Z","author_association":"NONE","body":"I was hoping to move forward the discussion so that maybe these functions can be added to the standard library. But happy to do that elsewhere if that's preferred?"}}
{"actor":{"display_login":"sicking"}}