Използване на Option като итератор

Програмиране с Rust

Курс във Факултета по Математика и Информатика към СУ

Решение на Search от Николай Коцев

Обратно към всички решения

Към профила на Николай Коцев

Резултати

  • 15 точки от тестове
  • 0 бонус точки
  • 15 точки общо
  • 5 успешни тест(а)
  • 0 неуспешни тест(а)

Код

// Changes from the lunch break
use std::collections::HashSet;
pub fn extract_words(str_slc: &str) -> Vec<String> {
::WordIterator::new(str_slc).collect()
}
pub struct WordIterator<'a> {
original: &'a str,
}
impl<'a> WordIterator<'a> {
pub fn new(words: &'a str) -> Self {
WordIterator {
original: words,
}
}
fn skip_while_nonalphabetic(&mut self) {
self.skip_while(|character| !character.is_alphabetic())
}
fn skip_while<F>(&mut self, closure: F) where F: Fn(char) -> bool {
if self.original.len() == 0 { return };
let mut index = 0;
for (current_index, character) in self.original.char_indices() {
if !closure(character) {
index = current_index;
break;
}
}
let (_, skipped_nonalpha) = self.original.split_at(index);
self.original = skipped_nonalpha;
}
}
impl<'a> Iterator for WordIterator<'a> {
type Item = String;
fn next(&mut self) -> Option<Self::Item> {
if self.original.len() == 0 { return None }
let mut index = 0;
let mut last_char = 0 as char;
self.skip_while_nonalphabetic();
for (current_index, character) in self.original.char_indices() {
last_char = character;
if !character.is_alphabetic() {
index = current_index;
break;
}
}
if index == 0 && !last_char.is_alphabetic() { return None };
if last_char.is_alphabetic() { index = self.original.len() }
let (result, skipped_word) = self.original.split_at(index);
self.original = skipped_word;
Some(String::from(result))
}
}
pub struct TextIndex {
index: HashSet<String>
}
impl TextIndex {
pub fn new() -> Self {
Self { index: HashSet::new() }
}
pub fn push(&mut self, text: &str) {
self.index.insert(String::from(text));
}
pub fn search(&self, query: &str) -> HashSet<&str> {
let query_words = extract_words(query);
let mut result_set: HashSet<&str> = HashSet::new();
for word in query_words.iter() {
let lowercased_word = word.to_lowercase();
for sentence in &self.index {
let lowercased_sentence = sentence.to_lowercase();
if lowercased_sentence.contains(&lowercased_word) {
result_set.insert(sentence);
}
}
}
result_set
}
}

Лог от изпълнението

Compiling solution v0.1.0 (file:///tmp/d20180105-6053-gw9pem/solution)
    Finished dev [unoptimized + debuginfo] target(s) in 4.83 secs
     Running target/debug/deps/solution-3f98bfa5c86a5dd9

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

     Running target/debug/deps/solution_test-3d9e4ea2eafbbc82

running 5 tests
test solution_test::test_extract_words_basic ... ok
test solution_test::test_extract_words_extra ... ok
test solution_test::test_search_multiple_words ... ok
test solution_test::test_search_special_cases ... ok
test solution_test::test_search_word ... ok

test result: ok. 5 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

   Doc-tests solution

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

История (3 версии и 5 коментара)

Николай качи първо решение на 27.12.2017 10:10 (преди над 7 години)

Радвам се, че се усети за формата, че предизвикателствата нямат коментари :)

Иначе, няма проблеми да е просто решение, както казахме, но е доста добра идея да го изтестваш с някакви по-особени примери, да видиш дали работи правилно :). Конкретно extract_words може би има edge case-ове, с които не се справя супер добре.

Благодаря за загрижеността, относно формите.

Относно edge case-а, един който намерих е, че няма да може да намира думи с тирета. Примери: по-голям, най-интересен и тн.

Смятам да го оправя с използването на WordIterator, но когато започнах да го пиша стигнах до следния момент:

pub struct WordIterator<'a> {
    chars: std::str::Chars<'a>
}

...

impl<'a> Iterator for WordIterator<'a> {
    type Item = String;

    fn next(&mut self) -> Option<Self::Item> {
        self.chars = self.chars.skip_while(|c| !c.is_alphabetic());
        ...
    }
}

