gin_rummy/
deck.rs

1//! Random card shuffling and dealing.
2//!
3//! [`Deck`] is a 52-card-bounded set backed by [`Hand`]; cards can be
4//! inserted and drawn (uniformly at random) without materializing the full
5//! card set.  [`Round::deal`](crate::Round::deal) and
6//! [`Game::deal`](crate::Game::deal) build on it to start rounds from a
7//! shuffled deck.
8//!
9//! This module is gated behind the `rand` feature.
10
11use crate::{Card, Hand};
12use core::fmt;
13use core::str::FromStr;
14use rand::{Rng, RngExt as _};
15
16/// A subset of the standard 52-card deck
17///
18/// This is a set of unique cards backed by [`Hand`].  Duplicates are
19/// structurally impossible.  It requires shuffling to partially retrieve
20/// cards from the deck.  However, it is deterministic to collect all cards.
21#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
22#[cfg_attr(
23    feature = "serde",
24    derive(serde_with::SerializeDisplay, serde_with::DeserializeFromStr)
25)]
26pub struct Deck(Hand);
27
28impl Deck {
29    /// The standard 52-card deck
30    pub const ALL: Self = Self(Hand::ALL);
31
32    /// An empty deck
33    pub const EMPTY: Self = Self(Hand::EMPTY);
34
35    /// The number of cards currently in the deck
36    #[must_use]
37    #[inline]
38    pub const fn len(&self) -> usize {
39        self.0.len()
40    }
41
42    /// Whether the deck is empty
43    #[must_use]
44    #[inline]
45    pub const fn is_empty(&self) -> bool {
46        self.0.is_empty()
47    }
48
49    /// Clear the deck, removing all the cards.
50    pub const fn clear(&mut self) {
51        self.0 = Hand::EMPTY;
52    }
53
54    /// Insert a card into the deck
55    ///
56    /// Returns `true` if the card was newly inserted, `false` if it was
57    /// already present.
58    pub fn insert(&mut self, card: Card) -> bool {
59        self.0.insert(card)
60    }
61
62    /// Take the remaining cards in the deck into a hand.
63    #[must_use]
64    #[inline]
65    pub const fn take(&mut self) -> Hand {
66        core::mem::replace(&mut self.0, Hand::EMPTY)
67    }
68
69    /// Randomly draw `n` cards from the deck and collect them into a hand.
70    ///
71    /// If `n >= self.len()`, all remaining cards are drawn without
72    /// shuffling.
73    ///
74    /// On each iteration, pick a uniform `k` in `0..remaining`, then strip
75    /// the `k` lowest set bits from `self.0`.  The new lowest set bit is the
76    /// `k`-th smallest card, which is moved from the deck to the hand.  This
77    /// performs `n` selections without materializing the card set.
78    #[must_use]
79    pub fn draw(&mut self, rng: &mut (impl Rng + ?Sized), n: usize) -> Hand {
80        let len = self.0.len();
81        if n >= len {
82            return self.take();
83        }
84
85        let mut hand = Hand::EMPTY;
86        for i in 0..n {
87            let bits = (0..rng.random_range(..len - i))
88                .fold(self.0.to_bits(), |bits, _| bits & (bits - 1));
89            let selected = Hand::from_bits_retain(bits & bits.wrapping_neg());
90            hand |= selected;
91            self.0 ^= selected;
92        }
93        hand
94    }
95
96    /// Randomly pop a card from the deck
97    #[must_use]
98    pub fn pop(&mut self, rng: &mut (impl Rng + ?Sized)) -> Option<Card> {
99        self.draw(rng, 1).into_iter().next()
100    }
101}
102
103impl From<Hand> for Deck {
104    fn from(hand: Hand) -> Self {
105        Self(hand)
106    }
107}
108
109impl From<Deck> for Hand {
110    fn from(deck: Deck) -> Self {
111        deck.0
112    }
113}
114
115impl fmt::Display for Deck {
116    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
117        self.0.fmt(f)
118    }
119}
120
121impl FromStr for Deck {
122    type Err = <Hand as FromStr>::Err;
123
124    fn from_str(s: &str) -> Result<Self, Self::Err> {
125        s.parse::<Hand>().map(Self)
126    }
127}
128
129#[cfg(test)]
130mod tests {
131    use super::*;
132
133    /// A tiny deterministic generator, good enough to exercise the paths
134    struct Lcg(u64);
135
136    impl Lcg {
137        fn step(&mut self) -> u32 {
138            self.0 = self
139                .0
140                .wrapping_mul(6_364_136_223_846_793_005)
141                .wrapping_add(1_442_695_040_888_963_407);
142            (self.0 >> 32) as u32
143        }
144    }
145
146    impl rand::rand_core::TryRng for Lcg {
147        type Error = core::convert::Infallible;
148
149        fn try_next_u32(&mut self) -> Result<u32, Self::Error> {
150            Ok(self.step())
151        }
152
153        fn try_next_u64(&mut self) -> Result<u64, Self::Error> {
154            Ok(u64::from(self.step()) << 32 | u64::from(self.step()))
155        }
156
157        fn try_fill_bytes(&mut self, dst: &mut [u8]) -> Result<(), Self::Error> {
158            dst.fill_with(|| self.step() as u8);
159            Ok(())
160        }
161    }
162
163    #[test]
164    fn drawing_partitions_the_deck() {
165        let mut rng = Lcg(2026);
166        let mut deck = Deck::ALL;
167
168        let first = deck.draw(&mut rng, 10);
169        let second = deck.draw(&mut rng, 10);
170        let upcard = deck.pop(&mut rng).unwrap();
171
172        assert_eq!(first.len(), 10);
173        assert_eq!(second.len(), 10);
174        assert_eq!(deck.len(), 31);
175        assert!((first & second).is_empty());
176        assert!(!first.contains(upcard) && !second.contains(upcard));
177
178        let rest = deck.take();
179        assert!(deck.is_empty());
180        assert_eq!(first | second | Hand::from(upcard) | rest, Hand::ALL);
181
182        assert_eq!(deck.pop(&mut rng), None);
183        assert!(deck.insert(upcard));
184        assert!(!deck.insert(upcard));
185        deck.clear();
186        assert_eq!(deck, Deck::EMPTY);
187    }
188}
gin_rummy/deck.rs

gin_rummy/
deck.rs
