package main

import (
    "fmt"
    "sort"
)

// PairKeyValue 定義鍵值對結(jié)構(gòu)體
type PairKeyValue[K comparable, V any] struct {
    Key   K
    Value V
}

// PairKeyValueSlice 定義可排序的鍵值對切片
type PairKeyValueSlice[K comparable, V any] struct {
    data []PairKeyValue[K, V]
    less func(a, b K) bool // 比較函數(shù)
}

// Len 實(shí)現(xiàn) sort.Interface 接口
func (pks PairKeyValueSlice[K, V]) Len() int {
    return len(pks.data)
}

// Swap 實(shí)現(xiàn) sort.Interface 接口
func (pks PairKeyValueSlice[K, V]) Swap(i, j int) {
    pks.data[i], pks.data[j] = pks.data[j], pks.data[i]
}

// Less 實(shí)現(xiàn) sort.Interface 接口
func (pks PairKeyValueSlice[K, V]) Less(i, j int) bool {
    return pks.less(pks.data[i].Key, pks.data[j].Key)
}

// NewSortedPairKeyValueSlice 從map創(chuàng)建并排序鍵值對切片
func NewSortedPairKeyValueSlice[K comparable, V any](m map[K]V, less func(a, b K) bool) PairKeyValueSlice[K, V] {
    ps := make([]PairKeyValue[K, V], 0, len(m))
    for k, v := range m {
        ps = append(ps, PairKeyValue[K, V]{Key: k, Value: v})
    }
    sortedSlice := PairKeyValueSlice[K, V]{data: ps, less: less}
    sort.Sort(sortedSlice)
    return sortedSlice
}

// 假設(shè)的自定義Key類型
type MyKey struct {
    ID   int
    Name string
}

// 自定義Key的比較函數(shù)
func LessMyKey(a, b MyKey) bool {
    if a.ID != b.ID {
        return a.ID < b.ID
    }
    return a.Name < b.Name
}

func main() {
    // 示例使用
    myMap := map[MyKey]string{
        {ID: 2, Name: "Beta"}:  "Value B",
        {ID: 1, Name: "Alpha"}: "Value A",
        {ID: 3, Name: "Gamma"}: "Value C",
    }

    // 創(chuàng)建并排序切片
    sortedPairs := NewSortedPairKeyValueSlice(myMap, LessMyKey)

    // 遍歷排序后的切片
    fmt.Println("Sorted iteration:")
    for _, kv := range sortedPairs.data {
        fmt.Printf("  Key: {%d, %s}, Value: %s\n", kv.Key.ID, kv.Key.Name, kv.Value)
    }
}

package main

import (
    "fmt"
    "sort"
    // "github.com/google/btree" // 假設(shè)引入B樹庫
)

// MyKey 自定義鍵類型
type MyKey struct {
    ID   int
    Name string
}

// Less 方法，用于比較MyKey類型，以滿足B樹或排序的需求
func (mk MyKey) Less(other MyKey) bool {
    if mk.ID != other.ID {
        return mk.ID < other.ID
    }
    return mk.Name < other.Name
}

// OrderedMap 定義一個(gè)有序映射接口
type OrderedMap[K comparable, V any] interface {
    Put(key K, value V)
    Get(key K) (V, bool)
    Delete(key K)
    Len() int
    // Ascend 允許按升序遍歷，可以傳入一個(gè)回調(diào)函數(shù)處理每個(gè)鍵值對
    Ascend(iterator func(key K, value V) bool)
    // Descend 允許按降序遍歷
    Descend(iterator func(key K, value V) bool)
    // AscendRange 允許在指定范圍內(nèi)按升序遍歷
    AscendRange(greaterOrEqual, lessThan K, iterator func(key K, value V) bool)
    // ... 其他有序操作，如Min(), Max()
}

// SimpleSortedSliceMap 是一個(gè)基于排序切片的OrderedMap實(shí)現(xiàn)（僅用于演示概念，不推薦生產(chǎn)環(huán)境大規(guī)模使用）
type SimpleSortedSliceMap[K MyKey, V any] struct {
    data []PairKeyValue[K, V]
}

func NewSimpleSortedSliceMap[K MyKey, V any]() *SimpleSortedSliceMap[K, V] {
    return &SimpleSortedSliceMap[K, V]{}
}

