     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

    use std::ops::Deref;
    use std::slice;

    /// A sparse set used for representing ordered NFA states.
    ///
    /// This supports constant time addition and membership testing. Clearing an
    /// entire set can also be done in constant time. Iteration yields elements
    /// in the order in which they were inserted.
    ///
    /// The data structure is based on: http://research.swtch.com/sparse
    /// Note though that we don't actually use unitialized memory. We generally
    /// reuse allocations, so the initial allocation cost is bareable. However,
    /// its other properties listed above are extremely useful.
    ///
    /// N.B. The type parameter is misleading. For the most part, this is only
    /// meant to work on instruction pointers. We use a touch of generics to
    /// support 32 bit instruction pointers.
    #[derive(Debug)]
    pub struct SparseSet {
        /// Dense contains the instruction pointers in the order in which they
        /// were inserted. Accessing elements >= self.size is illegal.
        dense: Vec<usize>,
        /// Sparse maps instruction pointers to their location in dense.
        ///
        /// An instruction pointer is in the set if and only if
        /// sparse[ip] < size && ip == dense[sparse[ip]].
        sparse: Vec<usize>,
        /// The number of elements in the set.
        size: usize,
    }

    impl SparseSet {
        pub fn new(size: usize) -> SparseSet {
            SparseSet {
                dense: vec![0; size],
                sparse: vec![0; size],
                size: 0,
            }
        }

        pub fn len(&self) -> usize {
            self.size
        }

        pub fn is_empty(&self) -> bool {
            self.size == 0
        }

        pub fn capacity(&self) -> usize {
            self.dense.len()
        }

        pub fn add(&mut self, ip: usize) {
            let i = self.size;
            self.dense[i] = ip;
            self.sparse[ip] = i;
            self.size += 1;
        }

        pub fn contains_ip(&self, ip: usize) -> bool {
            let i = self.sparse[ip];
            i < self.size && self.dense[i] == ip
        }

        pub fn clear(&mut self) {
            self.size = 0;
        }
    }

    impl Deref for SparseSet {
        type Target = [usize];

        fn deref(&self) -> &Self::Target {
            &self.dense[0..self.size]
        }
    }

    impl<'a> IntoIterator for &'a SparseSet {
        type Item = &'a usize;
        type IntoIter = slice::Iter<'a, usize>;
        fn into_iter(self) -> Self::IntoIter { self.iter() }
    }

# Help

## Keyboard Shortcuts

?
  Show this help dialog
S
  Focus the search field
⇤
  Move up in search results
⇥
  Move down in search results
⏎
  Go to active search result

## Search Tricks

Prefix searches with a type followed by a colon (e.g. `fn:`) to restrict the search to a given type.

Accepted types are: `fn`, `mod`, `struct`, `enum`, `trait`, `type`, `macro`, and `const`.

Search functions by type signature (e.g. `vec -> usize` or `* -> vec`)