Arithmetic Nonmax

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 for more details.

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:

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.

Algorithm	With `NonMax`	Without `NonMax`	With Sentinel
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:

(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 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: Uses Option<NonMax<u32>> for distances, representing unreachable nodes as None.
GRL_1_C: All Pairs Shortest Path: Uses Option<NonMax<i32>> for distances, representing unreachable nodes as None.
DSL_1_A: Disjoint Set: Manages parent indices in a Union-Find data structure using Option<NonMaxUsize>.
DPL_1_A: Coin Changing Problem: Solves the coin change problem using DP with Option<NonMax<u32>>.

Similar Libraries

License