func (m *SimpleSortedSliceMap[K, V]) Put(key K, value V) {
    // 在一個(gè)始終保持有序的切片中插入/更新，效率為O(N)
    // 實(shí)際實(shí)現(xiàn)會(huì)使用二分查找找到插入位置，然后插入
    for i, kv := range m.data {
        if kv.Key == key { // 鍵已存在，更新
            m.data[i].Value = value
            return
        }
    }
    // 鍵不存在，插入新元素并保持有序
    m.data = append(m.data, PairKeyValue[K, V]{Key: key, Value: value})
    sort.Slice(m.data, func(i, j int) bool {
        return m.data[i].Key.Less(m.data[j].Key)
    })
}

func (m *SimpleSortedSliceMap[K, V]) Get(key K) (V, bool) {
    // 實(shí)際實(shí)現(xiàn)會(huì)使用二分查找，效率O(log N)
    for _, kv := range m.data {
        if kv.Key == key {
            return kv.Value, true
        }
    }
    var zero V
    return zero, false
}

func (m *SimpleSortedSliceMap[K, V]) Delete(key K) {
    // 實(shí)際實(shí)現(xiàn)會(huì)使用二分查找，然后刪除，效率O(N)
    for i, kv := range m.data {
        if kv.Key == key {
            m.data = append(m.data[:i], m.data[i+1:]...)
            return
        }
    }
}

func (m *SimpleSortedSliceMap[K, V]) Len() int {
    return len(m.data)
}

func (m *SimpleSortedSliceMap[K, V]) Ascend(iterator func(key K, value V) bool) {
    for _, kv := range m.data {
        if !iterator(kv.Key, kv.Value) {
            return
        }
    }
}

func (m *SimpleSortedSliceMap[K, V]) Descend(iterator func(key K, value V) bool) {
    for i := len(m.data) - 1; i >= 0; i-- {
        kv := m.data[i]
        if !iterator(kv.Key, kv.Value) {
            return
        }
    }
}

func (m *SimpleSortedSliceMap[K, V]) AscendRange(greaterOrEqual, lessThan K, iterator func(key K, value V) bool) {
    for _, kv := range m.data {
        // 假設(shè)MyKey有比較方法
        if kv.Key.Less(greaterOrEqual) {
            continue
        }
        if !kv.Key.Less(lessThan) { // kv.Key >= lessThan
            break
        }
        if !iterator(kv.Key, kv.Value) {
            return
        }
    }
}


func main() {
    // 使用自定義的SimpleSortedSliceMap演示
    fmt.Println("--- Using SimpleSortedSliceMap ---")
    osm := NewSimpleSortedSliceMap[MyKey, string]()
    osm.Put(MyKey{ID: 2, Name: "Beta"}, "Value B")
    osm.Put(MyKey{ID: 1, Name: "Alpha"}, "Value A")
    osm.Put(MyKey{ID: 3, Name: "Gamma"}, "Value C")
    osm.Put(MyKey{ID: 1, Name: "Alpha"}, "Updated Value A") // 更新

    fmt.Println("Ascending order:")
    osm.Ascend(func(key MyKey, value string) bool {
        fmt.Printf("  Key: {%d, %s}, Value: %s\n", key.ID, key.Name, value)
        return true // 繼續(xù)遍歷
    })

    fmt.Println("\nDescending order:")
    osm.Descend(func(key MyKey, value string) bool {
        fmt.Printf("  Key: {%d, %s}, Value: %s\n", key.ID, key.Name, value)
        return true
    })

    // 實(shí)際生產(chǎn)中，會(huì)使用如github.com/google/btree這樣的庫
    // var btreeMap *btree.BTree // 偽代碼，實(shí)際使用需初始化并傳入比較函數(shù)
    // btreeMap.ReplaceOrInsert(btree.Item(MyKey{ID: 1, Name: "Alpha"}))
    // btreeMap.Ascend(func(item btree.Item) bool {
    //     kv := item.(PairKeyValue[MyKey, string]) // 類型斷言
    //     fmt.Printf("  Key: {%d, %s}, Value: %s\n", kv.Key.ID, kv.Key.Name, kv.Value)
    //     return true
    // })
}