lisa 0.2.0

lisa - longest increasing subsequence algorithm [ O( nlogn ) ]
Documentation 
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

use std::collections::VecDeque;

 /// # Example
 /// ```
 /// use lisa::interface::find_lis;
 ///
 /// let slice = [3, 10, 2, 1, 20];
 /// let lis = find_lis(&slice);
 ///
 /// println!("{:?}", lis);
 /// ```

pub fn find_lis<T>(slice: &[T]) -> VecDeque<T>
where
	T: PartialOrd + Copy,
{
	// `head_idxs` -> increasing subsequence head idxs
	let mut head_idxs: Vec<usize> = vec![0];

	let mut symlinks: Vec<Option<usize>> = vec![None];

	// Initialized with first idx of `symlinks`, it will only
	// update if a new item is appended to `head_idxs`.
	let mut super_head = 0;

	let mut lis: VecDeque<T> = VecDeque::new();

	for (idx, item) in slice.iter().skip(1).enumerate() {
		let res = lower_bound(slice, &head_idxs, *item);

		match res {
			Some(replace_idx) => {
				head_idxs[replace_idx] = idx;

				if replace_idx == 0 {
					symlinks.push(None)
				} else {
					let prev_head_idx = head_idxs[replace_idx - 1];
					symlinks.push(Some(prev_head_idx));
				}

				// If the new subseq is equal len of prev longest
				// subseq, update `super_head` to head of new subseq
				if replace_idx == head_idxs.len() - 1 {
					super_head = symlinks.len() - 1;
				}
			}

			None => {
				let this_head_idx = head_idxs[head_idxs.len() - 1];
				symlinks.push(Some(this_head_idx));
				super_head = symlinks.len() - 1;
				head_idxs.push(idx);
			}
		}
	}

	lis.push_front(slice[super_head]);

	let mut chain = super_head;

	while let Some(val) = symlinks[chain] {
		lis.push_front(slice[val]);
		chain = val;
	}

	lis
}

// returns idx of a value not less than `given`. If such value not
// exists, returns `None`.
fn lower_bound<T>(slice: &[T], head_idxs: &[usize], given: T) -> Option<usize>
where
	T: PartialOrd,
{
	let slice_len = head_idxs.len();
	let mut left_idx: usize = 0;
	let mut right_idx: usize = slice_len - 1;

	// Loop until 2 items left
	let turns: usize = (slice_len as f64).log2().ceil() as usize;

	for _ in 1..=turns {
		let mid_idx = (left_idx + right_idx) / 2;

		if slice[head_idxs[mid_idx]] >= given {
			right_idx = mid_idx;
		} else {
			left_idx = mid_idx;
		}
	}

	if slice[head_idxs[left_idx]] >= given {
		Some(left_idx)
	} else if slice[head_idxs[right_idx]] >= given {
		Some(right_idx)
	} else {
		None
	}
}