do_util/priority_queue/
mod.rs

1/// Pareto element trait. Defines an element that is present on the pareto front.
2pub trait ParetoElement<T:Ord> {
3    /// Iterator trait over the coordinates of the element
4    type CoordIterator: Iterator<Item=T>;
5
6    /// returns the dimensions of the element
7    /// the return value has to match the number of dimensions of the element
8    fn coordinates(&self) -> Self::CoordIterator;
9
10    /// returns true iff the element dominates the other
11    fn dominates(&self, other:&Self) -> bool;
12
13    /// returns the number of dimensions
14    fn nb_dimensions(&self) -> usize;
15
16    /// returns the k-th coordinate
17    fn kth(&self, k:usize) -> T;
18}
19
20/// Defines a guided element. The element provides a guide function used by the priority queue.
21pub trait GuidedElement<T:Ord> {
22    /// returns the guide value of the element
23    fn guide(&self) -> T;
24}
25
26
27/// Defines the behavior of a priority queue.
28/// 
29/// It allows to insert some guided element, remove the minimum or maximum, etc.
30pub trait PriorityQueue<T,Elt> where Elt:GuidedElement<T>, T:Ord {
31
32    /// peeks the minimum element in the queue
33    fn peek_min(&self) -> Option<&Elt>;
34
35    /// peeks the maximum element in the queue
36    fn peek_max(&self) -> Option<&Elt>;
37
38    /// pops the minimum element in the queue
39    fn pop_min(&mut self) -> Option<Elt>;
40
41    /// pops the maximum element in the queue
42    fn pop_max(&mut self) -> Option<Elt>;
43
44    /// inserts an element in the queue
45    /// 
46    /// returns true iff the element was successfully inserted.
47    /// In some situations (for instance pareto priority queues, an insertion does not always
48    /// leads to a successful insertion)
49    fn insert(&mut self, elt:Elt) -> bool;
50
51    /// returns the minimum guide of the priority queue
52    fn peek_min_guide(&self) -> Option<T> {
53        self.peek_min().map(|e| e.guide())
54    }
55
56    /// returns the maximum guide of the priority queue
57    fn peek_max_guide(&self) -> Option<T> {
58        self.peek_max().map(|e| e.guide())
59    }
60
61    /// returns true iff the queue is empty
62    fn is_empty(&self) -> bool { self.peek_min().is_none() }
63}
64
65
66/// Implements pareto front specific functions
67pub trait ParetoFront<T,Elt>:Default where T:Ord, Elt:ParetoElement<T> {
68
69    /// returns an element dominating the element if it exists
70    fn find_dominating(&self, elt:&Elt) -> Option<&Elt>;
71
72    /// creates a new instance of the pareto front with discretization hints
73    fn new_with_discretization(_hint:&[Option<(T,T,T)>]) -> Self {
74        Self::default()
75    }
76    
77}
78
79
80/// Pareto Priority-queue list.
81/// 
82/// Implements a Pareto priority queue. Each element is stored in a simple vector.
83/// When inserting, check all other elements for dominations.
84/// It assumes that if an element e1 dominates an element e2, guide(e1) <= guide(e2)
85pub mod pareto_list;
86
87/// Kd-tree pareto priority queue.
88/// 
89/// Implements a kd-tree as a pareto priority queue.
90pub mod kd_tree;
91
92/// Utility class
93pub mod util;
do_util/priority_queue/mod.rs

do_util/priority_queue/
mod.rs
