Keeping coordinates sorted

Question

I have some coordinates (x,y) and I need these coordinates to be sorted and keep them sorted. After I sort them every coordinate change from (x,y) to (x+1,y) or (x-1,y) or (x,y-1) or (x,y+1), so the coordinates are not sorted anymore.

Is there a better way of solving this problem besides, sorting the coordinates, coordinates change, sorting the coordinates again, coordinates change, sorting the coordinates again based on the condition that every coordinate changes with +-1?

Answer 1

A std::set will handle all this for you. In particular, the contents are inherently sorted by the set members' operator< function, so when you insert new items you don't have to do any sorting yourself. The complexity of an insertion is O(log(N)).

As for sorting the coordinates correctly, you can make use of the fact that std::pair defines operator< like so:

If lhs.first<rhs.first, returns true. Otherwise, if rhs.first<lhs.first, returns false. Otherwise, if lhs.second<rhs.second, returns true. Otherwise, returns false.

which is what you say you want.

So, to sum up, you can do:

#include <utility>
#include <set>

using coordinate = std::pair<int, int>;
std::set<coordinate> stored_coordinates;

where the first member of the std::pair representing a coordinate is x and the second is y.

Finally, if you want to associate a data item with each coordinate, use a map instead, with a std::pair as the key.

Answer 2

You can maintain the sorted order when you update the coordinate by moving the coordinate to the correct place after the update.

If you are doing (x+1, y) or (x, y+1) then the coordinate will be somewhere ahead of its current position in the vector. If you are doing (x-1, y) or (x, y-1) then the coordinate will be somewhere behind of its current position in the vector.

(There is also the possibility the coordinate does not need to change position if it is still correct with respect to the other elements in the vector).

Using this, you can search ahead (or behind) for the position where the updated coordinate needs to go. As you search you can copy the elements back (or forward) to close up the gap left behind by your current element.

|   a   |   b   |   c   |   d   |
| {1,1} | {1,2} | {2,0} | {2,2} |

In the above example, consider that we update c to {1,0}. We move backwards, checking c < b, which is true, so we shuffle b forward:

|   a   |       |   b   |   d   |
| {1,1} |       | {1,2} | {2,2} |

We move back again, checking c < a, which is also true, so we shuffle a forward.

|       |   a   |   b   |   d   |
|       | {1,1} | {1,2} | {2,2} |

At this point we have reached the beginning of the vector so we know that c must go in this position.

|   c   |   a   |   b   |   d   |
| {1,0} | {1,1} | {1,2} | {2,2} |

The other terminal case is when c is no longer less than the element you are checking.

This works similarly in the forwards direction.

Some code to demonstrate this idea:

#include <algorithm>
#include <ctime>
#include <iostream>
#include <random>
#include <vector>

struct Point {
    int x;
    int y;

    void Adjust(int i) {
        switch (i) {
            case 0: x++; return;
            case 1: y++; return;
            case 2: x--; return;
            case 3: y--; return;
        }
    }

    bool operator<(const Point & rhs) {
        if (x == rhs.x)
            return y < rhs.y;

        return x < rhs.x;
    }

    bool operator>(const Point & rhs) {
        if (x == rhs.x)
            return y > rhs.y;

        return x > rhs.x;
    }
};

int main() {
    std::vector<Point> points;

    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j)
            points.push_back({i,j});
    }

    std::sort(std::begin(points), std::end(points));

    std::default_random_engine rng{std::time(nullptr)};
    std::uniform_int_distribution<int> distrib{0, 3};

    for (int i = 0; i < 10000; ++i) {
        for (auto iter = std::begin(points); iter != std::end(points); ++iter) {
            auto p = *iter;
            int adjustment = distrib(rng);

            p.Adjust(adjustment);

            auto current = iter;

            if (adjustment < 2) {
                auto next = std::next(current);

                while (next != std::end(points) && p > *next) {
                    *current = *next;
                    current = next;
                    next = std::next(current);
                }

                *current = p;
            }
            else if (current != std::begin(points)) {
                auto prev = std::prev(current);

                while (p < *prev) {
                    *current = *prev;
                    current = prev;

                    if (current != std::begin(points))
                        prev = std::prev(current);
                    else
                        break;
                }

                *current = p;
            }
        }
    }

    for (auto && p : points)
        std::cout << "{" << p.x << "," << p.y << "}\n";

    std::cout << "is_sorted = "
        << std::is_sorted(std::begin(points), std::end(points))
        << std::endl;

    return 0;
}

Live example

Disclaimer: I haven't measured the performance of this solution. It may be slower than just sorting the vector after all the updates due to the shuffling that happens for every element update.