igo/trie/
shrinktail.rs

1use std::cmp;
2use crate::{Utf16Char, Utf16String};
3
4
5/// TAIL配列(文字列)の圧縮を行うクラス
6/// TAILに格納されている文字列群の内で、末尾部分が重複するものは、同じ領域を使用するようにする。
7///
8/// 圧縮対象となるTAIL配列および、TAIL配列へのインデックスを渡してインスタンスを初期化する。
9/// 引数に渡した各オブジェクトはshrinkメソッドの呼び出しに伴い、破壊的に更新される。
10pub fn shrink(tail: Utf16String, mut begs: Vec<i32>, mut lens: Vec<Utf16Char>)
11              -> (Utf16String, Vec<i32>, Vec<Utf16Char>) {
12    let mut new_tail: Utf16String;
13    {
14        // TAILに格納されている文字列群を、その末尾から比較してソートする
15        let sorted: Vec<TailString> = {
16            let mut list = Vec::with_capacity(begs.len());
17            for i in 0..begs.len() {
18                list.push(TailString {
19                    id: i,
20                    s: &tail[(begs[i] as usize)..(begs[i] as usize + lens[i] as usize)]
21                });
22            }
23            list.sort();
24            list
25        };
26
27        // 新しいTAILを用意する
28        // その際に、末尾部分が重複する文字列同士は、領域を共有するようにする
29        new_tail = Vec::new();
30        for i in 0..sorted.len() {
31            let ts = &sorted[i];
32
33            let mut beg_index = new_tail.len();
34            if i > 0 && sorted[i - 1].s.ends_with(ts.s) {
35                beg_index -= ts.s.len();  // 末尾文字列を共有する
36            } else {
37                new_tail.extend_from_slice(ts.s);       // 新しく追加する
38            }
39
40            // TAIL配列へのポインタを更新する
41            begs[ts.id] = beg_index as i32;
42            lens[ts.id] = ts.s.len() as Utf16Char;
43        }
44    }
45
46    (new_tail, begs, lens)
47}
48
49struct TailString<'a> {
50    id: usize,
51    s: &'a [Utf16Char]
52}
53
54impl<'a> cmp::Ord for TailString<'a> {
55    // TailStringを文字列の末尾から順に比較する
56    fn cmp(&self, ts: &Self) -> cmp::Ordering {
57        let mut i = self.s.len() as isize - 1;
58        let mut j = ts.s.len() as isize - 1;
59        loop {
60            if i < 0 {
61                if j < 0 {
62                    return cmp::Ordering::Equal;
63                } else {
64                    return cmp::Ordering::Greater;
65                }
66            } else if j < 0 || self.s[i as usize] > ts.s[j as usize] {
67                return cmp::Ordering::Less;
68            } else if self.s[i as usize] < ts.s[j as usize] {
69                return cmp::Ordering::Greater;
70            }
71
72            i -= 1;
73            j -= 1;
74        }
75    }
76}
77
78impl<'a> cmp::PartialOrd for TailString<'a> {
79    fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
80        Some(self.cmp(other))
81    }
82}
83
84impl<'a> cmp::PartialEq for TailString<'a> {
85    fn eq(&self, other: &Self) -> bool {
86        self.s.eq(other.s)
87    }
88}
89
90impl<'a> cmp::Eq for TailString<'a> {}
igo/trie/shrinktail.rs

igo/trie/
shrinktail.rs
