algorithms4 0.0.3

A rust implementation of the 4th edition of Algorithms by R. Sedgewick and K. Wayne.
Documentation
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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
//! Utitlies for BST
//!
//! # Safety
//!
//! All getters are safe functions, as they do NOT mutate any memory.
//! However, the others may mutate memory, and therefore to uphold invariants they are marked unsafe,
//! and a notice on how to safely use them are given.
//!

use super::*;

/// Makes a right-leaning red link left-leaning. It returns a new link to `raw_h.right`
///
/// It must be called like so
/// ```
/// # let mut raw_h = true;
/// # fn rotate_left(x: bool) -> bool { x }
/// raw_h = rotate_left(raw_h)
/// ```
///
/// # Safety
///
/// Must be called with a valid `raw_h` which also has a valid [Color::Red] right [Node]
#[must_use]
unsafe fn rotate_left<K, V>(raw_h: Link<K, V>) -> Link<K, V> {
    debug_assert!(raw_h.is_some());
    debug_assert!(Node::is_red(unsafe { raw_h.unwrap().as_ref().right }));

    // SAFETY: raw_h is gurantted to be initialized, since it is Some else propagates
    let h = unsafe { raw_h.unwrap().as_mut() };
    let raw_x = h.right;
    // SAFETY: raw_x must always be there (and therefore initialized), else rotate_left was called with a wrong input
    let x = unsafe { raw_x.unwrap().as_mut() };
    h.right = x.left;
    x.left = raw_h;

    x.color = h.color;
    h.color = Color::Red;

    x.size = h.size;
    h.size = 1 + Node::size(h.left) + Node::size(h.right);

    raw_x
}

/// Makes a left-leaning red link right-leaning. It returns a new link to `raw_h.left`
///
/// It must be called like so
/// ```
/// # let mut raw_h = true;
/// # fn rotate_right(x: bool) -> bool { x }
/// raw_h = rotate_right(raw_h)
/// ```
///
/// # Safety
///
/// Must be called with a valid `raw_h` which also has a valid [Color::Red] left [Node]
#[must_use]
unsafe fn rotate_right<K, V>(raw_h: Link<K, V>) -> Link<K, V> {
    debug_assert!(raw_h.is_some());
    debug_assert!(Node::is_red(unsafe { raw_h?.as_ref().left }));

    // SAFETY: raw_h is gurantted to be initialized, since it is Some else propagates
    let h = unsafe { raw_h?.as_mut() };
    let raw_x = h.left;
    // SAFETY: raw_x must always be there (and therefore initialized), else rotate_left was called with a wrong input
    let x = unsafe { raw_x?.as_mut() };
    h.left = x.right;
    x.right = raw_h;

    x.color = h.color;
    h.color = Color::Red;

    x.size = h.size;
    h.size = 1 + Node::size(h.left) + Node::size(h.right);

    raw_x
}

/// Flips the color of the parent with its children.
///
/// The parent must have opposite color of both its children.
///
/// # Safety
///
/// Must be called with a valid `raw_h` which also has a valid left [Node] and valid right [Node].
unsafe fn flip_colors<K, V>(raw_h: Link<K, V>) {
    // SAFETY: it is assumed raw_h is valid and has valid children
    unsafe {
        let h = raw_h.unwrap().as_mut();
        let left = h.left.unwrap().as_mut();
        let right = h.right.unwrap().as_mut();
        debug_assert!(if h.color == Color::Red {
            left.color == Color::Black && right.color == Color::Black
        } else {
            left.color == Color::Red && right.color == Color::Red
        });
        h.color.switch();
        right.color.switch();
        left.color.switch();
    }
}

/// Make `h.left` or one of its children red. It returns a new link to set as previous `h`
///
/// It must be called like so
/// ```
/// # let mut raw_h = true;
/// # fn move_red_left(x: bool) -> bool { x }
/// raw_h = move_red_left(raw_h)
/// ```
///
/// # Safety
///
/// Must be called with a valid [Color::Red] `raw_h`,
/// valid [Color::Black] `raw_h.left` and valid [Color::Black] `raw_h.left.left`
#[must_use]
unsafe fn move_red_left<K, V>(mut raw_h: Link<K, V>) -> Link<K, V> {
    // SAFETY: Everything inside handles with raw pointers,
    // however they are assumed to be valid on call
    unsafe {
        flip_colors(raw_h);
        let h = raw_h.unwrap().as_mut();
        let right_left_is_red = if let Some(r) = h.right {
            Node::is_red(r.as_ref().left)
        } else {
            false
        };
        if right_left_is_red {
            h.right = rotate_right(h.right);
            raw_h = rotate_left(raw_h);
            flip_colors(raw_h);
        }
    }
    raw_h
}

