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 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811
/* ************************************************************************ ** ** This file is part of rsp2, and is licensed under EITHER the MIT license ** ** or the Apache 2.0 license, at your option. ** ** ** ** http://www.apache.org/licenses/LICENSE-2.0 ** ** http://opensource.org/licenses/MIT ** ** ** ** Be aware that not all of rsp2 is provided under this permissive license, ** ** and that the project as a whole is licensed under the GPL 3.0. ** ** ************************************************************************ */ use std::fmt; /// Represents a reordering operation on an array. /// /// See the [`Permute`] trait for more information. #[derive(Debug, Clone, PartialEq, Eq, Hash)] pub struct Perm { inv: PermVec, } // This is a Perm stored in the form that's easiest to reason about. // (documented in `Perm::from_vec`) // // It exists solely for clarity of implementation, because implementing // `Perm::shift_right` as `inv: self.inv.prefix_shift_left()` says it a lot // better than any comment I could write above the inlined method body. // // Basically, method bodies on Perm describe the relationship between // the perm and its inverse, while method bodies on PermVec do the real work. #[derive(Clone, PartialEq, Eq, Hash)] struct PermVec( // PermVec<Src, Dest> Vec<usize>, // Indexed<Dest, Vec<Src>> ); impl fmt::Debug for PermVec { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { fmt::Debug::fmt(&self.0, f) } } /// An error which indicates that a permutation vector is invalid. /// /// A permutation vector `vec` is valid if and only if it contains one copy of every /// index in the range `0..vec.len()`. #[derive(Debug)] pub struct InvalidPermutationError { _private: () } impl fmt::Display for InvalidPermutationError { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { fmt::Display::fmt("Tried to construct an invalid permutation.", f) } } impl Perm { /// Construct the identity perm of a given length. pub fn eye(n: usize) -> Perm { Perm { inv: PermVec::eye(n) } } /// Get the length of the permutation. pub fn len(&self) -> usize { self.inv.0.len() } /// Compute the `Perm` that, when applied to the input slice, would (stably) sort it. pub fn argsort<T: Ord>(xs: &[T]) -> Perm { Perm { inv: PermVec::argsort(xs).inverted() } } /// Compute a `Perm` that, when applied to the input slice, would sort it. (not necessarily stably) pub fn argsort_unstable<T: Ord>(xs: &[T]) -> Perm { Perm { inv: PermVec::argsort_unstable(xs).inverted() } } /// Construct a perm. Useful for literals in unit tests. /// /// The representation accepted by this is comparable to indexing with an /// integer array in numpy. If the `k`th element of the permutation vector /// is `value`, then applying the permutation will *pull* the data at index /// `value` into index `k`. /// /// This performs O(n log n) validation on the data to verify that it /// satisfies the invariants of Perm. It also inverts the perm (an O(n) /// operation). pub fn from_vec(vec: Vec<usize>) -> Result<Perm, InvalidPermutationError> { Ok(Perm { inv: PermVec::from_vec(vec)? }.inverted()) } /// Construct a perm from the vector internally used to represent it. /// /// The format taken by this method is actually **the inverse** of the format /// accepted by `from_vec`. If the `k`th element of the permutation vector is /// `value`, then applying the permutation will *push* the data at index `k` /// over to index `value`. This format is generally trickier to think about, /// but is superior to the `from_vec` representation in terms of efficiency. /// /// This performs O(n log n) validation on the data to verify that it /// satisfies the invariants of `Perm`. pub fn from_raw_inv(inv: Vec<usize>) -> Result<Perm, InvalidPermutationError> { Ok(Perm { inv: PermVec::from_vec(inv)? }) } /// No-op constructor. Still performs checking in debug builds. /// /// # Safety /// /// `inv` must contain every element in `(0..inv.len())`, /// or else the behavior is undefined. pub unsafe fn from_raw_inv_unchecked(inv: Vec<usize>) -> Perm { Perm { inv: PermVec(inv).debug_validated() } } /// Construct a permutation of length `a.len() + b.len()`. /// /// Mathematically speaking, this computes the "direct sum" of two permutations. /// /// The inserted elements will be shifted by this permutation's length, /// so that they operate on an entirely independent set of data from /// the existing elements. pub fn append_mut(&mut self, other: &Perm) { // (a direct sum of inverses is the inverse of the direct sum) self.inv.append_mut(&other.inv); } /// Construct a random permutation of the given length. pub fn random(n: usize) -> Perm { use rand::Rng; let mut inv: Vec<_> = (0..n).collect(); rand::thread_rng().shuffle(&mut inv); Perm { inv: PermVec(inv) } } /// Recover the vector representation of the permutation. /// /// See [`Perm::from_vec`] for more details about this representation. /// /// This has a runtime cost of O(n), because [`Perm`] does not actually store this /// vector. See [`Perm::into_raw_inv`] for a constant-time alternative. pub fn into_vec(self) -> Vec<usize> { self.inverted().inv.0 } /// Obtain the vector that is internally used to represent the permutation. /// /// This representation is actually the inverse of the representation produced by /// [`Perm::into_vec`]. See [`Perm::from_raw_inv`] for more information. pub fn into_raw_inv(self) -> Vec<usize> { self.inv.0 } /// Get the inverse of this permutation. #[must_use = "not an in-place operation"] pub fn inverted(&self) -> Perm { // (the inverse of the inverse is... you know...) Perm { inv: self.inv.inverted() } } // (this might sound niche, but it's not like we can safely expose `&mut [u32]`, // so what's the harm in having a niche method?) // /// Compose with the permutation that shifts elements forward (performing `self` first) /// /// To construct the shift permutation itself, use `Perm::eye(n).shift_right(amt)`. pub fn shift_right(self, amt: usize) -> Self { Perm { inv: self.inv.prefix_shift_left(amt) } } /// Compose with the permutation that shifts elements backward (performing `self` first) /// /// To construct the shift permutation itself, use `Perm::eye(n).shift_left(amt)`. pub fn shift_left(self, amt: usize) -> Self { Perm { inv: self.inv.prefix_shift_right(amt) } } /// Compose with the permutation that shifts elements to the right by a signed offset. pub fn shift_signed(self, n: isize) -> Self { if n < 0 { assert_ne!(n, std::isize::MIN, "(exasperated sigh)"); self.shift_left((-n) as usize) } else { self.shift_right(n as usize) } } /// Apply the permutation to an index. O(1). /// /// Calling this on the indices contained in a sparse-format data structure will /// produce the same indices as if the corresponding dense-format data structure /// were permuted. /// /// # Panics /// /// Panics if `i` is out of bounds for the permutation length. pub fn permute_index(&self, i: usize) -> usize { // F.Y.I. this method is **literally the entire reason** that we store the inverse. self.inv.0[i] } /// Construct the outer product of self and `slower`, with `self` /// being the fast (inner) index. /// /// The resulting `Perm` will permute blocks of size `self.len()` /// according to `slower`, and will permute elements within each /// block by `self`. pub fn with_outer(&self, slower: &Perm) -> Perm { // the inverse of the outer product is the outer product of inverses Perm { inv: self.inv.with_outer(&slower.inv) } } /// Construct the outer product of self and `faster`, with `self` /// being the slow (outer) index. pub fn with_inner(&self, faster: &Perm) -> Perm { faster.with_outer(self) } /// Compute the permutation that applies this permutation `exp` times in a row. /// /// This uses exponentiation by squaring to run in `O(log(exp))` time. pub fn pow_unsigned(&self, mut exp: u64) -> Perm { // Exponentiation by squaring (permutations form a monoid) // NOTE: there's plenty of room to optimize the number of heap // allocations here let mut acc = Perm::eye(self.len()); let mut base = self.clone(); while exp > 0 { if (exp & 1) == 1 { acc = acc.permuted_by(&base); } base = base.clone().permuted_by(&base); exp /= 2; } acc } /// Compute the permutation that applies this permutation `exp` times in a row. /// /// This version of the function takes a signed value, so that negative values can produce /// powers of the inverse. /// /// This uses exponentiation by squaring to run in `O(log(exp))` time. pub fn pow_signed(&self, exp: i64) -> Perm { if exp < 0 { assert_ne!(exp, std::i64::MIN); // technically possible to support but... come on, man self.inverted().pow_unsigned((-exp) as u64) } else { self.pow_unsigned(exp as u64) } } } impl PermVec { fn eye(n: usize) -> PermVec { PermVec((0..n).collect()) } fn argsort<T: Ord>(xs: &[T]) -> PermVec { let mut perm: Vec<_> = (0..xs.len()).collect(); perm.sort_by(|&a, &b| xs[a].cmp(&xs[b])); PermVec(perm) } fn argsort_unstable<T: Ord>(xs: &[T]) -> PermVec { let mut perm: Vec<_> = (0..xs.len()).collect(); perm.sort_unstable_by(|&a, &b| xs[a].cmp(&xs[b])); PermVec(perm) } fn from_vec(vec: Vec<usize>) -> Result<PermVec, InvalidPermutationError> { if !Self::validate_data(&vec) { return Err(InvalidPermutationError { _private: () }); } Ok(PermVec(vec)) } // Checks invariants required by Perm for unsafe code. #[must_use = "doesn't assert"] fn validate_data(xs: &[usize]) -> bool { let mut vec = xs.to_vec(); vec.sort(); vec.into_iter().eq(0..xs.len()) } fn debug_validated(self) -> PermVec { debug_assert!(PermVec::validate_data(&self.0)); self } fn append_mut(&mut self, other: &Self) { let offset = self.0.len(); self.0.extend(other.0.iter().map(|&i| i + offset)); debug_assert!(PermVec::validate_data(&self.0)); } #[must_use = "not an in-place operation"] fn inverted(&self) -> Self { let mut inv = vec![::std::usize::MAX; self.0.len()]; // [Src] -> Dest for (i, &x) in self.0.iter().enumerate() { // i: Dest, x: Src inv[x] = i; } PermVec(inv).debug_validated() } // The perm that does `self`, then shifts right. #[allow(unused)] fn postfix_shift_right(mut self, amt: usize) -> PermVec { let n = self.0.len(); self.0.rotate_right(amt % n); self.debug_validated() } // The perm that does `self`, then shifts left. #[allow(unused)] fn postfix_shift_left(mut self, amt: usize) -> PermVec { let n = self.0.len(); self.0.rotate_left(amt % n); self.debug_validated() } // The perm that shifts left, then applies `self` fn prefix_shift_left(mut self, amt: usize) -> PermVec { // Add amt to each value. let n = self.0.len(); let amt = amt % n; for x in &mut self.0 { *x = (*x + amt) % n; } self.debug_validated() } // The perm that shifts right, then applies `self` fn prefix_shift_right(self, amt: usize) -> PermVec { // Subtract amt from each value. // ...or rather, shift left by `(-amt) mod len` // // (technically, this puts it into the range `[1, len]` instead of `[0, len)` // due to a silly edge case, but that doesn't matter) let len = self.0.len(); self.prefix_shift_left(len - amt % len) } fn with_outer(&self, slower: &PermVec) -> PermVec { assert!(self.0.len().checked_mul(slower.0.len()).is_some()); let mut perm = Vec::with_capacity(self.0.len() * slower.0.len()); for &block_index in &slower.0 { let offset = self.0.len() * block_index; perm.extend(self.0.iter().map(|&x| x + offset)); } PermVec(perm).debug_validated() } // Perm that applies self then other. fn then(&self, other: &PermVec) -> PermVec { assert_eq!(self.0.len(), other.0.len(), "Incorrect permutation length"); let mut out = vec![::std::usize::MAX; self.0.len()]; for (out_i, &self_i) in other.0.iter().enumerate() { out[out_i] = self.0[self_i]; } PermVec(out).debug_validated() } } impl Perm { /// Flipped group operator, which composes left-to-right. /// /// Very simply. `a.then(b) == b.of(a)`. The flipped order can feel more natural /// when using method syntax, or if you are dealing with matrix equations written /// in a row-centric formalism. /// /// Additionally, it has a straightforward relation to the group action: /// ```text /// x.permuted_by(a).permuted_by(b) == x.permuted_by(a.then(b)) /// ``` pub fn then(&self, other: &Perm) -> Perm { // The inverses compose in reverse. Perm { inv: other.inv.then(&self.inv) } } /// Conventional group operator, which composes right-to-left. pub fn of(&self, other: &Perm) -> Perm { other.then(self) } } /// Trait for applying a permutation operation. /// /// Impls of `Permute` do not always necessarily apply the permutation directly to /// vectors contained in the type. For instance, data in a sparse format will likely /// use the permutation to transform stored indices. /// /// As a conceptual tool, it can help to consider indices as having distinct types /// (e.g. vertex indices, component indices; or more specific things like "indices of /// rows when sorted by column 2"); in this model, `Perm` can be thought of as being /// parametrized over two index types, where `Perm<Src, Dest>` transforms data indexed /// by type `Src` into data indexed by type `Dest`. Again, this is just a conceptual /// tool; `Perm` does not actually have these type parameters! /// (More about this in [this blog post](https://exphp.github.io/blog/2018/07/30/that-weekend-i-wasted-on-newtyped-indices.html)) /// /// # Laws /// /// All implementations of `Permute` must satisfy the following properties, /// which give `Permute::permuted_by` the qualities of a group action. /// (whose group operator is, incidentally, also `Permute::permuted_by`!) /// /// * **Identity:** /// ```text /// data.permuted_by(Perm::eye(data.len())) == data /// ``` /// * **Compatibility:** /// ```text /// data.permuted_by(a).permuted_by(b) == data.permuted_by(a.permuted_by(b)) /// ``` /// /// When envisioning `Perm` as generic over `Src` and `Dest` types, it could /// perhaps be said that `Perm`s are the morphisms of a category. (brushing /// aside issues of mismatched length) pub trait Permute: Sized { // awkward name, but it makes it makes two things clear // beyond a shadow of a doubt: // - The receiver gets permuted, not the argument. // (relevant when Self is Perm) // - The permutation is not in-place. fn permuted_by(self, perm: &Perm) -> Self; } // (module to protect from lollipop model; the unsafety here // is extremely localized) mod unsafe_impls { use super::*; pub(super) fn inv_permute_to_new_vec<T>(vec: Vec<T>, inv: &PermVec) -> Vec<T> { let mut out = Vec::with_capacity(vec.len()); inv_permute_to_mut_vec(vec, inv, &mut out); out } pub(super) fn inv_permute_to_mut_vec<T>(mut vec: Vec<T>, inv: &PermVec, out: &mut Vec<T>) { assert_eq!( vec.len(), inv.0.len(), "Incorrect permutation length", ); out.clear(); out.reserve_exact(inv.0.len()); //------------------------------------------------ // You are now entering a PANIC FREE ZONE { // scope ptrs so we can reason about them let vec_ptr = vec.as_ptr(); let out_ptr = out.as_mut_ptr(); // a perm holds indices into the data vec, so the inverse holds indices into `out`. for (vec_i, &out_i) in inv.0.iter().enumerate() { // SAFETY: // // * vec_i < vec.len() because: // * vec_i comes from the standard library implementation of `impl Iterator for std::iter::Enumerate`, // and is thus guaranteed to be `< inv.0.len()`. // * We asserted earlier that `inv.0.len() == vec.len()`. // // * vec[vec_i] will not be double-dropped, because: // * we perform `vec.set_len(0)` after this loop. // * we cannot possibly panic before this occurs. let value = unsafe { vec_ptr.offset(vec_i as isize).read() }; // SAFETY: // // * out_i < out.capacity() because: // * A privacy-protected invariant of PermVec guarantees that `out_i < inv.0.len()`. // * We called `Vec::reserve_exact` to ensure that `inv.0.len() <= out.capacity()`. let dest_ptr = unsafe { out_ptr.offset(out_i as isize) }; unsafe { dest_ptr.write(value) }; } } // Don't drop the original items, but do allow the original // vec to fall out of scope so the memory can be freed. // SAFETY: // // * All elements in out[0..vec.len()] are initialized because: // * A privacy-protected invariant of PermVec guarantees that, in the above `for` loop, // every index from 0..vec.len() will have appeared exactly once as `out_i`. unsafe { out.set_len(vec.len()); } unsafe { vec.set_len(0); } // Thank you for flying with us. You may now PANIC! //------------------------------------------------ } } impl<T> Permute for Vec<T> { fn permuted_by(self, perm: &Perm) -> Vec<T> { self::unsafe_impls::inv_permute_to_new_vec(self, &perm.inv) } } // `Permute` doubles as the group operator. // (think of it as matrix multiplication in the matrix representation) impl Permute for PermVec { fn permuted_by(self, perm: &Perm) -> PermVec { PermVec(self.0.permuted_by(perm)) } } impl Permute for Perm { fn permuted_by(self, other: &Perm) -> Perm { self.then(other) } } // rsp2-tasks needs this impl<T: Clone> Permute for std::rc::Rc<[T]> { fn permuted_by(self, perm: &Perm) -> Self { // this could be done with less copying... // (though it absolutely has to make at least one full copy) let vec = self.to_vec(); // an O(n) copy let vec = vec.permuted_by(perm); // O(n) work let slice = vec.into_boxed_slice(); slice.into() // another O(n) copy to embed refcount } } impl<T: Permute + Clone> Permute for std::rc::Rc<T> { fn permuted_by(self, perm: &Perm) -> Self { Box::new((*self).clone().permuted_by(perm)).into() } } #[cfg(test)] #[deny(unused)] mod tests { use super::*; use self::drop_pusher::DropPusher; mod drop_pusher { use std::rc::Rc; use std::cell::RefCell; /// Helper for testing panic/drop safety. pub struct DropPusher<T: Copy>(Rc<RefCell<Vec<T>>>, T); impl<T: Copy + 'static> DropPusher<T> { /// Create a shared vector, and a `new` function which constructs /// `DropPushers` tied to that vector. pub fn new_trial() -> (Rc<RefCell<Vec<T>>>, Box<dyn Fn(T) -> DropPusher<T>>) { let history = Rc::new(RefCell::new(vec![])); let new = { let history = history.clone(); Box::new(move |x| DropPusher(history.clone(), x)) }; (history, new) } } impl<T: Copy> Drop for DropPusher<T> { fn drop(&mut self) { self.0.borrow_mut().push(self.1); } } } #[test] fn inverse() { let perm = Perm::random(20); let inv = perm.inverted(); assert_eq!(perm.clone().permuted_by(&inv), Perm::eye(20)); assert_eq!(inv.permuted_by(&perm), Perm::eye(20)); } #[test] fn inverse_is_argsort() { let perm = Perm::random(20); assert_eq!( Perm::argsort(&perm.clone().into_vec()).into_vec(), perm.inverted().into_vec(), ); } #[test] fn invalid() { assert!(matches!( Perm::from_vec(vec![0, 1, 3, 3]), Err(InvalidPermutationError {..}), )); assert!(matches!( Perm::from_vec(vec![1, 2, 3]), Err(InvalidPermutationError {..}), )); } #[test] #[should_panic(expected = "permutation length")] fn incompatible() { // another requirement for the Vec impl's safety let _ = vec![4, 2, 1].permuted_by(&Perm::eye(2)); } #[test] fn drop_safety() { let (drop_history, dp) = DropPusher::new_trial(); { let vec = vec![dp(0), dp(1), dp(2), dp(3), dp(4)]; let vec2 = vec.permuted_by(&Perm::from_vec(vec![3, 1, 0, 4, 2]).unwrap()); assert_eq!(drop_history.borrow().len(), 0); drop(vec2); assert_eq!(drop_history.borrow().len(), 5); } assert_eq!(drop_history.borrow().len(), 5); } #[test] fn argsort_is_stable() { use rand::Rng; // a long vector of only two unique values; a prime target for stability checks let n = 300; let values: Vec<_> = (0..n).map(|_| rand::thread_rng().gen_range(0, 2)).collect(); let perm = Perm::argsort(&values); let permuted_indices = (0..n).collect::<Vec<_>>().permuted_by(&perm); let permuted_values = values.permuted_by(&perm); let error = format!("not your lucky day, Mister one-in-{:e}", 2f64.powi(n)); let first_one = permuted_values.iter().position(|&x| x == 1).expect(&error); let is_strictly_sorted = |xs: &[_]| xs.windows(2).all(|w| w[0] < w[1]); assert!(is_strictly_sorted(&permuted_indices[..first_one])); assert!(is_strictly_sorted(&permuted_indices[first_one..])); let error = format!("DEFINITELY not your lucky day, Mister one-in-{}-factorial!!", n); assert!(!is_strictly_sorted(&permuted_indices[..]), "{}", error); } #[test] fn associativity() { let xy = Perm::from_vec(vec![1, 0, 2]).unwrap(); let zx = Perm::from_vec(vec![2, 1, 0]).unwrap(); let xyzx = Perm::from_vec(vec![2, 0, 1]).unwrap(); assert_eq!(xy.clone().permuted_by(&zx), xyzx); assert_eq!(xy.then(&zx), xyzx); assert_eq!(zx.of(&xy), xyzx); assert_eq!( vec![0,1,2].permuted_by(&xy).permuted_by(&zx), vec![0,1,2].permuted_by(&xyzx), ); assert_eq!( vec![0,1,2].permuted_by(&xy).permuted_by(&zx), vec![2,0,1], ); for _ in 0..10 { use rand::Rng; let mut rng = rand::thread_rng(); let n = rng.gen_range(10, 20); let s = b"abcdefghijklmnopqrstuvwxyz"[..n].to_vec(); let a = Perm::random(n); let b = Perm::random(n); let c = Perm::random(n); let bc = b.clone().permuted_by(&c); assert_eq!( a.clone().permuted_by(&b).permuted_by(&c), a.clone().permuted_by(&bc), "compatibility, for Self = Perm (a.k.a. associativity)", ); assert_eq!( a.inv.clone().permuted_by(&b).permuted_by(&c), a.inv.clone().permuted_by(&bc), "compatibility, for Self = PermVec", ); assert_eq!( s.clone().permuted_by(&b).permuted_by(&c), s.clone().permuted_by(&bc), "compatibility, for Self = Vec", ); } } #[test] fn append() { let mut a = Perm::from_vec(vec![1, 0]).unwrap(); let b = Perm::from_vec(vec![1, 2, 0]).unwrap(); a.append_mut(&b); assert_eq!( vec![00, 01, /* -- */ 10, 11, 12].permuted_by(&a), vec![01, 00, /* -- */ 11, 12, 10], ); } #[test] fn outer() { let use_outer = |a, b| { let a = Perm::from_vec(a).unwrap(); let b = Perm::from_vec(b).unwrap(); let xs: Vec<_> = (0..b.len()).flat_map(|slow| { (0..a.len()).map(move |fast| 10 * slow + fast) }).collect(); xs.permuted_by(&a.with_outer(&b)) }; assert_eq!( use_outer( vec![1, 0, 2, 3], vec![1, 2, 0], ), vec![ 11, 10, 12, 13, 21, 20, 22, 23, 01, 00, 02, 03, ], ); // empty perms assert_eq!(use_outer(vec![1, 0], vec![]), vec![]); assert_eq!(use_outer(vec![], vec![1, 0]), vec![]); } #[test] fn shift() { assert_eq!( vec![0, 1, 2, 3, 4, 5].permuted_by(&Perm::eye(6).shift_right(8)), vec![4, 5, 0, 1, 2, 3], ); assert_eq!( vec![0, 1, 2, 3, 4, 5].permuted_by(&Perm::eye(6).shift_left(8)), vec![2, 3, 4, 5, 0, 1], ); assert_eq!( vec![0, 1, 2, 3, 4, 5].permuted_by(&Perm::eye(6).shift_signed(8)), vec![4, 5, 0, 1, 2, 3], ); assert_eq!( vec![0, 1, 2, 3, 4, 5].permuted_by(&Perm::eye(6).shift_signed(-8)), vec![2, 3, 4, 5, 0, 1], ); // potentially dumb edge case assert_eq!( vec![0, 1, 2, 3, 4, 5].permuted_by(&Perm::eye(6).shift_signed(6)), vec![0, 1, 2, 3, 4, 5], ); assert_eq!( vec![0, 1, 2, 3, 4, 5].permuted_by(&Perm::eye(6).shift_signed(-6)), vec![0, 1, 2, 3, 4, 5], ); } #[test] fn pow_unsigned() { for &len in &[0, 1, 4, 20] { for _ in 0..5 { let perm = Perm::random(len); for &exp in &[0, 1, 4, 20, 21] { let original = b"abcdefghijklmnopqrstuvwxyz"[..len as usize].to_owned(); let mut brute_force = original.clone(); for _ in 0..exp { brute_force = brute_force.permuted_by(&perm); } let fast = original.permuted_by(&perm.pow_unsigned(exp)); assert_eq!(fast, brute_force); } } } } #[test] /// ```rust /// // IMPORTANT: If you modify this test, UPDATE THE README!!! /// /// use perm_vec::{Perm, Permute}; /// /// fn main() { /// // The vec that permutes "abcd" into "bcda". /// let perm_shl = Perm::from_vec(vec![1, 2, 3, 0]).unwrap(); /// assert_eq!(vec![0, 10, 20, 30].permuted_by(&perm_shl), vec![10, 20, 30, 0]); /// /// // The permutation that reverses a vector /// let perm_rev = Perm::from_vec((0..4).rev().collect()).unwrap(); /// assert_eq!(vec![0, 10, 20, 30].permuted_by(&perm_rev), vec![30, 20, 10, 0]); /// /// // Let's compose them! /// let perm_comp_1 = perm_shl.then(&perm_rev); // this one shifts, then reverses /// let perm_comp_2 = perm_rev.then(&perm_shl); // this one reverses, then shifts /// assert_eq!(vec![0, 10, 20, 30].permuted_by(&perm_comp_1), vec![0, 30, 20, 10]); /// assert_eq!(vec![0, 10, 20, 30].permuted_by(&perm_comp_2), vec![20, 10, 0, 30]); /// } /// ``` fn _readme_doctest() {} }