class_Sort-AHK2.ahk

#Requires AutoHotkey v2.0-

; #IncludeAgain *i %A_ScriptDir%\..\lib\Counter.ahk

class Sorts {

    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    ; --- Global Variables --- ;
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    
    static SHOW_ARROWS := 0
    static ALIGN_LEN := 6
    
    ;;;;;;;;;;;;;;;;;;;;;
    ; --- Functions --- ;
    ;;;;;;;;;;;;;;;;;;;;;
    
    StringToSortedListString(str, comparator, type := "MERGE", default_delim := "", width := 0, tracking := 0) {
        if (tracking) {
            TrackingCounter.Reset()
            TrackingCounter.SetSegmentLength(width)
        }
        
        list := Sorts.GetList(str, list, delim)
        list := Sorts.SortBy(list, comparator, type, tracking)
        
        if (width > 0)
            str := TrackingCounter.GetIndent() . Sorts.ListToAlignedString(list, width)
        else
            str := Sorts.ListToDelimitedString(list, (default_delim = "") ? delim : default_delim)
            
        if (tracking)
            str := TrackingCounter.NewNumberLine() . "`r`n" . str . "`r`n`r`n" . TrackingCounter.GetTrackingString()
            
        return str
    }
    
    SortAscending(ByRef list, type := "MERGE") {
        return Sorts.__Sort(list, 1, list.MaxIndex(), "CompareAscending", type, tracking)
    }
    
    SortDescending(ByRef list, type := "MERGE") {
        return Sorts.__Sort(list, 1, list.MaxIndex(), "CompareDescending", type, tracking)
    }
    
    SortBy(ByRef list, comparator, type := "MERGE", tracking := 1) {
        return Sorts.__Sort(list, 1, list.MaxIndex(), comparator, type, tracking)
    }
    
    CompareAscending(left, right) {
        what := ""
        
        if (left < right) {
            what := -1
        } else if (left > right) {
            what := 1
        } else {
            what := 0
        }
        
        return what
    }
    
    CompareDescending(left, right) {
        return Sorts.CompareAscending(right, left)
    }
    
    Swap(ByRef list, first, secnd, tracking) {
        if (tracking)
            TrackingCounter.GetTrackingCounters()[1].AddComment(Format(" Swap {1} and {2}.", first, secnd))
            
        what := list[first]
        list[first] := list[secnd]
        list[secnd] := what
    }
    
    __Sort(ByRef list, start, end, comparator, type, tracking) {
        StringUpper, type, type
        sort_proc := ""
        what := ""
        
        if (type = "MERGE") {
            what := Sorts.__MergeSort(list, start, end, comparator, tracking)
        } else if (type = "LQUICK") {
            what := Sorts.__LomutoQuickSort(list, start, end, comparator, tracking)
        } else if (type = "HQUICK") {
            what := Sorts.__HoareQuickSort(list, start, end, comparator, tracking)
        }
        
        return what
    }
    
    __LomutoQuickSort(ByRef list, start, end, comparator, tracking) {
        if (start < end) {
            pos := Sorts.__LomutoPartition(list, start, end, comparator, tracking)
            Sorts.__LomutoQuickSort(list, start, pos - 1, comparator, tracking)
            Sorts.__LomutoQuickSort(list, pos + 1, end, comparator, tracking)
        }
        
        return list
    }
    
    CName(name, name_with_arrow, show_arrows) {
        return show_arrows ? name_with_arrow : name
    }
    
    __LomutoPartition(ByRef list, start, end, comparator, tracking) {
        global
        
        if (tracking) {
            p := New TrackingCounter(end, "p")
            i := New TrackingCounter(start - 1, Sorts.CName("i", "i->", Sorts.SHOW_ARROWS))
            j := New TrackingCounter(start, Sorts.CName("j", "j->", Sorts.SHOW_ARROWS))
        } else {
            p := New Counter(end)
            i := New Counter(start - 1)
            j := New Counter(start)
        }
        
        pivot := list[p.Get()]
        
        while (j.Get() <= end - 1) {
            if (Sorts.InvokeCompare(comparator, list[j.Get()], pivot) <= 0) {
                i.Increment()
                Sorts.Swap(list, i.Get(), j.Get(), tracking)
            }
            
            j.Increment()
        }
        
        i := i.Get()
        Sorts.Swap(list, i + 1, end, tracking)
        
        if (tracking) {
            TrackingCounter.Consume()
            TrackingCounter.AddCommentLine("")
        }
        
        return i + 1
    }
    
    __HoareQuickSort(ByRef list, start, end, comparator, tracking) {
        if (start < end) {
            pos := Sorts.__HoarePartition(list, start, end, comparator, tracking)
            Sorts.__HoareQuickSort(list, start, pos, comparator, tracking)
            Sorts.__HoareQuickSort(list, pos + 1, end, comparator, tracking)
        }
        
        return list
    }
    
