/*****************************************************************************
*
* Copyright (c) 2000 - 2017, Lawrence Livermore National Security, LLC
* Produced at the Lawrence Livermore National Laboratory
* LLNL-CODE-442911
* All rights reserved.
*
* This file is  part of VisIt. For  details, see https://visit.llnl.gov/.  The
* full copyright notice is contained in the file COPYRIGHT located at the root
* of the VisIt distribution or at http://www.llnl.gov/visit/copyright.html.
*
* Redistribution  and  use  in  source  and  binary  forms,  with  or  without
* modification, are permitted provided that the following conditions are met:
*
*  - Redistributions of  source code must  retain the above  copyright notice,
*    this list of conditions and the disclaimer below.
*  - Redistributions in binary form must reproduce the above copyright notice,
*    this  list of  conditions  and  the  disclaimer (as noted below)  in  the
*    documentation and/or other materials provided with the distribution.
*  - Neither the name of  the LLNS/LLNL nor the names of  its contributors may
*    be used to endorse or promote products derived from this software without
*    specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT  HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR  IMPLIED WARRANTIES, INCLUDING,  BUT NOT  LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND  FITNESS FOR A PARTICULAR  PURPOSE
* ARE  DISCLAIMED. IN  NO EVENT  SHALL LAWRENCE  LIVERMORE NATIONAL  SECURITY,
* LLC, THE  U.S.  DEPARTMENT OF  ENERGY  OR  CONTRIBUTORS BE  LIABLE  FOR  ANY
* DIRECT,  INDIRECT,   INCIDENTAL,   SPECIAL,   EXEMPLARY,  OR   CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT  LIMITED TO, PROCUREMENT OF  SUBSTITUTE GOODS OR
* SERVICES; LOSS OF  USE, DATA, OR PROFITS; OR  BUSINESS INTERRUPTION) HOWEVER
* CAUSED  AND  ON  ANY  THEORY  OF  LIABILITY,  WHETHER  IN  CONTRACT,  STRICT
* LIABILITY, OR TORT  (INCLUDING NEGLIGENCE OR OTHERWISE)  ARISING IN ANY  WAY
* OUT OF THE  USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
* DAMAGE.
*
*****************************************************************************/

// ************************************************************************* //
//  File: avtConnCompReduceFilter.C
// ************************************************************************* //

#include <avtConnCompReduceFilter.h>

#include <vector>

#include <vtkCellData.h>
#include <vtkIdList.h>
#include <vtkPointData.h>
#include <vtkPolyData.h>
#include <vtkUnstructuredGrid.h>

#include <avtCallback.h>


using     std::vector;


// ****************************************************************************
//  Method: avtConnCompReduceFilter constructor
//
//  Programmer: childs -- generated by xml2info
//  Creation:   Tue Oct 29 10:16:45 PDT 2002
//
// ****************************************************************************

avtConnCompReduceFilter::avtConnCompReduceFilter()
{
    haveIssuedWarning = false;
}


// ****************************************************************************
//  Method: avtConnCompReduceFilter destructor
//
//  Programmer: childs -- generated by xml2info
//  Creation:   Tue Oct 29 10:16:45 PDT 2002
//
//  Modifications:
//
// ****************************************************************************

avtConnCompReduceFilter::~avtConnCompReduceFilter()
{
}


// ****************************************************************************
//  Method:  avtConnCompReduceFilter::Create
//
//  Programmer: childs -- generated by xml2info
//  Creation:   Tue Oct 29 10:16:45 PDT 2002
//
// ****************************************************************************

avtFilter *
avtConnCompReduceFilter::Create()
{
    return new avtConnCompReduceFilter();
}


// ****************************************************************************
//  Method:      avtConnCompReduceFilter::SetAtts
//
//  Purpose:
//      Sets the state of the filter based on the attribute object.
//
//  Arguments:
//      a        The attributes to use.
//
//  Programmer: childs -- generated by xml2info
//  Creation:   Tue Oct 29 10:16:45 PDT 2002
//
// ****************************************************************************

