1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
/*
 *  Copyright 2017 Gianmarco Garrisi and contributors
 *
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Lesser General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version, or (at your option) under the terms
 *  of the Mozilla Public License version 2.0.
 *
 *  ----
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 *  ----
 *
 *  This Source Code Form is subject to the terms of the Mozilla Public License,
 *  v. 2.0. If a copy of the MPL was not distributed with this file, You can
 *  obtain one at http://mozilla.org/MPL/2.0/.
 *
 */

//! This crate provides 2 main data structures:
//!  *  a [priority queue](PriorityQueue)
//!  *  a [double priority queue](DoublePriorityQueue).
//!
//! Both data structures are backed by an hashmap, allowing
//! to change the priority of an element with some efficient methods in
//! **O(log(N))** time (worst case).
//!
//! The elements (called `Item`s, of type `I`) must implement
//! [`Hash`](https://doc.rust-lang.org/std/hash/trait.Hash.html)
//! and [`Eq`](https://doc.rust-lang.org/std/cmp/trait.Eq.html) traits.
//!
//! This can frequently be achieved by using `#[derive(PartialEq, Eq, Hash)]`.
//! If you implement these yourself, it is important that the following property holds:
//!
//! ```text
//! k1 == k2 -> hash(k1) == hash(k2)
//! ```
//!
//! In other words, if two keys are equal, their hashes must be equal.
//!
//! The priority `P` may be any type that implements
//! [`Ord`](https://doc.rust-lang.org/std/cmp/trait.Ord.html).
//! For reverse order remember the standard wrapper
//! [`Reverse<T>`](https://doc.rust-lang.org/std/cmp/struct.Reverse.html)
//!
//! # Examples
//! ```rust
//! use priority_queue::PriorityQueue;
//!
//! let mut pq = PriorityQueue::new();
//!
//! assert!(pq.is_empty());
//! pq.push("Apples", 5);
//! pq.push("Bananas", 8);
//! pq.push("Strawberries", 23);
//!
//! assert_eq!(pq.peek(), Some((&"Strawberries", &23)));
//!
//! pq.change_priority("Bananas", 25);
//! assert_eq!(pq.peek(), Some((&"Bananas", &25)));
//!
//! for (item, _) in pq.into_sorted_iter() {
//!     println!("{}", item); // Will print Bananas, Strawberries, Apples
//! }
//! ```
//!
//! Reverse ordering
//! ```rust
//! use priority_queue::PriorityQueue;
//! use std::cmp::Reverse;
//!
//! let mut pq = PriorityQueue::new();
//!
//! assert!(pq.is_empty());
//! pq.push("Apples", Reverse(5));
//! pq.push("Bananas", Reverse(8));
//! pq.push("Strawberries", Reverse(23));
//!
//! assert_eq!(pq.peek(), Some((&"Apples", &Reverse(5))));
//!
//! for (item, _) in pq.into_sorted_iter() {
//!     println!("{}", item); // Will print Apples, Bananas, Strawberries
//! }
//! ```

#![cfg_attr(not(feature = "std"), no_std)]
#![cfg_attr(docsrs, feature(doc_cfg))]

#[cfg(not(feature = "std"))]
extern crate alloc;

#[cfg(not(feature = "std"))]
pub(crate) mod std {
    pub use ::alloc::collections;
    pub use core::*;
}

pub mod core_iterators;
pub mod double_priority_queue;
pub mod priority_queue;
mod store;

pub use crate::double_priority_queue::DoublePriorityQueue;
pub use crate::priority_queue::PriorityQueue;

use indexmap::TryReserveError as IndexMapTryReserveError;
use std::collections::TryReserveError as StdTryReserveError;

#[derive(Clone, PartialEq, Eq, Debug)]
pub struct TryReserveError {
    kind: TryReserveErrorKind,
}

/// The error type for `try_reserve` methods.
#[derive(Clone, PartialEq, Eq, Debug)]
enum TryReserveErrorKind {
    Std(StdTryReserveError),
    IndexMap(IndexMapTryReserveError),
}

#[cfg(feature = "std")]
impl std::error::Error for TryReserveError {}

impl core::fmt::Display for TryReserveError {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        match &self.kind {
            TryReserveErrorKind::Std(e) => core::fmt::Display::fmt(e, f),
            TryReserveErrorKind::IndexMap(e) => core::fmt::Display::fmt(e, f),
        }
    }
}

use TryReserveErrorKind::*;
impl From<StdTryReserveError> for TryReserveError {
    fn from(source: StdTryReserveError) -> Self {
        Self { kind: Std(source) }
    }
}

impl From<IndexMapTryReserveError> for TryReserveError {
    fn from(source: IndexMapTryReserveError) -> Self {
        Self {
            kind: IndexMap(source),
        }
    }
}