Php sorting

[edo494]

Its 2:30 am and my brain is not working basically.

But I am trying to solve this problem(mentioned below) and I thought that it's not worst of ideas to ask for some help on this, since someone will most likely come with a lot better approach for this than me.

The problem is:

Imagine a Mysql table with columns: id, major, whole, name.

Id represents the Primary key.
Major(integer) represents the first clause's number(this is used to display the data ordered by clause in tables, 1 table per 1 primary clause number, and its the easiest approach to do this this way).
Whole(string) represet the whole clause.
Name(string) represents the name of the clause.

The clauses have forms like this: "1.2.1", "1.15", "2.5.4.2" etc.

They are not all of same depth, and there are exceptions like "21." which has no sub-clause.

My problem is that I want to dynamically add a clause to the table, and I want it to make it so that it will get the id of the next element after its parent or sibling clause, for the table reasons. The table has the data sorted, because it has been inserted in such order, e.g. "1", "1.1", "1.2", "1.2.1", "1.2.2"... And I want to keep this order in the table.

I have all the data loaded inside _SESSION, so I dont have to do useless queries to database.

Quite complicated problem, so lets go to example:

Starting at id 1, we have "1.15", "2.", "2.1", "2.2", "2.2.1", "2.3".

Now I say I want to add clause "2.1.1" for instance. So I want the new layout to be, starting at id 1: "1.15", "2.", "2.1", "2.1.1", "2.2", "2.2.1", "2.3".

In other wors, the newly inserted clause shall receive id of the element that was after "2.1", and they should all get their ids increased.

Ids increasing is no problem("UPDATE X SET id=id+1 WHERE Y>Z"), but my problem is to find the id I should put the "2.1" into.

I tried bunch of methods, but all of them failed so far.

Any help is appreciated.

Also if you want to point out just query the table with "ORDER BY", that would work in here, but my table is a bit more complicated, and you will end up with "1.1.2", "1.10", "1.10.1", ..., "1.2"..., because Mysql does sorting of strings in such way.

 

[Xonok]

This sounds very much like a problem that is handled with binary trees.

 

[GhostWolf]

http://php.net/manual/en/function.ksort.php (as in, a normal character based sort).

However I just read the last sentence, and for that you'll need to provide your own sorting function.
Split your key to tokens (e.g. "1.10.2" => ["1", "10", "2"]), then sort by each one.
That is, something along the lines of (and I am not going to write this in PHP, because ew):

function mySorter(a, b) {
    // If you don't want to do the splitting outside:
    // var a = a["myKey"].split(",");
    // var b = b["myKey"].split(",");
    var s = sign(parseInt(b[0]) - parseInt(a[0]));

    if (s !== 0) {
        return s;
    }

    s = sign(parseInt(b[1]) - parseInt(a[1]));
    
    f (s !== 0) {
        return s;
    }

    // And so on, you can do this in a loop if you have an arbitrary number of tokens.
    // In that case, don't forget to handle the case where one token list is longer than the other.

    return 0;
}

And I just read again and noticed you want an insert...so use the above sort with a binary insert (unless your table is smaller than some N, in which case a loop will be faster. For JavaScript, and from my own experiments (although I didn't need any tokenizing, so that would change the results, since the more intensive per-item processing is, the more benefit you'll rip from a binary search (probably?)), N was around 100. This is because the logic of a loop is much simpler, so eventually as N gets smaller, the benefits of a binary search get smaller in comparison to its additional logic. FUN FACTS YOU DON'T CARE ABOUT).