void
avtConnCompReduceFilter::SetAtts(const AttributeGroup *a)
{
    atts = *(const ConnCompReduceAttributes*)a;
}


// ****************************************************************************
//  Method: avtConnCompReduceFilter::Equivalent
//
//  Purpose:
//      Returns true if creating a new avtConnCompReduceFilter with the given
//      parameters would result in an equivalent avtConnCompReduceFilter.
//
//  Programmer: childs -- generated by xml2info
//  Creation:   Tue Oct 29 10:16:45 PDT 2002
//
// ****************************************************************************

bool
avtConnCompReduceFilter::Equivalent(const AttributeGroup *a)
{
    return (atts == *(ConnCompReduceAttributes*)a);
}


// ****************************************************************************
//  Method: avtConnCompReduceFilter::PreExecute
//
//  Purpose:
//      Called before Execute is called, this will set a Boolean indicating
//      whether we have issued a warning or not.
//
//  Programmer: Hank Childs
//  Creation:   October 29, 2002
//
//  Modifications:
//    Jeremy Meredith, Thu Feb 15 11:55:03 EST 2007
//    Call inherited PreExecute before everything else.
//
// ****************************************************************************

void
avtConnCompReduceFilter::PreExecute(void)
{
    avtPluginDataTreeIterator::PreExecute();

    haveIssuedWarning = false;
}


// ****************************************************************************
//  Method: avtConnCompReduceFilter::ExecuteData
//
//  Purpose:
//      Sends the specified input and output through the ConnCompReduce filter.
//
//  Arguments:
//      in_dr      The input data representation.
//
//  Returns:       The output data representation.
//
//  Programmer: childs -- generated by xml2info
//  Creation:   Tue Oct 29 10:16:45 PDT 2002
//
//  Modifications:
//    Eric Brugger, Wed Jul 23 08:42:01 PDT 2014
//    Modified the class to work with avtDataRepresentation.
//
// ****************************************************************************

avtDataRepresentation *
avtConnCompReduceFilter::ExecuteData(avtDataRepresentation *in_dr)
{
    //
    // Get the VTK data set.
    //
    vtkDataSet *in_ds = in_dr->GetDataVTK();

    int dstype = in_ds->GetDataObjectType();
    vtkDataSet *rv = NULL;
    bool ownDS = true;
    if (dstype == VTK_POLY_DATA)
    {
        rv = PolyDataExecute((vtkPolyData *) in_ds);
    }
    else if (dstype == VTK_UNSTRUCTURED_GRID)
    {
        rv = UnstructuredGridExecute((vtkUnstructuredGrid *) in_ds);
    }
    else
    {
        if (!haveIssuedWarning)
        {
            avtCallback::IssueWarning("The connected component reduce operator"
                     " cannot be applied to structured meshes.");
            haveIssuedWarning = true;
        }
        rv = in_ds;
        ownDS = false;
    }

    avtDataRepresentation *out_dr = new avtDataRepresentation(rv,
        in_dr->GetDomain(), in_dr->GetLabel());

    if (ownDS)
    {
        rv->Delete();
    }

    return out_dr;
}


// ****************************************************************************
//  Method: avtConnCompReduceFilter::UnstructuredGridExecute
//
//  Purpose:
//      Finds the connected components in this dataset and then throws out
//      some portion of them.
//
//  Programmer: Hank Childs
//  Creation:   October 29, 2002
//
// ****************************************************************************

