Why `!0` instead of -1 and recursive type "isn't recursive" when wrapped in a hashmap

help
1

I have been trying to solve leetcode problems lately with Rust. While looking at others' solutions, I found several language-related things that I don' understand, so I decided to ask for help here.

When solving graph problems which are represented as a matrix, you will often write something like this

[0, 1, 0, !0, 0].windows(2)...

to search for neighbor cells. My question is why should we use !0 instead of -1.

When implementing the Trie data structure, my struct for a trie node was something like the following:

struct TrieNode {
    children: HashMap<char, Box<TrieNode>>,
    eow: bool,
}

I wrapped the child trie nodes in Box because I thought it is a recursive data structure and if I didn't do so the compiler wouldn't be able to know the size of this data structure at compile time (since it could be infinitely large) and won't type check. But, when I finished implementing and looked at others' solutions, one of the solutions had the TrieNode defined as follows:

struct TrieNode {
    children: HashMap<char,TrieNode>,
    eow: bool,
}

The child trie node is not wrapped in a Box and this code type checks. My question is why wrapping a recursive data structure in a HashMap (or possibly any container?) makes it non recursive (since if it is recursive, the compiler won't be able to know the size at compile time and therefore refuses to compile).

Thanks for any help!

2

The HashMap (like the Box) is allocated on the heap and contains a pointer to its elements, so the children field has a fixed size.

2 Likes
3

Thanks! This makes perfect sense.

1 Like
4

If you're using integers as bitfields, it's more common to see something like 0xFFFFFFFFu32 instead of using a signed !0 or -1. If you're using integers as numbers, then -1 makes the most sense. I've never had a reason to do !0, but it would be good for code golf on unsigned integers.

2 Likes
5

That is false. A type that contains itself behind indirection is still recursive.

It's not recursion in itself that makes a type infinite-size, but the lack of indirection.

5 Likes
6

Thank you so much for pointing this out!

7

Thank you for your response which really inspired me. I think the key point here is the type. Because the vector index needs to be of type usize and -1 can only be used on usize if it is in literal form like r - 1 where r is of type usize. But we also want the convenience of directly applying the offset regardless of the sign, for example row + row_offset and col + col_offset . As mentioned previously, row and col are of type usize which means rows_offset and col_offset cannot directly store -1 and do arithmetic operations without constantly casting them. And that's why wrapping_add is used instead of add to apply the offset, because we want the overflow from wrapping_add and !0 to have the effect of subtracting. Sorry for not providing enough context. I really should have provided the snippet as:

for w in [0, 1, 0, !0, 0].windows(2) {
    let (new_row, new_col) = (row.wrapping_add(w[0]), col.wrapping_add(w[1]));
    ...
}
8

Ah, for this issue I think usize::MAX is most common. You could also do [1, 2, 1, 0, 1].map(|n: usize| n.wrapping_sub(1)) or [0, 1, 0, -1, 0].map(|n: isize| n as usize). And another way is to make a wrapper type around Vec that implements Index<isize>.

1 Like