/*
Copyright 2019 The Kubernetes Authors.

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

    http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/

package value

// List represents a list object.
type List interface {
	// Length returns how many items can be found in the map.
	Length() int
	// At returns the item at the given position in the map. It will
	// panic if the index is out of range.
	At(int) Value
	// AtUsing uses the provided allocator and returns the item at the given
	// position in the map. It will panic if the index is out of range.
	// The returned Value should be given back to the Allocator when no longer needed
	// by calling Allocator.Free(Value).
	AtUsing(Allocator, int) Value
	// Range returns a ListRange for iterating over the items in the list.
	Range() ListRange
	// RangeUsing uses the provided allocator and returns a ListRange for
	// iterating over the items in the list.
	// The returned Range should be given back to the Allocator when no longer needed
	// by calling Allocator.Free(Value).
	RangeUsing(Allocator) ListRange
	// Equals compares the two lists, and return true if they are the same, false otherwise.
	// Implementations can use ListEquals as a general implementation for this methods.
	Equals(List) bool
	// EqualsUsing uses the provided allocator and compares the two lists, and return true if
	// they are the same, false otherwise. Implementations can use ListEqualsUsing as a general
	// implementation for this methods.
	EqualsUsing(Allocator, List) bool
}

// ListRange represents a single iteration across the items of a list.
type ListRange interface {
	// Next increments to the next item in the range, if there is one, and returns true, or returns false if there are no more items.
	Next() bool
	// Item returns the index and value of the current item in the range. or panics if there is no current item.
	// For efficiency, Item may reuse the values returned by previous Item calls. Callers should be careful avoid holding
	// pointers to the value returned by Item() that escape the iteration loop since they become invalid once either
	// Item() or Allocator.Free() is called.
	Item() (index int, value Value)
}

var EmptyRange = &emptyRange{}

type emptyRange struct{}

func (_ *emptyRange) Next() bool {
	return false
}

func (_ *emptyRange) Item() (index int, value Value) {
	panic("Item called on empty ListRange")
}

// ListEquals compares two lists lexically.
// WARN: This is a naive implementation, calling lhs.Equals(rhs) is typically the most efficient.
func ListEquals(lhs, rhs List) bool {
	return ListEqualsUsing(HeapAllocator, lhs, rhs)
}

// ListEqualsUsing uses the provided allocator and compares two lists lexically.
// WARN: This is a naive implementation, calling lhs.EqualsUsing(allocator, rhs) is typically the most efficient.
func ListEqualsUsing(a Allocator, lhs, rhs List) bool {
	if lhs.Length() != rhs.Length() {
		return false
	}

	lhsRange := lhs.RangeUsing(a)
	defer a.Free(lhsRange)
	rhsRange := rhs.RangeUsing(a)
	defer a.Free(rhsRange)

	for lhsRange.Next() && rhsRange.Next() {
		_, lv := lhsRange.Item()
		_, rv := rhsRange.Item()
		if !EqualsUsing(a, lv, rv) {
			return false
		}
	}
	return true
}

// ListLess compares two lists lexically.
func ListLess(lhs, rhs List) bool {
	return ListCompare(lhs, rhs) == -1
}

// ListCompare compares two lists lexically. The result will be 0 if l==rhs, -1
// if l < rhs, and +1 if l > rhs.
func ListCompare(lhs, rhs List) int {
	return ListCompareUsing(HeapAllocator, lhs, rhs)
}

// ListCompareUsing uses the provided allocator and compares two lists lexically. The result will be 0 if l==rhs, -1
// if l < rhs, and +1 if l > rhs.
func ListCompareUsing(a Allocator, lhs, rhs List) int {
	lhsRange := lhs.RangeUsing(a)
	defer a.Free(lhsRange)
	rhsRange := rhs.RangeUsing(a)
	defer a.Free(rhsRange)

	for {
		lhsOk := lhsRange.Next()
		rhsOk := rhsRange.Next()
		if !lhsOk && !rhsOk {
			// Lists are the same length and all items are equal.
			return 0
		}
		if !lhsOk {
			// LHS is shorter.
			return -1
		}
		if !rhsOk {
			// RHS is shorter.
			return 1
		}
		_, lv := lhsRange.Item()
		_, rv := rhsRange.Item()
		if c := CompareUsing(a, lv, rv); c != 0 {
			return c
		}
		// The items are equal; continue.
	}
}