vtkDataSet *
avtConnCompReduceFilter::UnstructuredGridExecute(vtkUnstructuredGrid *ug)
{
    int       npts    = ug->GetNumberOfPoints();
    int       ncells  = ug->GetNumberOfCells();

    //
    // This subroutine will determine what the components are and each points
    // membership in a certain component (one per component, obviously).
    //
    int      *comps   = new int[npts];
    int       ncomps  = DetermineConnectedComponents(ug, comps);

    //
    // This subroutine determines which components to keep and which to throw
    // away.
    //
    double    target   = atts.GetTarget();
    bool     *compList = new bool[ncomps];
    MakeComponentList(target, ncomps, compList);

    //
    // Below is the VTK magic to keep cells that are in the "right" components
    // and throw out the ones in the "wrong" components.
    //
    vtkUnstructuredGrid *outug = vtkUnstructuredGrid::New();
    outug->Allocate(ncells);

    outug->SetPoints(ug->GetPoints());
    outug->GetPointData()->PassData(ug->GetPointData());

    vtkCellData *incd  = ug->GetCellData();
    vtkCellData *outcd = outug->GetCellData();
    outcd->CopyAllocate(incd, ncells);

    vtkIdList *cellIds = vtkIdList::New();
    for (int i = 0 ; i < ncells ; i++)
    {
        ug->GetCellPoints(i, cellIds);
        int id = cellIds->GetId(0);
        if (compList[comps[id]])
        {
            int index = outug->InsertNextCell(ug->GetCellType(i), cellIds);
            outcd->CopyData(incd, i, index);
        }
    }

    outcd->Squeeze();
    outug->Squeeze();

    cellIds->Delete();
    delete [] comps;
    delete [] compList;

    return outug;
}


// ****************************************************************************
//  Method: avtConnCompReduceFilter::PolyDataExecute
//
//  Purpose:
//      Finds the connected components in this dataset and then throws out
//      some portion of them.
//
//  Programmer: Hank Childs
//  Creation:   October 29, 2002
//
// ****************************************************************************

vtkDataSet *
avtConnCompReduceFilter::PolyDataExecute(vtkPolyData *pd)
{
    int       npts    = pd->GetNumberOfPoints();
    int       ncells  = pd->GetNumberOfCells();

    //
    // This subroutine will determine what the components are and each points
    // membership in a certain component (one per component, obviously).
    //
    int      *comps   = new int[npts];
    int       ncomps  = DetermineConnectedComponents(pd, comps);

    //
    // This subroutine determines which components to keep and which to throw
    // away.
    //
    double    target   = atts.GetTarget();
    bool     *compList = new bool[ncomps];
    MakeComponentList(target, ncomps, compList);

    //
    // Below is the VTK magic to keep cells that are in the "right" components
    // and throw out the ones in the "wrong" components.
    //
    vtkPolyData *outpd = vtkPolyData::New();
    outpd->Allocate(ncells);

    outpd->SetPoints(pd->GetPoints());
    outpd->GetPointData()->PassData(pd->GetPointData());

    vtkCellData *incd  = pd->GetCellData();
    vtkCellData *outcd = outpd->GetCellData();
    outcd->CopyAllocate(incd, ncells);

    vtkIdList *cellIds = vtkIdList::New();
    for (int i = 0 ; i < ncells ; i++)
    {
        pd->GetCellPoints(i, cellIds);
        int id = cellIds->GetId(0);
        if (compList[comps[id]])
        {
            int index = outpd->InsertNextCell(pd->GetCellType(i), cellIds);
            outcd->CopyData(incd, i, index);
        }
    }

    outcd->Squeeze();
    outpd->Squeeze();

    cellIds->Delete();
    delete [] comps;
    delete [] compList;

    return outpd;
}


// ****************************************************************************
//  Method: avtConnCompReduce::DetermineConnectedComponents
//
//  Purpose:
//      Walks through the cells of a vtkDataset and determines which cells are
//      connected to which. 
//
//  Arguments:
//      ds      A VTK dataset.
//      comps   An array to store which component each point is located in.
//
//  Returns:    The total number of connected components (excludes points
//              that are not explicitly attached to a cell -- VTK_VERTEX).
//
//  Programmer: Hank Childs
//  Creation:   October 29, 2002
//
// ****************************************************************************

