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
//! Check whether a digraph is complete.
//!
//! A digraph is complete if, for every pair `u`, `v` of distinct vertices,
//! there is an arc from `u` to `v` and an arc from `v` to `u`.
//!
//! # Examples
//!
//! ```
//! use graaf::{
//!     AdjacencyList,
//!     Circuit,
//!     Complete,
//!     Empty,
//!     IsComplete,
//!     RandomTournament,
//! };
//!
//! assert!(AdjacencyList::complete(3).is_complete());
//! assert!(!AdjacencyList::circuit(3).is_complete());
//! assert!(!AdjacencyList::empty(3).is_complete());
//! assert!(!AdjacencyList::random_tournament(3, 0).is_complete());
//! ```

use crate::{
    HasEdge,
    Order,
};

/// Check whether a digraph is complete.
///
/// # Implementing [`IsComplete`] for a custom type
///
/// Provide an implementation of [`is_complete`](IsComplete::is_complete) that
/// returns whether the digraph is complete OR implement `HasEdge` and `Order`.
///
/// ```
/// use {
///     graaf::{
///         Circuit,
///         Complete,
///         Empty,
///         HasArc,
///         IsComplete,
///         Order,
///         RandomTournament,
///     },
///     std::collections::BTreeSet,
/// };
///
/// struct AdjacencyList {
///     pub arcs: Vec<BTreeSet<usize>>,
/// }
///
/// impl HasArc for AdjacencyList {
///     fn has_arc(&self, u: usize, v: usize) -> bool {
///         self.arcs.get(u).map_or(false, |set| set.contains(&v))
///     }
/// }
///
/// impl Order for AdjacencyList {
///     fn order(&self) -> usize {
///         self.arcs.len()
///     }
/// }
///
/// assert!(AdjacencyList {
///     arcs: vec![
///         BTreeSet::from([1, 2]),
///         BTreeSet::from([0, 2]),
///         BTreeSet::from([0, 1])
///     ]
/// }
/// .is_complete());
///
/// assert!(!AdjacencyList {
///     arcs: vec![
///         BTreeSet::from([1]),
///         BTreeSet::from([2]),
///         BTreeSet::from([0])
///     ]
/// }
/// .is_complete());
///
/// assert!(!AdjacencyList {
///     arcs: vec![BTreeSet::new(); 3]
/// }
/// .is_complete());
/// ```
pub trait IsComplete {
    /// Check whether the digraph is complete.
    ///
    /// # Examples
    ///
    /// ```
    /// use graaf::{
    ///     AdjacencyList,
    ///     Circuit,
    ///     Complete,
    ///     Empty,
    ///     IsComplete,
    ///     RandomTournament,
    /// };
    ///
    /// assert!(AdjacencyList::complete(3).is_complete());
    /// assert!(!AdjacencyList::circuit(3).is_complete());
    /// assert!(!AdjacencyList::empty(3).is_complete());
    /// assert!(!AdjacencyList::random_tournament(3, 0).is_complete());
    /// ```
    #[must_use]
    fn is_complete(&self) -> bool;
}

impl<D> IsComplete for D
where
    D: HasEdge + Order,
{
    fn is_complete(&self) -> bool {
        let order = self.order();

        for u in 0..order {
            for v in (u + 1)..order {
                if !self.has_edge(u, v) {
                    return false;
                }
            }
        }

        true
    }
}