Quelle movable_complex.cpp Sprache: C

//
//  movable_complex.cpp
//  Bistellar
//
//  Created by Alexander Thumm on 07.10.11.
//  Copyright 2011 -. All rights reserved.
//

#include "movable_complex.h"
#include "face.h"
#include "util.h"
#include <algorithm>
#include <iostream>

MovableComplex::MovableComplex() : _faces(1, face_list_t(0)), _moves(1, bistellar_move_option_list_t(0)), _dimension(0)
{
}

MovableComplex::MovableComplex(const face_list_t & facets, unsigned int dimension) : _faces(dimension+1), _moves(dimension+1), _dimension(dimension)
{

    #ifdef Bistellar_debug_output
    std::cout << "Creating "<< dimension <<"-dimensional MovableComplex from Facets: ";
    list_print(std::cout, facets.begin(), facets.end());
    std::cout << std::endl;
    #endif

    // init facets
    _faces[dimension] = facets;

    // init lower dimensional faces
    for (int codimension = 1; codimension < dimension+1; codimension++)
    {
        if(!_faces[dimension - codimension + 1].empty())
        {
            for (face_list_t::const_iterator it = _faces[dimension - codimension + 1].begin();
             it != _faces[dimension - codimension + 1].end(); it++)
            {
                for (int i = 0; i < dimension - codimension + 2; i++)
                {
                    Face * boundaryFace = it->createBoundaryFace(i);
                    // only add boundaryFace if it is not already contained in complex
                    if (std::find(_faces[dimension - codimension].begin(), _faces[dimension - codimension].end(), *boundaryFace) == _faces[dimension - codimension].end())
                    {
                        _faces[dimension - codimension].push_back(*boundaryFace);
                    }

                    delete boundaryFace;
                }
            }
        }
    }

    // init moves
    if (!_faces[dimension].empty())
    {
        for (face_list_t::const_iterator it = _faces[dimension].begin(); it != _faces[dimension].end(); it++)
        {
            // add all 0-moves
            _moves[0].push_back(std::make_pair(BistellarMove(*it, Face()), true));
        }
    }
    for (int codimension = 1; codimension < dimension+1; codimension++)
    {
        if (!_faces[dimension-codimension].empty())
        {
            for (face_list_t::const_iterator it = _faces[dimension-codimension].begin(); it != _faces[dimension-codimension].end(); it++)
            {
                std::deque< Face > linkFacets;
                // copy all Facets that contain (*it) as a subface to linkFacets
                if (!_faces[dimension].empty())
                {
                    for (face_list_t::const_iterator it2 = _faces[dimension].begin(); it2 != _faces[dimension].end(); it2++)
                    {
                        if (it->isSubfaceOf(*it2))
                            linkFacets.push_back(*it2);
                    }
                }

                if (linkFacets.size() == codimension+1)
                {
                    // add the move option.
                    Face linkFace = Face::linkFace(*it, linkFacets);
                    if (linkFace.dimension() <= _dimension)
                        _moves[codimension].push_back(std::make_pair(BistellarMove(*it, linkFace), (std::find(_faces[linkFace.dimension()].begin(), _faces[linkFace.dimension()].end(), linkFace) == _faces[linkFace.dimension()].end())));
                }
            }
        }
    }

    #ifdef Bistellar_debug_output
    for (int i = 0; i < dimension+1; i++)
    {
        std::cout << i << "-Moves: ";
        if (!_moves[i].empty()) list_print(std::cout, _moves[i].begin(), _moves[i].end());
        std::cout << std::endl;
    }
    #endif
}

MovableComplex::MovableComplex(const MovableComplex & cpy)
{
    _dimension = cpy._dimension;
    _faces = cpy._faces;
    _moves = cpy._moves;
}

MovableComplex & MovableComplex::operator=(const MovableComplex & cpy)
{
    if (this == &cpy)
        return *this;

    _dimension = cpy._dimension;
    _faces = cpy._faces;
    _moves = cpy._moves;

    return *this;
}

MovableComplex::~MovableComplex()
{
}

unsigned int MovableComplex::dimension() const
{
    return _dimension;
}

