func iterated(it graph.Iterator) []int {
	var res []int
	for graph.Next(it) {
		res = append(res, it.Result().(int))
	}
	return res
}

func iterated(it graph.Iterator) []int {
	var res []int
	for it.Next() {
		res = append(res, int(it.Result().(Int64Node)))
	}
	return res
}

func TestIterators(t *testing.T) {
	qs, opts, closer := makeGAE(t)
	defer closer()

	graphtest.MakeWriter(t, qs, opts, graphtest.MakeQuadSet()...)

	require.Equal(t, int64(11), qs.Size(), "Incorrect number of quads")

	var expected = []quad.Quad{
		quad.MakeRaw("C", "follows", "B", ""),
		quad.MakeRaw("C", "follows", "D", ""),
	}

	it := qs.QuadIterator(quad.Subject, qs.ValueOf(quad.Raw("C")))
	graphtest.ExpectIteratedQuads(t, qs, it, expected)

	// Test contains
	it = qs.QuadIterator(quad.Label, qs.ValueOf(quad.Raw("status_graph")))
	gqs := qs.(*QuadStore)
	key := gqs.createKeyForQuad(quad.MakeRaw("G", "status", "cool", "status_graph"))
	token := &Token{quadKind, key.StringID()}

	require.True(t, it.Contains(token), "Contains failed")

	// Test cloning an iterator
	var it2 graph.Iterator
	it2 = it.Clone()
	x := it2.Describe()
	y := it.Describe()

	require.Equal(t, y.Name, x.Name, "Iterator Clone was not successful")
}

func (qs *QuadStore) OptimizeIterator(it graph.Iterator) (graph.Iterator, bool) {
	switch it.Type() {
	case graph.LinksTo:
		return qs.optimizeLinksTo(it.(*iterator.LinksTo))

	}
	return it, false
}

func iteratedQuads(qs graph.QuadStore, it graph.Iterator) []quad.Quad {
	var res ordered
	for graph.Next(it) {
		res = append(res, qs.Quad(it.Result()))
	}
	sort.Sort(res)
	return res
}

func iteratedNames(qs graph.QuadStore, it graph.Iterator) []string {
	var res []string
	for graph.Next(it) {
		res = append(res, qs.NameOf(it.Result()))
	}
	sort.Strings(res)
	return res
}

func OutputQueryShapeForIterator(it graph.Iterator, qs graph.QuadStore, outputMap map[string]interface{}) {
	s := &queryShape{
		qs:     qs,
		nodeID: 1,
	}

	node := s.MakeNode(it.Clone())
	s.AddNode(node)
	outputMap["nodes"] = s.nodes
	outputMap["links"] = s.links
}

// moveTagsTo() gets the tags for all of the src's subiterators and the
// src itself, and moves them to dst.
func moveTagsTo(dst graph.Iterator, src *And) {
	tags := src.getSubTags()
	for _, tag := range dst.Tagger().Tags() {
		if _, ok := tags[tag]; ok {
			delete(tags, tag)
		}
	}
	dt := dst.Tagger()
	for k := range tags {
		dt.Add(k)
	}
}

func TestIterators(t *testing.T) {
	clog.Infof("\n-----------\n")
	inst, opts, err := createInstance()
	defer inst.Close()

	if err != nil {
		t.Fatalf("failed to create instance: %v", err)
	}
	qs, _, _ := makeTestStore(simpleGraph, opts)
	if qs.Size() != 11 {
		t.Fatal("Incorrect number of quads")
	}

	var expected = []string{
		quad.Quad{"C", "follows", "B", ""}.String(),
		quad.Quad{"C", "follows", "D", ""}.String(),
	}

	it := qs.QuadIterator(quad.Subject, qs.ValueOf("C"))
	if got, ok := compareResults(qs, it, expected); !ok {
		t.Errorf("Unexpected iterated result, got:%v expect:%v", got, expected)
	}

	// Test contains
	it = qs.QuadIterator(quad.Label, qs.ValueOf("status_graph"))
	gqs := qs.(*QuadStore)
	key := gqs.createKeyForQuad(quad.Quad{"G", "status", "cool", "status_graph"})
	token := &Token{quadKind, key.StringID()}
	if !it.Contains(token) {
		t.Error("Contains failed")
	}

	// Test cloning an iterator
	var it2 graph.Iterator
	it2 = it.Clone()
	x := it2.Describe()
	y := it.Describe()

	if x.Name != y.Name {
		t.Errorf("Iterator Clone was not successful got: %v, expected: %v", x.Name, y.Name)
	}
}

