1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167

//! A pool which manages allocation of unique indices. Acts like a
//! psuedo-memory allocator.
//!
//! ```
//! extern crate index_pool;
//! use index_pool::IndexPool;
//! 
//! fn main() {
//!     let mut pool = IndexPool::new();
//! 
//!     let a = pool.new_id();
//!     let b = pool.new_id();
//!     let c = pool.new_id();
//! 
//!     let mut data = vec![""; pool.maximum()];
//!     data[a] = "apple";
//!     data[b] = "banana";
//!     data[c] = "coconut";
//! 
//!     // Nevermind, no bananas
//!     pool.return_id(b).unwrap();
//! 
//!     let p = pool.new_id();
//!     data[p] = "pineapple";
//! 
//!     assert_eq!(data, vec!["apple", "pineapple", "coconut"]);
//! }
//! ```

extern crate free_ranges;

use free_ranges::FreeRanges;
use free_ranges::Range;

use std::error::Error;
use std::fmt;

pub mod iter;

/// A pool which manages allocation of unique indices. Acts like a
/// psuedo-memory allocator.
#[derive(Debug)]
pub struct IndexPool {
    next_id: usize,
    in_use: usize,
    free_list: FreeRanges,
}

impl IndexPool {
    /// Constructs an empty IndexPool. Indices will start at `0`.
    #[inline]
    pub fn new() -> Self {
        Self::with_initial_index(0)
    }

    /// Constructs an empty IndexPool. `index` will be the first
    /// index returned from `new_id`. You can logically think of
    /// this as either specifying a base index for the pool, or
    /// pre-allocating the `[0..index)` range. This datastructure
    /// does not care which is your usecase, and neither has any
    /// kind of performance penalty, except that `in_use()` will
    /// include the `[0..index)` range.
    pub fn with_initial_index(index: usize) -> Self {
        IndexPool {
            next_id: index,
            in_use: 0,
            free_list: FreeRanges::new(),
        }
    }

    /// Allocates a new index for use. This is guaranteed to not be any index
    /// which has previously been returned from `new_id` but has not yet been
    /// passed to `return_id`.
    #[inline]
    pub fn new_id(&mut self) -> usize {
        self.in_use += 1;

        if let Some(id) = self.free_list.set_first_used() {
            return id;
        }

        let id = self.next_id;
        self.next_id += 1;
        return id;
    }

    /// Gives an Id back to the pool so that it may be handed out again.
    /// Returns Err if the Id was not in use at the time. Whether ignoring
    /// such an error is okay is up to your own usecase.
    #[inline]
    pub fn return_id(&mut self, id: usize) -> Result<(), AlreadyReturned> {
        if id >= self.next_id {
            return Err(AlreadyReturned);
        }

        if id + 1 == self.next_id {
            self.next_id -= 1;
        } else {
            if !self.free_list.set_free(id) {
                return Err(AlreadyReturned);
            }
        }

        self.in_use -= 1;

        while self.collapse_next() {}

        Ok(())
    }

    /// Returns an upper bound on the number of IDs which have been
    /// allocated, specifically the `highest numbered ID in use + 1`.
    /// Useful if you're going to e.g. create a Vec which has room
    /// for all of your IDs.
    #[inline]
    pub fn maximum(&self) -> usize {
        self.next_id
    }

    /// Returns the number of currently in-use indices
    #[inline]
    pub fn in_use(&self) -> usize {
        self.in_use
    }

    /// Returns an iterator over all indices which are in use
    #[inline]
    pub fn all_indices(&self) -> iter::IndexIter {
        iter::IndexIter::new(self.free_list.free_ranges(), self.next_id)
    }

    #[inline]
    fn collapse_next(&mut self) -> bool {
        if let Some(last_range) = self.free_list.free_ranges().rev().nth(0).cloned() {
            if last_range.max + 1 == self.next_id {
                self.free_list.remove_last_contiguous();
                self.next_id = last_range.min;
                return true;
            }
        }

        false
    }
}

impl Default for IndexPool {
    /// Constructs an empty IndexPool. Indices will start at `0`.
    #[inline]
    fn default() -> Self {
        IndexPool::new()
    }
}

#[derive(Debug)]
pub struct AlreadyReturned;

impl fmt::Display for AlreadyReturned {
    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
        fmt.write_str(self.description())
    }
}

impl Error for AlreadyReturned {
    fn description(&self) -> &str {
        "An index was tried to be returned to the pool, but it was already marked as free."
    }
}