// Copyright 2016 Attic Labs, Inc. All rights reserved.
// Licensed under the Apache License, version 2.0:
// http://www.apache.org/licenses/LICENSE-2.0

package types

import (
	"crypto/sha1"
	"sort"

	"github.com/attic-labs/noms/go/d"
)

type orderedSequence interface {
	sequence
	getKey(idx int) orderedKey
}

type orderedMetaSequence struct {
	metaSequenceObject
}

func newSetMetaSequence(tuples metaSequenceData, vr ValueReader) orderedMetaSequence {
	ts := make([]*Type, len(tuples))
	for i, mt := range tuples {
		// Ref<Set<T>>
		ts[i] = mt.ref.Type().Desc.(CompoundDesc).ElemTypes[0].Desc.(CompoundDesc).ElemTypes[0]
	}
	t := MakeSetType(MakeUnionType(ts...))
	return newOrderedMetaSequence(tuples, t, vr)
}

func newMapMetaSequence(tuples metaSequenceData, vr ValueReader) orderedMetaSequence {
	kts := make([]*Type, len(tuples))
	vts := make([]*Type, len(tuples))
	for i, mt := range tuples {
		// Ref<Map<K, V>>
		ets := mt.ref.Type().Desc.(CompoundDesc).ElemTypes[0].Desc.(CompoundDesc).ElemTypes
		kts[i] = ets[0]
		vts[i] = ets[1]
	}
	t := MakeMapType(MakeUnionType(kts...), MakeUnionType(vts...))
	return newOrderedMetaSequence(tuples, t, vr)
}

func newOrderedMetaSequence(tuples metaSequenceData, t *Type, vr ValueReader) orderedMetaSequence {
	leafCount := uint64(0)
	for _, mt := range tuples {
		leafCount += mt.numLeaves
	}

	return orderedMetaSequence{
		metaSequenceObject{tuples, t, vr, leafCount},
	}
}

func (oms orderedMetaSequence) getKey(idx int) orderedKey {
	return oms.tuples[idx].key
}

func (oms orderedMetaSequence) getCompareFn(other sequence) compareFn {
	ooms := other.(orderedMetaSequence)
	return func(idx, otherIdx int) bool {
		return oms.tuples[idx].ref.TargetHash() == ooms.tuples[otherIdx].ref.TargetHash()
	}
}

func newCursorAtValue(seq orderedSequence, val Value, forInsertion bool, last bool) *sequenceCursor {
	var key orderedKey
	if val != nil {
		key = newOrderedKey(val)
	}
	return newCursorAt(seq, key, forInsertion, last)
}

func newCursorAt(seq orderedSequence, key orderedKey, forInsertion bool, last bool) *sequenceCursor {
	var cur *sequenceCursor
	for {
		idx := 0
		if last {
			idx = -1
		}
		seqIsMeta := isMetaSequence(seq)
		cur = newSequenceCursor(cur, seq, idx)
		if key != emptyKey {
			if !seekTo(cur, key, forInsertion && seqIsMeta) {
				return cur
			}
		}

		cs := cur.getChildSequence()
		if cs == nil {
			break
		}
		seq = cs.(orderedSequence)
	}

	d.Chk.True(cur != nil)
	return cur
}

func seekTo(cur *sequenceCursor, key orderedKey, lastPositionIfNotFound bool) bool {
	seq := cur.seq.(orderedSequence)

	cur.idx = sort.Search(seq.seqLen(), func(i int) bool {
		return !seq.getKey(i).Less(key)
	})

	if cur.idx == seq.seqLen() && lastPositionIfNotFound {
		d.Chk.True(cur.idx > 0)
		cur.idx--
	}

	return cur.idx < seq.seqLen()
}

// Gets the key used for ordering the sequence at current index.
func getCurrentKey(cur *sequenceCursor) orderedKey {
	seq, ok := cur.seq.(orderedSequence)
	d.Chk.True(ok, "need an ordered sequence here")
	return seq.getKey(cur.idx)
}

func newOrderedMetaSequenceBoundaryChecker() boundaryChecker {
	return newBuzHashBoundaryChecker(orderedSequenceWindowSize, sha1.Size, objectPattern, func(item sequenceItem) []byte {
		digest := item.(metaTuple).ref.TargetHash().Digest()
		return digest[:]
	})
}

// If |vw| is not nil, chunks will be eagerly written as they're created. Otherwise they are
// written when the root is written.
func newOrderedMetaSequenceChunkFn(kind NomsKind, vr ValueReader, vw ValueWriter) makeChunkFn {
	return func(items []sequenceItem) (metaTuple, sequence) {
		tuples := make(metaSequenceData, len(items))
		numLeaves := uint64(0)

		for i, v := range items {
			mt := v.(metaTuple)
			tuples[i] = mt // chunk is written when the root sequence is written
			numLeaves += mt.numLeaves
		}

		var metaSeq orderedMetaSequence
		var col Collection
		if kind == SetKind {
			metaSeq = newSetMetaSequence(tuples, vr)
			col = newSet(metaSeq)
		} else {
			d.Chk.True(MapKind == kind)
			metaSeq = newMapMetaSequence(tuples, vr)
			col = newMap(metaSeq)
		}

		if vw != nil {
			return newMetaTuple(vw.WriteValue(col), tuples.last().key, numLeaves, nil), metaSeq
		}
		return newMetaTuple(NewRef(col), tuples.last().key, numLeaves, col), metaSeq
	}
}
