# Arithmetic Nonmax
[](https://crates.io/crates/arithmetic-nonmax)
[](https://docs.rs/arithmetic-nonmax)
[](LICENSE)
The `arithmetic-nonmax` crate provides `NonMax*` types for integer types that are guaranteed to never be their maximum value (`MAX`). Using `NonMax*` types enables memory layout optimization.
Additionally, arithmetic operations can be written intuitively as shown below. For example, in shortest path algorithms, using the `Option<NonMax*>` type allows you to leverage the type system while optimizing the memory layout. See [Benchmarks](#benchmarks) for more details.
```rust
use arithmetic_nonmax::{NonMaxU32, non_max};
let a: NonMaxU32 = NonMaxU32::new(5).unwrap();
let b = non_max!(10); // Conveniently create values with the non_max! macro
let c = b - a; // Arithmetic operations between NonMax types
assert_eq!(a, c);
let d = a * 5; // Arithmetic operations with primitive integers
assert!(a < d);
assert_eq!(d.to_string(), "25"); // Can be converted to string
let array = [non_max!(3), non_max!(4), non_max!(5)];
let e = array[non_max!(2)]; // Support indexing
assert_eq!(a, e);
```
Memory layout optimization can be verified as follows:
```rust
use arithmetic_nonmax::*;
// Check byte size for u32
assert_eq!(std::mem::size_of::<NonMaxU32>(), 4);
assert_eq!(std::mem::size_of::<Option<NonMaxU32>>(), 4);
assert_eq!(std::mem::size_of::<u32>(), 4);
assert_eq!(std::mem::size_of::<Option<u32>>(), 8);
// Check byte size for Option<NonMax*>
assert_eq!(std::mem::size_of::<Option<NonMaxU8>>(), 1);
assert_eq!(std::mem::size_of::<Option<NonMaxU16>>(), 2);
assert_eq!(std::mem::size_of::<Option<NonMaxU32>>(), 4);
assert_eq!(std::mem::size_of::<Option<NonMaxU64>>(), 8);
assert_eq!(std::mem::size_of::<Option<NonMaxU128>>(), 16);
assert_eq!(std::mem::size_of::<Option<NonMaxI8>>(), 1);
assert_eq!(std::mem::size_of::<Option<NonMaxI16>>(), 2);
assert_eq!(std::mem::size_of::<Option<NonMaxI32>>(), 4);
assert_eq!(std::mem::size_of::<Option<NonMaxI64>>(), 8);
assert_eq!(std::mem::size_of::<Option<NonMaxI128>>(), 16);
```
## Benchmarks
Benchmarks are available in `benches/comparison.rs`. They compare execution time and memory usage between using and not using `NonMax` types.
| Dijkstra ($V=5.0 \times 10^5, E = 5.0 \times 10^6$) | 436ms / 18.8MB | 473ms / 20.8MB | 427ms / 18.8MB |
| Floyd-Warshall ($V=5.0 \times 10^2, E = 5.0 \times 10^3$) | 100ms / 1.00MB | 127ms / 2.00MB | 84ms / 1.00MB |
## Bundling for Competitive Programming
When submitting to online judges, you can bundle the library into a single file using the following command:
```bash
(echo "pub mod arithmetic_nonmax {"; sed -e 's/#!\[no_std\]//' -e '/#\[cfg(test)\]/,$d' -e 's/\$crate/crate::arithmetic_nonmax/g' -e 's|//.*||' -e '/^[[:space:]]*$/d' src/lib.rs; echo "}") > bundled.rs
```
## Examples
You can find programs that solve [Aizu Online Judge](https://onlinejudge.u-aizu.ac.jp/home) problems using this library in the `examples/` directory.
Note that you need to bundle the library into a single file when submitting to an online judge.
* [GRL_1_A: Single Source Shortest Path](examples/dijkstra.rs): Uses `Option<NonMax<u32>>` for distances, representing unreachable nodes as `None`.
* [GRL_1_C: All Pairs Shortest Path](examples/floyd_warshall.rs): Uses `Option<NonMax<i32>>` for distances, representing unreachable nodes as `None`.
* [DSL_1_A: Disjoint Set](examples/union_find.rs): Manages parent indices in a Union-Find data structure using `Option<NonMaxUsize>`.
* [DPL_1_A: Coin Changing Problem](examples/coin_change.rs): Solves the coin change problem using DP with `Option<NonMax<u32>>`.
## Similar Libraries
* [`nonmax`](https://github.com/LPGhatguy/nonmax)
* [`nonany`](https://github.com/rick-de-water/nonany)
## License
[CC0 1.0 Universal](LICENSE)