spaced_repetition/lib.rs
1//! A library implementing a spaced repetition algorithm.
2
3#![warn(missing_docs)]
4
5use chrono::{DateTime, Duration, TimeZone, Utc};
6use rand::Rng;
7use rand_distr::Distribution;
8use rand_distr::Normal;
9use rand_distr::Uniform;
10#[cfg(serde)]
11use serde::{Deserialize, Serialize};
12use std::cmp::Ordering;
13
14#[cfg(test)]
15mod tests;
16
17/// The repetition state of a learnable item.
18#[derive(Clone, Debug)]
19#[cfg_attr(serde, derive(Serialize, Deserialize))]
20pub enum RepetitionState {
21 /// The item has made it through the initial learning phase and will now be repeated at larger intervals.
22 Reviewing {
23 /// The ease factor of the word.
24 /// It influences how fast the intervals between repetitions get larger.
25 ease_factor: f64,
26 /// The time of the last repetition.
27 last_repetition: DateTime<Utc>,
28 /// The time of the next repetition.
29 next_repetition: DateTime<Utc>,
30 },
31
32 /// The item is in the initial learning phase where it is repeated in shorter intervals.
33 Learning {
34 /// The count of easy repetition results.
35 /// [RepetitionResult::Easy] increments this by one, and [RepetitionResult::Hard] and [RepetitionResult::Again] decrement this by one.
36 easy_count: i16,
37 /// The current stage of the item within the learning phase.
38 stage: u16,
39 /// The time of the next repetition.
40 next_repetition: DateTime<Utc>,
41 },
42}
43
44impl RepetitionState {
45 /// Construct a new repetition state in learning stage 0, with its first repetition being at the given `datetime`.
46 pub fn new<TZ: TimeZone>(datetime: DateTime<TZ>) -> Self {
47 Self::Learning {
48 easy_count: 0,
49 stage: 0,
50 next_repetition: datetime.with_timezone(&Utc),
51 }
52 }
53
54 /// Update the repetition state after an item was repeated by the user.
55 /// The time of the repetition was `datetime`, and the result of the repetition was `result`.
56 /// The configuration of the algorithm is given as `configuration`.
57 /// The source of randomness used for jitter is [rand::thread_rng].
58 pub fn update<TZ: TimeZone>(
59 self,
60 datetime: DateTime<TZ>,
61 result: RepetitionResult,
62 configuration: &Configuration,
63 ) -> Result<Self, Error> {
64 self.update_with_rng(datetime, result, configuration, &mut rand::thread_rng())
65 }
66
67 /// Update the repetition state after an item was repeated by the user.
68 /// The time of the repetition was `datetime`, and the result of the repetition was `result`.
69 /// The configuration of the algorithm is given as `configuration`.
70 /// The given `rng` is the source of randomness used for jitter.
71 pub fn update_with_rng<TZ: TimeZone, RngType: Rng>(
72 self,
73 datetime: DateTime<TZ>,
74 result: RepetitionResult,
75 configuration: &Configuration,
76 rng: &mut RngType,
77 ) -> Result<Self, Error> {
78 let datetime = datetime.with_timezone(&Utc);
79 match self {
80 RepetitionState::Reviewing {
81 ease_factor,
82 last_repetition,
83 next_repetition,
84 } => {
85 if datetime < last_repetition {
86 return Err(Error::NegativeRepetitionInterval);
87 }
88
89 let last_planned_interval = next_repetition - last_repetition;
90 let last_planned_interval_seconds = last_planned_interval.num_seconds() as f64;
91 let last_real_interval = datetime - last_repetition;
92 let last_real_interval_seconds = last_real_interval.num_seconds() as f64;
93
94 let ease_factor = match result {
95 RepetitionResult::Again => {
96 ease_factor * configuration.reviewing_phase_ease_factor_again_update
97 }
98 RepetitionResult::Hard => {
99 ease_factor * configuration.reviewing_phase_ease_factor_hard_update
100 }
101 RepetitionResult::Normal => ease_factor,
102 RepetitionResult::Easy => {
103 if last_real_interval_seconds < last_planned_interval_seconds {
104 // If the real interval was shorter than the planned one, do not update the ease factor as much.
105 let interpolation_factor =
106 last_real_interval_seconds / last_planned_interval_seconds;
107 ease_factor
108 * (configuration.reviewing_phase_ease_factor_easy_update
109 * interpolation_factor
110 + (1.0 - interpolation_factor))
111 } else {
112 ease_factor * configuration.reviewing_phase_ease_factor_easy_update
113 }
114 }
115 }
116 .min(configuration.reviewing_phase_max_ease_factor)
117 .max(configuration.reviewing_phase_min_ease_factor);
118
119 let next_interval_seconds = match result {
120 RepetitionResult::Again => {
121 configuration.reviewing_phase_initial_delay_seconds as f64 * ease_factor
122 / configuration.reviewing_phase_initial_ease_factor
123 }
124 RepetitionResult::Hard => {
125 if let Some(fixed_factor) =
126 configuration.reviewing_phase_hard_fixed_interval_factor
127 {
128 last_real_interval_seconds * fixed_factor
129 } else {
130 last_real_interval_seconds * ease_factor
131 }
132 }
133 RepetitionResult::Normal => {
134 if last_real_interval_seconds < last_planned_interval_seconds {
135 // Do not apply ease to the part of the interval that was planned, but not waited out.
136 last_real_interval_seconds * ease_factor
137 + (last_planned_interval_seconds - last_real_interval_seconds)
138 } else {
139 last_real_interval_seconds * ease_factor
140 }
141 }
142 RepetitionResult::Easy => {
143 if last_real_interval_seconds < last_planned_interval_seconds {
144 // Do not apply ease to the part of the interval that was planned, but not waited out.
145 (last_real_interval_seconds * ease_factor
146 + (last_planned_interval_seconds - last_real_interval_seconds))
147 * configuration.reviewing_phase_easy_one_time_interval_bonus
148 } else {
149 last_real_interval_seconds
150 * ease_factor
151 * configuration.reviewing_phase_easy_one_time_interval_bonus
152 }
153 }
154 };
155 let next_interval_seconds = next_interval_seconds
156 * configuration.reviewing_phase_delay_jitter.sample(rng)?;
157
158 // Add one percent because I am not totally sure how accurately i64 -> f64 conversion works.
159 if next_interval_seconds * 1.01 >= i64::MAX as f64 {
160 return Err(Error::Overflow);
161 }
162 let next_interval = Duration::seconds(next_interval_seconds as i64);
163
164 Ok(Self::Reviewing {
165 ease_factor,
166 last_repetition: datetime,
167 next_repetition: datetime + next_interval,
168 })
169 }
170 RepetitionState::Learning {
171 easy_count, stage, ..
172 } => {
173 match result {
174 // If the user chooses again during learning, the word starts from the beginning.
175 RepetitionResult::Again => {
176 if let Some(delay_seconds) = configuration
177 .learning_phase_stage_delay_seconds
178 .first()
179 .cloned()
180 {
181 Ok(Self::Learning {
182 stage: 0,
183 easy_count: easy_count.checked_sub(1).ok_or(Error::Overflow)?,
184 next_repetition: datetime
185 + Duration::seconds(
186 configuration
187 .learning_phase_delay_jitter
188 .apply(rng, delay_seconds)?,
189 ),
190 })
191 } else {
192 Err(Error::ConfigurationMissesLearningStage)
193 }
194 }
195 RepetitionResult::Hard => {
196 if let Some(delay_seconds) = configuration
197 .learning_phase_stage_delay_seconds
198 .get(usize::from(stage.max(1) - 1)) // Cannot overflow because it is at least one.
199 .cloned()
200 {
201 Ok(Self::Learning {
202 stage,
203 easy_count: easy_count.checked_sub(1).ok_or(Error::Overflow)?,
204 next_repetition: datetime
205 .checked_add_signed(Duration::seconds(
206 configuration
207 .learning_phase_delay_jitter
208 .apply(rng, delay_seconds)?,
209 ))
210 .ok_or(Error::Overflow)?,
211 })
212 } else {
213 Err(Error::ConfigurationMissesLearningStage)
214 }
215 }
216 RepetitionResult::Normal => {
217 if let Some(delay_seconds) = configuration
218 .learning_phase_stage_delay_seconds
219 .get(usize::from(stage))
220 .cloned()
221 {
222 Ok(Self::Learning {
223 stage: stage.checked_add(1).ok_or(Error::Overflow)?,
224 easy_count,
225 next_repetition: datetime
226 .checked_add_signed(Duration::seconds(
227 configuration
228 .learning_phase_delay_jitter
229 .apply(rng, delay_seconds)?,
230 ))
231 .ok_or(Error::Overflow)?,
232 })
233 } else {
234 let (delay_seconds, ease_factor) = configuration
235 .compute_reviewing_phase_initial_delay_seconds_and_ease_factor(
236 easy_count,
237 )?;
238 Ok(Self::Reviewing {
239 ease_factor,
240 last_repetition: datetime,
241 next_repetition: datetime
242 .checked_add_signed(Duration::seconds(
243 configuration
244 .learning_phase_delay_jitter
245 .apply(rng, delay_seconds)?,
246 ))
247 .ok_or(Error::Overflow)?,
248 })
249 }
250 }
251 RepetitionResult::Easy => {
252 if usize::from(stage)
253 >= configuration.learning_phase_stage_delay_seconds.len()
254 || (configuration.learning_phase_easy_may_skip_last_stage
255 && usize::from(
256 stage
257 .checked_add(configuration.learning_phase_easy_skip_stages)
258 .ok_or(Error::Overflow)?,
259 ) >= configuration.learning_phase_stage_delay_seconds.len())
260 {
261 let (delay_seconds, ease_factor) = configuration
262 .compute_reviewing_phase_initial_delay_seconds_and_ease_factor(
263 easy_count,
264 )?;
265 Ok(Self::Reviewing {
266 ease_factor,
267 last_repetition: datetime,
268 next_repetition: datetime
269 .checked_add_signed(Duration::seconds(
270 configuration
271 .learning_phase_delay_jitter
272 .apply(rng, delay_seconds)?,
273 ))
274 .ok_or(Error::Overflow)?,
275 })
276 } else {
277 let stage = (stage + configuration.learning_phase_easy_skip_stages)
278 .min(
279 u16::try_from(
280 configuration.learning_phase_stage_delay_seconds.len(),
281 )
282 .map_err(|_| Error::Overflow)?
283 .checked_sub(1)
284 .ok_or(Error::ConfigurationMissesLearningStage)?,
285 );
286 let delay_seconds = configuration
287 .learning_phase_stage_delay_seconds
288 .get(usize::from(stage))
289 .cloned()
290 .unwrap();
291 Ok(Self::Learning {
292 stage: stage.checked_add(1).ok_or(Error::Overflow)?,
293 easy_count: easy_count.checked_add(1).ok_or(Error::Overflow)?,
294 next_repetition: datetime
295 .checked_add_signed(Duration::seconds(
296 configuration
297 .learning_phase_delay_jitter
298 .apply(rng, delay_seconds)?,
299 ))
300 .ok_or(Error::Overflow)?,
301 })
302 }
303 }
304 }
305 }
306 }
307 }
308}
309
310/// The configuration of the algorithm.
311#[derive(Clone, Debug)]
312#[cfg_attr(serde, derive(Serialize, Deserialize))]
313pub struct Configuration {
314 /// The delays between repetitions in the initial learning phase.
315 /// These are given as seconds.
316 ///
317 /// **Warning:** This vector must contain at least one value.
318 ///
319 /// **Example:**
320 /// Setting learning_stages to `[10, 60]` causes the item to be repeated 10 seconds after the initial repetition, and another 60 seconds after that.
321 pub learning_phase_stage_delay_seconds: Vec<u16>,
322
323 /// The amount of stages skipped if the user chooses easy in the learning phase.
324 /// A value of zero resembles the behaviour of a normal result.
325 pub learning_phase_easy_skip_stages: u16,
326
327 /// If true, if the user chooses easy in the learning phase and this would skip past the last stage, the item directly enters the reviewing phase.
328 /// If false, then the item will always enter the last stage, and only after successfully repeating again the item may enter the reviewing phase.
329 pub learning_phase_easy_may_skip_last_stage: bool,
330
331 /// A random variation of the delay during the learning phase.
332 pub learning_phase_delay_jitter: Jitter,
333
334 /// The initial delay in the reviewing phase in seconds.
335 pub reviewing_phase_initial_delay_seconds: u32,
336
337 /// The initial ease factor used in the reviewing phase.
338 pub reviewing_phase_initial_ease_factor: f64,
339
340 /// The minimum ease factor used in the reviewing phase.
341 pub reviewing_phase_min_ease_factor: f64,
342
343 /// The maximum ease factor used in the reviewing phase.
344 pub reviewing_phase_max_ease_factor: f64,
345
346 /// The maximum number of easy results from the learning phase to be applied to the initial ease factor when entering the reviewing phase.
347 pub reviewing_phase_initial_ease_max_easy_count: u16,
348
349 /// The maximum number of hard results from the learning phase to be applied to the initial ease factor when entering the reviewing phase.
350 pub reviewing_phase_initial_ease_max_hard_count: u16,
351
352 /// The factor applied to the ease factor on an easy result.
353 pub reviewing_phase_ease_factor_easy_update: f64,
354
355 /// The factor applied to the ease factor on a hard result.
356 pub reviewing_phase_ease_factor_hard_update: f64,
357
358 /// The factor applied to the ease factor on an again result.
359 pub reviewing_phase_ease_factor_again_update: f64,
360
361 /// A factor applied to the length of the learning interval on an easy answer, additionally to the ease factor.
362 /// This factor is applied only one an easy answer, and does not affect the update of the ease factor.
363 pub reviewing_phase_easy_one_time_interval_bonus: f64,
364
365 /// If set, the learning interval is updated by this exact factor on an hard answer, without accounting for the ease factor.
366 /// The ease factor is still updated in the background.
367 pub reviewing_phase_hard_fixed_interval_factor: Option<f64>,
368
369 /// A random variation of the delay during the reviewing phase.
370 pub reviewing_phase_delay_jitter: Jitter,
371}
372
373impl Configuration {
374 fn compute_reviewing_phase_initial_ease_factor(&self, easy_count: i16) -> Result<f64, Error> {
375 if self.reviewing_phase_initial_ease_factor < 1.0 {
376 return Err(Error::ReviewingPhaseInitialEaseFactorLowerThanOne);
377 }
378
379 match easy_count.cmp(&0) {
380 Ordering::Equal => Ok(self.reviewing_phase_initial_ease_factor),
381 Ordering::Greater => {
382 let easy_count = easy_count.min(
383 self.reviewing_phase_initial_ease_max_easy_count
384 .try_into()
385 .map_err(|_| Error::Overflow)?,
386 );
387 if self.reviewing_phase_ease_factor_easy_update < 1.0 {
388 return Err(Error::ReviewingPhaseEaseFactorEasyUpdateLowerThanOne);
389 }
390 Ok((self.reviewing_phase_initial_ease_factor
391 * self
392 .reviewing_phase_ease_factor_easy_update
393 .powi(easy_count.into()))
394 .min(self.reviewing_phase_max_ease_factor))
395 }
396 Ordering::Less => {
397 let hard_count = easy_count.checked_mul(-1).ok_or(Error::Overflow)?.min(
398 self.reviewing_phase_initial_ease_max_hard_count
399 .try_into()
400 .map_err(|_| Error::Overflow)?,
401 );
402 if self.reviewing_phase_ease_factor_hard_update > 1.0 {
403 return Err(Error::ReviewingPhaseEaseFactorHardUpdateGreaterThanOne);
404 }
405 Ok((self.reviewing_phase_initial_ease_factor
406 * self
407 .reviewing_phase_ease_factor_hard_update
408 .powi(hard_count.into()))
409 .max(self.reviewing_phase_min_ease_factor))
410 }
411 }
412 }
413
414 fn compute_reviewing_phase_initial_delay_seconds_and_ease_factor(
415 &self,
416 easy_count: i16,
417 ) -> Result<(u32, f64), Error> {
418 let initial_ease_factor = self.compute_reviewing_phase_initial_ease_factor(easy_count)?;
419 let ease_ratio = initial_ease_factor / self.reviewing_phase_initial_ease_factor;
420 let initial_delay_seconds =
421 (f64::from(self.reviewing_phase_initial_delay_seconds) * ease_ratio).round();
422
423 // Subtract one because I am not totally sure how accurately u32 -> f64 conversion works.
424 if initial_delay_seconds >= (u32::MAX - 1) as f64 {
425 Err(Error::Overflow)
426 } else {
427 Ok((initial_delay_seconds as u32, initial_ease_factor))
428 }
429 }
430}
431
432/// The result of a repetition as specified by the user.
433#[derive(Clone, Copy, Debug, Eq, PartialEq)]
434#[cfg_attr(serde, derive(Serialize, Deserialize))]
435pub enum RepetitionResult {
436 /// The user was not able to repeat the item.
437 Again,
438 /// The user was able to repeat the item, but found it especially hard.
439 Hard,
440 /// The user was able to repeat the item, with average difficulty.
441 Normal,
442 /// The user was able to repeat the item, and found it especially easy.
443 Easy,
444}
445
446/// The error type used by this crate.
447#[derive(Debug, Clone, Eq, PartialEq)]
448pub enum Error {
449 /// The configuration has no or not enough stages in the learning phase.
450 /// The stages in the learning phase are defined by [Configuration::learning_phase_stage_delay_seconds].
451 ConfigurationMissesLearningStage,
452
453 /// The value of [Configuration::reviewing_phase_ease_factor_easy_update] is lower than one.
454 ReviewingPhaseEaseFactorEasyUpdateLowerThanOne,
455
456 /// The value of [Configuration::reviewing_phase_ease_factor_hard_update] is greater than one.
457 ReviewingPhaseEaseFactorHardUpdateGreaterThanOne,
458
459 /// The value of [Configuration::reviewing_phase_initial_ease_factor] is lower than one.
460 ReviewingPhaseInitialEaseFactorLowerThanOne,
461
462 /// An overflow occurred.
463 Overflow,
464
465 /// The standard deviation given for the gaussian jitter variant is not accepted by [rand_distr::Normal].
466 IllegalJitterStandardDeviation,
467
468 /// An unexpected error in [rand_distr] occurred.
469 UnknownRandDistrError,
470
471 /// An item was repeated before its previous repetition.
472 NegativeRepetitionInterval,
473}
474
475/// A random relative variation of a number.
476#[derive(Clone, Debug)]
477#[cfg_attr(serde, derive(Serialize, Deserialize))]
478pub enum Jitter {
479 /// No jitter is applied.
480 /// The method [Jitter::sample] always returns `1.0` for this variant.
481 None,
482
483 /// Uniform jitter is applied.
484 /// The [Jitter::sample] methods samples from a uniform distribution with the given range.
485 Uniform {
486 /// The minimum of the range of the uniform distribution.
487 min: f64,
488 /// The maximum of the range of the uniform distribution.
489 max: f64,
490 },
491 /// Gaussian jitter is applied.
492 /// The [Jitter::sample] method samples from a gaussian (normal) distribution with mean `1.0` and given standard deviation.
493 Gaussian {
494 /// The standard deviation of the gaussian distribution.
495 standard_deviation: f64,
496 },
497}
498
499impl Default for Jitter {
500 fn default() -> Self {
501 Self::None
502 }
503}
504
505impl Jitter {
506 /// Sample from the jitter.
507 /// This yields a factor that can be multiplied to a number to add random variation.
508 pub fn sample<RngType: Rng>(&self, rng: &mut RngType) -> Result<f64, Error> {
509 Ok(match self {
510 Jitter::None => 1.0,
511 Jitter::Uniform { min, max } => Uniform::new(*min, *max).sample(rng),
512 Jitter::Gaussian { standard_deviation } => Normal::new(1.0, *standard_deviation)
513 .map_err(|error| match error {
514 rand_distr::NormalError::BadVariance => Error::IllegalJitterStandardDeviation,
515 _ => Error::UnknownRandDistrError,
516 })?
517 .sample(rng),
518 })
519 }
520
521 /// Apply random relative jitter to a number.
522 pub fn apply<RngType: Rng, DelayType: Into<f64>>(
523 &self,
524 rng: &mut RngType,
525 delay: DelayType,
526 ) -> Result<i64, Error> {
527 let jitter = self.sample(rng)?;
528 let delay = (jitter * delay.into()).round();
529
530 // Add one percent because I am not totally sure how accurately i64 -> f64 conversion works.
531 if delay * 1.01 >= i64::MAX as f64 {
532 return Err(Error::Overflow);
533 }
534
535 Ok(delay as i64)
536 }
537}