func iterateResults(qs graph.QuadStore, it graph.Iterator) []string {
	var res []string
	for graph.Next(it) {
		v := it.Result()
		if t, ok := v.(*Token); ok && t.Kind == nodeKind {
			res = append(res, qs.NameOf(it.Result()))
		} else {
			res = append(res, qs.Quad(it.Result()).String())
		}
	}
	sort.Strings(res)
	it.Reset()
	return res
}

func (wk *worker) runIteratorToArray(it graph.Iterator, limit int) []map[string]string {
	output := make([]map[string]string, 0)
	n := 0
	it, _ = it.Optimize()
	for {
		select {
		case <-wk.kill:
			return nil
		default:
		}
		if !graph.Next(it) {
			break
		}
		tags := make(map[string]graph.Value)
		it.TagResults(tags)
		output = append(output, wk.tagsToValueMap(tags))
		n++
		if limit >= 0 && n >= limit {
			break
		}
		for it.NextPath() {
			select {
			case <-wk.kill:
				return nil
			default:
			}
			tags := make(map[string]graph.Value)
			it.TagResults(tags)
			output = append(output, wk.tagsToValueMap(tags))
			n++
			if limit >= 0 && n >= limit {
				break
			}
		}
	}
	it.Close()
	return output
}

func IteratedRawStrings(t testing.TB, qs graph.QuadStore, it graph.Iterator) []string {
	var res []string
	for it.Next() {
		res = append(res, qs.NameOf(it.Result()).String())
	}
	require.Nil(t, it.Err())
	sort.Strings(res)
	return res
}

func IteratedValues(t testing.TB, qs graph.QuadStore, it graph.Iterator) []quad.Value {
	var res []quad.Value
	for it.Next() {
		res = append(res, qs.NameOf(it.Result()))
	}
	require.Nil(t, it.Err())
	sort.Sort(quad.ByValueString(res))
	return res
}

func IteratedQuads(t testing.TB, qs graph.QuadStore, it graph.Iterator) []quad.Quad {
	var res quad.ByQuadString
	for it.Next() {
		res = append(res, qs.Quad(it.Result()))
	}
	require.Nil(t, it.Err())
	sort.Sort(res)
	return res
}

func (wk *worker) runIteratorToArrayNoTags(it graph.Iterator, limit int) []string {
	output := make([]string, 0)
	n := 0
	it, _ = it.Optimize()
	for {
		select {
		case <-wk.kill:
			return nil
		default:
		}
		if !graph.Next(it) {
			break
		}
		output = append(output, wk.qs.NameOf(it.Result()))
		n++
		if limit >= 0 && n >= limit {
			break
		}
	}
	it.Close()
	return output
}

func (s *queryShape) MakeNode(it graph.Iterator) *Node {
	n := Node{ID: s.nodeID}
	for _, tag := range it.Tagger().Tags() {
		n.Tags = append(n.Tags, tag)
	}
	for k := range it.Tagger().Fixed() {
		n.Tags = append(n.Tags, k)
	}

	switch it.Type() {
	case graph.And:
		for _, sub := range it.SubIterators() {
			s.nodeID++
			newNode := s.MakeNode(sub)
			if sub.Type() != graph.Or {
				s.StealNode(&n, newNode)
			} else {
				s.AddNode(newNode)
				s.AddLink(&Link{n.ID, newNode.ID, 0, 0})
			}
		}
	case graph.Fixed:
		n.IsFixed = true
		for it.Next() {
			n.Values = append(n.Values, s.qs.NameOf(it.Result()).String())
		}
	case graph.HasA:
		hasa := it.(*HasA)
		s.PushHasa(n.ID, hasa.dir)
		s.nodeID++
		newNode := s.MakeNode(hasa.primaryIt)
		s.AddNode(newNode)
		s.RemoveHasa()
	case graph.Or:
		for _, sub := range it.SubIterators() {
			s.nodeID++
			newNode := s.MakeNode(sub)
			if sub.Type() == graph.Or {
				s.StealNode(&n, newNode)
			} else {
				s.AddNode(newNode)
				s.AddLink(&Link{n.ID, newNode.ID, 0, 0})
			}
		}
	case graph.LinksTo:
		n.IsLinkNode = true
		lto := it.(*LinksTo)
		s.nodeID++
		newNode := s.MakeNode(lto.primaryIt)
		hasaID, hasaDir := s.LastHasa()
		if (hasaDir == quad.Subject && lto.dir == quad.Object) ||
			(hasaDir == quad.Object && lto.dir == quad.Subject) {
			s.AddNode(newNode)
			if hasaDir == quad.Subject {
				s.AddLink(&Link{hasaID, newNode.ID, 0, n.ID})
			} else {
				s.AddLink(&Link{newNode.ID, hasaID, 0, n.ID})
			}
		} else if lto.primaryIt.Type() == graph.Fixed {
			s.StealNode(&n, newNode)
		} else {
			s.AddNode(newNode)
		}
	case graph.Optional:
		// Unsupported, for the moment
		fallthrough
	case graph.All:
	}
	return &n
}

