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

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.

In the Dijkstra algorithm, the NonMax implementation is faster than using manual sentinel values. This is due to specialized optimizations leveraged by the internal representation where None is mapped to 0.

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>.

Similar Libraries

• nonmax
• nonany

License

CC0 1.0 Universal