[meta] Optimize the sequence table to use whole table suffix prefixing;
@@ -52,9 +52,25 @@ impl<T: PartialEq + Clone> UniqueSeqTable<T> {
if let Some(offset) = find_subsequence(values, &self.table) {
offset
} else {
- let offset = self.table.len();
- self.table.extend((*values).clone());
- offset
+ let table_len = self.table.len();
+
+ // Try to put in common the last elements of the table if they're a prefix of the new
+ // sequence.
+ //
+ // We know there wasn't a full match, so the best prefix we can hope to find contains
+ // all the values but the last one.
+ let mut start_from = usize::min(table_len, values.len() - 1);
+ while start_from != 0 {
+ // Loop invariant: start_from <= table_len, so table_len - start_from >= 0.
+ if values[0..start_from] == self.table[table_len - start_from..table_len] {
+ break;
+ }
+ start_from -= 1;
+ }
+
+ self.table
+ .extend(values[start_from..values.len()].iter().cloned());
+ table_len - start_from
}
}
pub fn len(&self) -> usize {
@@ -74,17 +90,10 @@ fn find_subsequence<T: PartialEq>(sub: &Vec<T>, whole: &Vec<T>) -> Option<usize>
if whole.len() < sub.len() {
return None;
}
- let max = whole.len() + 1 - sub.len();
- for i in 0..max {
- let mut found: Option<usize> = Some(i);
- for j in 0..sub.len() {
- if sub[j] != whole[i + j] {
- found = None;
- break;
- }
- }
- if found.is_some() {
- return found;
+ let max = whole.len() - sub.len();
+ for i in 0..max + 1 {
+ if whole[i..i + sub.len()] == sub[..] {
+ return Some(i);
}
}
return None;
@@ -105,3 +114,24 @@ fn test_find_subsequence() {
Some(1)
);
}
+
+#[test]
+fn test_optimal_add() {
+ let mut seq_table = UniqueSeqTable::new();
+ // [0, 1, 2, 3]
+ assert_eq!(seq_table.add(&vec![0, 1, 2, 3]), 0);
+ assert_eq!(seq_table.add(&vec![0, 1, 2, 3]), 0);
+ assert_eq!(seq_table.add(&vec![1, 2, 3]), 1);
+ assert_eq!(seq_table.add(&vec![2, 3]), 2);
+ assert_eq!(seq_table.len(), 4);
+ // [0, 1, 2, 3, 4]
+ assert_eq!(seq_table.add(&vec![2, 3, 4]), 2);
+ assert_eq!(seq_table.len(), 5);
+ // [0, 1, 2, 3, 4, 6, 5, 7]
+ assert_eq!(seq_table.add(&vec![4, 6, 5, 7]), 4);
+ assert_eq!(seq_table.len(), 8);
+ // [0, 1, 2, 3, 4, 6, 5, 7, 8, 2, 3, 4]
+ assert_eq!(seq_table.add(&vec![8, 2, 3, 4]), 8);
+ assert_eq!(seq_table.add(&vec![8]), 8);
+ assert_eq!(seq_table.len(), 12);
+}