Това е невалидно, тъй като self.chars очаква std::str::Chars, докато аз се опитвам да му дам std::iter::SkipWhile. Няма имплементация за into (Тъй като, ако не се лъжа, типа се получава std::iter::SkipWhile<std::str::Chars>) и ми се налага да правя:

self.chars = self.chars.skip_while(|c| !c.is_alphabetic()).collect::<String>().chars();

което не мисля, че е напълно коректно. Има ли някакъв вграден начин за преобразуване на итератори, или съм тръгнал изцяло в грешна посока?

Не, това е проблем, на който удари и някой друг -- няма конкретен общ тип, до който може да се "сведе" един итератор. Няма "наследяване" реално, това се имплементира с trait-ове. Но конкретния тип трябва да е същия. На теория, може да се държи Box<Iterator>, което обаче би изисквало алокация на heap-а, и едно ниво на индирекция на всяко викане на next, така че не бих го приел като валидно решение за целите на бонус точките.

Ако минеш през collect().chars(), единственото, което ще постигнеш, е да го конвертираш в наново-алокиран низ, и после да вземеш неговите символи. Дори не съм сигурен дали това ще проработи в случая, понеже низа би бил временен, и би взел reference към току-що деструктиран низ.

Съветвам те да направиш крачка назад и да пробваш различна тактика. Трябва някак да сменяш вътрешното състояние, но то трябва да си остане същия тип. Има няколко различни посоки (включително една-две измислена от колегите ти, които не бях се сетил :)), но трябва да си харесаш една, която работи :). Разгледай документациите на str, Chars, char, има какво да намериш. Не се притеснявай да пробваш и с "глупава" итерация, не винаги е по-лесно да композираш неща :).

Николай качи решение на 29.12.2017 14:55 (преди над 7 години)

+// Quite uglier than the previous solution
use std::collections::HashSet;
-const PUNCTUATION_PATTERN: &[char] = &[',', '.', '!', '?'];
-// Ultra simple/stupid solution incoming
pub fn extract_words(str_slc: &str) -> Vec<String> {
- let string = String::from(str_slc);
- let word_vec = string.split_whitespace().collect::<Vec<_>>();
- word_vec.into_iter()
- .map(|string| string.trim_matches(PUNCTUATION_PATTERN))
- .filter(|string| string.chars().all(char::is_alphabetic))
- .filter(|string| string.len() != 0)
- .map(String::from)
- .collect()
+ ::WordIterator::new(str_slc).collect()
}
+pub struct WordIterator<'a> {
+ original: &'a str,
+}
+
+impl<'a> WordIterator<'a> {
+ pub fn new(words: &'a str) -> Self {
+ WordIterator {
+ original: words,
+ }
+ }
+
+ const PUNCTUATION: [char; 5] = [',', '.', '!', '?', '-'];
+ fn is_separator(character: char) -> bool {
+ WordIterator::PUNCTUATION.contains(&character) ||
+ character.is_whitespace()
+ }
+
+ fn skip_while_nonalphabetic(&mut self) {
+ self.skip_while(|character| !character.is_alphabetic())
+ }
+
+ fn skip_while_not_separator(&mut self) {
+ self.skip_while(|character| !WordIterator::is_separator(character))
+ }
+
+ fn skip_while<F>(&mut self, closure: F) where F: Fn(char) -> bool {
+ if self.original.len() == 0 { return };
+
+ let mut index = 0;
+ for (current_index, character) in self.original.char_indices() {
+ if !closure(character) {
+ index = current_index;
+ break;
+ }
+ }
+
+ let (_, skipped_nonalpha) = self.original.split_at(index);
+ self.original = skipped_nonalpha;
+ }
+}
+
+impl<'a> Iterator for WordIterator<'a> {
+ type Item = String;
+
+ fn next(&mut self) -> Option<Self::Item> {
+ if self.original.len() == 0 { return None }
+
+ let mut index = 0;
+ let mut last_char = 0 as char;
+
+ self.skip_while_nonalphabetic();
+
+ for (current_index, character) in self.original.char_indices() {
+ last_char = character;
+ if !character.is_alphabetic() {
+ index = current_index;
+ break;
+ }
+ }
+
+ if index == 0 && !last_char.is_alphabetic() { return None };
+
+ if last_char.is_alphabetic() { index = self.original.len() }
+
+ let (result, skipped_word) = self.original.split_at(index);
+
+ self.original = skipped_word;
+ if WordIterator::is_separator(last_char) || skipped_word.is_empty() {
+ Some(String::from(result))
+ }
+ else {
+ self.skip_while_not_separator();
+ self.next()
+ }
+ }
+}
+
pub struct TextIndex {
index: HashSet<String>
}
impl TextIndex {
pub fn new() -> Self {
- Self {index: HashSet::new()}
+ Self { index: HashSet::new() }
}
pub fn push(&mut self, text: &str) {
self.index.insert(String::from(text));
}
pub fn search(&self, query: &str) -> HashSet<&str> {
let query_words = extract_words(query);
let mut result_set: HashSet<&str> = HashSet::new();
for word in query_words.iter() {
let lowercased_word = word.to_lowercase();
for sentence in &self.index {
let lowercased_sentence = sentence.to_lowercase();
if lowercased_sentence.contains(&lowercased_word) {
result_set.insert(sentence);
}
}
}
result_set
}
}