/// Make `h.right` or one of its children red. It returns a new link to set as previous `h`
///
/// It must be called like so
/// ```
/// # let mut raw_h = true;
/// # fn move_red_right(x: bool) -> bool { x }
/// raw_h = move_red_right(raw_h)
/// ```
///
/// # Safety
///
/// Must be called with a valid [Color::Red] `raw_h`,
/// valid [Color::Black] `raw_h.right` and valid [Color::Black] `raw_h.right.left`
#[must_use]
unsafe fn move_red_right<K, V>(mut raw_h: Link<K, V>) -> Link<K, V> {
    // SAFETY: Everything inside handles with raw pointers,
    // however they are assumed to be valid on call
    unsafe {
        flip_colors(raw_h);
        let h = raw_h.unwrap().as_mut();
        let left_left_is_red = if let Some(l) = h.left {
            Node::is_red(l.as_ref().left)
        } else {
            false
        };
        if left_left_is_red {
            raw_h = rotate_right(raw_h);
            flip_colors(raw_h);
        }
    }
    raw_h
}

/// Restore Red-Black tree invariants
///
/// # Safety
///
/// Must be called with a valid [Color::Red] `raw_h`
#[must_use]
unsafe fn balance<K, V>(mut raw_h: Link<K, V>) -> Link<K, V> {
    // SAFETY: a lot of raw pointer dereferencing, therefore to keep it simple, everything is in an unsafe block
    unsafe {
        let node = raw_h?.as_ref();
        if Node::is_red(node.right) && !Node::is_red(node.left) {
            // make right-leaning links left-leaning
            // SAFETY: called correctly
            raw_h = rotate_left(raw_h);
        }
        let node = raw_h?.as_ref();
        if Node::is_red(node.left)
            && Node::is_red(node.left.unwrap().as_ref().left)
        {
            // rotate right, if two red links in a row on the left sides
            // this allows for flipping the colors (next check)
            // SAFETY: called correctly
            raw_h = rotate_right(raw_h);
        }
        let node = raw_h?.as_ref();
        if Node::is_red(node.left) && Node::is_red(node.right) {
            // if both left and right are red, flip the color up, so the parent becomes red instead
            flip_colors(raw_h);
        }

        // update the size to correctly keep track of total size of the tree
        let node = raw_h?.as_mut();
        node.size = Node::size(node.left) + Node::size(node.right) + 1;

        raw_h
    }
}

/// Finds and inserts the key and value, overriding if key is already present.
///
/// # Safety
///
/// This must be called with complete valid links, and the result must be set as follows
///
/// ```
/// # let mut raw_h = true;
/// # let key = false;
/// # let value = false;
/// # fn put(x: bool, key: bool, value: bool) -> bool { x }
/// raw_h = put(raw_h, key, value);
/// ```
///
/// Doing so gurantees the invariant that all NonNulls are initialized, unless that invairant was already broken.
#[must_use]
pub unsafe fn put<K: Ord, V>(
    raw_h: Link<K, V>,
    key: K,
    value: V,
) -> Link<K, V> {
    if let Some(mut n) = raw_h {
        // SAFETY: since raw_h is Some, it must exist,
        // as all created NonNulls are created in the other part of this if-statement.
        // Furthermore, seeing as balance(raw_h) is returned, that part is called correctly and invariants are restored.
        unsafe {
            let node = n.as_mut();
            match key.cmp(&node.key) {
                Ordering::Less => node.left = put(node.left, key, value),
                Ordering::Greater => node.right = put(node.right, key, value),
                Ordering::Equal => node.value = value,
            }

            balance(raw_h)
        }
    } else {
        // SAFETY: create an initialized node, box it and pack the raw pointer into a NonNull.
        // This allows for the use of Option :)
        // Furthermore, since all nodes are ONLY created here, it gurantees all NonNulls to be initialized,
        // until they're deleted, in which case that function must gurantee that invariant.
        unsafe {
            Some(NonNull::new_unchecked(Box::into_raw(Box::new(Node::new(
                key, value,
            )))))
        }
    }
}

