/*
    This file is part of Mitsuba, a physically based rendering system.

    Copyright (c) 2007-2014 by Wenzel Jakob and others.

    Mitsuba is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License Version 3
    as published by the Free Software Foundation.

    Mitsuba is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program. If not, see <http://www.gnu.org/licenses/>.
*/

#pragma once
#if !defined(__MITSUBA_BIDIR_PATH_H_)
#define __MITSUBA_BIDIR_PATH_H_

#include <mitsuba/bidir/vertex.h>
#include <mitsuba/bidir/edge.h>
#include <mitsuba/bidir/mempool.h>

MTS_NAMESPACE_BEGIN

/**
 * \brief Bidirectional path data structure
 *
 * In the path-space light transport framework, a path is represented as a
 * linear sequence of interactions (expressed using vertices) and transport
 * (expressed using edges).
 *
 * The \ref Path data structure is responsible for the storage of this
 * information. It also contains useful utility functions, for instance
 * to perform a random walk, or to splice and connect path segments.
 *
 * \sa PathVertex
 * \sa PathEdge
 *
 * \author Wenzel Jakob
 * \ingroup libbidir
 */
struct MTS_EXPORT_BIDIR Path {
public:
    typedef PathEdge *          PathEdgePtr;
    typedef PathVertex *        PathVertexPtr;

    /* ==================================================================== */
    //! @{ \name              Path construction
    /* ==================================================================== */

    /// Create a new, empty path
    inline Path() { }

    /// Create a new path of the specified size
    inline Path(size_t size) : m_vertices(size) { }

    /// Copy constructor
    inline Path(const Path &path) : m_vertices(path.m_vertices),
        m_edges(path.m_edges) { }

    /**
     * \brief Initialize the path with an endpoint vertex
     *
     * This function clears the path and initializes it with a single
     * endpoint vertex of the type implied by the \c mode parameter.
     *
     * \param scene
     *     Pointer to the underlying scene
     * \param time
     *     Specifies the time value to be associated with the path.
     * \param mode
     *     Specifies the desired endpoint type
     * \param pool
     *     Reference to a memory pool that will be used to release
     *     and allocate edges and vertices.
     */
    void initialize(const Scene *scene, Float time,
        ETransportMode mode, MemoryPool &pool);

    /**
     * \brief Perform/continue a random walk starting from the current endpoint
     *
     * \param scene
     *     Pointer to the underlying scene
     * \param sampler
     *     Pointer to a sample generator
     * \param nSteps
     *     Desired number of random walk steps (<tt>-1</tt>=infinite)
     * \param rrStart
     *     Depth to start using russian roulette
     *     (<tt>-1</tt>=never, <tt>0</tt>=starting at the first
     *     bounce, and so on)
     * \param mode
     *     Denotes whether radiance or importance are being transported
     * \param pool
     *     Reference to a memory pool that will be used to allocate
     *     edges and vertices.
     * \return The number of successful steps performed by the random walk.
     */
    int randomWalk(const Scene *scene, Sampler *sampler,
        int nSteps, int rrStart, ETransportMode mode,
        MemoryPool &pool);

    /**
     * \brief Perform a random walk starting at a specified
     * pixel on the sensor
     *
     * \param scene
     *     Pointer to the underlying scene
     * \param sampler
     *     Pointer to a sample generator
     * \param nSteps
     *     Desired number of random walk steps (<tt>-1</tt>=infinite)
     * \param pixelPosition
     *     Pixel position associated with the newly created
     *     sensor subpath
     * \param rrStart
     *     Depth to start using russian roulette
     *     (<tt>-1</tt>=never, <tt>0</tt>=starting at the first
     *     bounce, and so on)
     * \param pool
     *     Reference to a memory pool that will be used to allocate
     *     edges and vertices.
     * \return The number of successful steps performed by the random walk.
     */
    int randomWalkFromPixel(const Scene *scene, Sampler *sampler,
        int nSteps, const Point2i &pixelPosition, int rrStart,
        MemoryPool &pool);

