Crate for this?

help
1

Is there something for generating the least unique ID available? Something along the lines of...

pub struct UniqueIdsU64 {
    ids: Vec<u64>,
}

impl UniqueIdsU64 {
    pub fn add(&mut self) -> u64 {
        let ids = self.ids;
        let n = ids.len();
        let last_id_index = n - 1;
        let mut semilast_id: Option<u64> = None;
        let mut last_id: Option<u64> = None;
        for i in 0..n {
            if i == last_id_index {
                semilast_id = last_id;
                last_id = ids.get(i).map(|id| *id);
            } else {
                semilast_id = Some(ids[i]);
                last_id = ids.get(i + 1).map(|id| *id);
            }
            let next_id = ids[i + 1];
        }
        if let Some(semilast_id) = semilast_id {
            //
        } else if let Some(last_id) = last_id {
            if 0 == last_id {
                let id = last_id + 1;
                self.ids.push(id);
                return id;
            } else {
                self.ids.insert(0, 0);
                return 0;
            }
        } else {
            self.ids.push(0);
            return 0;
        }
    }

    pub fn all(&self) -> Vec<u64> {
        self.ids.clone()
    }

    pub fn clear(&mut self) {
        self.ids.clear();
    }

    pub fn remove(&mut self, id: u64) -> bool {
        ...
    }
}
2

I don't get what exactly the requirements are, but it sounds a lot like BTreeSet::range().

2 Likes
3

Why do you need the least unique ID? If you just need a unique ID, you could use a 64-bit counter. If you are using them to index a vector you might want to use slotmap. But you're asking for something like an allocator. You might want to take a look at how something like malloc is implemented.

1 Like
4

This is a pretty odd use case, so I'd recommend rolling your own. However, I think there's a more efficient approach, since your current implementation is linear in n, where n is the largest ID you've allocated.

A better approach would be something like this: make a structure with a max ID and a pool of free small ids.

struct IdPool {
    max: u64,
    free: BTreeSet<u64>,
}

When allocating a new ID, first check if free has anything. If so, pop the minimum ID off of free. If not, increment max and then return max - 1.

When freeing an ID, check if the provided ID is equal to max - 1. If so, simply decrement the value of max. Next, check if the maximum element of free is equal to max - 1, popping it off repeatedly if so. If not, simply add the ID to free.

This approach would yield logarithmic performance on both add and remove operations. If you relax the need to retrieve the minimum ID, it's trivial to get O(1) performance instead.

5 Likes