// Next()ing a LinksTo operates as described above.
func (it *LinksTo) Next() bool {
	graph.NextLogIn(it)
	it.runstats.Next += 1
	if graph.Next(it.nextIt) {
		it.runstats.ContainsNext += 1
		it.result = it.nextIt.Result()
		return graph.NextLogOut(it, it.nextIt, true)
	}

	// If there's an error in the 'next' iterator, we save it and we're done.
	it.err = it.nextIt.Err()
	if it.err != nil {
		return false
	}

	// Subiterator is empty, get another one
	if !graph.Next(it.primaryIt) {
		// Possibly save error
		it.err = it.primaryIt.Err()

		// We're out of nodes in our subiterator, so we're done as well.
		return graph.NextLogOut(it, 0, false)
	}
	it.nextIt.Close()
	it.nextIt = it.qs.QuadIterator(it.dir, it.primaryIt.Result())

	// Recurse -- return the first in the next set.
	return it.Next()
}

func TestSQLLinkIteration(t *testing.T) {
	if *postgres_path == "" {
		t.SkipNow()
	}
	db, err := newQuadStore(*postgres_path, nil)
	qs := db.(*QuadStore)
	if err != nil {
		t.Fatal(err)
	}
	it := NewSQLLinkIterator(qs, quad.Object, "Humphrey Bogart")
	for graph.Next(it) {
		fmt.Println(it.Result())
	}
	it = NewSQLLinkIterator(qs, quad.Subject, "/en/casablanca_1942")
	s, v := it.sql.buildSQL(true, nil)
	t.Log(s, v)
	c := 0
	for graph.Next(it) {
		fmt.Println(it.Result())
		c += 1
	}
	if c != 18 {
		t.Errorf("Not enough results, got %d expected 18", c)
	}
}

func TestMultipleConstraintParse(t *testing.T) {
	qs, _ := graph.NewQuadStore("memstore", "", nil)
	w, _ := graph.NewQuadWriter("single", qs, nil)
	for _, tv := range []quad.Quad{
		{"i", "like", "food", ""},
		{"i", "like", "beer", ""},
		{"you", "like", "beer", ""},
	} {
		w.AddQuad(tv)
	}
	query := `(
		$a
		(:like :beer)
		(:like "food")
	)`
	it := BuildIteratorTreeForQuery(qs, query)
	if it.Type() != graph.And {
		t.Errorf("Odd iterator tree. Got: %#v", it.Describe())
	}
	if !graph.Next(it) {
		t.Error("Got no results")
	}
	out := it.Result()
	if out != qs.ValueOf("i") {
		t.Errorf("Got %d, expected %d", out, qs.ValueOf("i"))
	}
	if graph.Next(it) {
		t.Error("Too many results")
	}
}

// Next advances the Skip iterator. It will skip all initial values
// before returning actual result.
func (it *Skip) Next() bool {
	graph.NextLogIn(it)
	for ; it.skipped < it.skip; it.skipped++ {
		if !graph.Next(it.primaryIt) {
			return graph.NextLogOut(it, nil, false)
		}
	}
	if graph.Next(it.primaryIt) {
		curr := it.primaryIt.Result()
		return graph.NextLogOut(it, curr, true)
	}
	return graph.NextLogOut(it, nil, false)
}

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

func TestRemoveQuad(t *testing.T) {
	qs, w, _ := makeTestStore(simpleGraph)

	err := w.RemoveQuad(quad.Quad{
		Subject:   "E",
		Predicate: "follows",
		Object:    "F",
		Label:     "",
	})

	if err != nil {
		t.Error("Couldn't remove quad", err)
	}

	fixed := qs.FixedIterator()
	fixed.Add(qs.ValueOf("E"))

	fixed2 := qs.FixedIterator()
	fixed2.Add(qs.ValueOf("follows"))

	innerAnd := iterator.NewAnd(qs)
	innerAnd.AddSubIterator(iterator.NewLinksTo(qs, fixed, quad.Subject))
	innerAnd.AddSubIterator(iterator.NewLinksTo(qs, fixed2, quad.Predicate))

	hasa := iterator.NewHasA(qs, innerAnd, quad.Object)

	newIt, _ := hasa.Optimize()
	if graph.Next(newIt) {
		t.Error("E should not have any followers.")
	}
}

