Function ipv6_binary_split 

pub fn ipv6_binary_split<T>(nets: &[T]) -> Option<(Ipv6Network, Range<usize>)>
where
    T: AsRef<Ipv6Network>,

Finds the shortest common network for the given slice of networks that covers at least half of slice.

Shortest means that it will have the shortest segment of subnets, or the largest mask.

Imagine that you are building a radix tree or graph from networks and at some point you need to split one of the nodes into two parts.

In other words, it is necessary to find the shortest network that contains at least half of the child networks.

This function implements such an algorithm.

For example, suppose we have the following tree:

.
├─ ::1
├─ ::2
└─ ::3

After splitting:

.
├─ ::1
└─ ::2/127
  ├─ ::2
  └─ ::3

Another more interesting example:

.
├─ 2a02:6b8:0:2302::/64
├─ 2a02:6b8:0:2303::/64
├─ 2a02:6b8:0:2305::/64
├─ 2a02:6b8:0:2308::/64
├─ 2a02:6b8:0:2309::/64
├─ 2a02:6b8:0:230a::/64
├─ 2a02:6b8:0:230b::/64
├─ 2a02:6b8:0:230c::/64
├─ 2a02:6b8:0:230d::/64
├─ 2a02:6b8:0:2314::/64
└─ 2a02:6b8:0:231f::/64

After splitting:

.
├─ 2a02:6b8:0:2302::/64
├─ 2a02:6b8:0:2303::/64
├─ 2a02:6b8:0:2305::/64
└─ 2a02:6b8:0:2308::/61
│ ├─ 2a02:6b8:0:2308::/64
│ ├─ 2a02:6b8:0:2309::/64
│ ├─ 2a02:6b8:0:230a::/64
│ ├─ 2a02:6b8:0:230b::/64
│ ├─ 2a02:6b8:0:230c::/64
│ └─ 2a02:6b8:0:230d::/64
├─ 2a02:6b8:0:2314::/64
└─ 2a02:6b8:0:231f::/64

Complexity

This function runs in O(N) and requires O(1) memory.

Warning

The specified slice must be sorted, otherwise the result is unspecified and meaningless.

Specified networks must not overlap.

Examples

use netip::{Ipv6Network, ipv6_binary_split};

let nets = &["::1", "::2", "::3"];
let mut nets: Vec<_> = nets
    .iter()
    .map(|net| Ipv6Network::parse(net).unwrap())
    .collect();

// The input must be sorted.
nets.sort();

let (supernet, range) = ipv6_binary_split(&nets).unwrap();
// ::2/127 in binary is "0b...10/0b...10", which contains both "::2" and "::3".
assert_eq!(Ipv6Network::parse("::2/127").unwrap(), supernet);

for (idx, net) in nets.iter().enumerate() {
    assert_eq!(range.contains(&idx), supernet.contains(net));
}

// For the second example above.

let nets = &[
    "2a02:6b8:0:2302::/64",
    "2a02:6b8:0:2303::/64",
    "2a02:6b8:0:2305::/64",
    "2a02:6b8:0:2308::/64",
    "2a02:6b8:0:2309::/64",
    "2a02:6b8:0:230a::/64",
    "2a02:6b8:0:230b::/64",
    "2a02:6b8:0:230c::/64",
    "2a02:6b8:0:230d::/64",
    "2a02:6b8:0:2314::/64",
    "2a02:6b8:0:231f::/64",
];
let mut nets: Vec<_> = nets
    .iter()
    .map(|net| Ipv6Network::parse(net).unwrap())
    .collect();
nets.sort();

let (supernet, range) = ipv6_binary_split(&nets).unwrap();
assert_eq!(
    Ipv6Network::parse("2a02:6b8:0:2308::/61").unwrap(),
    supernet
);

for (idx, net) in nets.iter().enumerate() {
    assert_eq!(range.contains(&idx), supernet.contains(net));
}