// Start and end of a string.
	{"^[a-c]*", "x", "abcdabc", "xdabc"},
	{"[a-c]*$", "x", "abcdabc", "abcdx"},
	{"^[a-c]*$", "x", "abcdabc", "abcdabc"},
	{"^[a-c]*", "x", "abc", "x"},
	{"[a-c]*$", "x", "abc", "x"},
	{"^[a-c]*$", "x", "abc", "x"},
	{"^[a-c]*", "x", "dabce", "xdabce"},
	{"[a-c]*$", "x", "dabce", "dabcex"},
	{"^[a-c]*$", "x", "dabce", "dabce"},
	{"^[a-c]*", "x", "", "x"},

E	a?(ac{0}b|ba)ab			abab	(0,4)(0,2)
E	ab|abab				abbabab	(0,2)
E	aba|bab|bba			baaabbbaba	(5,8)
E	aba|bab				baaabbbaba	(6,9)
E	(aa|aaa)*|(a|aaaaa)		aa	(0,2)(0,2)
E	(a.|.a.)*|(a|.a...)		aa	(0,2)(0,2)
E	ab|a				xabc	(1,3)
E	ab|a				xxabc	(2,4)
Ei	(Ab|cD)*			aBcD	(0,4)(2,4)
BE	[^-]			--a		(2,3)
BE	[a-]*			--a		(0,3)
BE	[a-m-]*			--amoma--	(0,4)
E	:::1:::0:|:::1:1:0:	:::0:::1:::1:::0:	(8,17)
E	:::1:::0:|:::1:1:1:	:::0:::1:::1:::0:	(8,17)

    assertEqualCharNodes(traverser.breadthFirst('b'), "bcda");
    assertEqualCharNodes(traverser.breadthFirst('c'), "cdab");
    assertEqualCharNodes(traverser.breadthFirst('d'), "dabc");
  }

  @Test
  public void forGraph_breadthFirstIterable_cycle() {
    Traverser<Character> traverser = Traverser.forGraph(CYCLE_GRAPH);
    assertEqualCharNodes(traverser.breadthFirst(charactersOf("a")), "abcd");

    assertEqualCharNodes(traverser.breadthFirst('b'), "bcda");
    assertEqualCharNodes(traverser.breadthFirst('c'), "cdab");
    assertEqualCharNodes(traverser.breadthFirst('d'), "dabc");
  }

  @Test
  public void forGraph_breadthFirstIterable_cycle() {
    Traverser<Character> traverser = Traverser.forGraph(CYCLE_GRAPH);
    assertEqualCharNodes(traverser.breadthFirst(charactersOf("a")), "abcd");

        "abc"               | "  "   | "  abc"
        "abc"               | "def"  | "defabc"
        "abc\ndef\nghi"     | " "    | " abc\n def\n ghi"
        "abc\n\t\n   \nghi" | "X"    | "Xabc\n\t\n   \nXghi"
    }

    def shorterOf() {
        expect:
        TextUtil.shorterOf("a", "b") == "a"
        TextUtil.shorterOf("aa", "b") == "b"
        TextUtil.shorterOf("a", "bb") == "a"

	// to shift the frame to align this portion of the prefix to the
	// suffix. For example, in the pattern "abcxxxabc", when the first
	// mismatch from the back is found to be in position 3, the matching
	// suffix "xxabc" is not found elsewhere in the pattern. However, its
	// rightmost "abc" (at position 6) is a prefix of the whole pattern, so
	// goodSuffixSkip[3] == shift+len(suffix) == 6+5 == 11.
	goodSuffixSkip []int
}

	{"", "ab", -1},
	{"bc", "ab", -1},
	{"ab", "ab", 0},
	{"xab", "ab", 1},
	{"xab"[:2], "ab", -1},
	{"", "abc", -1},
	{"xbc", "abc", -1},
	{"abc", "abc", 0},
	{"xabc", "abc", 1},
	{"xabc"[:3], "abc", -1},
	{"xabxc", "abc", -1},
	{"", "abcd", -1},
	{"xbcd", "abcd", -1},
	{"abcd", "abcd", 0},
	{"xabcd", "abcd", 1},
	{"xyabcd"[:5], "abcd", -1},
	{"xbcqq", "abcqq", -1},