func TestIterator(t *testing.T) {
	tmpDir, err := ioutil.TempDir(os.TempDir(), "cayley_test")
	if err != nil {
		t.Fatalf("Could not create working directory: %v", err)
	}
	defer os.RemoveAll(tmpDir)
	t.Log(tmpDir)

	err = createNewLevelDB(tmpDir, nil)
	if err != nil {
		t.Fatal("Failed to create LevelDB database.")
	}

	qs, err := newQuadStore(tmpDir, nil)
	if qs == nil || err != nil {
		t.Error("Failed to create leveldb QuadStore.")
	}

	w, _ := writer.NewSingleReplication(qs, nil)
	w.AddQuadSet(makeQuadSet())
	var it graph.Iterator

	it = qs.NodesAllIterator()
	if it == nil {
		t.Fatal("Got nil iterator.")
	}

	size, exact := it.Size()
	if size <= 0 || size >= 20 {
		t.Errorf("Unexpected size, got:%d expect:(0, 20)", size)
	}
	if exact {
		t.Errorf("Got unexpected exact result.")
	}
	if typ := it.Type(); typ != graph.All {
		t.Errorf("Unexpected iterator type, got:%v expect:%v", typ, graph.All)
	}
	optIt, changed := it.Optimize()
	if changed || optIt != it {
		t.Errorf("Optimize unexpectedly changed iterator.")
	}

	expect := []string{
		"A",
		"B",
		"C",
		"D",
		"E",
		"F",
		"G",
		"follows",
		"status",
		"cool",
		"status_graph",
	}
	sort.Strings(expect)
	for i := 0; i < 2; i++ {
		got := iteratedNames(qs, it)
		sort.Strings(got)
		if !reflect.DeepEqual(got, expect) {
			t.Errorf("Unexpected iterated result on repeat %d, got:%v expect:%v", i, got, expect)
		}
		it.Reset()
	}

	for _, pq := range expect {
		if !it.Contains(qs.ValueOf(pq)) {
			t.Errorf("Failed to find and check %q correctly", pq)
		}
	}
	// FIXME(kortschak) Why does this fail?
	/*
		for _, pq := range []string{"baller"} {
			if it.Contains(qs.ValueOf(pq)) {
				t.Errorf("Failed to check %q correctly", pq)
			}
		}
	*/
	it.Reset()

	it = qs.QuadsAllIterator()
	graph.Next(it)
	q := qs.Quad(it.Result())
	set := makeQuadSet()
	var ok bool
	for _, t := range set {
		if t.String() == q.String() {
			ok = true
			break
		}
	}
	if !ok {
		t.Errorf("Failed to find %q during iteration, got:%q", q, set)
	}

	qs.Close()
}