Хмм, две неща: WordIterator не би трябвало да връща String -- може да върне slice от подадения низ, вместо да прави нова алокация. Другото е, че пунктуацията не е нещо, описано в условието. Никой не е казал, че думите се разделят по пунктуация, просто се вземат поредица от поне-един азбучни символи и се връщат slice-ове към тях.

Впрочем, сега осъзнах какво си имал предвид относно думите с тирета. Валидно съображение, но за целите на задачата:

"Дума" дефинираме като поредица от символи, за които char::is_alphabetic връща истина.

Тоест, думите на "кой е по-по-най", ще са ["кой", "е", "по", "по", "най"]

Николай качи решение на 05.01.2018 13:38 (преди над 7 години)

-// Quite uglier than the previous solution
+// Changes from the lunch break
use std::collections::HashSet;
pub fn extract_words(str_slc: &str) -> Vec<String> {
::WordIterator::new(str_slc).collect()
}
pub struct WordIterator<'a> {
original: &'a str,
}
impl<'a> WordIterator<'a> {
pub fn new(words: &'a str) -> Self {
WordIterator {
original: words,
}
}
- const PUNCTUATION: [char; 5] = [',', '.', '!', '?', '-'];
- fn is_separator(character: char) -> bool {
- WordIterator::PUNCTUATION.contains(&character) ||
- character.is_whitespace()
- }
-
fn skip_while_nonalphabetic(&mut self) {
self.skip_while(|character| !character.is_alphabetic())
}
- fn skip_while_not_separator(&mut self) {
- self.skip_while(|character| !WordIterator::is_separator(character))
- }
-
fn skip_while<F>(&mut self, closure: F) where F: Fn(char) -> bool {
if self.original.len() == 0 { return };
let mut index = 0;
for (current_index, character) in self.original.char_indices() {
if !closure(character) {
index = current_index;
break;
}
}
let (_, skipped_nonalpha) = self.original.split_at(index);
self.original = skipped_nonalpha;
}
}
impl<'a> Iterator for WordIterator<'a> {
type Item = String;
fn next(&mut self) -> Option<Self::Item> {
if self.original.len() == 0 { return None }
let mut index = 0;
let mut last_char = 0 as char;
self.skip_while_nonalphabetic();
for (current_index, character) in self.original.char_indices() {
last_char = character;
if !character.is_alphabetic() {
index = current_index;
break;
}
}
if index == 0 && !last_char.is_alphabetic() { return None };
if last_char.is_alphabetic() { index = self.original.len() }
let (result, skipped_word) = self.original.split_at(index);
self.original = skipped_word;
- if WordIterator::is_separator(last_char) || skipped_word.is_empty() {
- Some(String::from(result))
- }
- else {
- self.skip_while_not_separator();
- self.next()
- }
+ Some(String::from(result))
}
}
pub struct TextIndex {
index: HashSet<String>
}
impl TextIndex {
pub fn new() -> Self {
Self { index: HashSet::new() }
}
pub fn push(&mut self, text: &str) {
self.index.insert(String::from(text));
}
pub fn search(&self, query: &str) -> HashSet<&str> {
let query_words = extract_words(query);
let mut result_set: HashSet<&str> = HashSet::new();
for word in query_words.iter() {
let lowercased_word = word.to_lowercase();
for sentence in &self.index {
let lowercased_sentence = sentence.to_lowercase();
if lowercased_sentence.contains(&lowercased_word) {
result_set.insert(sentence);
}
}
}
result_set
}
}