User defined order for the fields of a struct that implements Iterator?

Given a struct like the following

struct MyStruct {
    field1: Option<String>,
    field2: Option<String>,
    field3: Option<String>,
}

impl IntoIterator for MyStruct {
    type Item = String;

    type IntoIter = IteratingStruct;

    fn into_iter(self) -> Self::IntoIter {
        IteratingStruct { my: self }
    }
}

struct IteratingStruct {
    my: MyStruct,
}

impl Iterator for IteratingStruct {
    type Item = String;

    fn next(&mut self) -> Option<Self::Item> {
        if let Some(one) = self.my.field1.take() {
            return Some(one);
        }

        if let Some(two) = self.my.field2.take() {
            return Some(two);
        }

        if let Some(three) = self.my.field3.take() {
            return Some(three);
        }

        None
    }
}

What would be a good approach to be able to define a custom order for IteratingStruct?

One could do something like my.ordered(vec![Order::Two, Order::One, Order::Three]) . But that leaves a few footguns, such as missing or duplicated entries

Another approach I tried is my.ordered(Order::TwoOneThree), which would need to grow at a rate of n! elements to represent all states and requires a manual impl for each one, so its also not ideal.

Could you just provide a conversion function from MyStruct to [Option<String>; 3] and let the user figure out the order themselves?

If the user needs to specify the order manually with .ordered(...) then your custom iterator is just extra boilerplate (it's not helping manage access, adding abstraction, hiding internal details like field order, etc.).

2 Likes

I was using the custom iterator impl inside other code, but I guess I could adapt it to use a plain array.

I too think this isn't a great interface as far as the example goes. But anyway, we can abstract the question to be "what's a good API for constructing a permutation of a fixed size?" The metrics you've described are "infallible construction from the inputs" and "no factorially growing enums as inputs".

Thinking aloud...

Every permutation can be decomposed into a sequence of swaps, so one way would be to take an iterator of valid swaps ((i, j) where i < j). That's n * (n - 1) / 2 possibilities for size n; going from size k to k+1 introduces k new possibilities. You could nest these, but the code would be gnarly. So probably you'd just make an enum per size, and that's quadratic for a single size, but cubed if you need all smaller sizes.

Another possibility would be to take a Lehmer code in some form, like a tuple of (TwoOrLess, OneOrLess, Zero) (or reversed; Zero optional). Going from k to k+1 again introduces k new variants, but since they're used separately, you'd just introduce a new enum with n-1 variants. You always need all smaller sizes, but it is quadratic in total. In a sense you get the benefits of nesting the other suggestion for free. (If you nested this version, it would be linear, but again gnarly.)

Assuming you want a [uint; N] permutation to come out, we might consider conversion cost. The number of transpositions needed or supplied may vary, but an optimal encoding will involve a linear number of swaps. The direct encoding/decoding of Lehmer codes is quadratic, but you could instead use a modified definition:

  • Start with the identity permutation
  • Largest radix digit is the index of the first element: swap first element with that index
  • Second largest radix digit is the index of the second element out of the remaining elements
  • Etc

In this modified form, the encoding can be seen as an alternative way to supply a sequence of transpositions.


So one way would be to have

#[derive(Copy, Clone)] #[repr(u8)] pub enum D1 { Zero, One, }
#[derive(Copy, Clone)] #[repr(u8)] pub enum D2 { Zero, One, Two, }
#[derive(Copy, Clone)] #[repr(u8)] pub enum D3 { Zero, One, Two, Three, }

And then to construct a permutation [u8; 4] from a tuple = (D1, D2, D3) you could start with the identity permutation = [0, 1, 2, 3] and then

let indices = [tuple.2 as usize, tuple.1 as usize, tuple.0 as usize];
for (offset, idx) in indices.into_iter().enumerate() {
    permutation.swap(offset, offset + idx);
}

Linear growth of variants for a quadratic total, bijection between inputs and outputs, linear construction.