func (qs *QuadStore) optimizeLinksTo(it *iterator.LinksTo) (graph.Iterator, bool) {
	subs := it.SubIterators()
	if len(subs) != 1 {
		return it, false
	}
	primary := subs[0]
	if primary.Type() == graph.Fixed {
		size, _ := primary.Size()
		if size == 1 {
			if !graph.Next(primary) {
				panic("unexpected size during optimize")
			}
			val := primary.Result()
			newIt := qs.QuadIterator(it.Direction(), val)
			nt := newIt.Tagger()
			nt.CopyFrom(it)
			for _, tag := range primary.Tagger().Tags() {
				nt.AddFixed(tag, val)
			}
			it.Close()
			return newIt, true
		}
	}
	return it, false
}

func TestSQLNodeIteration(t *testing.T) {
	if *postgres_path == "" {
		t.SkipNow()
	}
	db, err := newQuadStore(*postgres_path, nil)
	if err != nil {
		t.Fatal(err)
	}
	link := NewSQLLinkIterator(db.(*QuadStore), quad.Object, "/en/humphrey_bogart")
	it := &SQLIterator{
		uid: iterator.NextUID(),
		qs:  db.(*QuadStore),
		sql: &SQLNodeIterator{
			tableName: newTableName(),
			linkIt: sqlItDir{
				it:  link.sql,
				dir: quad.Subject,
			},
		},
	}
	s, v := it.sql.buildSQL(true, nil)
	t.Log(s, v)
	c := 0
	for graph.Next(it) {
		t.Log(it.Result())
		c += 1
	}
	if c != 56 {
		t.Errorf("Not enough results, got %d expected 56", c)
	}

}

func (s *Session) Execute(input string, c chan interface{}, _ int) {
	defer close(c)
	var mqlQuery interface{}
	err := json.Unmarshal([]byte(input), &mqlQuery)
	if err != nil {
		return
	}
	s.currentQuery = NewQuery(s)
	s.currentQuery.BuildIteratorTree(mqlQuery)
	if s.currentQuery.isError() {
		return
	}
	it, _ := s.currentQuery.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 graph.Next(it) {
		tags := make(map[string]graph.Value)
		it.TagResults(tags)
		c <- tags
		for it.NextPath() == true {
			tags := make(map[string]graph.Value)
			it.TagResults(tags)
			c <- tags
		}
	}
}

// Next advances the Or graph.iterator. Because the Or is the union of its
// subiterators, it must produce from all subiterators -- unless it it
// shortcircuiting, in which case, it is the first one that returns anything.
func (it *Or) Next() bool {
	graph.NextLogIn(it)
	var first bool
	for {
		if it.currentIterator == -1 {
			it.currentIterator = 0
			first = true
		}
		curIt := it.internalIterators[it.currentIterator]

		if graph.Next(curIt) {
			it.result = curIt.Result()
			return graph.NextLogOut(it, it.result, true)
		}

		it.err = curIt.Err()
		if it.err != nil {
			return graph.NextLogOut(it, nil, false)
		}

		if it.isShortCircuiting && !first {
			break
		}
		it.currentIterator++
		if it.currentIterator == it.itCount {
			break
		}
	}

	return graph.NextLogOut(it, nil, false)
}

