package ksuid

import (
	
	
)

// CompressedSet is an immutable data type which stores a set of KSUIDs.
type CompressedSet []byte

// Iter returns an iterator that produces all KSUIDs in the set.
func ( CompressedSet) () CompressedSetIter {
	return CompressedSetIter{
		content: []byte(),
	}
}

// String satisfies the fmt.Stringer interface, returns a human-readable string
// representation of the set.
func ( CompressedSet) () string {
	 := bytes.Buffer{}
	.WriteByte('[')
	.writeTo(&)
	.WriteByte(']')
	return .String()
}

// String satisfies the fmt.GoStringer interface, returns a Go representation of
// the set.
func ( CompressedSet) () string {
	 := bytes.Buffer{}
	.WriteString("ksuid.CompressedSet{")
	.writeTo(&)
	.WriteByte('}')
	return .String()
}

func ( CompressedSet) ( *bytes.Buffer) {
	 := [27]byte{}

	for ,  := 0, .Iter(); .Next(); ++ {
		if  != 0 {
			.WriteString(", ")
		}
		.WriteByte('"')
		.KSUID.Append([:0])
		.Write([:])
		.WriteByte('"')
	}
}

// Compress creates and returns a compressed set of KSUIDs from the list given
// as arguments.
func ( ...KSUID) CompressedSet {
	 := 1 + byteLength + (len() / 5)
	 := make([]byte, 0, )
	return AppendCompressed(, ...)
}

// AppendCompressed uses the given byte slice as pre-allocated storage space to
// build a KSUID set.
//
// Note that the set uses a compression technique to store the KSUIDs, so the
// resuling length is not 20 x len(ids). The rule of thumb here is for the given
// byte slice to reserve the amount of memory that the application would be OK
// to waste.
func ( []byte,  ...KSUID) CompressedSet {
	if len() != 0 {
		if !IsSorted() {
			Sort()
		}
		 := makeUint128(0, 1)

		// The first KSUID is always written to the set, this is the starting
		// point for all deltas.
		 = append(, byte(rawKSUID))
		 = append(, [0][:]...)

		 := [0].Timestamp()
		 := [0]
		 := uint128Payload([0])

		for  := 1;  != len(); ++ {
			 := []

			if  ==  {
				continue
			}

			 := .Timestamp()
			 := uint128Payload()

			if  !=  {
				 :=  - 
				 := varintLength32()

				 = append(, timeDelta|byte())
				 = appendVarint32(, , )
				 = append(, [timestampLengthInBytes:]...)

				 = 
			} else {
				 := sub128(, )

				if  !=  {
					 := varintLength128()

					 = append(, payloadDelta|byte())
					 = appendVarint128(, , )
				} else {
					,  := rangeLength([+1:], , , )
					 := uint64( + 1)
					 := varintLength64()

					 = append(, payloadRange|byte())
					 = appendVarint64(, , )

					 += 
					 = []
					 = uint128Payload()
				}
			}

			 = 
			 = 
		}
	}
	return CompressedSet()
}

func rangeLength( []KSUID,  uint32,  KSUID,  uint128) ( int,  int) {
	 := makeUint128(0, 1)

	for  := range  {
		 := []

		if  ==  {
			continue
		}

		if .Timestamp() !=  {
			 = 
			return
		}

		 := uint128Payload()

		if sub128(, ) !=  {
			 = 
			return
		}

		 = 
		 = 
		++
	}

	 = len()
	return
}

func appendVarint128( []byte,  uint128,  int) []byte {
	 := .bytes()
	return append(, [len()-:]...)
}

func appendVarint64( []byte,  uint64,  int) []byte {
	 := [8]byte{}
	binary.BigEndian.PutUint64([:], )
	return append(, [len()-:]...)
}

func appendVarint32( []byte,  uint32,  int) []byte {
	 := [4]byte{}
	binary.BigEndian.PutUint32([:], )
	return append(, [len()-:]...)
}