/// Finds and deletes the minimum key, and its associated value, by following left links recursively.
///
/// # Safety
///
/// This must be called with complete valid links,
/// `raw_h`, or one of its children, must be a [Color::Red] link, and the result must be set as follows
///
/// ```
/// # let mut raw_h = true;
/// # fn delete_min(x: bool) -> bool { x }
/// raw_h = delete_min(raw_h);
/// ```
///
/// Doing so gurantees the invariant that all NonNulls are initialized, unless that invairant was already broken.
#[must_use]
pub unsafe fn delete_min<K: Ord, V>(mut raw_h: Link<K, V>) -> Link<K, V> {
    // SAFETY: handles raw pointers, that are assumed to be valid
    unsafe {
        let node = raw_h?.as_ref();

        if node.left.is_none() {
            // SAFETY: if node is the minimum (has no more on left), it is set to be deleted.
            // To uphold the invariants required for proper use, the following requirements must be fulfilled:
            //
            // 1. If a right link exist it must be given to the parent of node. This *SHOULD* always be None to uphold Red-Black invariants.
            // 2. This should always be a red link, and that is guranteed as long as the start call to delete_min is given a red link.
            // Because then move_red_left continously moves the link red down as this function is recursively called.
            // 3. The value must be dropped appropriately to not leak any memory. To do this,
            // the raw pointer is returned to a Box and implicitly dropped.
            //
            // As this is the one of the ONLY two place any value is dropped, it is guranteed to always uphold all invariants, if `raw_h` is always a red link.
            let _ = Box::from_raw(raw_h.unwrap().as_ptr());
            return None;
        }

        // unwrap can be used, as node.left is guranteed to be some here (else None is returned by above if-statement)
        if !Node::is_red(node.left)
            && !Node::is_red(node.left.unwrap().as_ref().left)
        {
            // keep the red link with us on the way down to keep uphold the requirements in previous if-statement
            raw_h = move_red_left(raw_h);
        }

        let node = raw_h?.as_mut();

        node.left = delete_min(node.left);
        balance(raw_h)
    }
}

/// Finds and deletes the maximum key, and its associated value, by following left links recursively.
///
/// # Safety
///
/// This must be called with complete valid links,
/// `raw_h`, or one of its children, must be a [Color::Red] link, and the result must be set as follows
///
/// ```
/// # let mut raw_h = true;
/// # fn delete_max(x: bool) -> bool { x }
/// raw_h = delete_max(raw_h);
/// ```
///
/// Doing so gurantees the invariant that all NonNulls are initialized, unless that invairant was already broken.
#[must_use]
pub unsafe fn delete_max<K: Ord, V>(mut raw_h: Link<K, V>) -> Link<K, V> {
    // SAFETY: handles raw pointers, that are assumed to be valid
    unsafe {
        let node = raw_h?.as_ref();
        if Node::is_red(node.left) {
            raw_h = rotate_right(raw_h);
        }
        let node = raw_h?.as_ref();

        if node.right.is_none() {
            // SAFETY: if node is the maximum (has no more on right), it is set to be deleted.
            // To uphold the invariants required for proper use, the following requirements must be fulfilled:
            //
            // 1. If a left link exist it must be given to the parent of node. This *SHOULD* always be None to uphold Red-Black invariants.
            // 2. This should always be a red link, and that is guranteed as long as the start call to delete_max is given a red link.
            // Because then move_red_right continously moves the link red down as this function is recursively called.
            // 3. The value must be dropped appropriately to not leak any memory. To do this,
            // the raw pointer is returned to a Box and implicitly dropped.
            //
            // As this is one of the ONLY two place any value is dropped, it is guranteed to always uphold all invariants, if `raw_h` is always a red link.
            let _ = Box::from_raw(raw_h.unwrap().as_ptr());
            return None;
        }

        // unwrap can be used, as node.right is guranteed to be some here (else None is returned by above if-statement)
        if !Node::is_red(node.right)
            && !Node::is_red(node.right.unwrap().as_ref().left)
        {
            // keep the red link with us on the way down to keep uphold the requirements in previous if-statement
            raw_h = move_red_right(raw_h);
        }

        let node = raw_h?.as_mut();

        node.right = delete_max(node.right);
        balance(raw_h)
    }
}

