package main

import "fmt"

type TimeBucket struct {
	entries []TimeEntry
}

type TimeEntry struct {
	time  int
	value string
}

type TimeMap struct {
	buckets map[string]*TimeBucket
}

func (bucket *TimeBucket) insertOrdered(time int, value string) {
	// 1. Binary Search to find the correct index
	index := bucket.insertionIndex(time) // This is exactly where the item needs to go

	// 2. Slice Primitives to perform the insertion
	// First, append a zero-value element to grow the slice safely (handles allocation)
	bucket.entries = append(bucket.entries, TimeEntry{})

	// Next, copy the elements over by 1 position to the right to make room
	copy(bucket.entries[index+1:], bucket.entries[index:])

	// Finally, drop the new item into the open slot
	bucket.entries[index] = TimeEntry{
		time:  time,
		value: value,
	}
}

func (bucket *TimeBucket) insertionIndex(time int) int {
	low, high := 0, len(bucket.entries)
	for low < high {
		// Calculate mid carefully to prevent integer overflow
		mid := low + (high-low)/2

		if bucket.entries[mid].time <= time {
			low = mid + 1
		} else {
			high = mid
		}
	}

	return low
}

func Constructor() TimeMap {
	return TimeMap{
		buckets: map[string]*TimeBucket{},
	}
}

func (this *TimeMap) Set(key string, value string, timestamp int) {
	bucket, okay := this.buckets[key]
	if !okay {
		this.buckets[key] = &TimeBucket{
			entries: []TimeEntry{},
		}
		bucket = this.buckets[key]
	}

	bucket.insertOrdered(timestamp, value)
}

func (this *TimeMap) Get(key string, timestamp int) string {
	bucket, okay := this.buckets[key]
	if !okay {
		return ""
	}

	idx := bucket.insertionIndex(timestamp)
	if idx > 0 {
		idx = idx - 1
	}

	entry := bucket.entries[idx]
	if entry.time > timestamp {
		return ""
	} else {
		return entry.value
	}
}

func main() {
	timeMap := Constructor()
	timeMap.Set("foo", "bar", 1)       // store the key "foo" and value "bar" along with timestamp = 1.
	fmt.Println(timeMap.Get("foo", 1)) // return "bar"
	fmt.Println(timeMap.Get("foo", 3)) // return "bar", since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is "bar".
	timeMap.Set("foo", "bar2", 4)      // store the key "foo" and value "bar2" along with timestamp = 4.
	fmt.Println(timeMap.Get("foo", 4)) // return "bar2"
	fmt.Println(timeMap.Get("foo", 5)) // return "bar2"
}