    /**
     * \brief Perform two random walks on an emitter and sensor subpath
     *
     * This function is almost identical to calling \ref randomWalk() twice
     * in sequence. The main difference is that it performs the random
     * walk steps in a staggered order (i.e. one step on the emitter subpath,
     * one step on the sensor subpath, and so on..), which is important for
     * obtaining good results with QMC random number sequences.
     * Additinally, it ensures that the sensor path passes through a specified
     * pixel instead of sampling it uniformly.
     *
     * Used by bidirectional path tracing.
     *
     * \param scene
     *     Pointer to the underlying scene
     * \param sampler
     *     Pointer to a sample generator
     * \param emitterPath
     *     Reference to the emitter subpath to be filled
     * \param nEmitterSteps
     *     Desired number of random walk steps on the emitter subpath
     *     (<tt>-1</tt>=infinite)
     * \param sensorPath
     *     Reference to the sensor subpath to be filled
     * \param nSensorSteps
     *     Desired number of random walk steps on the sensor subpath
     *     (<tt>-1</tt>=infinite)
     * \param pixelPosition
     *     Pixel position associated with the newly created
     *     sensor subpath
     * \param rrStart
     *     Depth to start using russian roulette
     *     (<tt>-1</tt>=never, <tt>0</tt>=starting at the first
     *     bounce, and so on)
     * \param pool
     *     Reference to a memory pool that will be used to allocate
     *     edges and vertices.
     * \return The number of successful steps performed by the random walk
     *         on the emitter and sensor subpath, respectively.
     */
    static std::pair<int, int> alternatingRandomWalkFromPixel(const Scene *scene,
        Sampler *sampler, Path &emitterPath, int nEmitterSteps,
        Path &sensorPath, int nSensorSteps, const Point2i &pixelPosition,
        int rrStart, MemoryPool &pool);

    /**
     * \brief Verify the cached values stored in this path
     *
     * This function re-evaluates a series of quantities associated with
     * each vertex and edge and compares them to locally cached values.
     * If any mismatch is found, the function sends debug output to a
     * specified output stream and returns \c false.
     *
     * \param scene
     *     Pointer to the underlying scene
     * \param mode
     *     Disambiguates the order of the vertices in this path
     * \param os
     *     Target output stream for error messages
     */
    bool verify(const Scene *scene, ETransportMode mode, std::ostream &os) const;

    //! @}
    /* ==================================================================== */

    /* ==================================================================== */
    //! @{ \name                     Accessors
    /* ==================================================================== */

    /**
     * \brief Return the number of vertices stored in this path
     *
     * For a nonempty path, the number of vertices is always equal
     * To \ref edgeCount()+1.
     */
    inline size_t vertexCount() const {
        return m_vertices.size();
    }

    /**
     * \brief Return the number of edges stored in this path
     *
     * For a nonempty path, the number of vertices is always equal
     * To \ref vertexCount()-1.
     */
    inline size_t edgeCount() const {
        return m_edges.size();
    }

    /**
     * \brief Return the length of the path. This is just the
     * number of edges.
     */
    inline int length() const {
        return (int) m_edges.size();
    }

    /// Return an vertex by its index
    inline PathVertexPtr &vertex(size_t index) {
        #if MTS_BD_DEBUG == 1
            if (index >= m_vertices.size())
                SLog(EError, "Path vertex index " SIZE_T_FMT
                    " is out of bounds, array size: " SIZE_T_FMT,
                    index, m_vertices.size());
        #endif
        return m_vertices[index];
    }

    /// Return an vertex by its index (const version)
    inline const PathVertexPtr &vertex(size_t index) const {
        #if MTS_BD_DEBUG == 1
            if (index >= m_vertices.size())
                SLog(EError, "Path vertex index " SIZE_T_FMT
                    " is out of bounds, array size: " SIZE_T_FMT,
                    index, m_vertices.size());
        #endif
        return m_vertices[index];
    }

    /// Return an vertex by its index (or NULL if out of bounds)
    inline PathVertexPtr vertexOrNull(size_t index) {
        if (index >= m_vertices.size())
            return NULL;
        return m_vertices[index];
    }

    /// Return an vertex by its index (or NULL if out of bounds, const version)
    inline PathVertexPtr vertexOrNull(size_t index) const {
        if (index >= m_vertices.size())
            return NULL;
        return m_vertices[index];
    }

