package main

import (
    "fmt"
    "math"
    "math/rand"
    "time"
)

func main() {
    //1.Build
    tableau := buildYoungTableau(108)
    for _, row := range tableau.array {
        fmt.Println(row)
    }

    //2.Sort
    permutation := tableau.sort()
    fmt.Println(permutation)

    //3.Search
    row, column := tableau.search(74)
    fmt.Println("row column =", row, column)
}

//================
//Data Structure
//================

type T struct {
    x int
    y string
    z []int
}

type D struct {
    t T
}

type Tableau struct {
    ///Underlying representation
    array [][]int
    ///Exact size of array
    size int
    ///dimension * dimension elements
    dimension int
    ///X,Y axis of nearest available slot while increasing and
    ///of last existed slot while decreasing.Its effective scope
    ///is [(0, 0), (dimension, 0)]
    x, y int
}

//================
//Global methods
//================

///build a young tableau with count capacity.O(row^3) in a square where row==column
func buildYoungTableau(count int) *Tableau {
    random := rand.New(rand.NewSource(time.Now().UnixNano()))
    source := random.Perm(count)
    tableau := Tableau{size: count}
    tableau.dimension = int(math.Ceil(math.Sqrt(float64(count))))
    tableau.array = make([][]int, tableau.dimension)
    //Make second dimension
    for i := range tableau.array {
        tableau.array[i] = make([]int, tableau.dimension)
    }

    for _, key := range source {
        tableau.insert(key + 1)
    }
    return &tableau
}

//================
//Tableau methods
//================

func (tableau *Tableau) hasCapacity() bool {
    return tableau.x*tableau.dimension+tableau.y < tableau.size
}

func (tableau *Tableau) increaseDelimitor() bool {
    fmt.Println("increase:", tableau.x, tableau.y)
    if tableau.x >= tableau.dimension {
        return false
    }
    y := (tableau.y + 1) % tableau.dimension
    x := tableau.x
    if y == 0 {
        x = tableau.x + 1
    }
    tableau.x, tableau.y = x, y
    return true
}

func (tableau *Tableau) decreaseDelimitor() bool {
    fmt.Println("decrease:", tableau.x, tableau.y)
    if tableau.x == 0 && tableau.y == 0 {
        return false
    }
    y := (tableau.y + tableau.dimension - 1) % tableau.dimension
    x := tableau.x
    if y == tableau.dimension-1 {
        x = tableau.x - 1
    }
    tableau.x, tableau.y = x, y
    return true
}

///O(row+column)
func (tableau *Tableau) insert(key int) {
    if !tableau.hasCapacity() || key <= 0 {
        panic("Tableau hasn't got enough capacity.")
    }

    tableau.array[tableau.x][tableau.y] = key
    maxX, maxY := tableau.x, tableau.y
    curX, curY := maxX, maxY

    for {
        if curX > 0 && tableau.array[curX-1][curY] > tableau.array[maxX][maxY] {
            maxX = curX - 1
            maxY = curY
        }
        if curY > 0 && tableau.array[curX][curY-1] > tableau.array[maxX][maxY] {
            maxX = curX
            maxY = curY - 1
        }
        if maxX == curX && maxY == curY {
            break
        }
        tableau.array[curX][curY], tableau.array[maxX][maxY] = tableau.array[maxX][maxY], tableau.array[curX][curY]
        curX, curY = maxX, maxY
    }

    tableau.increaseDelimitor()
}

///O(row+column)
func (tableau *Tableau) extractMin() int {
    tableau.decreaseDelimitor()
    target := tableau.array[0][0]
    tableau.array[0][0] = tableau.array[tableau.x][tableau.y]
    tableau.array[tableau.x][tableau.y] = 0
    var minX, minY, curX, curY int

    for {
        if curX < tableau.dimension-1 && tableau.array[curX+1][curY] > 0 && tableau.array[curX+1][curY] < tableau.array[minX][minY] {
            minX = curX + 1
            minY = curY
        }
        if curY < tableau.dimension-1 && tableau.array[curX][curY+1] > 0 && tableau.array[curX][curY+1] < tableau.array[minX][minY] {
            minX = curX
            minY = curY + 1
        }
        if minX == curX && minY == curY {
            break
        }
        tableau.array[curX][curY], tableau.array[minX][minY] = tableau.array[minX][minY], tableau.array[curX][curY]
        curX, curY = minX, minY
    }
    return target
}

///O(row^3) in a square where row==column
func (tableau *Tableau) sort() (permutation []int) {
    permutation = make([]int, tableau.size)
    for i := range permutation {
        permutation[i] = tableau.extractMin()
    }
    return
}

///O(row+column)
func (tableau *Tableau) search(key int) (row, column int) {
    row, column = 0, tableau.dimension-1
    if tableau.array[row][column] == 0 {
        return -1, -1
    }
    for row < tableau.dimension && column >= 0 {
        switch {
        case key > tableau.array[row][column]:
            row++
        case key < tableau.array[row][column]:
            column--
        default:
            return row, column
        }
    }
    return -1, -1
}