func TestOptimize(t *testing.T) {
	tmpDir, _ := ioutil.TempDir(os.TempDir(), "cayley_test")
	t.Log(tmpDir)
	defer os.RemoveAll(tmpDir)
	err := createNewLevelDB(tmpDir, nil)
	if err != nil {
		t.Fatalf("Failed to create working directory")
	}
	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())

	// With an linksto-fixed pair
	fixed := qs.FixedIterator()
	fixed.Add(qs.ValueOf("F"))
	fixed.Tagger().Add("internal")
	lto := iterator.NewLinksTo(qs, fixed, quad.Object)

	oldIt := lto.Clone()
	newIt, ok := lto.Optimize()
	if !ok {
		t.Errorf("Failed to optimize iterator")
	}
	if newIt.Type() != Type() {
		t.Errorf("Optimized iterator type does not match original, got:%v expect:%v", newIt.Type(), Type())
	}

	newQuads := iteratedQuads(qs, newIt)
	oldQuads := iteratedQuads(qs, oldIt)
	if !reflect.DeepEqual(newQuads, oldQuads) {
		t.Errorf("Optimized iteration does not match original")
	}

	graph.Next(oldIt)
	oldResults := make(map[string]graph.Value)
	oldIt.TagResults(oldResults)
	graph.Next(newIt)
	newResults := make(map[string]graph.Value)
	newIt.TagResults(newResults)
	if !reflect.DeepEqual(newResults, oldResults) {
		t.Errorf("Discordant tag results, new:%v old:%v", newResults, oldResults)
	}
}

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 TestInterestingQuery(t *testing.T) {
	if *postgres_path == "" {
		t.SkipNow()
	}
	db, err := newQuadStore(*postgres_path, nil)
	if err != nil {
		t.Fatal(err)
	}
	qs := db.(*QuadStore)
	a := NewSQLLinkIterator(qs, quad.Object, "Humphrey Bogart")
	b := NewSQLLinkIterator(qs, quad.Predicate, "name")
	it1, err := intersect(a.sql, b.sql, qs)
	if err != nil {
		t.Error(err)
	}
	it2, err := hasa(it1.sql, quad.Subject, qs)
	if err != nil {
		t.Error(err)
	}
	it2.Tagger().Add("hb")
	it3, err := linksto(it2.sql, quad.Object, qs)
	if err != nil {
		t.Error(err)
	}
	b = NewSQLLinkIterator(db.(*QuadStore), quad.Predicate, "/film/performance/actor")
	it4, err := intersect(it3.sql, b.sql, qs)
	if err != nil {
		t.Error(err)
	}
	it5, err := hasa(it4.sql, quad.Subject, qs)
	if err != nil {
		t.Error(err)
	}
	it6, err := linksto(it5.sql, quad.Object, qs)
	if err != nil {
		t.Error(err)
	}
	b = NewSQLLinkIterator(db.(*QuadStore), quad.Predicate, "/film/film/starring")
	it7, err := intersect(it6.sql, b.sql, qs)
	if err != nil {
		t.Error(err)
	}
	it8, err := hasa(it7.sql, quad.Subject, qs)
	if err != nil {
		t.Error(err)
	}
	s, v := it8.sql.buildSQL(true, nil)
	it8.Tagger().Add("id")
	t.Log(s, v)
	for graph.Next(it8) {
		t.Log(it8.Result())
		out := make(map[string]graph.Value)
		it8.TagResults(out)
		for k, v := range out {
			t.Log("%s: %v\n", k, v.(string))
		}
	}
}

//experimental
func (exp *Exporter) ExportGml() {
	var seen map[string]int32 // todo eliminate this for large dbs
	var id int32

	exp.Write("Creator Cayley\ngraph\n[\n")

	seen = make(map[string]int32)
	exp.qi.Reset()
	for it := exp.qi; graph.Next(it); {
		cur := exp.qstore.Quad(it.Result())
		if _, ok := seen[cur.Subject]; !ok {
			exp.Write("  node\n  [\n    id ")
			seen[cur.Subject] = id
			exp.Write(strconv.FormatInt(int64(id), 10))
			exp.Write("\n    label ")
			exp.WriteEscString(cur.Subject)
			exp.Write("\n  ]\n")
			id++
		}
		if _, ok := seen[cur.Object]; !ok {
			exp.Write("  node\n  [\n    id ")
			seen[cur.Object] = id
			exp.Write(strconv.FormatInt(int64(id), 10))
			exp.Write("\n    label ")
			exp.WriteEscString(cur.Object)
			exp.Write("\n  ]\n")
			id++
		}
		exp.count++
	}

	exp.qi.Reset()
	for it := exp.qi; graph.Next(it); {
		cur := exp.qstore.Quad(it.Result())
		exp.Write("  edge\n  [\n    source ")
		exp.Write(strconv.FormatInt(int64(seen[cur.Subject]), 10))
		exp.Write("\n    target ")
		exp.Write(strconv.FormatInt(int64(seen[cur.Object]), 10))
		exp.Write("\n    label ")
		exp.WriteEscString(cur.Predicate)
		exp.Write("\n  ]\n")
		exp.count++
	}
	exp.Write("]\n")
}