    /// Return an edge by its index
    inline PathEdgePtr &edge(size_t index) {
        #if MTS_BD_DEBUG == 1
            if (index >= m_edges.size())
                SLog(EError, "Path edge index " SIZE_T_FMT
                    " is out of bounds, array size: " SIZE_T_FMT,
                    index, m_edges.size());
        #endif
        return m_edges[index];
    }

    /// Return an edge by its index (const version)
    inline const PathEdgePtr &edge(size_t index) const {
        #if MTS_BD_DEBUG == 1
            if (index >= m_edges.size())
                SLog(EError, "Path edge index " SIZE_T_FMT
                    " is out of bounds, array size: " SIZE_T_FMT,
                    index, m_edges.size());
        #endif
        return m_edges[index];
    }

    /// Return an edge by its index (or \c NULL if out of bounds)
    inline PathEdgePtr edgeOrNull(size_t index) {
        if (index >= m_edges.size())
            return NULL;
        return m_edges[index];
    }

    /// Return an edge by its index (or \c NULL if out of bounds, const version)
    inline PathEdgePtr edgeOrNull(size_t index) const {
        if (index >= m_edges.size())
            return NULL;
        return m_edges[index];
    }


    //! @}
    /* ==================================================================== */

    /* ==================================================================== */
    //! @{ \name                    Miscellaneous
    /* ==================================================================== */

    /**
     * \brief Return the spectrally varying path weight that corresponds to
     * a prefix of length \c l and a suffix of length \c m.
     *
     * This operation is used by path mutation strategies that operate
     * by cutting out a pice of a path and replacing it with something else.
     * In that case, it is necessary know about the effects of vertices
     * and edges \a outside of the modified range.
     */
    inline Spectrum getPrefixSuffixWeight(int l, int m) const {
        Spectrum weight(1.0f);

        for (int s=0; s<l; ++s)
            weight *= m_vertices[s]->weight[EImportance]
                * m_edges[s]->weight[EImportance];

        for (int t=length(); t>m; --t)
            weight *= m_vertices[t]->weight[ERadiance]
                * m_edges[t-1]->weight[ERadiance];

        return weight;
    }

    /**
     * \brief Determine whether another path of the same length
     * matches the configuration of this path
     *
     * More specifically, this function verifies that the length matches,
     * that all vertices are of the same type, and that the paths have
     * identical values of \ref isConnectable() for each vertex.
     */
    inline bool matchesConfiguration(const Path &p) const {
        if (p.length() != length())
            return false;

        for (size_t i=0; i<m_vertices.size(); ++i) {
            if (m_vertices[i]->type != p.vertex(i)->type ||
                m_vertices[i]->isConnectable() != p.vertex(i)->isConnectable())
                return false;
        }

        return true;
    }

    /**
     * \brief Return the relative spectrally varying path weight associated
     * with this path
     *
     * This function computes the product of all the importance weights
     * (see the \ref weight field) along the path, and the result is
     * normalized so that it has luminance 1. This quantity is required
     * by the sample splatting implementation in Veach-MLT.
     */
    inline Spectrum getRelativeWeight() const {
        Spectrum weight(1.0f);
        int k = length();

        for (int s=0; s<k-1; ++s)
            weight *= m_vertices[s]->weight[EImportance]
                * m_edges[s]->weight[EImportance];

        weight = weight
            * m_vertices[k]->weight[ERadiance]
            * m_vertices[k-1]->weight[ERadiance]
            * m_edges[k-1]->weight[ERadiance];

        Float lum = weight.getLuminance();
        return lum != 0.0f ? (weight / lum) : Spectrum(0.0f);
    }

