package main

import "bufio"
import "os"
import "container/vector"
import "sort"
import "strings"
import "fmt"


func atoi(s string) (v int) {
    for i := 0; i < len(s); i++ {
        v = v * 10 + int(s[i] - '0')
    }
    return
}

type bufferedLine struct {
    ch <-chan string
    line string
    fields []string
}

type sortableLines struct { lines []bufferedLine };

var keys vector.IntVector
var field_separator string

func (this sortableLines) Len() int {
    ln := len(this.lines)
    return ln
}

func (this sortableLines) Less(i, j int) bool {
    return lessFields(this.lines[i].fields, this.lines[j].fields)
}

func lessFields(fi, fj []string) bool {
    for k := 0; k < len(keys); k++ {
        kk := keys[k];
        if kk > len(fi) {
            return false
        } else if kk > len(fj) {
            return true
        } else if fi[kk] < fj[kk] {
            return true
        } else if fi[kk] > fj[kk] {
            return false
        }
    }
    return false
}

func (this sortableLines) Swap(i, j int) {
    this.lines[i], this.lines[j] = this.lines[j], this.lines[i]
}

func (this *sortableLines) Push(line string) {
    fields := strings.Split(line, field_separator, 0)
    if (cap(this.lines) > len(this.lines)) {
        this.lines = this.lines[0:len(this.lines)+1];
    } else {
        newlines := make([]bufferedLine, len(this.lines)+1, len(this.lines)*3/2+32)
        for i := range this.lines {
            newlines[i] = this.lines[i]
        }
        this.lines = newlines
    }
    this.lines[len(this.lines)-1].line = line
    this.lines[len(this.lines)-1].fields = fields
}

func (this sortableLines) At(i int) string {
    return this.lines[i].line
}




func main() {
    var processes int

    for i := 1; i < len(os.Args); i++ {
        switch os.Args[i] {
            case "-k":
                keys_s := strings.Split(os.Args[i+1], ",", 0)
                for j := 0; j < len(keys_s); j++ {
                    keys.Push(atoi(keys_s[j]))
                }
                i++
            case "-p": 
                processes = atoi(os.Args[i+1])
                i++
            case "-t":
                field_separator = os.Args[i+1];
                i++
            default:
                panic ("unexpected argument ", os.Args[i])
        }
    }

    in := bufio.NewReader(os.Stdin)
    var v sortableLines
    for {
        line, err := in.ReadString('\n');
        if err == os.EOF { break }
        v.Push(line)
    }
    wait_chan := make(chan int)
    go sorter(v.lines[0:len(v.lines)], processes, wait_chan)
    <- wait_chan

    for i := 0; i < v.Len(); i++ {
        line := v.At(i)
        os.Stdout.WriteString(line)
    }

}


func sorter (buf []bufferedLine, processes int, ch chan int) {
    if (processes >= 2) {
        fmt.Fprint(os.Stderr, "splitting and sorting ", len(buf), " lines (", processes, ")\n");
        half := len(buf)/2
        ch1 := make(chan int)
        ch2 := make(chan int)
        go sorter(buf[0:half], processes/2, ch1)
        go sorter(buf[half:len(buf)], processes/2, ch2)
        fmt.Fprint(os.Stderr, "waiting\n");
        <- ch1
        <- ch2
        fmt.Fprint(os.Stderr, "merging ", len(buf), " lines\n");
        merged := make([]bufferedLine, len(buf));
        i1 := 0;
        i2 := half;
        im := 0;
        for  {
            if i1 >= half || i2 >= len(buf) { break }
            if lessFields(buf[i1].fields, buf[i2].fields) {
                merged[im] = buf[i1]
                im++
                i1++
            } else {
                merged[im] = buf[i2]
                im++
                i2++
            }
        }
        for i1 < half {
            merged[im] = buf[i1]
            im++
            i1++
        }
        for i2 < len(buf) {
            merged[im] = buf[i2]
            im++
            i2++
        }
        for i := range buf {
            buf[i] = merged[i]
        }
    } else {
        fmt.Fprint(os.Stderr, "sorting ", len(buf), " lines\n");
        var v sortableLines;
        v.lines = buf;
        sort.Sort(v)
    }
    fmt.Fprint(os.Stderr, "sorting done\n");
    ch <- 1
    close(ch)
    
}