package trees; import java.util.Collection; import java.util.HashMap; import java.util.LinkedList; import java.util.Map; import java.util.Map.Entry; // arbres de préfixes public class Trie implements intf.Set<String> { private boolean word; private final Map<Character, Trie> branches; public Trie() { this.word = false; this.branches = new HashMap<Character, Trie>(); } public boolean contains(String s) { Trie t = this; for (int i = 0; i < s.length(); i++) { // invariant t != null t = t.branches.get(s.charAt(i)); if (t == null) return false; } return t.word; } public Trie branch(char c) { return this.branches.get(c); } public void add(String s) { Trie t = this; for (int i = 0; i < s.length(); i++) { // invariant t != null char c = s.charAt(i); Map<Character, Trie> b = t.branches; t = b.get(c); if (t == null) { t = new Trie(); b.put(c, t); } } t.word = true; } public boolean isEmpty() { return !this.word && this.branches.isEmpty(); } // cette méthode remove conduit à des sous-arbres entièrement vides public void removeSimple(String s) { Trie t = this; for (int i = 0; i < s.length(); i++) { // invariant t != null t = t.branches.get(s.charAt(i)); if (t == null) return; } t.word = false; } // cette méthode remove assure que l'arbre ne contient jamais de sous-arbre vide private void remove(String s, int i) { if (i == s.length()) { this.word = false; return; } char c = s.charAt(i); Trie b = this.branches.get(c); if (b == null) return; b.remove(s, i+1); if (b.isEmpty()) this.branches.remove(c); } public void remove(String s) { remove(s, 0); } public int size() { int s = 0; if (this.word) s++; for (Trie b: this.branches.values()) s += b.size(); return s; } public Trie get(String s) { Trie t = this; for (int i = 0; i < s.length(); i++) { // invariant t != null t = t.branches.get(s.charAt(i)); if (t == null) return null; } return t; } // tous les mots dont s est un préfixe public Collection<String> below(String s) { Collection<String> c = new LinkedList<String>(); Trie t = this.get(s); if (t == null) return c; t.collect(c, s); return c; } // tous les mots, en leur ajoutant le préfixe prefix private void collect(Collection<String> c, String prefix) { if (this.word) c.add(prefix); for (Entry<Character, Trie> b: this.branches.entrySet()) b.getValue().collect(c, prefix + b.getKey()); } // tous les mots public Collection<String> elements() { return this.below(""); } @Override public void clear() { this.word = false; this.branches.clear(); } } class TestTrie { public static void main(String[] args) { Trie t = new Trie(); assert (!t.contains("")); t.add(""); assert (t.contains("")); assert (!t.contains("a")); t.add("a"); assert (t.contains("a")); assert (!t.contains("aa")); assert (!t.contains("b")); t.add("b"); assert (t.contains("a")); assert (!t.contains("ab")); assert (t.contains("b")); t.add("abc"); assert (t.contains("a")); assert (!t.contains("aa")); assert (!t.contains("ab")); assert (!t.contains("acb")); assert (!t.contains("ba")); assert (t.contains("b")); assert (t.contains("abc")); t.remove("a"); assert (!t.contains("a")); assert (!t.contains("aa")); assert (!t.contains("ab")); assert (!t.contains("acb")); assert (!t.contains("ba")); assert (t.contains("b")); assert (t.contains("abc")); t.remove("b"); assert (t.contains("abc")); t.remove("abc"); assert (!t.isEmpty()); t.remove(""); assert (t.isEmpty()); System.out.println("TestTrie OK"); } } // version optimisée où les feuilles ont un champ branches qui vaut null class Trie2 implements intf.Set<String> { private boolean word; private Map<Character, Trie2> branches; public Trie2() { this.word = false; this.branches = null; } public boolean contains(String s) { Trie2 t = this; for (int i = 0; i < s.length(); i++) { // invariant t != null if (t.branches == null) return false; t = t.branches.get(s.charAt(i)); if (t == null) return false; } return t.word; } public void add(String s) { Trie2 t = this; for (int i = 0; i < s.length(); i++) { // invariant t != null char c = s.charAt(i); Map<Character, Trie2> b = t.branches; if (b == null) b = t.branches = new HashMap<Character, Trie2>(); t = b.get(c); if (t == null) { t = new Trie2(); b.put(c, t); } } t.word = true; } public boolean isEmpty() { return !this.word && this.branches == null; } // cette méthode remove assure que l'arbre ne contient jamais de sous-arbre vide private void removeRec(String s, int i) { if (i == s.length()) { this.word = false; return; } char c = s.charAt(i); if (this.branches == null) return; Trie2 b = this.branches.get(c); if (b == null) return; b.removeRec(s, i+1); if (b.isEmpty()) this.branches.remove(c); if (this.branches.isEmpty()) this.branches = null; } public void remove(String s) { removeRec(s, 0); } public int size() { int s = 0; if (this.word) s++; for (Trie2 b: this.branches.values()) s += b.size(); return s; } @Override public void clear() { this.word = false; this.branches.clear(); } } class TestTrie2 { public static void main(String[] args) { Trie2 t = new Trie2(); assert (!t.contains("")); t.add(""); assert (t.contains("")); assert (!t.contains("a")); t.add("a"); assert (t.contains("a")); assert (!t.contains("aa")); assert (!t.contains("b")); t.add("b"); assert (t.contains("a")); assert (!t.contains("ab")); assert (t.contains("b")); t.add("abc"); assert (t.contains("a")); assert (!t.contains("aa")); assert (!t.contains("ab")); assert (!t.contains("acb")); assert (!t.contains("ba")); assert (t.contains("b")); assert (t.contains("abc")); t.remove("a"); assert (!t.contains("a")); assert (!t.contains("aa")); assert (!t.contains("ab")); assert (!t.contains("acb")); assert (!t.contains("ba")); assert (t.contains("b")); assert (t.contains("abc")); t.remove("b"); assert (t.contains("abc")); t.remove("abc"); assert (!t.isEmpty()); t.remove(""); assert (t.isEmpty()); System.out.println("TestTrie2 OK"); } } //version avec des méthodes statiques class Trie1 { private boolean word; private final HashMap<Character, Trie1> branches; Trie1() { this.word = false; this.branches = new HashMap<Character, Trie1>(); } static boolean contains(Trie1 t, String s) { assert (t != null); for (int i = 0; i < s.length(); i++) { // invariant t != null t = t.branches.get(s.charAt(i)); if (t == null) return false; } return t.word; } static void add(Trie1 t, String s) { assert (t != null); for (int i = 0; i < s.length(); i++) { // invariant t != null char c = s.charAt(i); HashMap<Character, Trie1> b = t.branches; t = b.get(c); if (t == null) { t = new Trie1(); b.put(c, t); } } t.word = true; } static boolean isEmpty(Trie1 t) { return !t.word && t.branches.isEmpty(); } static private void removeRec(Trie1 t, String s, int i) { assert (t != null); if (i == s.length()) { t.word = false; return; } char c = s.charAt(i); Trie1 b = t.branches.get(c); if (b == null) return; removeRec(b, s, i+1); if (isEmpty(b)) t.branches.remove(c); } static void remove(Trie1 t, String s) { assert (t != null); removeRec(t, s, 0); } }