    /**
     * \brief Compute the multiple importance sampling weight of the <tt>(s,t)</tt>
     * sampling strategy in BDPT.
     *
     * This implementation uses the power heuristic with exponent 2 and
     * repeatedly evaluates equation (10.9) from Eric Veach's PhD thesis to
     * compute the weight in an efficient and numerically stable manner.
     *
     * The function completely ignores the effects of russian roulette, since
     * this allows for a more efficient implementation. The resulting estimator
     * is still unbiased despite this apparent inaccuracy.
     *
     * \param scene
     *    Pointer to the underlying scene
     * \param emitterSubpath
     *    Reference to the emitter subpath
     * \param connectionEdge
     *    Pointer to an edge data structure associated with the
     *    transport between <tt>emitterSubpath[s]</tt> and
     *    <tt>sensorSubpath[t]</tt>.
     * \param sensorSubpath
     *    Reference to the sensor subpath
     * \param s
     *    Number of steps to take along the emitter subpath
     * \param t
     *    Number of steps to take along the sensor subpath
     * \param direct
     *    When the parameter \c direct is set to \c true, the implementation
     *    accounts for the fact that specialized direct sampling strategies
     *    are used for paths with <tt>s==1</tt> and <tt>t==1</tt>.
     * \param lightImage
     *    Denotes whether or not rendering strategies that require a 'light image'
     *    (specifically, those with <tt>t==0</tt> or <tt>t==1</tt>) are included
     *    in the rendering process.
     */
    static Float miWeight(const Scene *scene,
            const Path &emitterSubpath,
            const PathEdge *connectionEdge,
            const Path &sensorSubpath, int s, int t,
            bool direct, bool lightImage);

    /**
     * \brief Collapse a path into an entire edge that summarizes the aggregate
     * transport and sampling densities
     *
     * This is only allowed when the path only consists of \ref BSDF::ENull
     * surface scattering events (e.g. index-matched medium transitions)
     */
    void collapseTo(PathEdge &edge) const;

    /// Reverse a path
    void reverse();

    /// Swap the two endpoint vertices of a path with the provided values
    inline void swapEndpoints(PathVertexPtr &supernode, PathEdgePtr &edge, PathVertexPtr &sample) {
        std::swap(supernode, m_vertices[0]);
        std::swap(sample, m_vertices[1]);
        std::swap(edge, m_edges[0]);
    }

    /// \brief Append a vertex to this path
    inline void append(PathVertex *vertex) { m_vertices.push_back(vertex); }

    /// \brief Append an edge to this path
    inline void append(PathEdge *edge) { m_edges.push_back(edge); }

    /**
     * \brief Append an edge and a vertex to this path
     *
     * \param edge
     *     And edge from <tt>vertex(vertexCount()-1)</tt> to \c vertex.
     * \param vertex
     *     A vertex to be appended at the end of the path
     */
    inline void append(PathEdge *edge, PathVertex *vertex) {
        m_edges.push_back(edge);
        m_vertices.push_back(vertex);
    }

    /// Append an entire path to this path
    void append(const Path &path);

    /**
     * \brief Append the vertex range <tt>[start, end)</tt> of \c path
     * (and all intermediate edges) to the current path.
     *
     * \param path
     *     Source of vertices and edges to be added
     * \param l
     *     Specifies the start of the range <tt>[start, end)</tt>.
     * \param m
     *     Specifies the end of the range <tt>[start, end)</tt>.
     * \param reverse
     *     Should the vertices and edges be added in \a reverse order?
     */
    void append(const Path &path, size_t start, size_t end, bool reverse = false);

    /// Clear the path and release all elements to the memory pool
    void release(MemoryPool &pool);

    /// Release a certain subpath [start, end) to the memory pool
    void release(size_t start, size_t end, MemoryPool &pool);

    /// Return the sample position associated with the path
    inline const Point2 &getSamplePosition() const {
        return m_vertices[length()-1]->getSamplePosition();
    }

    /// Clear the path
    inline void clear() {
        m_vertices.clear();
        m_edges.clear();
    }

    /// Compare this path against another path
    bool operator==(const Path &path) const;

    /// Compare this path against another path
    inline bool operator!=(const Path &path) const {
        return !operator==(path);
    }

    /// Create a deep copy of this path
    void clone(Path &target, MemoryPool &pool) const;

    /// Return a string representation of the path
    std::string toString() const;

    /// Return a basic string summary of the path
    std::string summarize() const;

    //! @}
    /* ==================================================================== */
private:
    std::vector<PathVertexPtr> m_vertices;
    std::vector<PathEdgePtr>   m_edges;
};

MTS_NAMESPACE_END

#endif /* __MITSUBA_BIDIR_PATH_H_ */