/// Finds and deletes the key, and its associated value.
///
/// # Safety
///
/// This must be called with complete valid links,
/// `raw_h`, or one of its children, must be a [Color::Red] link, and the result must be set as follows
///
/// ```
/// # let mut raw_h = true;
/// # let key = false;
/// # fn delete(x: bool, key: &bool) -> bool { x }
/// raw_h = delete(raw_h, &key);
/// ```
///
/// Doing so gurantees the invariant that all NonNulls are initialized, unless that invairant was already broken.
#[must_use]
pub unsafe fn delete<K: Clone + Ord, V: Clone>(
    mut raw_h: Link<K, V>,
    key: &K,
) -> Link<K, V> {
    // SAFETY: handling raw pointers
    unsafe {
        let node = raw_h?.as_ref();
        match key.cmp(&node.key) {
            Ordering::Less => {
                if !Node::is_red(node.left)
                    && !Node::is_red(node.left.unwrap().as_ref().left)
                {
                    // move red down our path to the left :))
                    raw_h = move_red_left(raw_h);
                }
                let node = raw_h?.as_mut();
                node.left = delete(node.left, key);
            }
            _ => {
                if Node::is_red(node.left) {
                    // if left is already red, we will make this link right leaning to allow moving right down the sub-tree
                    raw_h = rotate_right(raw_h);
                }
                let node = raw_h?.as_ref();

                if key.cmp(&node.key).is_eq() && node.right.is_none() {
                    let _ = Box::from_raw(raw_h.unwrap().as_ptr());
                    return None;
                }

                if !Node::is_red(node.right)
                    && !Node::is_red(node.right.unwrap().as_ref().left)
                {
                    // keep moving red along our path down
                    raw_h = move_red_right(raw_h);
                }
                let node = raw_h?.as_mut();
                if key.cmp(&node.key).is_eq() {
                    // copies the minimum key and its value on the right side to this node (so this node is still lower than the others)
                    let min_ptr = min(node.right).unwrap().as_ptr();
                    let min = &*min_ptr;

                    node.key = min.key.clone();
                    node.value = min.value.clone();

                    // then deletes this node, only via delete_min, so invariants are upheld.
                    node.right = delete_min(node.right);
                } else {
                    node.right = delete(node.right, key);
                }
            }
        }
        balance(raw_h)
    }
}

/// Finds the minimum node in this sub-tree, follows left links non-recursively.
///
/// # Safety
///
/// Must uphold RedBlack invariants and that Links that are Some must be initialized.
pub fn min<K: Ord, V>(mut current: Link<K, V>) -> Link<K, V> {
    while current.is_some() {
        // SAFETY: nodes are guranteed to be initialized,
        // as this requires current to be Some (and therefore initialized)
        let node = unsafe { current.unwrap().as_ref() };
        if node.left.is_none() {
            return current;
        } else {
            current = node.left;
        }
    }
    None
}

/// Recursively tries to find the highest key <= `key`.
///
/// # Safety
///
/// Must uphold RedBlack invariants and that Links that are Some must be initialized.
#[must_use]
pub fn floor<K: Ord, V>(x: Link<K, V>, key: &K) -> Link<K, V> {
    // SAFETY: nodes are guranteed to be initialized, as x would propagate None if x.is_none()
    let node = unsafe { x?.as_ref() };
    match key.cmp(&node.key) {
        Ordering::Equal => x,
        Ordering::Less => floor(node.left, key),
        Ordering::Greater => floor(node.right, key).or(x),
    }
}

/// Recursively tries to find the lowest key >= `key`.
///
/// # Safety
///
/// Must uphold RedBlack invariants and that Links that are Some must be initialized.
#[must_use]
pub fn ceiling<K: Ord, V>(x: Link<K, V>, key: &K) -> Link<K, V> {
    // SAFETY: nodes are guranteed to be initialized, as x would propagate None if x.is_none()
    let node = unsafe { x?.as_ref() };
    match key.cmp(&node.key) {
        Ordering::Equal => x,
        Ordering::Greater => ceiling(node.right, key),
        Ordering::Less => ceiling(node.left, key).or(x),
    }
}

/// Returns the amount of nodes < `key`.
///
/// # Safety
///
/// Must uphold RedBlack invariants and that Links that are Some must be initialized.
#[must_use]
pub fn rank<K: Ord, V>(x: Link<K, V>, key: &K) -> usize {
    if let Some(n) = x {
        // SAFETY: nodes are guranteed to be initialized, as n is not None
        let node = unsafe { n.as_ref() };
        match key.cmp(&node.key) {
            Ordering::Less => rank(node.left, key),
            Ordering::Greater => {
                1 + Node::size(node.left) + rank(node.right, key)
            }
            Ordering::Equal => Node::size(node.left),
        }
    } else {
        0
    }
}