// tiled-0002-test.cpp
// CWE-407 unit test: mapobjectmodel.cpp classChanged
// QList<Object*>.contains(tile) inside nested loop over all map objects = O(MapObjects * ChangedTiles)
// Fix: QSet lookup O(1) per item

#include <QList>
#include <QSet>
#include <QElapsedTimer>
#include <cstdio>
#include <cassert>

// Simulate: for each map object, check if its tile is in the changed-objects list
static int classChanged_defective(const QList<void*> &allMapObjects,
                                   const QList<void*> &objectTiles,
                                   const QList<void*> &changedObjects) {
    int count = 0;
    for (int i = 0; i < allMapObjects.size(); ++i) {
        if (changedObjects.contains(objectTiles[i]))  // O(N) per call
            count++;
    }
    return count;
}

static int classChanged_fixed(const QList<void*> &allMapObjects,
                               const QList<void*> &objectTiles,
                               const QList<void*> &changedObjects) {
    const QSet<void*> objectSet(changedObjects.begin(), changedObjects.end());
    int count = 0;
    for (int i = 0; i < allMapObjects.size(); ++i) {
        if (objectSet.contains(objectTiles[i]))  // O(1) per call
            count++;
    }
    return count;
}

int main() {
    const int MAP_OBJECTS = 2000;
    const int CHANGED_TILES = 500;

    QList<void*> tiles;
    for (int i = 0; i < CHANGED_TILES; ++i)
        tiles.append(reinterpret_cast<void*>(static_cast<uintptr_t>(i + 1)));

    QList<void*> allMapObjects;
    QList<void*> objectTiles;
    for (int i = 0; i < MAP_OBJECTS; ++i) {
        allMapObjects.append(reinterpret_cast<void*>(static_cast<uintptr_t>(i + 10000)));
        // Half the objects reference changed tiles
        objectTiles.append(tiles[i % CHANGED_TILES]);
    }

    const int ITERS = 500;

    QElapsedTimer timer;
    timer.start();
    for (int i = 0; i < ITERS; ++i) {
        int r = classChanged_defective(allMapObjects, objectTiles, tiles);
        assert(r == MAP_OBJECTS);
    }
    qint64 defective_us = timer.nsecsElapsed() / 1000;

    timer.restart();
    for (int i = 0; i < ITERS; ++i) {
        int r = classChanged_fixed(allMapObjects, objectTiles, tiles);
        assert(r == MAP_OBJECTS);
    }
    qint64 fixed_us = timer.nsecsElapsed() / 1000;

    double ratio = (double)defective_us / (double)fixed_us;

    printf("tiled-0002 CWE-407 classChanged QList.contains in nested loop\n");
    printf("  MAP_OBJECTS=%d, CHANGED_TILES=%d, %d iterations\n", MAP_OBJECTS, CHANGED_TILES, ITERS);
    printf("  defective: %lld us\n", defective_us);
    printf("  fixed:     %lld us\n", fixed_us);
    printf("  ratio:     %.1fx\n", ratio);
    printf("  %s\n", ratio >= 2.0 ? "PASS" : "FAIL");

    return ratio >= 2.0 ? 0 : 1;
}