func varint128( []byte) uint128 {
	 := [16]byte{}
	copy([16-len():], )
	return makeUint128FromPayload([:])
}

func varint64( []byte) uint64 {
	 := [8]byte{}
	copy([8-len():], )
	return binary.BigEndian.Uint64([:])
}

func varint32( []byte) uint32 {
	 := [4]byte{}
	copy([4-len():], )
	return binary.BigEndian.Uint32([:])
}

func varintLength128( uint128) int {
	if [1] != 0 {
		return 8 + varintLength64([1])
	}
	return varintLength64([0])
}

func varintLength64( uint64) int {
	switch {
	case ( & 0xFFFFFFFFFFFFFF00) == 0:
		return 1
	case ( & 0xFFFFFFFFFFFF0000) == 0:
		return 2
	case ( & 0xFFFFFFFFFF000000) == 0:
		return 3
	case ( & 0xFFFFFFFF00000000) == 0:
		return 4
	case ( & 0xFFFFFF0000000000) == 0:
		return 5
	case ( & 0xFFFF000000000000) == 0:
		return 6
	case ( & 0xFF00000000000000) == 0:
		return 7
	default:
		return 8
	}
}

func varintLength32( uint32) int {
	switch {
	case ( & 0xFFFFFF00) == 0:
		return 1
	case ( & 0xFFFF0000) == 0:
		return 2
	case ( & 0xFF000000) == 0:
		return 3
	default:
		return 4
	}
}

const (
	rawKSUID     = 0
	timeDelta    = (1 << 6)
	payloadDelta = (1 << 7)
	payloadRange = (1 << 6) | (1 << 7)
)

// CompressedSetIter is an iterator type returned by Set.Iter to produce the
// list of KSUIDs stored in a set.
//
// Here's is how the iterator type is commonly used:
//
//	for it := set.Iter(); it.Next(); {
//		id := it.KSUID
//		// ...
//	}
//
// CompressedSetIter values are not safe to use concurrently from multiple
// goroutines.
type CompressedSetIter struct {
	// KSUID is modified by calls to the Next method to hold the KSUID loaded
	// by the iterator.
	KSUID KSUID

	content []byte
	offset  int

	seqlength uint64
	timestamp uint32
	lastValue uint128
}

// Next moves the iterator forward, returning true if there a KSUID was found,
// or false if the iterator as reached the end of the set it was created from.
func ( *CompressedSetIter) () bool {
	if .seqlength != 0 {
		 := incr128(.lastValue)
		.KSUID = .ksuid(.timestamp)
		.seqlength--
		.lastValue = 
		return true
	}

	if .offset == len(.content) {
		return false
	}

	 := .content[.offset]
	.offset++

	const  = rawKSUID | timeDelta | payloadDelta | payloadRange
	 := int() & 
	 := int() & ^

	switch  {
	case rawKSUID:
		 := .offset
		 :=  + byteLength

		copy(.KSUID[:], .content[:])

		.offset = 
		.timestamp = .KSUID.Timestamp()
		.lastValue = uint128Payload(.KSUID)

	case timeDelta:
		 := .offset
		 :=  + 
		 :=  + payloadLengthInBytes

		.timestamp += varint32(.content[:])

		binary.BigEndian.PutUint32(.KSUID[:timestampLengthInBytes], .timestamp)
		copy(.KSUID[timestampLengthInBytes:], .content[:])

		.offset = 
		.lastValue = uint128Payload(.KSUID)

	case payloadDelta:
		 := .offset
		 :=  + 

		 := varint128(.content[:])
		 := add128(.lastValue, )

		.KSUID = .ksuid(.timestamp)
		.offset = 
		.lastValue = 

	case payloadRange:
		 := .offset
		 :=  + 

		 := incr128(.lastValue)
		.KSUID = .ksuid(.timestamp)
		.seqlength = varint64(.content[:])
		.offset = 
		.seqlength--
		.lastValue = 

	default:
		panic("KSUID set iterator is reading malformed data")
	}

	return true
}