//
//  DiffTraversal.cpp
//  assignment-client/src/entities
//
//  Created by Andrew Meadows 2017.08.08
//  Copyright 2017 High Fidelity, Inc.
//
//  Distributed under the Apache License, Version 2.0.
//  See the accompanying file LICENSE or http://www.apache.org/licenses/LICENSE-2.0.html
//

#include "DiffTraversal.h"

#include <OctreeUtils.h>

#include "EntityPriorityQueue.h"

DiffTraversal::Waypoint::Waypoint(EntityTreeElementPointer& element) : _nextIndex(0) {
    assert(element);
    _weakElement = element;
}

void DiffTraversal::Waypoint::getNextVisibleElementFirstTime(DiffTraversal::VisibleElement& next,
        const DiffTraversal::View& view) {
    // NOTE: no need to set next.intersection in the "FirstTime" context
    if (_nextIndex == -1) {
        // root case is special:
        // its intersection is always INTERSECT,
        // we never bother checking for LOD culling, and
        // we can skip it if the content hasn't changed
        ++_nextIndex;
        next.element = _weakElement.lock();
        return;
    } else if (_nextIndex < NUMBER_OF_CHILDREN) {
        EntityTreeElementPointer element = _weakElement.lock();
        if (element) {
            while (_nextIndex < NUMBER_OF_CHILDREN) {
                EntityTreeElementPointer nextElement = element->getChildAtIndex(_nextIndex);
                ++_nextIndex;
                if (nextElement && view.shouldTraverseElement(*nextElement)) {
                    next.element = nextElement;
                    return;
                }
            }
        }
    }
    next.element.reset();
}

void DiffTraversal::Waypoint::getNextVisibleElementRepeat(
        DiffTraversal::VisibleElement& next, const DiffTraversal::View& view, uint64_t lastTime) {
    if (_nextIndex == -1) {
        // root case is special
        ++_nextIndex;
        EntityTreeElementPointer element = _weakElement.lock();
        if (element->getLastChangedContent() > lastTime) {
            next.element = element;
            return;
        }
    }
    if (_nextIndex < NUMBER_OF_CHILDREN) {
        EntityTreeElementPointer element = _weakElement.lock();
        if (element) {
            while (_nextIndex < NUMBER_OF_CHILDREN) {
                EntityTreeElementPointer nextElement = element->getChildAtIndex(_nextIndex);
                ++_nextIndex;
                if (nextElement &&
                    nextElement->getLastChanged() > lastTime &&
                    view.shouldTraverseElement(*nextElement)) {

                    next.element = nextElement;
                    return;
                }
            }
        }
    }
    next.element.reset();
}

void DiffTraversal::Waypoint::getNextVisibleElementDifferential(DiffTraversal::VisibleElement& next,
        const DiffTraversal::View& view, const DiffTraversal::View& lastView) {
    if (_nextIndex == -1) {
        // root case is special
        ++_nextIndex;
        EntityTreeElementPointer element = _weakElement.lock();
        next.element = element;
        return;
    } else if (_nextIndex < NUMBER_OF_CHILDREN) {
        EntityTreeElementPointer element = _weakElement.lock();
        if (element) {
            while (_nextIndex < NUMBER_OF_CHILDREN) {
                EntityTreeElementPointer nextElement = element->getChildAtIndex(_nextIndex);
                ++_nextIndex;
                if (nextElement && view.shouldTraverseElement(*nextElement)) {
                    next.element = nextElement;
                    return;
                }
            }
        }
    }
    next.element.reset();
}

bool DiffTraversal::View::usesViewFrustums() const {
    return !viewFrustums.empty();
}

bool DiffTraversal::View::isVerySimilar(const View& view) const {
    auto size = view.viewFrustums.size();

    if (view.lodScaleFactor != lodScaleFactor ||
        viewFrustums.size() != size) {
        return false;
    }

    for (size_t i = 0; i < size; ++i) {
        if (!viewFrustums[i].isVerySimilar(view.viewFrustums[i])) {
            return false;
        }
    }
    return true;
}

float DiffTraversal::View::computePriority(const EntityItemPointer& entity) const {
    if (!entity) {
        return PrioritizedEntity::DO_NOT_SEND;
    }

    if (!usesViewFrustums()) {
        return PrioritizedEntity::WHEN_IN_DOUBT_PRIORITY;
    }

    bool success = false;
    auto cube = entity->getQueryAACube(success);
    if (!success) {
        return PrioritizedEntity::WHEN_IN_DOUBT_PRIORITY;
    }

    auto center = cube.calcCenter(); // center of bounding sphere
    auto radius = 0.5f * SQRT_THREE * cube.getScale(); // radius of bounding sphere

    auto priority = PrioritizedEntity::DO_NOT_SEND;

    for (const auto& frustum : viewFrustums) {
        auto position = center - frustum.getPosition(); // position of bounding sphere in view-frame
        float distance = glm::length(position); // distance to center of bounding sphere

        // Check the size of the entity, it's possible that a "too small to see" entity is included in a
        // larger octree cell because of its position (for example if it crosses the boundary of a cell it
        // pops to the next higher cell. So we want to check to see that the entity is large enough to be seen
        // before we consider including it.
        float angularSize = frustum.getAngularSize(distance, radius);
        if (angularSize > lodScaleFactor * MIN_ENTITY_ANGULAR_DIAMETER &&
            frustum.intersects(position, distance, radius)) {

            // use the angular size as priority
            // we compute the max priority for all frustums
            priority = std::max(priority, angularSize);
        }
    }

    return priority;
}