func TestIterator(t testing.TB, gen DatabaseFunc) {
	qs, opts, closer := gen(t)
	defer closer()

	MakeWriter(t, qs, opts, MakeQuadSet()...)

	var it graph.Iterator

	it = qs.NodesAllIterator()
	require.NotNil(t, it)

	size, _ := it.Size()
	require.True(t, size > 0 && size < 20, "Unexpected size")
	// TODO: leveldb had this test
	//if exact {
	//	t.Errorf("Got unexpected exact result.")
	//}
	require.Equal(t, graph.All, it.Type(), "Unexpected iterator type")

	optIt, changed := it.Optimize()
	require.True(t, !changed && optIt == it, "Optimize unexpectedly changed iterator: %v, %T", changed, optIt)

	expect := []string{
		"A",
		"B",
		"C",
		"D",
		"E",
		"F",
		"G",
		"follows",
		"status",
		"cool",
		"status_graph",
	}
	sort.Strings(expect)
	for i := 0; i < 2; i++ {
		got := IteratedRawStrings(t, qs, it)
		sort.Strings(got)
		require.Equal(t, expect, got, "Unexpected iterated result on repeat %d", i)
		it.Reset()
	}

	for _, pq := range expect {
		require.True(t, it.Contains(qs.ValueOf(quad.Raw(pq))), "Failed to find and check %q correctly", pq)

	}
	// FIXME(kortschak) Why does this fail?
	/*
		for _, pq := range []string{"baller"} {
			if it.Contains(qs.ValueOf(pq)) {
				t.Errorf("Failed to check %q correctly", pq)
			}
		}
	*/
	it.Reset()

	it = qs.QuadsAllIterator()
	optIt, changed = it.Optimize()
	require.True(t, !changed && optIt == it, "Optimize unexpectedly changed iterator: %v, %T", changed, optIt)

	require.True(t, it.Next())

	q := qs.Quad(it.Result())
	require.Nil(t, it.Err())
	require.True(t, q.IsValid(), "Invalid quad returned: %q", q)
	set := MakeQuadSet()
	var ok bool
	for _, e := range set {
		if e.String() == q.String() {
			ok = true
			break
		}
	}
	require.True(t, ok, "Failed to find %q during iteration, got:%q", q, set)
}

func (wk *worker) runIterator(it graph.Iterator) {
	if wk.wantShape() {
		iterator.OutputQueryShapeForIterator(it, wk.qs, wk.shape)
		return
	}
	it, _ = it.Optimize()
	if clog.V(2) {
		b, err := json.MarshalIndent(it.Describe(), "", "  ")
		if err != nil {
			clog.Infof("failed to format description: %v", err)
		} else {
			clog.Infof("%s", b)
		}
	}
	for {
		select {
		case <-wk.kill:
			return
		default:
		}
		if !graph.Next(it) {
			break
		}
		tags := make(map[string]graph.Value)
		it.TagResults(tags)
		if !wk.send(&Result{actualResults: tags}) {
			break
		}
		for it.NextPath() {
			select {
			case <-wk.kill:
				return
			default:
			}
			tags := make(map[string]graph.Value)
			it.TagResults(tags)
			if !wk.send(&Result{actualResults: tags}) {
				break
			}
		}
	}
	if clog.V(2) {
		bytes, _ := json.MarshalIndent(graph.DumpStats(it), "", "  ")
		clog.Infof(string(bytes))
	}
	it.Close()
}

func (wk *worker) runIteratorWithCallback(it graph.Iterator, callback otto.Value, this otto.FunctionCall, limit int) {
	n := 0
	it, _ = it.Optimize()
	if clog.V(2) {
		b, err := json.MarshalIndent(it.Describe(), "", "  ")
		if err != nil {
			clog.Infof("failed to format description: %v", err)
		} else {
			clog.Infof("%s", b)
		}
	}
	for {
		select {
		case <-wk.kill:
			return
		default:
		}
		if !graph.Next(it) {
			break
		}
		tags := make(map[string]graph.Value)
		it.TagResults(tags)
		val, _ := this.Otto.ToValue(wk.tagsToValueMap(tags))
		val, _ = callback.Call(this.This, val)
		n++
		if limit >= 0 && n >= limit {
			break
		}
		for it.NextPath() {
			select {
			case <-wk.kill:
				return
			default:
			}
			tags := make(map[string]graph.Value)
			it.TagResults(tags)
			val, _ := this.Otto.ToValue(wk.tagsToValueMap(tags))
			val, _ = callback.Call(this.This, val)
			n++
			if limit >= 0 && n >= limit {
				break
			}
		}
	}
	it.Close()
}