about summary refs log tree commit diff
path: root/src/libcollections/binary_heap.rs
AgeCommit message (Collapse)AuthorLines
2017-06-13Merge crate `collections` into `alloc`Murarth-1236/+0
2017-05-27Rollup merge of #42260 - stjepang:document-cmp-traits-agreement, r=alexcrichtonMark Simulacrum-1/+4
Docs: impls of PartialEq/PartialOrd/Ord must agree Fixes #41270. This PR brings two improvements to the docs: 1. Docs for `PartialEq`, `PartialOrd`, and `Ord` clarify that their implementations must agree. 2. Fixes a subtle bug in the Dijkstra example for `BinaryHeap`, where the impls are inconsistent. Thanks @Rufflewind for spotting the bug! r? @alexcrichton cc @frankmcsherry
2017-05-27Docs: impls of PartialEq/PartialOrd/Ord must agreeStjepan Glavina-1/+4
2017-05-20Stabilize library features for 1.18.0Steven Fackler-1/+1
Closes #38863 Closes #38980 Closes #38903 Closes #36648
2017-04-23Auto merge of #41437 - cuviper:remove-unstable-deprecated, r=alexcrichtonbors-76/+0
Remove items that are unstable and deprecated This removes unstable items that have been deprecated for more than one cycle. - Since 1.16.0, `#![feature(enumset)]` - All of `mod collections::enum_set` - Since 1.15.0, `#![feature(borrow_state)]` - `cell::BorrowState` - `RefCell::borrow_state()` - Since 1.15.0, `#![feature(is_unique)]` - `Rc::is_unique()` (made private like `Arc::is_unique()`) - Since 1.15.0, `#![feature(rc_would_unwrap)]` - `Rc::would_wrap()` - Since 1.13.0, `#![feature(binary_heap_extras)]` - `BinaryHeap::push_pop()` - `BinaryHeap::replace()` - Since 1.12.0, `#![feature(as_unsafe_cell)]` - `Cell::as_unsafe_cell()` - `RefCell::as_unsafe_cell()` - Since 1.12.0, `#![feature(map_entry_recover_keys)]` - `btree_map::OccupiedEntry::remove_pair()` - `hash_map::OccupiedEntry::remove_pair()` - Since 1.11.0, `#![feature(float_extras)]` - `Float::nan()` - `Float::infinity()` - `Float::neg_infinity()` - `Float::neg_zero()` - `Float::zero()` - `Float::one()` - `Float::integer_decode()` - `f32::integer_decode()` - `f32::ldexp()` - `f32::frexp()` - `f32::next_after()` - `f64::integer_decode()` - `f64::ldexp()` - `f64::frexp()` - `f64::next_after()` - Since 1.11.0, `#![feature(zero_one)]` - `num::Zero` - `num::One`
2017-04-22Fix invalid linkageGuillaume Gomez-1/+1
2017-04-20Remove BinaryHeap::{push_pop,replace}Josh Stone-76/+0
[unstable, deprecated since 1.13.0]
2017-04-14std::collections docs: Address issues that came up in PR #41286lukaramu-1/+1
* Bound: * Added another example using RangeArgument to illustrate how Bound maps to range endpoints. * Added a note to the existing example that says that it's better to use range syntax in most cases * Added missing /// line * binary_heap::PeakMut: s/Object representing/Structure wrapping * added collections/hash_set/struct.HashSet.html to linkchecker whitelist
2017-04-13Various fixes throughout std::collections' docslukaramu-2/+5
* Added links where possible (limited because of facading) * Changed references to methods from `foo()` to `foo` in module docs * Changed references to methods from `HashMap::foo` to just `foo` in top-level docs for `HashMap` and the `default` doc for `DefaultHasher` * Various small other fixes
2017-04-13Update std::collections' docs to use iterator (etc.) boilerplatelukaramu-5/+27
This greatly improves consistency.
2017-03-22Various fixes to wording consistency in the docsStjepan Glavina-2/+2
2017-03-13Remove function invokation parens from documentation links.Corey Farwell-2/+2
This was never established as a convention we should follow in the 'More API Documentation Conventions' RFC: https://github.com/rust-lang/rfcs/blob/master/text/1574-more-api-documentation-conventions.md
2017-02-07Auto merge of #39002 - GuillaumeGomez:debug_libcollections, r=aturonbors-0/+39
Add Debug implementations for libcollection structs Part of #31869.
2017-02-05Replace PlaceBack Debug implementation with deriveGuillaume Gomez-16/+10
2017-01-29Fix a few impl stability attributesOliver Middleton-2/+2
The versions show up in rustdoc.
2017-01-20Add debug implementation for BinaryHeapPlaceGuillaume Gomez-0/+9
2017-01-20Remove Debug implementations specializationGuillaume Gomez-30/+6
2017-01-20Add Debug implementations for libcollection structsGuillaume Gomez-0/+60
2017-01-17Fix BinaryHeap place by only constructing vec::PlaceBack onceMartin Hafskjold Thoresen-45/+24
2017-01-14Add initial impl of placement-in for `BinaryHeap`Martin Hafskjold Thoresen-1/+76
2017-01-05Add a tracking issueSteven Fackler-1/+1
2017-01-01Add PeekMut::popSteven Fackler-4/+19
A fairly common workflow is to put a bunch of stuff into a binary heap and then mutate the top value until its empty. This both makes that a bit more convenient (no need to save a boolean off and pop after to avoid borrowck issues), and a bit more efficient since you only shift once.
2016-12-20run rustfmt on libcollections folderSrinivas Reddy Thatiparthy-5/+5
2016-12-04binary_heap: Forward ExactSizeIterator::is_emptyUlrik Sverdrup-3/+15
2016-10-04Rollup merge of #36902 - ollie27:stab_impls, r=alexcrichtonManish Goregaokar-3/+3
std: Correct stability attributes for some implementations These are displayed by rustdoc so should be correct.
2016-10-03std: Stabilize and deprecate APIs for 1.13Alex Crichton-0/+4
This commit is intended to be backported to the 1.13 branch, and works with the following APIs: Stabilized * `i32::checked_abs` * `i32::wrapping_abs` * `i32::overflowing_abs` * `RefCell::try_borrow` * `RefCell::try_borrow_mut` * `DefaultHasher` * `DefaultHasher::new` * `DefaultHasher::default` Deprecated * `BinaryHeap::push_pop` * `BinaryHeap::replace` * `SipHash13` * `SipHash24` * `SipHasher` - use `DefaultHasher` instead in the `std::collections::hash_map` module Closes #28147 Closes #34767 Closes #35057 Closes #35070
2016-10-01std: Correct stability attributes for some implementationsOliver Middleton-3/+3
These are displayed by rustdoc so should be correct.
2016-09-11Documentation of what does for each typeathulappadan-0/+1
2016-08-29Remove BinaryHeap bounds checkingarthurprs-20/+23
2016-08-24Remove needless imports in `libcollections`.Jeffrey Seyfried-1/+1
2016-08-23Auto merge of #35656 - Stebalien:fused, r=alexcrichtonbors-1/+10
Implement 1581 (FusedIterator) * [ ] Implement on patterns. See https://github.com/rust-lang/rust/issues/27721#issuecomment-239638642. * [ ] Handle OS Iterators. A bunch of iterators (`Args`, `Env`, etc.) in libstd wrap platform specific iterators. The current ones all appear to be well-behaved but can we assume that future ones will be? * [ ] Does someone want to audit this? On first glance, all of the iterators on which I implemented `FusedIterator` appear to be well-behaved but there are a *lot* of them so a second pair of eyes would be nice. * I haven't touched rustc internal iterators (or the internal rand) because rustc doesn't actually call `fuse()`. * `FusedIterator` can't be implemented on `std::io::{Bytes, Chars}`. Closes: #35602 (Tracking Issue) Implements: rust-lang/rfcs#1581
2016-08-19std: Stabilize APIs for the 1.12 releaseAlex Crichton-6/+5
Stabilized * `Cell::as_ptr` * `RefCell::as_ptr` * `IpAddr::is_{unspecified,loopback,multicast}` * `Ipv6Addr::octets` * `LinkedList::contains` * `VecDeque::contains` * `ExitStatusExt::from_raw` - both on Unix and Windows * `Receiver::recv_timeout` * `RecvTimeoutError` * `BinaryHeap::peek_mut` * `PeekMut` * `iter::Product` * `iter::Sum` * `OccupiedEntry::remove_entry` * `VacantEntry::into_key` Deprecated * `Cell::as_unsafe_cell` * `RefCell::as_unsafe_cell` * `OccupiedEntry::remove_pair` Closes #27708 cc #27709 Closes #32313 Closes #32630 Closes #32713 Closes #34029 Closes #34392 Closes #34285 Closes #34529
2016-08-18Add a FusedIterator trait.Steven Allen-1/+10
This trait can be used to avoid the overhead of a fuse wrapper when an iterator is already well-behaved. Conforming to: RFC 1581 Closes: #35602
2016-07-03std: Stabilize APIs for the 1.11.0 releaseAlex Crichton-5/+1
Although the set of APIs being stabilized this release is relatively small, the trains keep going! Listed below are the APIs in the standard library which have either transitioned from unstable to stable or those from unstable to deprecated. Stable * `BTreeMap::{append, split_off}` * `BTreeSet::{append, split_off}` * `Cell::get_mut` * `RefCell::get_mut` * `BinaryHeap::append` * `{f32, f64}::{to_degrees, to_radians}` - libcore stabilizations mirroring past libstd stabilizations * `Iterator::sum` * `Iterator::product` Deprecated * `{f32, f64}::next_after` * `{f32, f64}::integer_decode` * `{f32, f64}::ldexp` * `{f32, f64}::frexp` * `num::One` * `num::Zero` Added APIs (all unstable) * `iter::Sum` * `iter::Product` * `iter::Step` - a few methods were added to accomodate deprecation of One/Zero Removed APIs * `From<Range<T>> for RangeInclusive<T>` - everything about `RangeInclusive` is unstable Closes #27739 Closes #27752 Closes #32526 Closes #33444 Closes #34152 cc #34529 (new tracking issue)
2016-06-21implemented peek_mut and unit testsNathan Moos-0/+68
2016-04-17Implement `Clone` for `binary_heap::IntoIter`Andrew Paseltiner-0/+1
2016-04-16collections: add append and extend specialization for binary heapAndrey Tonkih-5/+88
2016-03-30Rollup merge of #32607 - tshepang:we-gots-intoiterator, r=apasel422Steve Klabnik-1/+1
doc: no need for an explicit iter()
2016-03-30Rollup merge of #32603 - tshepang:capitalise, r=blussSteve Klabnik-1/+1
doc: first letter should be upper case
2016-03-30doc: no need for an explicit iter()Tshepang Lekhonkhobe-1/+1
2016-03-29doc: first letter should be upper caseTshepang Lekhonkhobe-1/+1
2016-03-28style: Use `iter` for IntoIterator parameter namesKamal Marhubi-4/+4
This commit standardizes the codebase on `iter` for parameters with IntoIterator bounds. Previously about 40% of IntoIterator parameters were named `iterable`, with most of the rest being named `iter`. There was a single place where it was named `iterator`.
2016-03-10Remove unnecessary mut in docs causing test failures.Nathan Kleyn-1/+1
2016-03-09Address review comments to add "basic usage" sections to docs.Nathan Kleyn-0/+38
2016-03-08Add missing documentation examples for BinaryHeap.Nathan Kleyn-0/+106
As part of the ongoing effort to document all methods with examples, this commit adds the missing examples for the `BinaryHeap` collection type. This is part of issue #29348.
2015-12-23BinaryHeap: Use full sift down in .pop()Ulrik Sverdrup-1/+26
.sift_down can either choose to compare the element on the way down (and place it during descent), or to sift down an element fully, then sift back up to place it. A previous PR changed .sift_down() to the former behavior, which is much faster for relatively small heaps and for elements that are cheap to compare. A benchmarking run suggested that BinaryHeap::pop() suffers improportionally from this, and that it should use the second strategy instead. It's logical since .pop() brings last element from the heapified vector into index 0, it's very likely that this element will end up at the bottom again.
2015-12-13Make BinaryHeap Dijkstra example return Optionjethrogb-8/+8
2015-12-10std: Remove deprecated functionality from 1.5Alex Crichton-20/+0
This is a standard "clean out libstd" commit which removes all 1.5-and-before deprecated functionality as it's now all been deprecated for at least one entire cycle.
2015-12-05std: Stabilize APIs for the 1.6 releaseAlex Crichton-5/+2
This commit is the standard API stabilization commit for the 1.6 release cycle. The list of issues and APIs below have all been through their cycle-long FCP and the libs team decisions are listed below Stabilized APIs * `Read::read_exact` * `ErrorKind::UnexpectedEof` (renamed from `UnexpectedEOF`) * libcore -- this was a bit of a nuanced stabilization, the crate itself is now marked as `#[stable]` and the methods appearing via traits for primitives like `char` and `str` are now also marked as stable. Note that the extension traits themeselves are marked as unstable as they're imported via the prelude. The `try!` macro was also moved from the standard library into libcore to have the same interface. Otherwise the functions all have copied stability from the standard library now. * The `#![no_std]` attribute * `fs::DirBuilder` * `fs::DirBuilder::new` * `fs::DirBuilder::recursive` * `fs::DirBuilder::create` * `os::unix::fs::DirBuilderExt` * `os::unix::fs::DirBuilderExt::mode` * `vec::Drain` * `vec::Vec::drain` * `string::Drain` * `string::String::drain` * `vec_deque::Drain` * `vec_deque::VecDeque::drain` * `collections::hash_map::Drain` * `collections::hash_map::HashMap::drain` * `collections::hash_set::Drain` * `collections::hash_set::HashSet::drain` * `collections::binary_heap::Drain` * `collections::binary_heap::BinaryHeap::drain` * `Vec::extend_from_slice` (renamed from `push_all`) * `Mutex::get_mut` * `Mutex::into_inner` * `RwLock::get_mut` * `RwLock::into_inner` * `Iterator::min_by_key` (renamed from `min_by`) * `Iterator::max_by_key` (renamed from `max_by`) Deprecated APIs * `ErrorKind::UnexpectedEOF` (renamed to `UnexpectedEof`) * `OsString::from_bytes` * `OsStr::to_cstring` * `OsStr::to_bytes` * `fs::walk_dir` and `fs::WalkDir` * `path::Components::peek` * `slice::bytes::MutableByteVector` * `slice::bytes::copy_memory` * `Vec::push_all` (renamed to `extend_from_slice`) * `Duration::span` * `IpAddr` * `SocketAddr::ip` * `Read::tee` * `io::Tee` * `Write::broadcast` * `io::Broadcast` * `Iterator::min_by` (renamed to `min_by_key`) * `Iterator::max_by` (renamed to `max_by_key`) * `net::lookup_addr` New APIs (still unstable) * `<[T]>::sort_by_key` (added to mirror `min_by_key`) Closes #27585 Closes #27704 Closes #27707 Closes #27710 Closes #27711 Closes #27727 Closes #27740 Closes #27744 Closes #27799 Closes #27801 cc #27801 (doesn't close as `Chars` is still unstable) Closes #28968
2015-11-25Auto merge of #30017 - nrc:fmt, r=brsonbors-28/+66
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-05-22 14:52:13 +0000