//experimental
func (exp *Exporter) ExportGraphml() {
	var seen map[string]bool // eliminate this for large databases

	exp.Write("<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n")
	exp.Write("<graphml xmlns=\"http://graphml.graphdrawing.org/xmlns\"\n")
	exp.Write("   xmlns:xsi=\"http://www.w3.org/2001/XMLSchema-instance\"\n")
	exp.Write("   xsi:schemaLocation=\"http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd\">\n")
	exp.Write("  <graph id=\"Caylay\" edgedefault=\"directed\">\n")

	seen = make(map[string]bool)
	exp.qi.Reset()
	for it := exp.qi; graph.Next(it); {
		cur := exp.qstore.Quad(it.Result())
		if found := seen[cur.Subject]; !found {
			seen[cur.Subject] = true
			exp.Write("    <node id=")
			exp.WriteEscString(cur.Subject)
			exp.Write(" />\n")
		}
		if found := seen[cur.Object]; !found {
			seen[cur.Object] = true
			exp.Write("    <node id=")
			exp.WriteEscString(cur.Object)
			exp.Write(" />\n")
		}
		exp.count++
	}

	exp.qi.Reset()
	for it := exp.qi; graph.Next(it); {
		cur := exp.qstore.Quad(it.Result())
		exp.Write("    <edge source=")
		exp.WriteEscString(cur.Subject)
		exp.Write(" target=")
		exp.WriteEscString(cur.Object)
		exp.Write(">\n")
		exp.Write("      <data key=\"predicate\">")
		exp.Write(cur.Predicate)
		exp.Write("</data>\n    </edge>\n")
		exp.count++
	}
	exp.Write("  </graph>\n</graphml>\n")
}

func runTopLevel(path *Path) []string {
	var out []string
	it := path.BuildIterator()
	it, _ = it.Optimize()
	for graph.Next(it) {
		v := path.qs.NameOf(it.Result())
		out = append(out, v)
	}
	return out
}

func (it *Comparison) Next() bool {
	for graph.Next(it.subIt) {
		val := it.subIt.Result()
		if it.doComparison(val) {
			it.result = val
			return true
		}
	}
	it.err = it.subIt.Err()
	return false
}

// Next advances the Limit iterator. It will stop iteration if limit was reached.
func (it *Limit) Next() bool {
	graph.NextLogIn(it)
	if it.limit > 0 && it.count >= it.limit {
		return graph.NextLogOut(it, nil, false)
	}
	if graph.Next(it.primaryIt) {
		curr := it.primaryIt.Result()
		it.count++
		return graph.NextLogOut(it, curr, true)
	}
	return graph.NextLogOut(it, nil, false)
}

// Returns advances the And iterator. Because the And is the intersection of its
// subiterators, it must choose one subiterator to produce a candidate, and check
// this value against the subiterators. A productive choice of primary iterator
// is therefore very important.
func (it *And) Next() bool {
	graph.NextLogIn(it)
	it.runstats.Next += 1
	for graph.Next(it.primaryIt) {
		curr := it.primaryIt.Result()
		if it.subItsContain(curr, nil) {
			it.result = curr
			return graph.NextLogOut(it, curr, true)
		}
	}
	it.err = it.primaryIt.Err()
	return graph.NextLogOut(it, nil, false)
}