How do I reverse a range?

I wanted to construct a more general range which can also count downward. I tried the following

    let range = if start < end {
        (start..end)
    } else {
        (end..start).rev()
    };
    println!("{:?}", range);

which doesn’t work because the types aren’t right. According to this question I have essentially two options:

  1. Erase the type.
  2. Collect into a vector

Erasing the type:
Something with Box::new but the given the example doesn’t actually use .rev():

    let items = if start < end {
        println!("start is smaller");
        Box::new((start..end))
    } else {
        println!("end is smaller");
        Box::new((end..start))
    };

And with .rev() it doesn’t work.

Collecting into a vector:

    let range = if start < end {
        (start..end).collect::<Vec<i32>>()
    } else {
        (end+1..start+1).rev().collect::<Vec<i32>>()
    };

This seems to work but now I also need to use .into_iter() so I can map over it again and it might - I don’t know - copy thing a round a bit too much.

What’s the right way to do this? I don’t have a good understanding of what is going on internally so I would like to know both, how to make this efficient and how to make it nice/idiomatic.

2 Likes

Not sure what exactly you want, but it seems you may want to create your own iterator.

struct MyRange {
  current: i32,
  target: i32,
  step: i32,
}

impl Iterator for MyRange {
  type Item = i32;
  fn next(&mut self) -> Option<i32> {
    if self.current == self.target {
      None
    } else {
      let res = self.current;
      self.current += self.step;
      Some(res)
    }
  }
}
3 Likes

I am not sure what I want but this is definitely an interesting suggestion! Thank you! :sun_with_face:

You can use Box like so:

let range = if start < end {
    Box::new(start..end) as Box<dyn Iterator<Item=usize>>
} else {
    Box::new((end..start).rev()) as Box<dyn Iterator<Item=usize>>
};

It can also be written like this:

let range: Box<dyn Iterator<Item=usize>> = if start < end {
    Box::new(start..end)
} else {
    Box::new((end..start).rev())
};

Your original code doesn’t work because Box::new returns Box<T> with the concrete type T you’ve supplied. But as long as T implements a trait Trait, Box<T> can be coerced to Box<dyn Trait> (a boxed trait object). In the first example the coercion is done explicitly via as. In the second example it’s done implicitly.

Permalink to the playground

1 Like

There’s a third option, which is to use an enum.

This is easiest done with the either crate, as

let range = if start < end { Either::Left(start..end) } 
    else { Either::Right((end..start).rev()) }; 
println!("{:?}", range);

BTW, you can achieve the same effect as Box with just a reference:

let range: &dyn Iterator<Item=i32> = if cond { &first_range } else { &second_range };

but I guess that Either may optimize better.

1 Like

Huh…so Either doesn’t require some sort of unwrapping? So what kind of type does a function have to take if I want to pass it an Either?

And what does it compile to?

A function should take impl Iterator<Item=...> in this case.

Either implements Iterator when both the left and right are themselves iterators:
https://docs.rs/either/1.5.2/either/enum.Either.html#impl-Iterator

Whenever you call an iterator method on the Either it does a match and calls that method on the inner iterator.

So it will be a dynamic type check?

But this seems more elegant. :slight_smile:
Referring to:

let range: &dyn Iterator<Item=i32> = if cond { &first_range } else { &second_range };

It is, but so is the Either solution, imho :slight_smile:

You can choose Either one :stuck_out_tongue:

But more seriously, there needs to be a dynamic dispatch in either case (it is needed to know, for instance, whether to increment or decrement), and whilst the Either enum achieves this with a pattern match on the discriminant (isomorphic to having a reverse: bool flag on the range struct), the &dyn Iterator uses a pointer to a vtable to resolve which iteration method to use; in other words, enum-based dispatch is often more performant than trait object / vtable-based dispatch.

1 Like

The way you have it written now, it is useless, because iterators need to have &mut to do anything.

But even if you rewrite it, it is better to use Either as @Yandros said.

2 Likes

Right, I hadn’t paid attention to that “detail” either :sweat_smile:. Indeed, you’d need to use &mut dyn Iterator (or Box<dyn Iterator> like @Riateche suggested if you want ownership, in which case the Either variant becomes even more interesting since it does not require a heap allocation to get ownership).

3 Likes

In my previous example I’ve failed to use &mut instead of &, but that wasn’t relevant. In either case you don’t need heap allocation for dynamic dispatch:

https://play.rust-lang.org/?gist=214cc4f5e7f37ba94d56d77a79359077

I ran into a similar situation with the specs crate and thought @kornel’s solution might do the trick but it appears the Join trait doesn’t allow that.

Context: !first converts BitSet into BitSetNot, both of which implement Join.

use specs::prelude::*;

fn main() {
    let first = BitSet::new();
    let second = !first;
    let cond = true;
    let bitset: &dyn Join = if cond {
        &first
    } else {
        &second
    }
    bitset.join();
}

Ignoring the fact that &dyn Join is missing its associated types, here’s one of the errors I get:

error[E0038]: the trait `specs::join::Join` cannot be made into an object
 --> src/main.rs:8:9
  |
8 |         &first
  |         ^^^^^^ the trait `specs::join::Join` cannot be made into an object
  |
  = note: method `get` has no receiver
  = note: method `is_unconstrained` has no receiver
  = note: required because of the requirements on the impl of `std::ops::CoerceUnsized<&dyn specs::join::Join>` for `&hibitset::BitSet`

Is there a way around this limitation?

You probably want something stronger than == in your test - in case (end - start) mod step isn’t 0

Some types are unusable as dyn. Rust calls it object safety: https://doc.rust-lang.org/book/ch17-02-trait-objects.html#object-safety-is-required-for-trait-objects

But the traits can be made to work, by qualifying the non-object-safe methods with where Self: Sized, if they are reasonably useful without these methods.

That would be a change that specs has to make, though.

1 Like

Besides changing specs, I was able to workaround it with a newtype which stores a BitSetLike as a trait object. I wish I didn’t have to do this though :confused:

use hibitset::BitSetLike;
use hibitset::BitSetNot;
use specs::prelude::*;
use specs::world::Index;

struct BitSetRef<'a>(&'a dyn BitSetLike);

impl<'a> From<&'a BitSet> for BitSetRef<'a> {
    fn from(bitset: &'a BitSet) -> Self {
        BitSetRef(bitset)
    }
}

impl<'a, T> From<&'a BitSetNot<T>> for BitSetRef<'a>
where
    T: BitSetLike,
{
    fn from(bitset: &'a BitSetNot<T>) -> Self {
        BitSetRef(bitset)
    }
}

impl<'a> BitSetLike for BitSetRef<'a> {
    fn layer3(&self) -> usize {
        self.0.layer3()
    }
    fn layer2(&self, i: usize) -> usize {
        self.0.layer2(i)
    }
    fn layer1(&self, i: usize) -> usize {
        self.0.layer1(i)
    }
    fn layer0(&self, i: usize) -> usize {
        self.0.layer0(i)
    }
    fn contains(&self, i: u32) -> bool {
        self.0.contains(i)
    }
}

impl<'a> Join for BitSetRef<'a> {
    type Type = Index;
    type Value = ();
    type Mask = Self;

    unsafe fn open(self) -> (Self::Mask, Self::Value) {
        (self, ())
    }

    unsafe fn get(_: &mut Self::Value, id: Index) -> Self::Type {
        id
    }
}

fn main() {
    let first = BitSet::new();
    let second = !first.clone();
    let cond = true;
    let bitset = if cond {
        BitSetRef::from(&first)
    } else {
        BitSetRef::from(&second)
    };
    bitset.join();
}