// Geometric Tools, Inc.
// http://www.geometrictools.com
// Copyright (c) 1998-2005.  All Rights Reserved
//
// The Wild Magic Library (WM3) source code is supplied under the terms of
// the license agreement
//     http://www.geometrictools.com/License/WildMagic3License.pdf
// and may not be copied or disclosed except in accordance with the terms
// of that agreement.

#include "Wm3Delaunay1.h"
#include <algorithm>
#include <vector>

namespace Wm3
{
//----------------------------------------------------------------------------
template <class Real>
Delaunay1<Real>::Delaunay1 (int iVertexQuantity, Real* afVertex,
    Real fEpsilon, bool bOwner, int eComputationType)
    :
    Delaunay<Real>(iVertexQuantity,fEpsilon,bOwner,eComputationType)
{
    assert( afVertex );
    m_afVertex = afVertex;

    std::vector<SortedVertex> kArray(m_iVertexQuantity);
    int i;
    for (i = 0; i < m_iVertexQuantity; i++)
    {
        kArray[i].Value = m_afVertex[i];
        kArray[i].Index = i;
    }
    std::sort(kArray.begin(),kArray.end());

    Real fRange = kArray[m_iVertexQuantity-1].Value - kArray[0].Value;
    if ( fRange >= m_fEpsilon )
    {
        m_iDimension = 1;
        m_iSimplexQuantity = m_iVertexQuantity - 1;
        m_aiIndex = new int[2*m_iSimplexQuantity];
        for (i = 0; i < m_iSimplexQuantity; i++)
        {
            m_aiIndex[2*i] = kArray[i].Index;
            m_aiIndex[2*i+1] = kArray[i+1].Index;
        }

        m_aiAdjacent = new int[2*m_iSimplexQuantity];
        for (i = 0; i < m_iSimplexQuantity; i++)
        {
            m_aiAdjacent[2*i] = i-1;
            m_aiAdjacent[2*i+1] = i+1;
        }
        m_aiAdjacent[2*m_iSimplexQuantity-1] = -1;
    }
}
//----------------------------------------------------------------------------
template <class Real>
Delaunay1<Real>::~Delaunay1 ()
{
    if ( m_bOwner )
        delete[] m_afVertex;
}
//----------------------------------------------------------------------------
template <class Real>
const Real* Delaunay1<Real>::GetVertices () const
{
    return m_afVertex;
}
//----------------------------------------------------------------------------
template <class Real>
bool Delaunay1<Real>::GetHull (int aiIndex[2])
{
    assert( m_iDimension == 1 );
    if ( m_iDimension != 1 )
        return false;

    aiIndex[0] = m_aiIndex[0];
    aiIndex[1] = m_aiIndex[2*m_iSimplexQuantity-1];
    return true;
}
//----------------------------------------------------------------------------
template <class Real>
int Delaunay1<Real>::GetContainingSegment (const Real fP) const
{
    assert( m_iDimension == 1 );
    if ( m_iDimension != 1 )
        return -1;

    if ( fP < m_afVertex[m_aiIndex[0]] )
        return -1;

    if ( fP > m_afVertex[m_aiIndex[2*m_iSimplexQuantity-1]] )
        return -1;

    int i;
    for (i = 0; i < m_iSimplexQuantity; i++)
    {
        if ( fP < m_afVertex[m_aiIndex[2*i+1]] )
            break;
    }

    assert( i < m_iSimplexQuantity );
    return i;
}
//----------------------------------------------------------------------------
template <class Real>
bool Delaunay1<Real>::GetVertexSet (int i, Real afV[2]) const
{
    assert( m_iDimension == 1 );
    if ( m_iDimension != 1 )
        return false;

    if ( 0 <= i && i < m_iSimplexQuantity )
    {
        afV[0] = m_afVertex[m_aiIndex[2*i]];
        afV[1] = m_afVertex[m_aiIndex[2*i+1]];
        return true;
    }
    return false;
}
//----------------------------------------------------------------------------
template <class Real>
bool Delaunay1<Real>::GetIndexSet (int i, int aiIndex[2]) const
{
    assert( m_iDimension == 1 );
    if ( m_iDimension != 1 )
        return false;

    if ( 0 <= i && i < m_iSimplexQuantity )
    {
        aiIndex[0] = m_aiIndex[2*i];
        aiIndex[1] = m_aiIndex[2*i+1];
        return true;
    }
    return false;
}
//----------------------------------------------------------------------------
template <class Real>
bool Delaunay1<Real>::GetAdjacentSet (int i, int aiAdjacent[2]) const
{
    assert( m_iDimension == 1 );
    if ( m_iDimension != 1 )
        return false;

    if ( 0 <= i && i < m_iSimplexQuantity )
    {
        aiAdjacent[0] = m_aiAdjacent[2*i];
        aiAdjacent[1] = m_aiAdjacent[2*i+1];
        return true;
    }
    return false;
}
//----------------------------------------------------------------------------
template <class Real>
bool Delaunay1<Real>::GetBarycentricSet (int i, const Real fP, Real afBary[2])
    const
{
    assert( m_iDimension == 1 );
    if ( m_iDimension != 1 )
        return false;

    if ( 0 <= i && i < m_iSimplexQuantity )
    {
        Real fV0 = m_afVertex[m_aiIndex[2*i]];
        Real fV1 = m_afVertex[m_aiIndex[2*i+1]];
        Real fDenom = fV1 - fV0;
        if ( fDenom > m_fEpsilon )
            afBary[0] = (fV1 - fP)/fDenom;
        else
            afBary[0] = (Real)1.0;

        afBary[1] = (Real)1.0 - afBary[0];
        return true;
    }
    return false;
}
//----------------------------------------------------------------------------

//----------------------------------------------------------------------------
// explicit instantiation
//----------------------------------------------------------------------------
template WM3_ITEM class Delaunay1<float>;
template WM3_ITEM class Delaunay1<double>;
//----------------------------------------------------------------------------
}


