SkipList doesn't have the same semantics as a Vec

[coriolinus]

Given the following library code:

extern crate skiplist;
use skiplist::SkipList;

pub const TWENTY_SEVENTEEN: usize = 2017;
pub const FIFTY_MILLION: usize = 50_000_000;

type List<T> = Vec<T>;

pub struct Spinner {
    index: usize,
    items: List<usize>,
    next_insert: usize,
}

impl Spinner {
    pub fn new() -> Spinner {
        let mut items = List::with_capacity(FIFTY_MILLION);
        items.insert(0, 0);
        Spinner {
            index: 0,
            items: items,
            next_insert: 1,
        }
    }

    fn spin_insert(&mut self, steps: usize, item: usize) {
        self.index = ((self.index + steps) % self.items.len()) + 1;
        self.items.insert(self.index, item);
    }

    pub fn insert_until(&mut self, until: usize, steps: usize) {
        for item in self.next_insert..(until + 1) {
            self.spin_insert(steps, item);
        }
        self.next_insert = until + 1;
    }

    pub fn get_index(&self) -> usize {
        self.index
    }

    pub fn get_items(&self) -> &List<usize> {
        &self.items
    }
}

then running the following produces a value of 640:

fn main() {
    let mut spinner = Spinner::new();
    spinner.insert_until(TWENTY_SEVENTEEN, INPUT);
    println!(
        "Item after 2017 inserts: {}",
        spinner.get_items()[spinner.get_index() + 1]
    );
}

However, if you replace type List<T> = Vec<T>; with type List<T> = SkipList<T>; in the library code, running the same code produces a value of 494. (No playground link because skiplist is not available in the playground; sorry.) In other words, though we haven't changed the algorithm at all, we get different results.

This is obviously not a minimal example, and for that I apologize. However, this case seems to prove that something is broken in the SkipList implementation.

[coriolinus]

In Cargo.toml:

[dependencies]
skiplist = "0.2.10"

[carlomilanesi]

The cause is that the signature of alloc::vec::Vec insert is pub fn insert(&mut self, index: usize, element: T), and the signature of skiplist::skiplist::SkipList insert is pub fn insert(&mut self, value: T, index: usize).
Using the former, insert(1, 'x') inserts an 'x' in position 1; using the latter, insert('y', 2) inserts a 'y' in position 2. If your items have type `usize', you can wrongly swap the item with the position.

[coriolinus]

Thanks for solving this! It's been a long while since I encountered this problem. Given that this is user error, one could plausibly just close this issue.

On the other hand, there's no obvious reason why this library shouldn't use the same insert signature that Vec does. Would a PR which normalizes the interface be welcomed?