summary refs log tree commit diff
path: root/src/libcollections/binary_heap.rs
AgeCommit message (Collapse)AuthorLines
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
2015-11-24rustfmt libcollectionsNick Cameron-28/+66
2015-11-20Rename #[deprecated] to #[rustc_deprecated]Vadim Petrochenkov-1/+1
2015-11-18Add missing annotations and some testsVadim Petrochenkov-0/+2
2015-11-13Auto merge of #29811 - bluss:binary-heap-sift-less, r=gankrobors-7/+8
BinaryHeap: Simplify sift down Sift down was doing all too much work: it can stop directly when the current element obeys the heap property in relation to its children. In the old code, sift down didn't compare the element to sift down at all, so it was maximally sifted down and relied on the sift up call to put it in the correct location. This should speed up heapify and .pop(). Also rename Hole::removed() to Hole::element()
2015-11-13BinaryHeap: Simplify sift downUlrik Sverdrup-7/+8
Sift down was doing all too much work: it can stop directly when the current element obeys the heap property in relation to its children. In the old code, sift down didn't compare the element to sift down at all, so it was maximally sifted down and relied on the sift up call to put it in the correct location. This should speed up heapify and .pop(). Also rename Hole::removed() to Hole::element()
2015-11-12libcollections: deny warnings in doctestsKevin Butler-0/+1
2015-10-25std: Stabilize library APIs for 1.5Alex Crichton-30/+31
This commit stabilizes and deprecates library APIs whose FCP has closed in the last cycle, specifically: Stabilized APIs: * `fs::canonicalize` * `Path::{metadata, symlink_metadata, canonicalize, read_link, read_dir, exists, is_file, is_dir}` - all moved to inherent methods from the `PathExt` trait. * `Formatter::fill` * `Formatter::width` * `Formatter::precision` * `Formatter::sign_plus` * `Formatter::sign_minus` * `Formatter::alternate` * `Formatter::sign_aware_zero_pad` * `string::ParseError` * `Utf8Error::valid_up_to` * `Iterator::{cmp, partial_cmp, eq, ne, lt, le, gt, ge}` * `<[T]>::split_{first,last}{,_mut}` * `Condvar::wait_timeout` - note that `wait_timeout_ms` is not yet deprecated but will be once 1.5 is released. * `str::{R,}MatchIndices` * `str::{r,}match_indices` * `char::from_u32_unchecked` * `VecDeque::insert` * `VecDeque::shrink_to_fit` * `VecDeque::as_slices` * `VecDeque::as_mut_slices` * `VecDeque::swap_remove_front` - (renamed from `swap_front_remove`) * `VecDeque::swap_remove_back` - (renamed from `swap_back_remove`) * `Vec::resize` * `str::slice_mut_unchecked` * `FileTypeExt` * `FileTypeExt::{is_block_device, is_char_device, is_fifo, is_socket}` * `BinaryHeap::from` - `from_vec` deprecated in favor of this * `BinaryHeap::into_vec` - plus a `Into` impl * `BinaryHeap::into_sorted_vec` Deprecated APIs * `slice::ref_slice` * `slice::mut_ref_slice` * `iter::{range_inclusive, RangeInclusive}` * `std::dynamic_lib` Closes #27706 Closes #27725 cc #27726 (align not stabilized yet) Closes #27734 Closes #27737 Closes #27742 Closes #27743 Closes #27772 Closes #27774 Closes #27777 Closes #27781 cc #27788 (a few remaining methods though) Closes #27790 Closes #27793 Closes #27796 Closes #27810 cc #28147 (not all parts stabilized)
2015-09-23Override `clone_from` for `{BinaryHeap, String}`Andrew Paseltiner-1/+11
CC #28481
2015-09-02Auto merge of #28156 - nagisa:binaryheap-debug, r=Gankrobors-0/+8
r? @Gankro
2015-09-01Implement Debug for BinaryHeapSimonas Kazlauskas-0/+8
Fixes #28154
2015-09-01Add missing stability markings to BinaryHeap.Eli Friedman-8/+23
2015-08-18Fixed example in documentationjotomicron-1/+1
Added the cost of the edge 3 -> 4 on the example in the module documentation
2015-08-15collections: Add issues for unstable featuresAlex Crichton-2/+3
2015-08-11Register new snapshotsAlex Crichton-3/+0
* Lots of core prelude imports removed * Makefile support for MSVC env vars and Rust crates removed * Makefile support for morestack removed
2015-08-03syntax: Implement #![no_core]Alex Crichton-1/+2
This commit is an implementation of [RFC 1184][rfc] which tweaks the behavior of the `#![no_std]` attribute and adds a new `#![no_core]` attribute. The `#![no_std]` attribute now injects `extern crate core` at the top of the crate as well as the libcore prelude into all modules (in the same manner as the standard library's prelude). The `#![no_core]` attribute disables both std and core injection. [rfc]: https://github.com/rust-lang/rfcs/pull/1184
2015-07-27Show appropriate feature flags in docsSteve Klabnik-8/+16
2015-06-17collections: Split the `collections` featureAlex Crichton-7/+9
This commit also deprecates the `as_string` and `as_slice` free functions in the `string` and `vec` modules.
2015-06-10Removed many pointless calls to *iter() and iter_mut()Joshua Landau-2/+2
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-07-06 20:43:23 +0000