    __HoarePartition(ByRef list, start, end, comparator, tracking) {
        global
        
        if (tracking) {
            p := New TrackingCounter(Floor((start + end)/2), "p")
            i := New TrackingCounter(start - 1, Sorts.CName("i", "i->", Sorts.SHOW_ARROWS))
            j := New TrackingCounter(end + 1, Sorts.CName("j", "<-j", Sorts.SHOW_ARROWS))
        } else {
            p := New Counter(Floor((start + end)/2))
            i := New Counter(start - 1)
            j := New Counter(end + 1)
        }
        
        pivot := list[p.Get()]
        
        loop {
            loop {
                i.Increment()
            } until (Sorts.InvokeCompare(comparator, list[i.Get()], pivot) >= 0)
            
            loop {
                j.Decrement()
            } until (Sorts.InvokeCompare(comparator, list[j.Get()], pivot) <= 0)
            
            if (i.Get() >= j.Get()) {
                j := j.Get()
                
                if (tracking) {
                    TrackingCounter.Consume()
                    TrackingCounter.AddCommentLine("")
                }
                
                return j
            }
            
            Sorts.Swap(list, i.Get(), j.Get(), tracking)
        }
    }
    
    __MergeSort(ByRef list, start, end, comparator, tracking) {
        if (start < end) {
            mid := Floor((start + end)/2)
            Sorts.__MergeSort(list, start, mid, comparator, tracking)
            Sorts.__MergeSort(list, mid + 1, end, comparator, tracking)
            Sorts.__Merge(list, start, mid, end, comparator, tracking)
        }
        
        return list
    }
    
    __Merge(ByRef list, start, mid, end, comparator, tracking) {
        global
        
        if (tracking) {
            cmid := New TrackingCounter(mid, Sorts.CName("m", "m->", Sorts.SHOW_ARROWS))
            cleft := New TrackingCounter(start, Sorts.CName("le", "le->", Sorts.SHOW_ARROWS))
            cright := New TrackingCounter(mid + 1, Sorts.CName("ri", "ri->", Sorts.SHOW_ARROWS))
        } else {
            cmid := New Counter(mid)
            cleft := New Counter(start)
            cright := New Counter(mid + 1)
        }
        
        if (Sorts.InvokeCompare(comparator, list[cmid.Get()], list[cright.Get()]) > 0) {
            while (cleft.Get() <= cmid.Get() and cright.Get() <= end) {
                if (Sorts.InvokeCompare(comparator, list[cleft.Get()], list[cright.Get()]) <= 0) {
                    cleft.Increment()
                } else {
                    if (tracking) {
                        cindex := New TrackingCounter(cright.Get(), Sorts.CName("i", "<-i", Sorts.SHOW_ARROWS))
                        what := list[cright.Get()]
                        cindex.AddComment(Format(" temp <- [{1}]", cright.Get()))
                        
                        while (cindex.Get() <> cleft.Get()) {
                            list[cindex.Get()] := list[cindex.Get() - 1]
                            cindex.AddComment(Format(" <- [{1}]", cindex.Get() - 1))
                            cindex.Decrement()
                        }
                        
                        list[cleft.Get()] := what
                        cindex.AddComment(Format(";  [{1}] <- temp", cleft.Get()))
                        cindex.End()
                    } else {
                        index := cright.Get()
                        what := list[cright.Get()]
                        
                        while (index <> cleft.Get()) {
                            list[index] := list[index - 1]
                            index := index - 1
                        }
                        
                        list[cleft.Get()] := what
                    }
                    
                    cmid.Increment()
                    cleft.Increment()
                    cright.Increment()
                }
            }
        }
        
        if (tracking) {
            TrackingCounter.Consume()
            TrackingCounter.AddCommentLine("")
        }
    }
    
    InvokeCompare(comparator_name, left_arg, right_arg) {
        return Func(comparator_name).Bind(left_arg, right_arg).Call()
    }
    
    AlignItem(payload, width) {
        return Format("{:" width "}", payload)
    }
    
    SublistToAlignedString(list, width, start, end) {
        out_str := ""
        i := start
        
        while (i < end) {
            out_str .= Sorts.AlignItem(list[i], width)
            i := i + 1
        }
        
        if (list.MaxIndex() >= 1)
            out_str .= Sorts.AlignItem(list[i], width)
            
        return out_str
    }
    
    SublistToDelimitedString(list, delim, start, end) {
        out_str := ""
        i := start
        
        while (i < end) {
            out_str .= list[i] . delim
            i := i + 1
        }
        
        if (list.MaxIndex() >= 1)
            out_str .= list[i]
            
        return out_str
    }
    
    ListToAlignedString(list, width) {
        return Sorts.SublistToAlignedString(list, width, 1, list.MaxIndex())
    }
    
    ListToDelimitedString(list, delim) {
        return Sorts.SublistToDelimitedString(list, delim, 1, list.MaxIndex())
    }
    
    GetList(in_str, ByRef list, ByRef delim) {
        word := ""
        
        ; Start a new list
        list := []
        
        ; Get the first word
        next := RegExMatch(in_str, "-\d+|\w+", word)
        
        ; Get the delimiter
        RegExMatch(in_str, "(?<=_|[0-9]|[A-Z]|[a-z])\W+\d?", delim, next + StrLen(word))  ; This is stupid.
        delim := RegExReplace(delim, "-?\d")
        
        while (next <> 0) {
            ; Add word to the list
            list.Push(word)
            
            ; Get next word
            next := RegExMatch(in_str, "-\d+|\w+", word, next + StrLen(word))
        }
        
        return list
    }
}