List with alternating element types?

[Michael-F-Bryan]

Say I need to create a list datastructure with the following constraints:

• Odd elements have type P
• Even elements have type Q
• The list can only ever have an odd number of items
• Random access needs to be an O(1) operation
• It would be nice to have iterators

Do you know of any datastructures which would have those properties?

I'm actually trying to do this in another language and worked around it with subclassing (i.e. P and Q both inherit from T and I store a List<T>) and lots of runtime checks, but that's not ideal. I'm wondering if Rust's stronger type system will allow nicer solutions.

(I know this has already been discussed on A Vec with alternating element types?, but they didn't really come to any conclusions)

[ZiCog]

Can't you simply use an enum to hold the two element types?
Wrap the thing up in a struct and add an overload for the indexing operation: IndexMut in std::ops - Rust
Enforce the odd/even rules in the overload.

Or use two arrays, one of each type, wrap and overload as above.

[RustyYato]

Would something like this work?

Rust Playground

edit: here is a version with a get method, which you can extend to other variants if needed.

Rust Playground

[Michael-F-Bryan]

I'd prefer to avoid the enum approach and runtime checks. It's effectively what I'm doing at the moment (except with inheritance instead of enums), but it's quite easy to accidentally add/remove/insert an incorrect number of items and break the invariant.

In my case, not maintaining that alternating constraint means things are broken visually at runtime and the end user has a bad time because now the world is in a broken state.

@ZiCog, I'm not sure you can overload indexing so even indices yield one type and odd indices return another. Can you show me an example of what you're intending?

@RustyYato I like your implementation using a Vec<(Separator, Value)> for the rest! That's a lot better than the doubly-linked list I had in mind.

[ZiCog]

@Michael-F-Bryan

I'm not sure you can overload indexing so even indices yield one type and odd indices return another. Can you show me an example of what you're intending?

Correct. An array is my definition homogeneous. All elements have to me the same type.

But I was only thinking that if the element type is an enum then that enum can carry different types within it. One can the overload indexing and have the overload return a different content type for the enum element for odd and even indices. Rather like one would use a base class for the elements in C++.

I'm a total newbie at Rust so this may not be even possible to do satisfactorily for all I know but this code at least returns different types for reads to odd and even indices as required:

use std::ops::{Index,IndexMut};

#[derive(Debug, PartialEq)]
enum Number {
    Even(i32),
    Odd(f32),
}

struct Numbers {
    pub even: Vec<Number>,
    pub odd: Vec<Number>,
}

impl Index<usize> for Numbers {
    type Output = Number;

    fn index(&self, index: usize) -> &Self::Output {
        let i = index / 2;
        if (index % 2) == 0 {
            &self.even[i]
        } else {
            &self.odd[i]
        }
    }
}

impl IndexMut<usize> for Numbers {
    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
        println!("IndexMut {:?}", index);
        let i = index / 2;
        if (index % 2) == 0 {
            println!("even");
            &mut self.even[i]
        } else {
            println!("odd");
            &mut self.odd[i]
        }
    }
}

fn main () {
    let mut numbers = Numbers {
        odd: Vec::new(),
        even: Vec::new(),
    };

    numbers.even.push(Number::Even(0));
    numbers.odd.push(Number::Odd(10.0));
    numbers.even.push(Number::Even(20));
    numbers.odd.push(Number::Odd(30.0));

    // Indexing now returns different types for odds and evens
    println!("{:?}", numbers[0]);
    println!("{:?}", numbers[1]);
    println!("{:?}", numbers[2]);
    println!("{:?}", numbers[3]);
}

As you say, it's quite possible to break the invariant when setting this up and mutating it.

But it is so tantalizingly close, surely with a bit more effort it can be made to enforce the invariant everywhere.

[ZiCog]

Hmm... so the problem is that when we overload [] with index_mut() we only have the array, self, and the index to work with. We don't have a reference to what is actually about to be written at that index so we cannot enforce the invariant at write time.

However, we do have visibility into what is already stored in the element we are about to read or overwrite.

So how about we check the invariant holds for existing elements in the array instead, when we read or are about to write to an index?

use std::ops::{Index,IndexMut};

// Indexing the Numbers array will panic if an odd index contains a Even item
// and vice versa.

#[derive(Debug, PartialEq)]
enum Number {
    Even(i32),
    Odd(f32),
}

struct Numbers {
    pub even: Vec<Number>,
    pub odd: Vec<Number>,
}

impl Index<usize> for Numbers {
    type Output = Number;

    fn index(&self, index: usize) -> &Self::Output {
        let i = index / 2;
        if (index % 2) == 0 {
            // Expect Even in element 
            match self.even[i] {
                Number::Odd(_)  => {
                    panic!("Error: There is an odd thing at an even index.");
                },
                _ => (),
            }
            &self.even[i]
        } else {
            // Expect Odd in element 
            match self.odd[i] {
                Number::Even(_)  => {
                    panic!("Error: There is an even thing at an odd index.");
                }, 
                _ => (),
            }
            &self.odd[i]
        }
    }
}

impl IndexMut<usize> for Numbers {
    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
        println!("IndexMut {:?}", index);
        let i = index / 2;
        if (index % 2) == 0 {
            // Expect Even in element 
            match self.even[i] {
                Number::Odd(_)  => {
                    panic!("Error: There is an odd thing at an even index.");
                },
                _ => (),
            }
            &mut self.even[i]
        } else {
            // Expect Odd in element 
            match self.odd[i] {
                Number::Even(_)  => {
                    panic!("Error: There is an even thing at an odd index.");
                }, 
                _ => (),
            }
            &mut self.odd[i]
        }
    }
}

fn main () {
    let mut numbers = Numbers {
        odd: Vec::new(),
        even: Vec::new(),
    };

    numbers.even.push(Number::Even(0));
    numbers.odd.push(Number::Odd(10.0));
    numbers.even.push(Number::Even(20));
    numbers.odd.push(Number::Odd(30.0));

    // Indexing now returns different types for odds and evens
    println!("{:?}", numbers[0]);
    println!("{:?}", numbers[1]);
    println!("{:?}", numbers[2]);
    println!("{:?}", numbers[3]);

    // Cause a panic with Even item in odd index.
    numbers[3] = Number::Even(20);
    println!("{:?}", numbers[3]);
}

Quite likely not what you want as the error does not show up until long after the erroneous write is made. Which might make debugging harder.

On the other hand the complete program will never see the wrong thing in the wrong place. It either runs OK or dies.

Anyway, I thought this was a weird and fun thing to do and have learned some more corners of Rust in the process.

In the play ground : Rust Playground