note description : "System's root class" author: "VT" class VT_TEST inherit ES_TEST create make feature -- Initialization make -- Creation procedure. do -- Test cases by V. Tzerpos all_expanded_tests all_reference_tests -- Test cases by G. Gotshalks all_make_tests all_height_tests all_insert_tests all_contains_tests all_count_tests all_precondition_tests -- Test cases by J. Ostroff add_boolean_case (agent test_insert_four_words) end test_insert_four_words: BOOLEAN local t: TRIE[CHARACTER] he, hers, his, she, hissing: LINKED_LIST[CHARACTER] do comment(" test_insert_four_words") create t.make he := stringToLL("he") hers := stringtoll ("hers") his := stringtoll ("his") she := stringtoll ("she") hissing := stringtoll ("hissing") create t.make t.insert(he) t.insert(hers) t.insert(his) t.insert(she) Result := t.contains (he) and t.contains(hers) and t.contains(his) and t.contains(she) check Result end Result := t.count = 4 and t.height = 5 check Result end Result := not t.contains(hissing) end all_expanded_tests -- Test cases using an expanded generic parameter (CHARACTER) do add_boolean_case (agent test_empty_trie) add_boolean_case (agent test_insert_one) add_boolean_case (agent test_insert_null) add_boolean_case (agent test_insert_one_and_null) add_boolean_case (agent test_insert_many) add_boolean_case (agent test_for_all_empty) add_boolean_case (agent test_for_all_true) add_boolean_case (agent test_for_all_false) add_boolean_case (agent test_for_all_one_true) add_boolean_case (agent test_for_all_one_false) add_boolean_case (agent test_exists_true) add_boolean_case (agent test_exists_false) add_boolean_case (agent test_exists_one_true) add_boolean_case (agent test_exists_one_false) add_boolean_case (agent test_exists_empty) add_boolean_case (agent test_exists1_true) add_boolean_case (agent test_exists1_false) add_boolean_case (agent test_exists1_one_true) add_boolean_case (agent test_exists1_one_false) add_boolean_case (agent test_exists1_empty) add_violation_case (agent test_insert_same_1) add_violation_case (agent test_insert_same_2) end all_reference_tests -- Test cases using an reference generic parameter (PERSON) do add_boolean_case (agent test_empty_trie_ref) add_boolean_case (agent test_insert_one_ref) add_boolean_case (agent test_insert_null_ref) add_boolean_case (agent test_insert_one_and_null_ref) add_boolean_case (agent test_insert_many_ref) add_boolean_case (agent test_for_all_empty_ref) add_boolean_case (agent test_for_all_true_ref) add_boolean_case (agent test_for_all_false_ref) add_boolean_case (agent test_for_all_one_true_ref) add_boolean_case (agent test_for_all_one_false_ref) add_boolean_case (agent test_exists_true_ref) add_boolean_case (agent test_exists_false_ref) add_boolean_case (agent test_exists_one_true_ref) add_boolean_case (agent test_exists_one_false_ref) add_boolean_case (agent test_exists_empty_ref) add_boolean_case (agent test_exists1_true_ref) add_boolean_case (agent test_exists1_false_ref) add_boolean_case (agent test_exists1_one_true_ref) add_boolean_case (agent test_exists1_one_false_ref) add_boolean_case (agent test_exists1_empty_ref) add_boolean_case (agent test_insert_same_1_ref) add_violation_case (agent test_insert_same_2_ref) end feature -- Expanded test cases test_empty_trie: BOOLEAN local t: TRIE[CHARACTER] do comment("Test an empty trie") create t.make Result := t.count = 0 and t.is_empty and t.height = 1 end test_insert_one: BOOLEAN local t: TRIE[CHARACTER] l: LINKED_LIST[CHARACTER] do comment("Test insert when adding one sequence") create t.make l := stringToLL("hi") t.insert(l) Result := t.count = 1 and not t.is_empty and t.height = 3 and t.contains(l) end test_insert_null: BOOLEAN local t: TRIE[CHARACTER] l: LINKED_LIST[CHARACTER] do comment("Test insert when adding one null sequence") create t.make l := stringToLL("") t.insert(l) Result := t.count = 1 and not t.is_empty and t.height = 1 and t.contains(l) end test_insert_one_and_null: BOOLEAN local t: TRIE[CHARACTER] l1, l2: LINKED_LIST[CHARACTER] do comment("Test insert when adding one sequence and then a null one") create t.make l1 := stringToLL("hi") t.insert(l1) l2 := stringToLL("") t.insert(l2) Result := t.count = 2 and not t.is_empty and t.height = 3 and t.contains(l1) and t.contains(l2) end test_insert_many: BOOLEAN local t: TRIE[CHARACTER] l1, l2, l3: LINKED_LIST[CHARACTER] do comment("Test insert when adding many sequences") create t.make l1 := stringToLL("hi") t.insert(l1) l2 := stringToLL("hello") t.insert(l2) Result := t.count = 2 and not t.is_empty and t.height = 6 and t.contains(l1) and t.contains(l2) l3 := stringToLL("hell") t.insert(l3) Result := Result and t.count = 3 and not t.is_empty and t.height = 6 and t.contains(l1) and t.contains(l2) and t.contains(l3) end test_for_all_true: BOOLEAN local t: TRIE[CHARACTER] do comment("Test for_all with expected true result") create t.make t.insert(stringToLL("hi")) t.insert(stringToLL("hello")) Result := t.for_all (agent startsWithH) end test_for_all_false: BOOLEAN local t: TRIE[CHARACTER] do comment("Test for_all with expected false result") create t.make t.insert(stringToLL("hi")) t.insert(stringToLL("yo")) Result := not t.for_all (agent startsWithH) end test_for_all_one_true: BOOLEAN local t: TRIE[CHARACTER] do comment("Test for_all with expected true result and only one sequence") create t.make t.insert(stringToLL("hello")) Result := t.for_all (agent startsWithH) end test_for_all_one_false: BOOLEAN local t: TRIE[CHARACTER] do comment("Test for_all with expected false result and only one sequence") create t.make t.insert(stringToLL("yo")) Result := not t.for_all (agent startsWithH) end test_for_all_empty: BOOLEAN local t: TRIE[CHARACTER] do comment("Test for_all with an empty trie") create t.make Result := t.for_all (agent startsWithH) end test_exists_true: BOOLEAN local t: TRIE[CHARACTER] do comment("Test exists with expected true result") create t.make t.insert(stringToLL("hi")) t.insert(stringToLL("hello")) Result := t.exists (agent startsWithH) end test_exists_false: BOOLEAN local t: TRIE[CHARACTER] do comment("Test exists with expected false result") create t.make t.insert(stringToLL("yo")) t.insert(stringToLL("cheers")) Result := not t.exists (agent startsWithH) end test_exists_one_true: BOOLEAN local t: TRIE[CHARACTER] do comment("Test exists with expected true result and only one sequence") create t.make t.insert(stringToLL("hi")) Result := t.exists (agent startsWithH) end test_exists_one_false: BOOLEAN local t: TRIE[CHARACTER] do comment("Test exists with expected false result and only one sequence") create t.make t.insert(stringToLL("cheers")) Result := not t.exists (agent startsWithH) end test_exists_empty: BOOLEAN local t: TRIE[CHARACTER] do comment("Test exists with an empty trie") create t.make Result := not t.exists (agent startsWithH) end test_exists1_true: BOOLEAN local t: TRIE[CHARACTER] do comment("Test exists1 with expected true result") create t.make t.insert(stringToLL("hi")) t.insert(stringToLL("cheers")) Result := t.exists1 (agent startsWithH) t.insert(stringToLL("yo")) t.insert(stringToLL("bye")) Result := Result and t.exists1 (agent startsWithH) end test_exists1_false: BOOLEAN local t: TRIE[CHARACTER] do comment("Test exists1 with expected false result") create t.make t.insert(stringToLL("yo")) t.insert(stringToLL("cheers")) Result := not t.exists1 (agent startsWithH) t.insert(stringToLL("hi")) t.insert(stringToLL("hello")) Result := Result and not t.exists1 (agent startsWithH) end test_exists1_one_true: BOOLEAN local t: TRIE[CHARACTER] do comment("Test exists1 with expected true result and only one sequence") create t.make t.insert(stringToLL("hi")) Result := t.exists1 (agent startsWithH) end test_exists1_one_false: BOOLEAN local t: TRIE[CHARACTER] do comment("Test exists1 with expected false result and only one sequence") create t.make t.insert(stringToLL("cheers")) Result := not t.exists1 (agent startsWithH) end test_exists1_empty: BOOLEAN local t: TRIE[CHARACTER] do comment("Test exists1 with an empty trie") create t.make Result := not t.exists1 (agent startsWithH) end test_insert_same_1 local t: TRIE[CHARACTER] do comment("Test that inserting a similar sequence twice causes a violation for expanded types") create t.make t.insert(stringToLL("hi")) t.insert(stringToLL("hi")) end test_insert_same_2 local t: TRIE[CHARACTER] l: LINKED_LIST[CHARACTER] do comment("Test that inserting the same sequence twice causes a violation for expanded types") create t.make l := stringToLL("hi") t.insert(l) t.insert(l) end feature -- Reference test cases test_empty_trie_ref: BOOLEAN local t: TRIE[PERSON] do comment("Test an empty trie for reference types") create t.make Result := t.count = 0 and t.is_empty and t.height = 1 end test_insert_one_ref: BOOLEAN local t: TRIE[PERSON] l: LINKED_LIST[PERSON] do comment("Test insert when adding one sequence for reference types") create t.make l := string_to_persons("hi") t.insert(l) Result := t.count = 1 and not t.is_empty and t.height = 3 and t.contains(l) end test_insert_null_ref: BOOLEAN local t: TRIE[PERSON] l: LINKED_LIST[PERSON] do comment("Test insert when adding one null sequence for reference types") create t.make l := string_to_persons("") t.insert(l) Result := t.count = 1 and not t.is_empty and t.height = 1 and t.contains(l) end test_insert_one_and_null_ref: BOOLEAN local t: TRIE[PERSON] l1, l2: LINKED_LIST[PERSON] do comment("Test insert when adding one sequence and then a null one for reference types") create t.make l1 := string_to_persons("hi") t.insert(l1) l2 := string_to_persons("") t.insert(l2) Result := t.count = 2 and not t.is_empty and t.height = 3 and t.contains(l1) and t.contains(l2) end test_insert_many_ref: BOOLEAN local t: TRIE[PERSON] l1, l2, l3: LINKED_LIST[PERSON] do comment("Test insert when adding many sequences for reference types") create t.make l1 := string_to_persons("hi") t.insert(l1) l2 := string_to_persons("hello") t.insert(l2) Result := t.count = 2 and not t.is_empty and t.height = 6 and t.contains(l1) and t.contains(l2) l3 := string_to_persons("hell") t.insert(l3) Result := Result and t.count = 3 and not t.is_empty and t.height = 6 and t.contains(l1) and t.contains(l2) and t.contains(l3) end test_for_all_true_ref: BOOLEAN local t: TRIE[PERSON] do comment("Test for_all with expected true result for reference types") create t.make t.insert(string_to_persons("hi")) t.insert(string_to_persons("hello")) Result := t.for_all (agent first_person_is_h) end test_for_all_false_ref: BOOLEAN local t: TRIE[PERSON] do comment("Test for_all with expected false result for reference types") create t.make t.insert(string_to_persons("hi")) t.insert(string_to_persons("yo")) Result := not t.for_all (agent first_person_is_h) end test_for_all_one_true_ref: BOOLEAN local t: TRIE[PERSON] do comment("Test for_all with expected true result and only one sequence for reference types") create t.make t.insert(string_to_persons("hello")) Result := t.for_all (agent first_person_is_h) end test_for_all_one_false_ref: BOOLEAN local t: TRIE[PERSON] do comment("Test for_all with expected false result and only one sequence for reference types") create t.make t.insert(string_to_persons("yo")) Result := not t.for_all (agent first_person_is_h) end test_for_all_empty_ref: BOOLEAN local t: TRIE[PERSON] do comment("Test for_all with an empty trie for reference types") create t.make Result := t.for_all (agent first_person_is_h) end test_exists_true_ref: BOOLEAN local t: TRIE[PERSON] do comment("Test exists with expected true result for reference types") create t.make t.insert(string_to_persons("hi")) t.insert(string_to_persons("hello")) Result := t.exists (agent first_person_is_h) end test_exists_false_ref: BOOLEAN local t: TRIE[PERSON] do comment("Test exists with expected false result for reference types") create t.make t.insert(string_to_persons("yo")) t.insert(string_to_persons("cheers")) Result := not t.exists (agent first_person_is_h) end test_exists_one_true_ref: BOOLEAN local t: TRIE[PERSON] do comment("Test exists with expected true result and only one sequence for reference types") create t.make t.insert(string_to_persons("hi")) Result := t.exists (agent first_person_is_h) end test_exists_one_false_ref: BOOLEAN local t: TRIE[PERSON] do comment("Test exists with expected false result and only one sequence for reference types") create t.make t.insert(string_to_persons("cheers")) Result := not t.exists (agent first_person_is_h) end test_exists_empty_ref: BOOLEAN local t: TRIE[PERSON] do comment("Test exists with an empty trie for reference types") create t.make Result := not t.exists (agent first_person_is_h) end test_exists1_true_ref: BOOLEAN local t: TRIE[PERSON] do comment("Test exists1 with expected true result for reference types") create t.make t.insert(string_to_persons("hi")) t.insert(string_to_persons("cheers")) Result := t.exists1 (agent first_person_is_h) t.insert(string_to_persons("yo")) t.insert(string_to_persons("bye")) Result := Result and t.exists1 (agent first_person_is_h) end test_exists1_false_ref: BOOLEAN local t: TRIE[PERSON] do comment("Test exists1 with expected false result for reference types") create t.make t.insert(string_to_persons("yo")) t.insert(string_to_persons("cheers")) Result := not t.exists1 (agent first_person_is_h) t.insert(string_to_persons("hi")) t.insert(string_to_persons("hello")) Result := Result and not t.exists1 (agent first_person_is_h) end test_exists1_one_true_ref: BOOLEAN local t: TRIE[PERSON] do comment("Test exists1 with expected true result and only one sequence for reference types") create t.make t.insert(string_to_persons("hi")) Result := t.exists1 (agent first_person_is_h) end test_exists1_one_false_ref: BOOLEAN local t: TRIE[PERSON] do comment("Test exists1 with expected false result and only one sequence for reference types") create t.make t.insert(string_to_persons("cheers")) Result := not t.exists1 (agent first_person_is_h) end test_exists1_empty_ref: BOOLEAN local t: TRIE[PERSON] do comment("Test exists1 with an empty trie for reference types") create t.make Result := not t.exists1 (agent first_person_is_h) end test_insert_same_1_ref: BOOLEAN local t: TRIE[PERSON] l1, l2: LINKED_LIST[PERSON] do comment("Test that inserting a sequence with similar objects twice is OK for reference types") create t.make l1 := string_to_persons("hi") l2 := string_to_persons("hi") t.insert(l1) t.insert(l2) Result := t.count = 2 and not t.is_empty and t.height = 3 and t.contains(l1) and t.contains(l2) end test_insert_same_2_ref local t: TRIE[PERSON] l: LINKED_LIST[PERSON] do comment("Test that inserting the same sequence twice causes a violation for reference types") create t.make l := string_to_persons("hi") t.insert(l) t.insert(l) end feature -- Gunnar tests all_make_tests -- Collection of all make tests do add_boolean_case (agent empty_trie_is_empty) add_boolean_case (agent empty_trie_count) add_boolean_case (agent empty_trie_height) end empty_trie_is_empty: BOOLEAN local t: TRIE[CHARACTER] do comment("Empty trie is empty") create t.make Result := t.is_empty end empty_trie_count: BOOLEAN local t: TRIE[CHARACTER] do comment("Empty trie count is 0") create t.make Result := t.count = 0 end empty_trie_height: BOOLEAN local t: TRIE[CHARACTER] do comment("Empty trie height is 1") create t.make Result := t.height = 1 end --============================================================= feature -- Insert all_insert_tests -- Collect all insert cases together do add_boolean_case (agent insert_null) add_boolean_case (agent insert_1_ln_1) add_boolean_case (agent insert_1_ln_1_null) add_boolean_case (agent insert_3_ln_1) add_boolean_case (agent insert_1_ln_q) add_boolean_case (agent insert_3_ln_q_diff) add_boolean_case (agent insert_3_ln_q_sub_1st) add_boolean_case (agent insert_3_ln_q_ext_1st) add_boolean_case (agent insert_3_ln_q_split_1st) end insert_null : BOOLEAN -- Insert just the null sequence local t : TRIE[CHARACTER] do comment("Insert null sequence") create t.make t.insert(stringToLL("")) Result := t.terminal and t.ll.count = 0 end insert_1_ln_1 : BOOLEAN -- Insert one length 1 sequence local t : TRIE[CHARACTER] t1 : TRIE[CHARACTER] do comment("Insert 1 length 1 sequence") create t.make t.insert(stringToLL("a")) t1 := t.ll.first Result := not t.terminal and t.ll.count = 1 and check_trie_node(t1,'a',True,0) end insert_1_ln_1_null : BOOLEAN -- Insert null sequence after inserting 1 length 1 sequence local t : TRIE[CHARACTER] t1 : TRIE[CHARACTER] do comment("Insert null after inserting 1 length 1 sequence") create t.make t.insert(stringToLL("a")) t.insert(stringToLL("")) t1 := t.ll.first Result := t.terminal and t.ll.count = 1 and check_trie_node(t1,'a',True,0) end insert_3_ln_1 : BOOLEAN -- Insert 3 length 1 sequences local t : TRIE[CHARACTER] l : LINKED_LIST[TRIE[CHARACTER]] do comment("Insert 3 length 1 sequences") create t.make t.insert(stringToLL("a")) t.insert(stringToLL("b")) t.insert(stringToLL("c")) Result := not t.terminal and t.ll.count = 3 l := t.ll l.start t := l.item l.forth Result := Result and check_trie_node(t,'a',True,0) t := l.item l.forth Result := Result and check_trie_node(t,'b',True,0) t := l.item l.forth Result := Result and check_trie_node(t,'c',True,0) end insert_1_ln_q : BOOLEAN -- Insert 1 length many sequence local t : TRIE[CHARACTER] do comment("Insert 1 length many sequence") create t.make t.insert(stringToLL("abc")) Result := not t.terminal and t.ll.count = 1 t := t.ll.first Result := Result and check_trie_node(t,'a',False,1) t := t.ll.first Result := Result and check_trie_node(t,'b',False,1) t := t.ll.first Result := Result and check_trie_node(t,'c',True,0) end insert_3_ln_q_diff : BOOLEAN -- Insert 3 length many sequences with no overlap first string local t : TRIE[CHARACTER] t1 : TRIE[CHARACTER] l : LINKED_LIST[TRIE[CHARACTER]] do comment ("Insert 3 different length many strings") create t.make t.insert(stringToLL("abc")) t.insert(stringToLL("def")) t.insert(stringToLL("ghi")) Result := not t.terminal and t.ll.count = 3 l := t.ll l.start t := l.item l.forth Result := Result and check_trie_node(t,'a',False,1) t1 := t.ll.first Result := Result and check_trie_node(t1,'b',False,1) t1 := t1.ll.first Result := Result and check_trie_node(t1,'c',True,0) t := l.item l.forth Result := Result and check_trie_node(t,'d',False,1) t1 := t.ll.first Result := Result and check_trie_node(t1,'e',False,1) t1 := t1.ll.first Result := Result and check_trie_node(t1,'f',True,0) t := l.item l.forth Result := Result and check_trie_node(t,'g',False,1) t1 := t.ll.first Result := Result and check_trie_node(t1,'h',False,1) t1 := t1.ll.first Result := Result and check_trie_node(t1,'i',True,0) end insert_3_ln_q_sub_1st : BOOLEAN -- Insert 3 length many sequences first two no overlap -- third string is substring of first string local t : TRIE[CHARACTER] t1 : TRIE[CHARACTER] l : LINKED_LIST[TRIE[CHARACTER]] do comment("Insert 3 length many, 2 no overlap, 1 subseq of 1st") create t.make t.insert(stringToLL("abc")) t.insert(stringToLL("def")) t.insert(stringToLL("ab")) Result := not t.terminal and t.ll.count = 2 l := t.ll l.start t := l.item l.forth Result := Result and check_trie_node(t,'a',False,1) check a_after: Result end t1 := t.ll.first Result := Result and check_trie_node(t1,'b',True,1) check b_after: Result end t1 := t1.ll.first Result := Result and check_trie_node(t1,'c',True,0) check c_after: Result end t := l.item l.forth Result := Result and check_trie_node(t,'d',False,1) t1 := t.ll.first Result := Result and check_trie_node(t1,'e',False,1) t1 := t1.ll.first Result := Result and check_trie_node(t1,'f',True,0) end insert_3_ln_q_ext_1st : BOOLEAN -- Insert 3 length many sequences first no overlap -- third string is an extention of first string local t : TRIE[CHARACTER] t1 : TRIE[CHARACTER] l : LINKED_LIST[TRIE[CHARACTER]] do comment("Insert 3 length many, 2 no overlap, 1 extension of 1st") create t.make t.insert(stringToLL("abc")) t.insert(stringToLL("def")) t.insert(stringToLL("abcd")) Result := not t.terminal and t.ll.count = 2 l := t.ll l.start t := l.item l.forth Result := Result and check_trie_node(t,'a',False,1) t1 := t.ll.first Result := Result and check_trie_node(t1,'b',False,1) t1 := t1.ll.first Result := Result and check_trie_node(t1,'c',True,1) t1 := t1.ll.first Result := Result and check_trie_node(t1,'d',True,0) t := l.item l.forth Result := Result and check_trie_node(t,'d',False,1) t1 := t.ll.first Result := Result and check_trie_node(t1,'e',False,1) t1 := t1.ll.first Result := Result and check_trie_node(t1,'f',True,0) end insert_3_ln_q_split_1st : BOOLEAN -- Insert 3 length many sequences first no overlap -- third string splits off at second char of first string local t : TRIE[CHARACTER] t1 : TRIE[CHARACTER] l : LINKED_LIST[TRIE[CHARACTER]] l1 : LINKED_LIST[TRIE[CHARACTER]] do comment("Insert 3 length many, 2 no overlap, 1 split of 1st") create t.make t.insert(stringToLL("abc")) t.insert(stringToLL("def")) t.insert(stringToLL("abd")) Result := not t.terminal and t.ll.count = 2 l := t.ll l.start t := l.item l.forth Result := Result and check_trie_node(t,'a',False,1) t1 := t.ll.first Result := Result and check_trie_node(t1,'b',False,2) l1 := t1.ll l1.start t1 := l1.item l1.forth Result := Result and check_trie_node(t1,'c',True,0) t1 := l1.item Result := Result and check_trie_node(t1,'d',True,0) t := l.item l.forth Result := Result and check_trie_node(t,'d',False,1) t1 := t.ll.first Result := Result and check_trie_node(t1,'e',False,1) t1 := t1.ll.first Result := Result and check_trie_node(t1,'f',True,0) end --============================================================= feature -- Contains -- Tests for contains and precondition are similar so we use the same -- cases. all_contains_tests -- Collect all contains cases do add_boolean_case (agent contains_null_1_1n_0_seq) add_boolean_case (agent contains_null_1_ln_1_seq) add_boolean_case (agent contains_null_p_ln_1_seq) add_boolean_case (agent contains_null_1_ln_q_seq) add_boolean_case (agent contains_null_p_ln_q__seq) add_boolean_case (agent contains_ln_1_1_ln_1_seq) add_boolean_case (agent contains_ln_1_1st_of_n_ln_1_seq) add_boolean_case (agent contains_ln_1_mid_of_n_ln_1_seq) add_boolean_case (agent contains_ln_1_last_of_n_ln_1_seq) add_boolean_case (agent contains_ln_1_in_1_ln_q_seq) add_boolean_case (agent contains_ln_1_in_1st_of_p_ln_q_seq) add_boolean_case (agent contains_ln_1_in_mid_of_p_ln_q_seq) add_boolean_case (agent contains_ln_1_in_last_of_p_ln_q_seq) add_boolean_case (agent contains_ln_q_in_1_ln_q_seq_same) add_boolean_case (agent contains_ln_q_in_1_ln_q_seq_longer) add_boolean_case (agent contains_ln_q_in_mid_of_p_ln_q_seq_same) add_boolean_case (agent contains_ln_q_in_mid_of_p_ln_q_seq_longer) add_boolean_case (agent contains_ln_q_in_last_of_p_ln_q_seq_same) add_boolean_case (agent contains_ln_q_in_last_of_p_ln_q_seq_longer) end contains_null_1_1n_0_seq : BOOLEAN local t: TRIE[CHARACTER] do comment("Contains null with only null sequence") create t.make t.insert(stringToLL("")) Result := t.contains(stringToLL("")) end contains_null_1_ln_1_seq : BOOLEAN local t: TRIE[CHARACTER] do comment("Contains null with 1 length 1 sequence") create t.make t.insert(stringToLL("a")) t.insert(stringToLL("")) Result := t.contains(stringToLL("")) end contains_null_p_ln_1_seq : BOOLEAN local t: TRIE[CHARACTER] do comment("Contains null with many length 1 sequences") t := create_many_ln_1_seq_char t.insert(stringToLL("")) Result := t.contains(stringToLL("")) end contains_null_1_ln_q_seq : BOOLEAN local t: TRIE[CHARACTER] do comment("Contains null with one length many sequence") create t.make t.insert(stringToLL("abcde")) t.insert(stringToLL("")) Result := t.contains(stringToLL("")) end contains_null_p_ln_q__seq : BOOLEAN local t: TRIE[CHARACTER] do comment("Contains null with many length many sequence") t := create_many_ln_q_seq_char t.insert(stringToLL("")) Result := t.contains(stringToLL("")) end contains_ln_1_1_ln_1_seq : BOOLEAN local t: TRIE[CHARACTER] do comment("Contains length 1 sequence with one length 1 sequences") create t.make t.insert(stringToLL("a")) Result := t.contains(stringToLL("a")) end contains_ln_1_1st_of_n_ln_1_seq : BOOLEAN local t: TRIE[CHARACTER] do comment("Contains length 1 as first of many length 1 sequences") t := create_many_ln_1_seq_char Result := t.contains(stringToLL("a")) end contains_ln_1_mid_of_n_ln_1_seq : BOOLEAN local t: TRIE[CHARACTER] do comment("Contains length 1 sequence as middle of many length 1 sequences") t := create_many_ln_1_seq_char Result := t.contains(stringToLL("c")) end contains_ln_1_last_of_n_ln_1_seq : BOOLEAN local t: TRIE[CHARACTER] do comment("Contains length 1 sequence as last of many length 1 sequences") t := create_many_ln_1_seq_char Result := t.contains(stringToLL("e")) end contains_ln_1_in_1_ln_q_seq : BOOLEAN local t: TRIE[CHARACTER] do comment("Contains length 1 sequence with 1 length many sequence") create t.make t.insert(stringToLL("abcde")) t.insert(stringToLL("a")) Result := t.contains(stringToLL("a")) end contains_ln_1_in_1st_of_p_ln_q_seq : BOOLEAN local t: TRIE[CHARACTER] do comment("Contains length 1 sequence in first of many length many sequences") t := create_many_ln_q_seq_char Result := t.contains(stringToLL("a")) end contains_ln_1_in_mid_of_p_ln_q_seq : BOOLEAN local t: TRIE[CHARACTER] do comment("Contains length 1 sequence in middle of many length many sequences") t := create_many_ln_q_seq_char Result := t.contains(stringToLL("c")) end contains_ln_1_in_last_of_p_ln_q_seq : BOOLEAN local t: TRIE[CHARACTER] do comment("Contains length 1 sequence in last of many length many sequences") t := create_many_ln_q_seq_char Result := t.contains(stringToLL("e")) end contains_ln_q_in_1_ln_q_seq_same : BOOLEAN local t: TRIE[CHARACTER] do comment("Contains ln many seq with 1 length many seq same length") create t.make t.insert(stringToLL("abcde")) Result := t.contains(stringToLL("abcde")) end contains_ln_q_in_1_ln_q_seq_longer : BOOLEAN local t: TRIE[CHARACTER] do comment("Contains ln many seq with 1 length many seq longer") create t.make t.insert(stringToLL("abcde")) t.insert(stringToLL("abc")) Result := t.contains(stringToLL("abc")) end contains_ln_q_in_first_ln_q_seq_same : BOOLEAN local t: TRIE[CHARACTER] do comment("Contains ln many seq in first of many length many seq same length") t := create_many_ln_q_seq_char Result := t.contains(stringToLL("abcde")) end contains_ln_q_in_first_ln_q_seq_longer : BOOLEAN local t: TRIE[CHARACTER] do comment("Contains ln many seq in first of many length many seq longer") t := create_many_ln_q_seq_char Result := t.contains(stringToLL("abc")) end contains_ln_q_in_mid_of_p_ln_q_seq_same : BOOLEAN local t: TRIE[CHARACTER] do comment("Contains ln many seq in middle of many length many seq same length") t := create_many_ln_q_seq_char Result := t.contains(stringToLL("cdefgh")) end contains_ln_q_in_mid_of_p_ln_q_seq_longer : BOOLEAN local t: TRIE[CHARACTER] do comment("Contains ln many seq in middle of many length many seq longer") t := create_many_ln_q_seq_char Result := t.contains(stringToLL("cde")) end contains_ln_q_in_last_of_p_ln_q_seq_same : BOOLEAN local t: TRIE[CHARACTER] do comment("Contains ln many seq in last of many length many seq same length") t := create_many_ln_q_seq_char Result := t.contains(stringToLL("efghijk")) end contains_ln_q_in_last_of_p_ln_q_seq_longer : BOOLEAN local t: TRIE[CHARACTER] do comment("Contains ln many seq in last of many length many seq longer") t := create_many_ln_q_seq_char Result := t.contains(stringToLL("efgh")) end --============================================================= feature -- Count all_count_tests -- Collect all count cases together do add_boolean_case (agent count_empty) add_boolean_case (agent count_null) add_boolean_case (agent count_1_ln_1) add_boolean_case (agent count_1_ln_1_null) add_boolean_case (agent count_3_ln_1) add_boolean_case (agent count_1_ln_q) add_boolean_case (agent count_3_ln_q_diff) add_boolean_case (agent count_3_ln_q_sub_1st) add_boolean_case (agent count_3_ln_q_ext_1st) add_boolean_case (agent count_3_ln_q_split_1st) add_boolean_case (agent count_create_many_ln_1) add_boolean_case (agent count_create_many_ln_q) end count_empty : BOOLEAN -- Count for an empty tree local t : TRIE[CHARACTER] do comment ("Count for an empty tree") create t.make Result := t.count = 0 end count_null : BOOLEAN -- Count just the null sequence local t : TRIE[CHARACTER] do comment("Count null sequence") create t.make t.insert(stringToLL("")) Result := t.count = 1 end count_1_ln_1 : BOOLEAN -- Count one length 1 sequence local t : TRIE[CHARACTER] do comment("Count 1 length 1 sequence") create t.make t.insert(stringToLL("a")) Result := t.count = 1 end count_1_ln_1_null : BOOLEAN -- Count null sequence after inserting 1 length 1 sequence local t : TRIE[CHARACTER] do comment("Count null after inserting 1 length 1 sequence") create t.make t.insert(stringToLL("a")) t.insert(stringToLL("")) Result := t.count = 2 end count_3_ln_1 : BOOLEAN -- Count 3 length 1 sequences local t : TRIE[CHARACTER] do comment("Count 3 length 1 sequences") create t.make t.insert(stringToLL("a")) t.insert(stringToLL("b")) t.insert(stringToLL("c")) Result := t.count = 3 end count_1_ln_q : BOOLEAN -- Count 1 length many sequence local t : TRIE[CHARACTER] do comment("Count 1 length many sequence") create t.make t.insert(stringToLL("abc")) Result := t.count = 1 end count_3_ln_q_diff : BOOLEAN -- Count 3 length many sequences with no overlap first string local t : TRIE[CHARACTER] do comment ("Count 3 different length many strings") create t.make t.insert(stringToLL("abc")) t.insert(stringToLL("def")) t.insert(stringToLL("ghi")) Result := t.count = 3 end count_3_ln_q_sub_1st : BOOLEAN -- Count 3 length many sequences first two no overlap -- third string is substring of first string local t : TRIE[CHARACTER] do comment("Count 3 length many, 2 no overlap, 1 subseq of 1st") create t.make t.insert(stringToLL("abc")) t.insert(stringToLL("def")) t.insert(stringToLL("ab")) Result := t.count = 3 end count_3_ln_q_ext_1st : BOOLEAN -- Count 3 length many sequences first no overlap -- third string is an extention of first string local t : TRIE[CHARACTER] do comment("Count 3 length many, 2 no overlap, 1 extension of 1st") create t.make t.insert(stringToLL("abc")) t.insert(stringToLL("def")) t.insert(stringToLL("abcd")) Result := t.count = 3 end count_3_ln_q_split_1st : BOOLEAN -- Count 3 length many sequences first no overlap -- third string splits off at second char of first string local t : TRIE[CHARACTER] do comment("Count 3 length many, 2 no overlap, 1 split of 1st") create t.make t.insert(stringToLL("abc")) t.insert(stringToLL("def")) t.insert(stringToLL("abd")) Result := t.count = 3 end count_create_many_ln_1 : BOOLEAN -- Count many length 1 sequences local t : TRIE[CHARACTER] do comment("Count for create many length 1 function") t := create_many_ln_1_seq_char Result := t.count = 5 end count_create_many_ln_q : BOOLEAN -- Count 3 length many sequences first no overlap -- third string splits off at second char of first string local t : TRIE[CHARACTER] do comment("Count for create many length q function") t := create_many_ln_q_seq_char Result := t.count = 11 end --============================================================= feature -- Height all_height_tests -- Collect all height cases together do add_boolean_case (agent height_empty) add_boolean_case (agent height_null) add_boolean_case (agent height_1_ln_1) add_boolean_case (agent height_create_many_ln_1) add_boolean_case (agent height_1_ln_q) add_boolean_case (agent height_3_ln_q_first_long) add_boolean_case (agent height_3_ln_q_mid_long) add_boolean_case (agent height_3_ln_q_1ast_long) add_boolean_case (agent height_3_ln_q_sub_1st) add_boolean_case (agent height_3_ln_q_ext_1st) add_boolean_case (agent height_3_ln_q_split_1st) add_boolean_case (agent height_create_many_ln_q) end height_empty : BOOLEAN -- Height for an empty tree local t : TRIE[CHARACTER] do comment ("Height for an empty tree") create t.make Result := t.height = 1 end height_null : BOOLEAN -- Height just the null sequence local t : TRIE[CHARACTER] do comment("Height null sequence") create t.make t.insert(stringToLL("")) Result := t.height = 1 end height_1_ln_1 : BOOLEAN -- Height one length 1 sequence local t : TRIE[CHARACTER] do comment("Height 1 length 1 sequence") create t.make t.insert(stringToLL("a")) Result := t.height = 2 end height_create_many_ln_1 : BOOLEAN -- Height many length 1 sequences local t : TRIE[CHARACTER] do comment("Height for create many length 1 function") t := create_many_ln_1_seq_char Result := t.height = 2 end height_1_ln_q : BOOLEAN -- Height 1 length many sequence local t : TRIE[CHARACTER] do comment("Height 1 length many sequence") create t.make t.insert(stringToLL("abc")) Result := t.height = 4 end height_3_ln_q_first_long : BOOLEAN -- Height 3 length many sequences with no overlap first string local t : TRIE[CHARACTER] do comment ("Height 3 different length many strings") create t.make t.insert(stringToLL("abcdef")) t.insert(stringToLL("defg")) t.insert(stringToLL("ghi")) Result := t.height = 7 end height_3_ln_q_mid_long : BOOLEAN -- Height 3 length many sequences with no overlap first string local t : TRIE[CHARACTER] do comment ("Height 3 different length many strings") create t.make t.insert(stringToLL("abc")) t.insert(stringToLL("defg")) t.insert(stringToLL("ghi")) Result := t.height = 5 end height_3_ln_q_1ast_long : BOOLEAN -- Height 3 length many sequences with no overlap first string local t : TRIE[CHARACTER] do comment ("Height 3 different length many strings") create t.make t.insert(stringToLL("abc")) t.insert(stringToLL("defg")) t.insert(stringToLL("ghijkl")) Result := t.height = 7 end height_3_ln_q_sub_1st : BOOLEAN -- Height 3 length many sequences first two no overlap -- third string is substring of first string local t : TRIE[CHARACTER] do comment("Height 3 length many, 2 no overlap, 1 subseq of 1st") create t.make t.insert(stringToLL("abc")) t.insert(stringToLL("def")) t.insert(stringToLL("ab")) Result := t.height = 4 end height_3_ln_q_ext_1st : BOOLEAN -- Height 3 length many sequences first no overlap -- third string is an extention of first string local t : TRIE[CHARACTER] do comment("Height 3 length many, 2 no overlap, 1 extension of 1st") create t.make t.insert(stringToLL("abc")) t.insert(stringToLL("def")) t.insert(stringToLL("abcd")) Result := t.height = 5 end height_3_ln_q_split_1st : BOOLEAN -- Height 3 length many sequences first no overlap -- third string splits off at second char of first string local t : TRIE[CHARACTER] do comment("Height 3 length many, 2 no overlap, 1 split of 1st") create t.make t.insert(stringToLL("abc")) t.insert(stringToLL("def")) t.insert(stringToLL("abd")) Result := t.height = 4 end height_create_many_ln_q : BOOLEAN -- Height 3 length many sequences first no overlap -- third string splits off at second char of first string local t : TRIE[CHARACTER] do comment("Height for create many length q function") t := create_many_ln_q_seq_char Result := t.height = 8 end --============================================================= feature -- Precondition tests -- It may appear that only one test is required for insert precondition -- since it is "not contains", so if contains is tested first, then any -- test that detects duplicates would be valid. A problem occurs if -- someone changes the requires clause. -- Tests for contains and precondition are similar so we use the same -- cases. all_precondition_tests -- Collect all precondition cases together -- Simiplifies commenting out during development do add_violation_case (agent insert_dup_null_1_1n_0_seq) add_violation_case (agent insert_dup_null_1_ln_1_seq) add_violation_case (agent insert_dup_null_p_ln_1_seq) add_violation_case (agent insert_dup_null_1_ln_q_seq) add_violation_case (agent insert_dup_null_p_ln_q__seq) add_violation_case (agent insert_dup_ln_1_1_ln_1_seq) add_violation_case (agent insert_dup_ln_1_1st_of_n_ln_1_seq) add_violation_case (agent insert_dup_ln_1_mid_of_n_ln_1_seq) add_violation_case (agent insert_dup_ln_1_last_of_n_ln_1_seq) add_violation_case (agent insert_dup_ln_1_in_1_ln_q_seq) add_violation_case (agent insert_dup_ln_1_in_1st_of_p_ln_q_seq) add_violation_case (agent insert_dup_ln_1_in_mid_of_p_ln_q_seq) add_violation_case (agent insert_dup_ln_1_in_last_of_p_ln_q_seq) add_violation_case (agent insert_dup_ln_q_in_1_ln_q_seq_same) add_violation_case (agent insert_dup_ln_q_in_1_ln_q_seq_longer) add_violation_case (agent insert_dup_ln_q_in_mid_of_p_ln_q_seq_same) add_violation_case (agent insert_dup_ln_q_in_mid_of_p_ln_q_seq_longer) add_violation_case (agent insert_dup_ln_q_in_last_of_p_ln_q_seq_same) add_violation_case (agent insert_dup_ln_q_in_last_of_p_ln_q_seq_longer) end insert_dup_null_1_1n_0_seq local t: TRIE[CHARACTER] do comment("Duplicate null with only null sequence") create t.make t.insert(stringToLL("")) t.insert(stringToLL("")) end insert_dup_null_1_ln_1_seq local t: TRIE[CHARACTER] do comment("Duplicate null with 1 length 1 sequence") create t.make t.insert(stringToLL("a")) t.insert(stringToLL("")) t.insert(stringToLL("")) end insert_dup_null_p_ln_1_seq local t: TRIE[CHARACTER] do comment("Duplicate null with many length 1 sequences") t := create_many_ln_1_seq_char t.insert(stringToLL("")) t.insert(stringToLL("")) end insert_dup_null_1_ln_q_seq local t: TRIE[CHARACTER] do comment("Duplicate null with one length many sequence") create t.make t.insert(stringToLL("abcde")) t.insert(stringToLL("")) t.insert(stringToLL("")) end insert_dup_null_p_ln_q__seq local t: TRIE[CHARACTER] do comment("Duplicate null with many length many sequence") t := create_many_ln_q_seq_char t.insert(stringToLL("")) t.insert(stringToLL("")) end insert_dup_ln_1_1_ln_1_seq local t: TRIE[CHARACTER] do comment("Duplicate length 1 sequence with one length 1 sequences") create t.make t.insert(stringToLL("a")) t.insert(stringToLL("a")) end insert_dup_ln_1_1st_of_n_ln_1_seq local t: TRIE[CHARACTER] do comment("Duplicate length 1 as first of many length 1 sequences") t := create_many_ln_1_seq_char t.insert(stringToLL("a")) end insert_dup_ln_1_mid_of_n_ln_1_seq local t: TRIE[CHARACTER] do comment("Duplicate length 1 sequence as middle of many length 1 sequences") t := create_many_ln_1_seq_char t.insert(stringToLL("c")) end insert_dup_ln_1_last_of_n_ln_1_seq local t: TRIE[CHARACTER] do comment("Duplicate length 1 sequence as last of many length 1 sequences") t := create_many_ln_1_seq_char t.insert(stringToLL("e")) end insert_dup_ln_1_in_1_ln_q_seq local t: TRIE[CHARACTER] do comment("Duplicate length 1 sequence with 1 length many sequence") create t.make t.insert(stringToLL("abcde")) t.insert(stringToLL("a")) t.insert(stringToLL("a")) end insert_dup_ln_1_in_1st_of_p_ln_q_seq local t: TRIE[CHARACTER] do comment("Duplicate length 1 sequence in first of many length many sequences") t := create_many_ln_q_seq_char t.insert(stringToLL("a")) end insert_dup_ln_1_in_mid_of_p_ln_q_seq local t: TRIE[CHARACTER] do comment("Duplicate length 1 sequence in middle of many length many sequences") t := create_many_ln_q_seq_char t.insert(stringToLL("c")) end insert_dup_ln_1_in_last_of_p_ln_q_seq local t: TRIE[CHARACTER] do comment("Duplicate length 1 sequence in last of many length many sequences") t := create_many_ln_q_seq_char t.insert(stringToLL("e")) end insert_dup_ln_q_in_1_ln_q_seq_same local t: TRIE[CHARACTER] do comment("Dup length many seq with 1 length many seq same length") create t.make t.insert(stringToLL("abcde")) t.insert(stringToLL("abcde")) end insert_dup_ln_q_in_1_ln_q_seq_longer local t: TRIE[CHARACTER] do comment("Dup length many seq with 1 length many seq longer") create t.make t.insert(stringToLL("abcde")) t.insert(stringToLL("abc")) t.insert(stringToLL("abc")) end insert_dup_ln_q_in_first_ln_q_seq_same local t: TRIE[CHARACTER] do comment("Dup length many seq in first of many length many seq same length") t := create_many_ln_q_seq_char t.insert(stringToLL("abcde")) end insert_dup_ln_q_in_first_ln_q_seq_longer local t: TRIE[CHARACTER] do comment("Dup length many seq in first of many length many seq longer") t := create_many_ln_q_seq_char t.insert(stringToLL("abc")) end insert_dup_ln_q_in_mid_of_p_ln_q_seq_same local t: TRIE[CHARACTER] do comment("Dup length many seq in middle of many length many seq same length") t := create_many_ln_q_seq_char t.insert(stringToLL("cdefgh")) end insert_dup_ln_q_in_mid_of_p_ln_q_seq_longer local t: TRIE[CHARACTER] do comment("Dup length many seq in middle of many length many seq longer") t := create_many_ln_q_seq_char t.insert(stringToLL("cde")) end insert_dup_ln_q_in_last_of_p_ln_q_seq_same local t: TRIE[CHARACTER] do comment("Dup length many seq in last of many length many seq same length") t := create_many_ln_q_seq_char t.insert(stringToLL("efghijk")) end insert_dup_ln_q_in_last_of_p_ln_q_seq_longer local t: TRIE[CHARACTER] do comment("Dup length many seq in last of many length many seq longer") t := create_many_ln_q_seq_char t.insert(stringToLL("efgh")) end --============================================================= feature -- Support stringtoLL (s: STRING): LINKED_LIST[CHARACTER] -- Transform a string into a linked list of characters local i: INTEGER do create Result.make from i := 1 invariant Result.count = i - 1 Result.count <= s.count until i > s.count loop Result.extend(s.item(i)) i := i + 1 variant s.count - i + 1 end end string_to_persons (s: STRING): LINKED_LIST[PERSON] -- Transform a string into a linked list of PERSON objects local i: INTEGER p: PERSON do create Result.make from i := 1 invariant Result.count = i - 1 Result.count <= s.count until i > s.count loop create p.make(s.substring(i,i),66) Result.extend(p) i := i + 1 variant s.count - i + 1 end end startsWithH(seq:LINKED_LIST[CHARACTER]):BOOLEAN do if not seq.is_empty then Result := seq.first = 'h' end end first_person_is_h(seq:LINKED_LIST[PERSON]):BOOLEAN do if not seq.is_empty then Result := seq.first.name.is_equal("h") end end create_many_ln_1_seq_char : TRIE[CHARACTER] -- Create TRIE with many length 1 sequences do create Result.make Result.insert(stringtoLL("a")) Result.insert(stringtoLL("b")) Result.insert(stringtoLL("c")) Result.insert(stringtoLL("d")) Result.insert(stringtoLL("e")) end create_many_ln_q_seq_char : TRIE[CHARACTER] -- Create TRIE with many length 1 sequences do create Result.make Result.insert(stringtoLL("abcde")) Result.insert(stringtoLL("bcde")) Result.insert(stringtoLL("cdefgh")) Result.insert(stringtoLL("defghi")) Result.insert(stringtoLL("efghijk")) Result.insert(stringtoLL("a")) -- for length 1 tests Result.insert(stringtoLL("c")) -- for length 1 tests Result.insert(stringtoLL("e")) -- for length 1 tests Result.insert(stringtoLL("abc")) -- for length q tests Result.insert(stringtoLL("cde")) -- for length q tests Result.insert(stringtoLL("efgh")) -- for length q tests end check_trie_node( t : TRIE[CHARACTER] ; c : CHARACTER ; ter : BOOLEAN ; subtries : INTEGER) : BOOLEAN -- Check the contents of a trie node do Result := t.terminal = ter and t.element = c and t.ll.count = subtries end end -- class ROOT_CLASS