bool DiffTraversal::View::shouldTraverseElement(const EntityTreeElement& element) const {
    if (!usesViewFrustums()) {
        return true;
    }

    const auto& cube = element.getAACube();

    auto center = cube.calcCenter(); // center of bounding sphere
    auto radius = 0.5f * SQRT_THREE * cube.getScale(); // radius of bounding sphere


    return any_of(begin(viewFrustums), end(viewFrustums), [&](const ConicalViewFrustum& frustum) {
        auto position = center - frustum.getPosition(); // position of bounding sphere in view-frame
        float distance = glm::length(position); // distance to center of bounding sphere

        // Check the size of the entity, it's possible that a "too small to see" entity is included in a
        // larger octree cell because of its position (for example if it crosses the boundary of a cell it
        // pops to the next higher cell. So we want to check to see that the entity is large enough to be seen
        // before we consider including it.
        float angularSize = frustum.getAngularSize(distance, radius);

        return angularSize > lodScaleFactor * MIN_ELEMENT_ANGULAR_DIAMETER &&
               frustum.intersects(position, distance, radius);
    });
}

DiffTraversal::DiffTraversal() {
    const int32_t MIN_PATH_DEPTH = 16;
    _path.reserve(MIN_PATH_DEPTH);
}

DiffTraversal::Type DiffTraversal::prepareNewTraversal(const DiffTraversal::View& view, EntityTreeElementPointer root,
                                                       bool forceFirstPass) {
    assert(root);
    // there are three types of traversal:
    //
    //   (1) First = fresh view --> find all elements in view
    //   (2) Repeat = view hasn't changed --> find elements changed since last complete traversal
    //   (3) Differential = view has changed --> find elements changed or in new view but not old
    //
    // for each traversal type we assign the appropriate _getNextVisibleElementCallback
    //
    //   _getNextVisibleElementCallback = identifies elements that need to be traversed,
    //        updates VisibleElement ref argument with pointer-to-element and view-intersection
    //        (INSIDE, INTERSECT, or OUTSIDE)
    //
    // external code should update the _scanElementCallback after calling prepareNewTraversal
    //

    Type type;
    // If usesViewFrustum changes, treat it as a First traversal
    if (forceFirstPass || _completedView.startTime == 0 || _currentView.usesViewFrustums() != _completedView.usesViewFrustums()) {
        type = Type::First;
        _currentView.viewFrustums = view.viewFrustums;
        _currentView.lodScaleFactor = view.lodScaleFactor;
        _getNextVisibleElementCallback = [this](DiffTraversal::VisibleElement& next) {
            _path.back().getNextVisibleElementFirstTime(next, _currentView);
        };
    } else if (!_currentView.usesViewFrustums() || _completedView.isVerySimilar(view)) {
        type = Type::Repeat;
        _getNextVisibleElementCallback = [this](DiffTraversal::VisibleElement& next) {
            _path.back().getNextVisibleElementRepeat(next, _completedView, _completedView.startTime);
        };
    } else {
        type = Type::Differential;
        _currentView.viewFrustums = view.viewFrustums;
        _currentView.lodScaleFactor = view.lodScaleFactor;
        _getNextVisibleElementCallback = [this](DiffTraversal::VisibleElement& next) {
            _path.back().getNextVisibleElementDifferential(next, _currentView, _completedView);
        };
    }

    _path.clear();
    _path.push_back(DiffTraversal::Waypoint(root));
    // set root fork's index such that root element returned at getNextElement()
    _path.back().initRootNextIndex();

    _currentView.startTime = usecTimestampNow();

    return type;
}

void DiffTraversal::getNextVisibleElement(DiffTraversal::VisibleElement& next) {
    if (_path.empty()) {
        next.element.reset();
        return;
    }
    _getNextVisibleElementCallback(next);
    if (next.element) {
        int8_t nextIndex = _path.back().getNextIndex();
        if (nextIndex > 0) {
            _path.push_back(DiffTraversal::Waypoint(next.element));
        }
    } else {
        // we're done at this level
        while (!next.element) {
            // pop one level
            _path.pop_back();
            if (_path.empty()) {
                // we've traversed the entire tree
                _completedView = _currentView;
                return;
            }
            // keep looking for next
            _getNextVisibleElementCallback(next);
            if (next.element) {
                // we've descended one level so add it to the path
                _path.push_back(DiffTraversal::Waypoint(next.element));
            }
        }
    }
}

void DiffTraversal::setScanCallback(std::function<void (DiffTraversal::VisibleElement&)> cb) {
    if (!cb) {
        _scanElementCallback = [](DiffTraversal::VisibleElement& a){};
    } else {
        _scanElementCallback = cb;
    }
}

void DiffTraversal::traverse(uint64_t timeBudget) {
    uint64_t expiry = usecTimestampNow() + timeBudget;
    DiffTraversal::VisibleElement next;
    getNextVisibleElement(next);
    while (next.element) {
        if (next.element->hasContent()) {
            _scanElementCallback(next);
        }
        if (usecTimestampNow() > expiry) {
            break;
        }
        getNextVisibleElement(next);
    }
}