Qtree.inl

template <class Object>
Quadtree<Object>::Quadtree(sf::Vector2f startingPoint, float width, float height, Quadtree<Object>* parent) {
    mAABB.left = startingPoint.x;
    mAABB.top =  startingPoint.y;
    mAABB.width =   width;
    mAABB.height = height;

    mDebugRect.setFillColor(sf::Color::Transparent);
    mDebugRect.setOutlineThickness(1.0f);
    mDebugRect.setOutlineColor(sf::Color::Blue);
    mDebugRect.setSize(sf::Vector2f(width-4, height-4));
    mDebugRect.setPosition(startingPoint.x + 2, startingPoint.y+2);

    mParent = parent;
}


template <class Object>
void Quadtree<Object>::removeWrecks()
{
    // Reverse iteration
    for (auto qtree : mChildren)
    {
        qtree->removeWrecks();
    }

    // If the number of objects < 4 and children vector not empty
    if (isMarkedForRemoval())
    {
        // Moving all of the objects of the children to the parent
        for (auto it = mChildren.begin(); it != mChildren.end(); ++it)
        {
            for (auto object : (*it)->mObjects)
            {
                (*it)->mParent->insertObject((object));
            }
            // Deleting child objects
            (*it)->mObjects.clear();
        }
        // Deleting children
        mChildren.clear();
    }
}

template <class Object>
int Quadtree<Object>::getLocalObjectCount()
{
    return mObjects.size();
}

template <class Object>
void Quadtree<Object>::getTotalObjectCount(int& count)
{
    count += getLocalObjectCount();

    for (auto qtree : mChildren)
    {
        qtree->getTotalObjectCount(count);
    }
}

template <class Object>
void Quadtree<Object>::insertObject(Object* object)
{
    mObjects.push_back(object);

    if (getLocalObjectCount() > MAX_OBJECTS && mChildren.empty())
        subdivide();
}


template <class Object>
void Quadtree<Object>::removeObject(Object* object)
{
    // Searching the object to remove, recursively through all of the children, if found, it erases it.
    bool isFound = false;

    if (!mObjects.empty())
    {
        auto found = std::find_if(mObjects.begin(), mObjects.end(), [&](Object* Qobj) {
            if (object == Qobj)
            {
                isFound = true;
                return true;
            }
            else
                return false;
        });

        if (isFound)
            mObjects.erase(found);

    }

    if (!isFound)
    {
        for (auto qtree : mChildren)
        {
            qtree->removeObject(object);
        }
    }
}

template <class Object>
void Quadtree<Object>::updateAll()
{
    // Updating objects position on the quadtree
    for (auto it = mObjects.begin(); it != mObjects.end(); ++it)
    {
        // getObjIndex returns a value which indicates the new position according to object's bounding rect.
        int index = getObjIndex((*it));


        // moving the object if needed

        if (index == -2)
        {
            mParent->insertObject((*it));
        }
        else if (index > -1)
        {
            switch (index)
            {
            case 0:
                mChildren[0]->insertObject((*it));
                break;
            case 1:
                mChildren[1]->insertObject((*it));
                break;
            case 2:
                mChildren[2]->insertObject((*it));
                break;
            case 3:
                mChildren[3]->insertObject((*it));
                break;
            default:
                break;
            }
        }
    }

    // erasing the moved objects from their old position ( = here )
    mObjects.erase(std::remove_if(mObjects.begin(), mObjects.end(), [this](Object* obj){ return getObjIndex(obj) == -2 || getObjIndex(obj) > -1; }), mObjects.end());

    // if marked for removal, we tell the oldest parent to remove his children which are marked for removal
    if (isMarkedForRemoval())
    {
        Quadtree<Object>* oldestParent = new Quadtree<Object>();
        getOldestParent(oldestParent);
        oldestParent->removeWrecks();
    }

    for (auto c : mChildren)
    {
        c->updateAll();
    }

}

template <class Object>
int Quadtree<Object>::getObjIndex(Object* obj)
{
    /*
    -2 = parent
    -1 = this
     0 = upleft
     1 = upright
     2 = downleft
     3 = downright
     */


    std::vector<int> counter;

    if (!mChildren.empty())
    {
        if (mChildren[0]->intersects(obj))
            counter.push_back(0);
        if (mChildren[1]->intersects(obj))
            counter.push_back(1);
        if (mChildren[2]->intersects(obj))
            counter.push_back(2);
        if (mChildren[3]->intersects(obj))
            counter.push_back(3);
    }

    int index;

    // if there is only one intersection, it means that only one child contains the object, we assign it to there
    // if there is more, the object don't move
    if (counter.size() == 1)
        index = counter[0];
    else
        index = -1;

    if (mParent == nullptr)
        return index;

    // it is important to get the position relative to all of his parents, if the object intersects more than one of his parents (for example the center), the object has to be moved to the parent of this parent,
    // this is done recursively.
    int indexFromParent;
    indexFromParent = mParent->getObjIndex(obj);

    if (indexFromParent <= -1)
        return -2;
    else
        return index;

}

template <class Object>
void Quadtree<Object>::subdivide()
{
    float height = mAABB.height / 2;
    float width  = mAABB.width / 2;
    float x = mAABB.left;
    float y = mAABB.top;

    mChildren.push_back(new Quadtree(sf::Vector2f(x        , y         ), width, height, this));
    mChildren.push_back(new Quadtree(sf::Vector2f(x + width, y         ), width, height, this));
    mChildren.push_back(new Quadtree(sf::Vector2f(x        , y + height), width, height, this));
    mChildren.push_back(new Quadtree(sf::Vector2f(x + width, y + height), width, height, this));
}

template <class Object>
void Quadtree<Object>::manage()
{
    updateAll();
}

template <class Object>
bool Quadtree<Object>::intersects(Object* object)
{
    return mAABB.intersects(object->getBoundingRect());
}

template <class Object>
void Quadtree<Object>::draw(sf::RenderTarget& target)
{
    target.draw(mDebugRect);

    for (auto qtree : mChildren)
    {
        qtree->draw(target);
    }
}


template <class Object>
bool Quadtree<Object>::isMarkedForRemoval()
{
    int count = 0;
    getTotalObjectCount(count);
    return count <= MAX_OBJECTS && !mChildren.empty();
}


template <class Object>
void Quadtree<Object>::getOldestParent(Quadtree<Object>*& parent)
{
    if (mParent != nullptr)
    {
        parent = mParent;

        mParent->getOldestParent(parent);
    }
    else
        parent = this;
}