| 60 | } |
| 61 | |
| 62 | func TestTrieRemove(t *testing.T) { |
| 63 | n := NewNode() |
| 64 | |
| 65 | insertWords := []string{ |
| 66 | "nikola", |
| 67 | "tesla", |
| 68 | "albert", |
| 69 | "einstein", |
| 70 | } |
| 71 | |
| 72 | checkWords := map[string]bool{ |
| 73 | "thomas": false, |
| 74 | "edison": false, |
| 75 | "nikola": true, |
| 76 | "albert": true, |
| 77 | "einstein": true, |
| 78 | } |
| 79 | |
| 80 | n.Insert(insertWords...) |
| 81 | n.verify(t, checkWords) |
| 82 | size, capa := n.Size(), n.Capacity() // 4 words ... |
| 83 | |
| 84 | n.Remove("albert") |
| 85 | checkWords["albert"] = false |
| 86 | size-- // 3 words in size, but no change in capacity |
| 87 | n.verify(t, checkWords) |
| 88 | n.verifySizeCapa(t, size, capa) |
| 89 | |
| 90 | n.Remove("albert") // no effect since already removed |
| 91 | n.verify(t, checkWords) |
| 92 | n.verifySizeCapa(t, size, capa) |
| 93 | |
| 94 | n.Remove("marcel") // no effect since ,o, existent |
| 95 | n.verify(t, checkWords) |
| 96 | n.verifySizeCapa(t, size, capa) |
| 97 | |
| 98 | n.Remove("nikola", "tesla") // 1 word |
| 99 | checkWords["nikola"] = false |
| 100 | checkWords["tesla"] = false |
| 101 | size -= 2 // t1 word left, but still no change in capacity |
| 102 | n.verify(t, checkWords) |
| 103 | n.verifySizeCapa(t, size, capa) |
| 104 | |
| 105 | // compact the Tree |
| 106 | if n.Compact() { |
| 107 | t.Fatal("the Trie should not be completely removable after compaction") |
| 108 | } |
| 109 | if capa <= n.Capacity() { |
| 110 | t.Fatal("capacity should have reduced following compaction") |
| 111 | } |
| 112 | capa = n.Capacity() |
| 113 | n.verify(t, checkWords) |
| 114 | n.verifySizeCapa(t, size, capa) // still 1 word, reduced capacity |
| 115 | |
| 116 | n.Remove("einstein") |
| 117 | checkWords["einstein"] = false |
| 118 | size-- // No more words |
| 119 | n.verify(t, checkWords) |