content: /*
   * The Alluxio Open Foundation licenses this work under the Apache License, version 2.0
   * (the "License"). You may not use this work except in compliance with the License, which is
   * available at www.apache.org/licenses/LICENSE-2.0
   *
   * This software is distributed on an "AS IS" basis, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND,
   * either express or implied, as more fully set forth in the License.
   *
   * See the NOTICE file distributed with this work for information regarding copyright ownership.
   */
  
  package alluxio.conf.path;
  
  import static org.junit.Assert.assertEquals;
  
  import com.google.common.collect.ImmutableList;
  import com.google.common.collect.Streams;
  import org.junit.Assert;
  import org.junit.Test;
  
  import java.util.Arrays;
  import java.util.Collections;
  import java.util.HashSet;
  import java.util.Optional;
  import java.util.Set;
  import java.util.stream.Collectors;
  
  /**
   * Tests {@link PrefixPathMatcher}.
   */
  public class TrieNodeTest {
    @Test
    public void hasTerminalIncludeChildren() {
      TrieNode<Object> node = new TrieNode<>();
      node.insert("/a/b");
      Assert.assertTrue(node.hasTerminal("/", true));
      Assert.assertFalse(node.hasTerminal("/c", true));
      Assert.assertTrue(node.hasTerminal("/a", true));
      Assert.assertTrue(node.hasTerminal("/a/b", true));
      Assert.assertTrue(node.hasTerminal("/a/b/c", true));
    }
  
    @Test
    public void hasTerminal() {
      TrieNode<Object> node = new TrieNode<>();
      node.insert("/a/b");
      Assert.assertFalse(node.hasTerminal("/", false));
      Assert.assertFalse(node.hasTerminal("/c", false));
      Assert.assertFalse(node.hasTerminal("/a", false));
      Assert.assertTrue(node.hasTerminal("/a/b", false));
      Assert.assertTrue(node.hasTerminal("/a/b/c", false));
    }
  
    @Test
    public void getCommonRoots() {
      TrieNode<Object> node = new TrieNode<>();
      TrieNode<Object> a = node.insert("/a");
      TrieNode<Object> b = node.insert("/a/b");
      TrieNode<Object> f = node.insert("/a/e/f");
      TrieNode<Object> d = node.insert("/c/d");
      TrieNode<Object> g = node.insert("/c/g");
      Set<TrieNode<Object>> roots = Streams.stream(node.getCommonRoots()).collect(Collectors.toSet());
      Assert.assertTrue(roots.contains(a));
      Assert.assertFalse(roots.contains(b));
      Assert.assertTrue(roots.contains(d));
      Assert.assertFalse(roots.contains(f));
      Assert.assertTrue(roots.contains(g));
    }
  
    @Test
    public void searchExact() {
      TrieNode<Object> node = new TrieNode<>();
      TrieNode<Object> a = node.insert("/a");
      TrieNode<Object> b = node.insert("/a/b");
      TrieNode<Object> f = node.insert("/a/e/f");
      TrieNode<Object> d = node.insert("/c/d");
      TrieNode<Object> g = node.insert("/c/g");
      TrieNode<Object> h = node.insert("/u/h");
      assertEquals(a, node.searchExact("/a").get());
      assertEquals(b, node.searchExact("/a/b").get());
      assertEquals(f, node.searchExact("/a/e/f").get());
      assertEquals(d, node.searchExact("/c/d").get());
      assertEquals(g, node.searchExact("/c/g").get());
      assertEquals(h, node.searchExact("/u/h").get());
      assertEquals(Optional.empty(), node.searchExact("/"));
      assertEquals(Optional.empty(), node.searchExact("/ab"));
      assertEquals(Optional.empty(), node.searchExact("/a/b/c"));
      assertEquals(Optional.empty(), node.searchExact("/a/d"));
    }
  
    @Test
    public void deleteIfTrue() {
      TrieNode<Object> node = new TrieNode<>();
      TrieNode<Object> a = node.insert("/a");
      TrieNode<Object> b = node.insert("/a/b");
      TrieNode<Object> f = node.insert("/a/e/f");
      TrieNode<Object> d = node.insert("/c/d");
      TrieNode<Object> g = node.insert("/c/g");
      TrieNode<Object> h = node.insert("/u/h");
      Assert.assertTrue(node.search("/a/b").contains(b));
      TrieNode<Object> b2 = node.deleteIf("/a/b", n -> {
        assertEquals(b, n);
        return true;
      });
      assertEquals(b, b2);
      Assert.assertFalse(node.search("/a/b").contains(b));
      Assert.assertTrue(node.search("/a").contains(a));
      TrieNode<Object> a2 = node.deleteIf("/a", n -> {
        assertEquals(a, n);
        return true;
      });
      assertEquals(a, a2);
      Assert.assertFalse(node.search("/a").contains(a));
      Assert.assertTrue(node.search("/a/e/f").contains(f));
      TrieNode<Object> c2 = node.deleteIf("/c", n -> true);
      Assert.assertNull(c2);
      Assert.assertTrue(node.search("/c/d").contains(d));
      Assert.assertTrue(node.search("/c/g").contains(g));
      TrieNode<Object> h2 = node.deleteIf("/u/h", n -> {
        assertEquals(h, n);
        return true;
      });
      assertEquals(h, h2);
      TrieNode<Object> nil = node.deleteIf("/n", n -> {
        Assert.fail();
        return true;
      });
      Assert.assertNull(nil);
    }
  
    @Test
    public void deleteIfFalse() {
      TrieNode<Object> node = new TrieNode<>();
      TrieNode<Object> a = node.insert("/a");
      TrieNode<Object> b = node.insert("/a/b");
      Assert.assertTrue(node.search("/a/b").contains(b));
      TrieNode<Object> b2 = node.deleteIf("/a/b", n -> false);
      Assert.assertNull(b2);
      Assert.assertTrue(node.search("/a").contains(a));
      TrieNode<Object> a2 = node.deleteIf("/a", n -> false);
      Assert.assertNull(a2);
    }
  
    @Test
    public void deleteAndInsert() {
      TrieNode<Object> node = new TrieNode<>();
      TrieNode<Object> a = node.insert("/a");
      TrieNode<Object> b = node.insert("/a/b");
  
      Assert.assertTrue(node.search("/a/b").contains(b));
      TrieNode<Object> b2 = node.deleteIf("/a/b", n -> {
        assertEquals(b, n);
        return true;
      });
      assertEquals(b, b2);
      Assert.assertFalse(node.search("/a/b").contains(b));
      TrieNode<Object> b3 = node.insert("/a/b");
      Assert.assertTrue(node.search("/a/b").contains(b3));
  
      Assert.assertTrue(node.search("/a").contains(a));
      Assert.assertTrue(node.search("/a/b").contains(a));
      TrieNode<Object> a2 = node.deleteIf("/a", n -> {
        assertEquals(a, n);
        return true;
      });
      assertEquals(a, a2);
      Assert.assertFalse(node.search("/a/b").contains(a));
      Assert.assertFalse(node.search("/a").contains(a));
      Assert.assertTrue(node.search("/a/b").contains(b3));
      TrieNode<Object> a3 = node.insert("/a");
      Assert.assertTrue(node.search("/a/b").contains(b3));
      Assert.assertTrue(node.search("/a").contains(a3));
      Assert.assertTrue(node.search("/a/b").contains(a3));
    }
  
    @Test
    public void getChildren() {
      TrieNode<Object> node = new TrieNode<>();
      TrieNode<Object> a = node.insert("/a");
      TrieNode<Object> b = node.insert("/a/b");
      TrieNode<Object> f = node.insert("/a/e/f");
      TrieNode<Object> d = node.insert("/c/d");
      TrieNode<Object> g = node.insert("/c/g");
      TrieNode<Object> h = node.insert("/u/h");
      Assert.assertArrayEquals(new TrieNode[] {a, b, f},
          node.getLeafChildren("/a").toArray(TrieNode[]::new));
      Assert.assertArrayEquals(new TrieNode[] {b},
          node.getLeafChildren("/a/b").toArray(TrieNode[]::new));
      Assert.assertArrayEquals(new TrieNode[] {f},
          node.getLeafChildren("/a/e/f").toArray(TrieNode[]::new));
      Assert.assertArrayEquals(new TrieNode[] {d},
          node.getLeafChildren("/c/d").toArray(TrieNode[]::new));
      assertEquals(new HashSet(Arrays.asList(a, b, f, d, g, h)),
          node.getLeafChildren("/").collect(Collectors.toSet()));
    }
  
    @Test
    public void clearTrie() {
      TrieNode<Object> node = new TrieNode<>();
      TrieNode<Object> a = node.insert("/a");
      TrieNode<Object> b = node.insert("/a/b");
      TrieNode<Object> f = node.insert("/a/e/f");
      TrieNode<Object> d = node.insert("/c/d");
      TrieNode<Object> g = node.insert("/c/g");
      TrieNode<Object> h = node.insert("/u/h");
  
      node.clear();
      // after clearing, each node should only contain itself
      for (TrieNode<Object> nxt : ImmutableList.of(a, b, f, d, g, h)) {
        assertEquals(Collections.singletonList(nxt),
            nxt.getLeafChildren("/").collect(Collectors.toList()));
      }
    }
  
    @Test
    public void getLeafChildrenOnRoot() {
      TrieNode<Object> node = new TrieNode<>();
      TrieNode<Object> a = node.insert("/a");
      TrieNode<Object> b = node.insert("/a/b");
      TrieNode<Object> f = node.insert("/a/e/f");
      TrieNode<Object> d = node.insert("/c/d");
      TrieNode<Object> g = node.insert("/c/g");
      TrieNode<Object> h = node.insert("/u/h");
      assertEquals(6, node.getLeafChildren("/").toArray().length);
    }
  }
  