unsigned int MovableComplex::f(unsigned int d) const
{
    if (d <= _dimension)
        return static_cast<unsigned int>(_faces[d].size());

    return 0;
}

bool MovableComplex::hasValidMoves(unsigned int codimension) const
{
    if (!_moves[codimension].empty())
    {
        for (bistellar_move_option_list_t::const_iterator it = _moves[codimension].begin(); it != _moves[codimension].end(); it++)
        {
            if(it->second)
                return true;
        }
    }

    return false;
}

bistellar_move_list_t MovableComplex::validMoves(unsigned int codimension) const
{
    bistellar_move_list_t validMoves;
    if (!_moves[codimension].empty())
    {
        for (bistellar_move_option_list_t::const_iterator it = _moves[codimension].begin(); it != _moves[codimension].end(); it++)
        {
            if(it->second)
                validMoves.push_back(it->first);
        }
    }
    return validMoves;
}

void MovableComplex::moveComplex(const BistellarMove & move)
{
    face_list_t::iterator faceIt = std::find(_faces[move.dimension()].begin(), _faces[move.dimension()].end(), move.face());
    bistellar_move_option_list_t::iterator moveIt = std::find(_moves[move.codimension()].begin(), _moves[move.codimension()].end(), std::make_pair(move, true));

    if (faceIt != _faces[move.dimension()].end() && moveIt != _moves[move.codimension()].end() && moveIt->second)
    {
        #ifdef Bistellar_debug_output
        std::cout << "Applying " << move << " to complex ";
        list_print(std::cout, _faces[_dimension].begin(), _faces[_dimension].end());
        std::cout << "." << std::endl;
        #endif
        if (move.codimension() == 0)
        {
            // remove face*∂link
            _faces[move.dimension()].erase(faceIt);
            _moves[move.codimension()].erase(moveIt);

            // add ∂face*link
            vertex_t largestVertex = 0;
            if (!_faces[0].empty())
            {
                for (face_list_t::const_iterator it = _faces[0].begin(); it != _faces[0].end(); it++)
                {
                    if (vertex_t_compare(&largestVertex, &(it->vertex(0))) < 0)
                        largestVertex = it->vertex(0);
                }
            }
            largestVertex++;
            Face newVertex(&largestVertex, 0);
            _faces[0].push_back(newVertex);

            face_list_t listOfSubfaces;
            addSubfacesOfFace(move.face(), listOfSubfaces);
            face_list_t listOfBoundaryfaces;
            addBoundaryfacesOfFace(move.face(), listOfBoundaryfaces);
            if (!listOfSubfaces.empty())
            {
                for (face_list_t::iterator it = listOfSubfaces.begin(); it != listOfSubfaces.end(); it++)
                {
                    Face newFace = Face::unite(*it, newVertex);
                    // add new face to complex
                    _faces[newFace.dimension()].push_back(newFace);

                    // add new move options
                    if (newFace.dimension() == this->dimension())
                    {
                        _moves[0].push_back(std::make_pair(BistellarMove(newFace, Face()), true));
                    }
                    else
                    {
                        face_list_t listOfLinkFaces;
                        for (face_list_t::iterator it2 = listOfBoundaryfaces.begin(); it2 != listOfBoundaryfaces.end(); it2++)
                        {
                            if (it->isSubfaceOf(*it2))
                                listOfLinkFaces.push_back(*it2);
                        }
                        if (listOfLinkFaces.size() == this->dimension() - it->dimension() + 1)
                        {
                            Face linkFace = Face::linkFace(*it, listOfLinkFaces);
                            if (linkFace.dimension() <= this->dimension())
                                _moves[this->dimension() - it->dimension()].push_back(std::make_pair(BistellarMove(*it, linkFace), false));
                        }
                    }
                }
                updateBallBoundary(*this, listOfSubfaces);
            }
        }
        else
        {
            // remove face*∂link
            face_list_t listOfLinkSubfaces;
            addSubfacesOfFace(move.link(), listOfLinkSubfaces);

            _faces[move.dimension()].erase(faceIt);
            _moves[move.codimension()].erase(moveIt);
            if (!listOfLinkSubfaces.empty())
            {
                for (face_list_t::iterator it = listOfLinkSubfaces.begin(); it != listOfLinkSubfaces.end(); it++)
                {
                    // remove old faces
                    Face oldFace = Face::unite(move.face(), *it);
                    face_list_t::iterator oldFaceIt = std::find(_faces[oldFace.dimension()].begin(), _faces[oldFace.dimension()].end(), oldFace);
                    if (oldFaceIt != _faces[oldFace.dimension()].end())
                        _faces[oldFace.dimension()].erase(oldFaceIt);

                    // remove old moves
                    if (!_moves[this->dimension() - oldFace.dimension()].empty())
                    {
                        for (bistellar_move_option_list_t::iterator oldMoveIt = _moves[this->dimension() - oldFace.dimension()].begin(); oldMoveIt != _moves[this->dimension() - oldFace.dimension()].end(); oldMoveIt++)
                        {
                            if (oldMoveIt->first.face() == oldFace)
                            {
                                _moves[this->dimension() - oldFace.dimension()].erase(oldMoveIt);
                                break;
                            }
                        }
                    }
                }
            }

            // add ∂face*link
            face_list_t listOfFaceSubfaces;
            addSubfacesOfFace(move.face(), listOfFaceSubfaces);
            listOfFaceSubfaces.push_back(Face());
            if (!listOfFaceSubfaces.empty())
            {
                face_list_t listOfNewFacets;
                face_list_t listOfBallInteriorFaces;

                // add the new faces
                for (face_list_t::iterator it = listOfFaceSubfaces.begin(); it != listOfFaceSubfaces.end(); it++)
                {
                    Face newFace = Face::unite(*it, move.link());

                    if (_faces[newFace.dimension()].empty() || std::find(_faces[newFace.dimension()].begin(), _faces[newFace.dimension()].end(), newFace) == _faces[newFace.dimension()].end())
                    {
                        _faces[newFace.dimension()].push_back(newFace);
                    }

                    if (newFace.dimension() == this->dimension())
                    {
                        listOfNewFacets.push_back(newFace);
                    }
                    else
                    {
                        listOfBallInteriorFaces.push_back(newFace);
                    }
                }

                // add the new moves
                for (face_list_t::iterator it = listOfFaceSubfaces.begin(); it != listOfFaceSubfaces.end(); it++)
                {
                    Face newFace = Face::unite(*it, move.link());
                    if (newFace.dimension() == this->dimension())
                    {
                        _moves[0].push_back(std::make_pair(BistellarMove(newFace, Face()),true));
                    }
                    else
                    {
                        face_list_t listOfLinkFaces;
                        for (face_list_t::iterator it2 = listOfNewFacets.begin(); it2 != listOfNewFacets.end(); it2++)
                        {
                            if (newFace.isSubfaceOf(*it2))
                                listOfLinkFaces.push_back(*it2);
                        }
                        if (listOfLinkFaces.size() == this->dimension() - newFace.dimension() + 1)
                        {
                            Face linkFace = Face::linkFace(newFace, listOfLinkFaces);
                            if (linkFace.dimension() <= this->dimension())
                                _moves[this->dimension() - newFace.dimension()].push_back(std::make_pair(BistellarMove(newFace, linkFace), false));
                        }
                    }
                }

                face_list_t listOfBallBounaryFaces;
                if (!listOfNewFacets.empty())
                {
                    for (face_list_t::iterator it = listOfNewFacets.begin(); it != listOfNewFacets.end(); it++)
                    {
                        face_list_t listOfNewFacetSubfaces;
                        addSubfacesOfFace(*it, listOfNewFacetSubfaces);
                        if (!listOfNewFacetSubfaces.empty())
                        {
                            for (face_list_t::iterator it2 = listOfNewFacetSubfaces.begin(); it2 != listOfNewFacetSubfaces.end(); it2++)
                            {
                                if ((listOfBallInteriorFaces.empty() || std::find(listOfBallInteriorFaces.begin(), listOfBallInteriorFaces.end(), *it2) == listOfBallInteriorFaces.end())
                                    && (listOfBallBounaryFaces.empty() || std::find(listOfBallBounaryFaces.begin(), listOfBallBounaryFaces.end(), *it2) == listOfBallBounaryFaces.end()))
                                    listOfBallBounaryFaces.push_back(*it2);
                            }
                        }
                    }
                }

                updateBallBoundary(*this, listOfBallBounaryFaces);
            }
        }

        updateMoveValidity(*this);

        #ifdef Bistellar_debug_output
        std::cout << "Resulting complex is ";
        list_print(std::cout, _faces[_dimension].begin(), _faces[_dimension].end());
        std::cout << "." << std::endl;
        for (int i = 0; i < _dimension+1; i++)
        {
            std::cout << _moves[i].size() << " " << i << "-Moves: ";
            if (!_moves[i].empty()) list_print(std::cout, _moves[i].begin(), _moves[i].end());
            std::cout << std::endl;
        }
        #endif
    }
    else
    {
        #ifdef Bistellar_debug_output
        std::cout << move << " is not a valid move for the complex " << *this << std::endl;
        #endif
    }
}

