1 | **use** std::slice; |

2 | |

3 | */// A sparse set used for representing ordered NFA states.* |

4 | *///* |

5 | */// This supports constant time addition and membership testing. Clearing an* |

6 | */// entire set can also be done in constant time. Iteration yields elements* |

7 | */// in the order in which they were inserted.* |

8 | *///* |

9 | */// The data structure is based on: https://research.swtch.com/sparse* |

10 | */// Note though that we don't actually use uninitialized memory. We generally* |

11 | */// reuse sparse sets, so the initial allocation cost is bareable. However, its* |

12 | */// other properties listed above are extremely useful.* |

13 | #[derive(Clone, Debug)] |

14 | **pub** **struct** SparseSet { |

15 | */// Dense contains the instruction pointers in the order in which they* |

16 | */// were inserted.* |

17 | dense: Vec<**usize**>, |

18 | */// Sparse maps instruction pointers to their location in dense.* |

19 | *///* |

20 | */// An instruction pointer is in the set if and only if* |

21 | */// sparse[ip] < dense.len() && ip == dense[sparse[ip]].* |

22 | sparse: Box<[**usize**]>, |

23 | } |

24 | |

25 | **impl** SparseSet { |

26 | **pub** **fn** new(size: **usize**) -> SparseSet { |

27 | SparseSet { |

28 | dense: Vec::with_capacity(size), |

29 | sparse: vec![`0`; size].into_boxed_slice(), |

30 | } |

31 | } |

32 | |

33 | **pub** **fn** len(&self) -> **usize** { |

34 | self.dense.len() |

35 | } |

36 | |

37 | **pub** **fn** insert(&**mut** self, value: **usize**) { |

38 | **let** i = self.len(); |

39 | assert!(i < **self**.dense.capacity()); |

40 | self.dense.push(value); |

41 | self.sparse[value] = i; |

42 | } |

43 | |

44 | **pub** **fn** contains(&self, value: **usize**) -> **bool** { |

45 | **let** i = self.sparse[value]; |

46 | self.dense.get(i) == Some(&value) |

47 | } |

48 | |

49 | **pub** **fn** clear(&**mut** self) { |

50 | self.dense.clear(); |

51 | } |

52 | } |

53 | |

54 | **impl**<'a> IntoIterator **for** &'a SparseSet { |

55 | **type** Item = &'a **usize**; |

56 | **type** IntoIter = slice::Iter<'a, **usize**>; |

57 | **fn** into_iter(self) -> Self::IntoIter { |

58 | self.dense.iter() |

59 | } |

60 | } |

61 | |