thalassa/lib/scriptpp/scrsort.cpp

// +-------------------------------------------------------------------------+
// |                     Script Plus Plus vers. 0.3.72                       |
// | Copyright (c) Andrey V. Stolyarov  <croco at croco dot net>  2003--2023 |
// | ----------------------------------------------------------------------- |
// | This is free software.  Permission is granted to everyone to use, copy  |
// |        or modify this software under the terms and conditions of        |
// |                 GNU LESSER GENERAL PUBLIC LICENSE, v. 2.1               |
// |     as published by Free Software Foundation (see the file LGPL.txt)    |
// |                                                                         |
// | Please visit http://www.croco.net/software/scriptpp to get a fresh copy |
// | ----------------------------------------------------------------------- |
// |   This code is provided strictly and exclusively on the "AS IS" basis.  |
// | !!! THERE IS NO WARRANTY OF ANY KIND, NEITHER EXPRESSED NOR IMPLIED !!! |
// +-------------------------------------------------------------------------+




#include "scrvar.hpp"
#include "scrvect.hpp"

#include "scrsort.hpp"

#define SWAP(v, a, b) \
    do { ScriptVariable t = v[a]; v[a] = v[b]; v[b] = t; } while(0)



    // the less argument can be NULL (0)
static void
scr_bubblesort(ScriptVector &v, int left, int right, scriptpp_cmpfunc less)
{
    if(right - left < 1)
        return;
    int i, j;
    for(i = right; i > left; i--) {
        int cnt = 0;
        for(j = left; j < i; j++)
            if(less ? less(v[j+1], v[j]) : v[j] > v[j+1]) {
                SWAP(v, j, j+1);
                cnt++;
            }
        if(!cnt)
            break;
    }
}

static void
do_scr_quicksort(ScriptVector &v, int left, int right, scriptpp_cmpfunc less)
{
    int i, j;

    if(right - left < 15) {
        scr_bubblesort(v, left, right, less);
        return;
    }
    ScriptVariable pivot = v[(left+right)/2];
    i = left;
    j = right;
    for(;;) {
        while(less ? less(v[i], pivot) : v[i] < pivot)
            i++;
        while(less ? less(pivot, v[j]) : v[j] > pivot)
            j--;
        if(i >= j) {
            do_scr_quicksort(v, left, j, less);
            do_scr_quicksort(v, j+1, right, less);
            return;
        }
        SWAP(v, i, j);
        i++;
        j--;
    }
}

void scriptpp_sort(ScriptVector &v, scriptpp_cmpfunc less)
{
    int vl = v.Length();
    do_scr_quicksort(v, 0, vl-1, less);
}

void
scriptpp_sort_range(ScriptVector &v, int idx, int len, scriptpp_cmpfunc less)
{
    int vl = v.Length();
    if(idx >= vl)
        return;
    if(idx + len > vl)
        len = vl - idx;
    do_scr_quicksort(v, idx, len-1, less);
}

#ifdef SCRSORT_TEST

#include <stdio.h>
#include "cmd.hpp"

bool xless(const ScriptVariable &a, const ScriptVariable &b)
{
    int al = a.Length();
    int bl = b.Length();
    if(al != bl)
        return al < bl;
    return a < b;
}

int main(int argc, const char * const *argv)
{
     bool use_xless = false;
     if(argc > 1) {
         if(argc > 2 || ScriptVariable(argv[1]) != "x") {
             fprintf(stderr, "Use: scsort [x] (x to use alternate less)\n");
             return 1;
         }
         use_xless = true;
     }

     ScriptVector v;
     ScriptVariable s;
     ReadStream rd;
     rd.FDOpen(0);
     while(rd.ReadLine(s))
         v.AddItem(s);
     scriptpp_sort(v, use_xless ? xless : 0);
     int i, vl;
     vl = v.Length();
     for(i = 0; i < vl; i++)
         printf("%s\n", v[i].c_str());
     return 0;
}

#endif  // SCRSORT_TEST