// used in the implementation of moveComplex
void updateBallBoundary(MovableComplex & complex, const face_list_t & ballBoundaryFaces)
{
    if (!ballBoundaryFaces.empty())
    {
        for (face_list_t::const_iterator it = ballBoundaryFaces.begin(); it != ballBoundaryFaces.end(); it++)
        {
            face_list_t linkFacets;
            // copy all facets that contain (*it) as a subface to linkFacets
            if (!complex._faces[complex._dimension].empty())
            {
                for (face_list_t::const_iterator it2 = complex._faces[complex._dimension].begin(); it2 != complex._faces[complex._dimension].end(); it2++)
                {
                    if (it->isSubfaceOf(*it2))
                        linkFacets.push_back(*it2);
                }
            }

            // remove the move option with (*it) as face
            if (!complex._moves[complex._dimension - it->dimension()].empty())
            {
                if (!complex._moves[complex._dimension - it->dimension()].empty())
                {
                    for (bistellar_move_option_list_t::iterator mIt = complex._moves[complex._dimension - it->dimension()].begin(); mIt != complex._moves[complex._dimension - it->dimension()].end(); mIt++)
                    {
                        if (mIt->first.face() == *it)
                        {
                            complex._moves[complex._dimension - it->dimension()].erase(mIt);
                            break;
                        }
                    }
                }
            }


            if (linkFacets.size() == complex._dimension - it->dimension() + 1)
            {
                // add the move option.
                Face linkFace = Face::linkFace(*it, linkFacets);
                if (linkFace.dimension() <= complex._dimension)
                    complex._moves[complex._dimension - it->dimension()].push_back(std::make_pair(BistellarMove(*it, linkFace), (std::find(complex._faces[linkFace.dimension()].begin(), complex._faces[linkFace.dimension()].end(), linkFace) == complex._faces[linkFace.dimension()].end())));
            }
        }
    }
}
void updateMoveValidity(MovableComplex & complex)
{
    for (unsigned int i = 1; i < complex._dimension + 1; i++)
    {
        if (!complex._moves[i].empty())
        {
            for (bistellar_move_option_list_t::iterator it = complex._moves[i].begin(); it != complex._moves[i].end(); it++)
                it->second = (std::find(complex._faces[it->first.link().dimension()].begin(), complex._faces[it->first.link().dimension()].end(), it->first.link()) == complex._faces[it->first.link().dimension()].end());
        }
    }
}

// serialization methods
std::ostream & operator<< (std::ostream & os, const MovableComplex & complex)
{
    if (!complex._faces[complex._dimension].empty())
    {
        list_print(os ,complex._faces[complex._dimension].begin(), complex._faces[complex._dimension].end());
    }
    else
    {
        os << "[]";
    }
    return os;
}
std::istream & operator>> (std::istream & is, MovableComplex & complex)
{
    std::deque< Face > facets;
    list_read(is, facets);

    if (facets.empty())
    {
        complex = MovableComplex();
    }
    else
    {
        complex = MovableComplex(facets, facets.begin()->dimension());
    }

    return is;
}

quality82%

¤ Dauer der Verarbeitung: 0.17 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.