int
avtConnCompReduceFilter::DetermineConnectedComponents(vtkDataSet *ds,
                                                      int *comps)
{
    int          i, j;

    int          npts    = ds->GetNumberOfPoints();
    int          ncells  = ds->GetNumberOfCells();
    vtkIdList   *cellIds = vtkIdList::New();

    //
    // The for loop below won't get us the connected components, but it will
    // get us close.  It walks through the cells and sets up a structure that
    // will allow us to find the connected components on a second pass.
    //
    int  currentComp = 0;
    for (i = 0 ; i < npts ; i++)
    {
        comps[i] = -1;
    }
    vector<int> realCompIds;
    for (i = 0 ; i < ncells ; i++)
    {
        //
        // Which points are in this cell?
        //
        ds->GetCellPoints(i, cellIds);

        //
        // Have any of the points been associated previously with a component?
        // Have multiple ones?  If so, associate this cell and all of its 
        // points with the lowest component id.
        //
        int lowestComp = ncells;
        int nIds = cellIds->GetNumberOfIds();
        for (j = 0 ; j < nIds ; j++)
        {
            int id = cellIds->GetId(j);
            if (comps[id] >= 0 && comps[id] < lowestComp)
            {
                lowestComp = comps[id];
            }
        }

        if (lowestComp == ncells)
        {
            //
            // We didn't find a component, so make a new one.
            //
            lowestComp = currentComp;
            realCompIds.push_back(currentComp);
            currentComp++;
        }

        for (j = 0 ; j < nIds ; j++)
        {
            int id = cellIds->GetId(j);
            if (comps[id] > lowestComp)
            {
                //
                // This cell bridged two previously unconnected components.
                // Now that we now know that they are the same component, when
                // we make our second pass we can associate them together.
                //
                realCompIds[comps[id]] = lowestComp;
            }
            comps[id] = lowestComp;
        }
    }

    //
    // We now have every point associated with a component and a (somewhat
    // complicated) system for linking the components.  Make a table that we
    // can use to renumber the components into a final list.
    //
    int nComponents = currentComp;
    int nRealComponents = 0;
    vector<int> condensedComponent;
    condensedComponent.resize(nComponents);
    for (i = 0 ; i < nComponents ; i++)
    {
        if (realCompIds[i] == i)
        {
            //
            // We never found a component with a smaller number that was
            // attached to this one.  So we will start a new group based on
            // this.
            //
            condensedComponent[i] = nRealComponents;
            nRealComponents++;
        }
        else
        {
            //
            // We know that this component is actually connected to a component
            // that we discovered before it.  So piggyback on its 'real'
            // component number.
            //
            condensedComponent[i] = condensedComponent[realCompIds[i]];
        }
    }

    //
    // Finally!, we can tell each point what its 'real' component is.
    //
    for (i = 0 ; i < npts ; i++)
    {
        comps[i] = condensedComponent[comps[i]];
    }
            
    cellIds->Delete();

    return nRealComponents;
}


// ****************************************************************************
//  Function: MakeComponentList
//
//  Purpose:
//      Determine which components to use, based on a target number.
//
//  Arguments:
//      target    A target ratio of components to use.
//      ncomps    The total number of components.
//      compList  A place to store the actual components.
//
//  Programmer: Hank Childs
//  Creation:   October 29, 2002
//
// ****************************************************************************

void
avtConnCompReduceFilter::MakeComponentList(double target, int ncomps, 
                                           bool *compList)
{
    for (int i = 0 ; i < ncomps ; i++)
    {
        compList[i] = false;
    }

    //
    // Make sure that we were given reasonable input.
    //
    if (target <= 0. || target > 1.)
    {
        if (!haveIssuedWarning)
        {
            avtCallback::IssueWarning("Target must be between 0 and 1.");
            haveIssuedWarning = true;
        }
        return;
    }
    if (ncomps == 0)
    {
        return;
    }

    //
    // Calculate what our "one out of every" value is and only accept the
    // ones that conform to that.
    //
    double totalComponentTarget = target * ncomps;
    double increment = ncomps / totalComponentTarget;
    double runningValue = 0.;
    while (runningValue < ncomps)
    {
        int comp = (int) runningValue;
        compList[comp] = true;
        runningValue += increment;
    }
}


