/*! \file src/link.cpp
    \author Klaas Holwerda
 
    Copyright: 2001-2004 (C) Klaas Holwerda
 
    Licence: see kboollicense.txt 
 
    RCS-ID: $Id: link.cpp,v 1.4 2009/09/07 19:23:28 titato Exp $
*/

#include "kbool/booleng.h"

#include "kbool/link.h"
#include "kbool/line.h"
#include <math.h>
#include <assert.h>

#include "kbool/node.h"
#include "kbool/graph.h"
#include "kbool/graphlst.h"

int linkXYsorter( kbLink *, kbLink * );

//
// Default constructor
//
kbLink::kbLink( Bool_Engine* GC )
{
    _GC = GC;
    Reset();
}


//
// This constructor makes this link a valid part of a graph
//
kbLink::kbLink( int graphnr, kbNode *begin, kbNode *end, Bool_Engine* GC )
{
    _GC = GC;
    Reset();

    // Set the references of the node and of this link correct
    begin->AddLink( this );
    end->AddLink( this );
    m_beginnode = begin;
    m_endnode = end;
    m_graphnum = graphnr;
}

//
// This constructor makes this link a valid part of a graph
//
kbLink::kbLink( kbNode *begin, kbNode *end, Bool_Engine* GC )
{
    _GC = GC;
    Reset();

    // Set the references of the node and of this link correct
    begin->AddLink( this );
    end->AddLink( this );
    m_beginnode = begin;
    m_endnode = end;
    m_graphnum = 0;
}


//
// Destructor
//
kbLink::~kbLink()
{
    UnLink();
}

//
// Checks whether the current algorithm has been on this link
//
bool kbLink::BeenHere()
{
    if ( m_bin ) return true;
    return false;
}

void kbLink::TakeOverOperationFlags( kbLink* link )
{
    m_merge_L = link->m_merge_L;
    m_a_substract_b_L = link->m_a_substract_b_L;
    m_b_substract_a_L = link->m_b_substract_a_L;
    m_intersect_L = link->m_intersect_L;
    m_exor_L = link->m_exor_L;

    m_merge_R = link->m_merge_R;
    m_a_substract_b_R = link->m_a_substract_b_R;
    m_b_substract_a_R = link->m_b_substract_a_R;
    m_intersect_R = link->m_intersect_R;
    m_exor_R = link->m_exor_R;
}
//
// Returns the next link from the argument
//
kbLink* kbLink::Forth( kbNode *node )
{
    assert( node == m_beginnode || node == m_endnode );
    return node->GetOtherLink( this );
}

//
// Returns the Beginnode
//
kbNode *kbLink::GetBeginNode()
{
    return m_beginnode;
}

//
// Returns the endnode
//
kbNode* kbLink::GetEndNode()
{
    return m_endnode;
}

kbNode* kbLink::GetLowNode()
{
    return ( ( m_beginnode->GetY() < m_endnode->GetY() ) ? m_beginnode : m_endnode );
}

kbNode* kbLink::GetHighNode()
{
    return ( ( m_beginnode->GetY() > m_endnode->GetY() ) ? m_beginnode : m_endnode );
}

//
// Returns the graphnumber
//
int kbLink::GetGraphNum()
{
    return m_graphnum;
}

bool kbLink::GetInc()
{
    return m_Inc;
//   if (Inc) return true;
// return false;
}

void kbLink::SetInc( bool inc )
{
    m_Inc = inc;
//   Inc=0;
//   if (inc) Inc=1;
}

bool kbLink::GetLeftA()
{
    return m_LeftA;
}

void kbLink::SetLeftA( bool la )
{
    m_LeftA = la;
}

bool kbLink::GetLeftB()
{
    return m_LeftB;
}

void kbLink::SetLeftB( bool lb )
{
    m_LeftB = lb;
}

bool kbLink::GetRightA()
{
    return m_RightA;
}

void kbLink::SetRightA( bool ra )
{
    m_RightA = ra;
}

bool kbLink::GetRightB()
{
    return m_RightB;
}

void kbLink::SetRightB( bool rb )
{
    m_RightB = rb;
}

//
// This function is very popular by GP-faults
// It returns the node different from a
//
kbNode* kbLink::GetOther( const kbNode *const a )
{
    return ( ( a != m_beginnode ) ? m_beginnode : m_endnode );
}


//
// Is this marked for given operation
//
bool kbLink::IsMarked( BOOL_OP operation )
{
    switch ( operation )
    {
        case( BOOL_OR ):     return m_merge_L || m_merge_R;
        case( BOOL_AND ):    return m_intersect_L || m_intersect_R;
        case( BOOL_A_SUB_B ):  return m_a_substract_b_L || m_a_substract_b_R;
        case( BOOL_B_SUB_A ):  return m_b_substract_a_L || m_b_substract_a_R;
        case( BOOL_EXOR ):    return m_exor_L || m_exor_R;
        default:             return false;
    }
}

bool kbLink::IsMarkedLeft( BOOL_OP operation )
{
    switch ( operation )
    {
        case( BOOL_OR ):      return m_merge_L;
        case( BOOL_AND ):     return m_intersect_L;
        case( BOOL_A_SUB_B ): return m_a_substract_b_L;
        case( BOOL_B_SUB_A ): return m_b_substract_a_L;
        case( BOOL_EXOR ):    return m_exor_L;
        default:            return false;
    }
}

bool kbLink::IsMarkedRight( BOOL_OP operation )
{
    switch ( operation )
    {
        case( BOOL_OR ):      return m_merge_R;
        case( BOOL_AND ):     return m_intersect_R;
        case( BOOL_A_SUB_B ): return m_a_substract_b_R;
        case( BOOL_B_SUB_A ): return m_b_substract_a_R;
        case( BOOL_EXOR ):    return m_exor_R;
        default:            return false;
    }
}

//
// Is this a hole for given operation
// beginnode must be to the left
bool kbLink::IsHole( BOOL_OP operation )
{

    bool topsideA, topsideB;

    if ( m_beginnode->GetX() < m_endnode->GetX() ) //going to the right?
    {  topsideA = m_RightA; topsideB = m_RightB;  }
    else
    {  topsideA = m_LeftA; topsideB = m_LeftB; }

    switch ( operation )
    {
        case( BOOL_OR ):      return ( !topsideB && !topsideA );
        case( BOOL_AND ):     return ( !topsideB || !topsideA );
        case( BOOL_A_SUB_B ): return ( topsideB || !topsideA );
        case( BOOL_B_SUB_A ): return ( topsideA || !topsideB );
        case( BOOL_EXOR ):    return !( ( topsideB && !topsideA ) || ( !topsideB && topsideA ) );
        default:            return false;
    }
}

//
// Is this a part of a hole
//
bool kbLink::GetHole()
{
    return ( m_hole );
}


void kbLink::SetHole( bool h )
{
    m_hole = h;
}


//
// Is this not marked at all
//
bool kbLink::IsUnused()
{
    return
        !( m_merge_L || m_merge_R ||
           m_a_substract_b_L || m_a_substract_b_R ||
           m_b_substract_a_L || m_b_substract_a_R ||
           m_intersect_L || m_intersect_R ||
           m_exor_L || m_exor_R );
}


bool kbLink::IsZero( B_INT marge )
{
    return ( m_beginnode->Equal( m_endnode, marge ) ) ;
}


bool kbLink::ShorterThan( B_INT marge )
{
    return ( m_beginnode->ShorterThan( m_endnode, marge ) ) ;
}


//
// Mark this link
//
void kbLink::Mark()
{
    m_mark = true;
}


#ifndef ABS
#define ABS(a) (((a)<0) ? -(a) : (a))
#endif


//
// This makes from the begin and endnode one node (argument begin_or_end_node)
// The references to this link in the node will also be deleted
// After doing that, link link can be deleted or be recycled.
//
void kbLink::MergeNodes( kbNode *const begin_or_end_node )
{
// assert(beginnode && endnode);
// assert ((begin_or_end_node == beginnode)||(begin_or_end_node == endnode));

    m_beginnode->RemoveLink( this );
    m_endnode->RemoveLink( this );

    if ( m_endnode != m_beginnode )
    { // only if beginnode and endnode are different nodes
        begin_or_end_node->Merge( GetOther( begin_or_end_node ) );
    }
    m_endnode = NULL;
    m_beginnode = NULL;
}

//
// Return the position of the second link compared to this link
// Result = IS_ON | IS_LEFT | IS_RIGHT
// Here Left and Right is defined as being left or right from
// the this link towards the center (common) node
//
LinkStatus kbLink::OutProduct( kbLink* const two, double accur )
{
    kbNode * center;
    double distance;
    if ( two->GetBeginNode()->Equal( two->GetEndNode(), 1 ) )
        assert( !two );
    if ( GetBeginNode()->Equal( GetEndNode(), 1 ) )
        assert( !this );
    kbLine* temp_line = new kbLine( this, _GC );

    //the this link should connect to the other two link at at least one node
    if ( m_endnode == two->m_endnode || m_endnode == two->m_beginnode )
        center = m_endnode;
    else
    {
        center = m_beginnode;
//  assert(center==two->endnode || center==two->beginnode);
    }

    //here something tricky
    // the factor 10000.0 is needed to asure that the pointonline
    // is more accurate in this case compared to the intersection for graphs
    int uitp = temp_line->PointOnLine( two->GetOther( center ), distance, accur );

    delete temp_line;

    /*double uitp= (_x - first._x) * (third._y - _y) -
        (_y - first._y) * (third._x - _x);
    if (uitp>0) return IS_LEFT;
    if (uitp<0) return IS_RIGHT;
    return IS_ON;*/

    //depending on direction of this link (going to or coming from centre)
    if ( center == m_endnode )
    {
        if ( uitp == LEFT_SIDE )
            return IS_LEFT;
        if ( uitp == RIGHT_SIDE )
            return IS_RIGHT;
    }
    else  //center=beginnode
    {
        if ( uitp == LEFT_SIDE )
            return IS_RIGHT;
        if ( uitp == RIGHT_SIDE )
            return IS_LEFT;
    }
    return IS_ON;
}

//
// Return the position of the third link compared to this link and
// the second link
// Result = IS_ON | IS_LEFT | IS_RIGHT
//
LinkStatus kbLink::PointOnCorner( kbLink* const two, kbLink* const third )
{
    LinkStatus
    TwoToOne,  // Position of two to this line
    ThirdToOne,    // Position of third to this line
    ThirdToTwo,  // Position of third to two
    Result;

//m  kbNode* center;

//the this link should connect to the other two link at at least one node
//m  if (endnode==two->endnode || endnode==two->beginnode)
//m   center=endnode;
//m  else
//m  { center=beginnode;
//  assert(center==two->endnode || center==two->beginnode);
//m }
// assert(center==third->endnode || center==third->beginnode);



    // Calculate the position of the links compared to eachother
    TwoToOne  = OutProduct( two, _GC->GetAccur() );
    ThirdToOne = OutProduct( third, _GC->GetAccur() );
    //center is used in outproduct to give de direction of two
    // this is why the result should be swapped
    ThirdToTwo = two->OutProduct( third, _GC->GetAccur() );
    if ( ThirdToTwo == IS_RIGHT )
        ThirdToTwo = IS_LEFT;
    else if ( ThirdToTwo == IS_LEFT )
        ThirdToTwo = IS_RIGHT;

    // Select the result
    switch( TwoToOne )
    {
            // Line 2 lies on  leftside of this line
        case IS_LEFT : if ( ( ThirdToOne == IS_RIGHT ) || ( ThirdToTwo == IS_RIGHT ) ) return IS_RIGHT;
            else if ( ( ThirdToOne == IS_LEFT ) && ( ThirdToTwo == IS_LEFT ) ) return IS_LEFT;
            else Result = IS_ON; break;
            // Line 2 lies on this line
        case IS_ON  : if ( ( ThirdToOne == IS_RIGHT ) && ( ThirdToTwo == IS_RIGHT ) )    return IS_RIGHT;
            else if ( ( ThirdToOne == IS_LEFT ) && ( ThirdToTwo == IS_LEFT ) )   return IS_LEFT;
            //  else if ((ThirdToOne==IS_RIGHT) && (ThirdToTwo==IS_LEFT))   return IS_RIGHT;
            //  else if ((ThirdToOne==IS_LEFT) && (ThirdToTwo==IS_RIGHT))   return IS_LEFT;
            else Result = IS_ON; break;
            // Line 2 lies on right side of this line
        case IS_RIGHT : if ( ( ThirdToOne == IS_RIGHT ) && ( ThirdToTwo == IS_RIGHT ) ) return IS_RIGHT;
            else if ( ( ThirdToOne == IS_LEFT ) || ( ThirdToTwo == IS_LEFT ) ) return IS_LEFT;
            else Result = IS_ON; break;
        default: Result = IS_ON; assert( false );
    }
    return Result;
}

//
// Remove the reference from this link to a_node
//
void kbLink::Remove( kbNode *a_node )
{
    ( m_beginnode == a_node ) ? m_beginnode = NULL : m_endnode = NULL;
}


//
// Replace oldnode by newnode and correct the references
//
void kbLink::Replace( kbNode *oldnode, kbNode *newnode )
{
    if ( m_beginnode == oldnode )
    {
        m_beginnode->RemoveLink( this ); // remove the reference to this
        newnode->AddLink( this );       // let newnode refer to this
        m_beginnode = newnode;    // let this refer to newnode
    }
    else
    { //assert(endnode==oldnode);
        m_endnode->RemoveLink( this );
        newnode->AddLink( this );
        m_endnode = newnode;
    }
}


//
// Reset all values
//
void kbLink::Reset()
{
    m_beginnode = 0;
    m_endnode = 0;
    Reset_flags();
}


//
// Reset all flags
//
void kbLink::Reset_flags()
{
    m_bin = false;    // Marker for walking over the graph
    m_hole  = false;   // Is this a part of hole ?
    m_hole_top = false;    // link that is toplink of hole?
    m_group = GROUP_A;  // Does this belong to group A or B ( o.a. for boolean operations between graphs)
    m_LeftA = false;      // Is left in polygongroup A
    m_RightA = false;      // Is right in polygon group A
    m_LeftB = false;      // Is left in polygon group B
    m_RightB = false;      // Is right in polygongroup B
    m_mark = false;      // General purose marker, internally unused
    m_holelink = false;

    m_merge_L = m_merge_R = false;   // Marker for Merge
    m_a_substract_b_L = m_a_substract_b_R = false; // Marker for substract
    m_b_substract_a_L = m_b_substract_a_R = false; // Marker for substract
    m_intersect_L = m_intersect_R = false;  // Marker for intersect
    m_exor_L = m_exor_R = false;          // Marker for Exor
}

//
// Refill this link by the arguments
//
void kbLink::Reset( kbNode *begin, kbNode *end, int graphnr )
{
    // Remove all the previous references
    UnLink();
    Reset();
    // Set the references of the node and of this link correct
    begin->AddLink( this );
    end->AddLink( this );
    m_beginnode = begin;
    m_endnode = end;
    if ( graphnr != 0 )
        m_graphnum = graphnr;
}


void kbLink::Set( kbNode *begin, kbNode *end )
{
    m_beginnode = begin;
    m_endnode = end;
}

void kbLink::SetBeenHere()
{
    m_bin = true;
}

void kbLink::SetNotBeenHere()
{
    m_bin = false;
}

void kbLink::SetBeginNode( kbNode* new_node )
{
    m_beginnode = new_node;
}


void kbLink::SetEndNode( kbNode* new_node )
{
    m_endnode = new_node;
}


//
// Sets the graphnumber to argument num
//
void kbLink::SetGraphNum( int num )
{
    m_graphnum = num;
}

GroupType kbLink::Group()
{
    return m_group;
}


//
// Reset the groupflag to argument groep
//
void kbLink::SetGroup( GroupType groep )
{
    m_group = groep;
}


//
// Remove all references to this link and from this link
//
void kbLink::UnLink()
{
    if ( m_beginnode )
    {
        m_beginnode->RemoveLink( this );
        if ( !m_beginnode->GetNumberOfLinks() ) delete m_beginnode;
    }
    m_beginnode = NULL;
    if ( m_endnode )
    {
        m_endnode->RemoveLink( this );
        if ( !m_endnode->GetNumberOfLinks() ) delete m_endnode;
    }
    m_endnode = NULL;
}


void kbLink::UnMark()
{
    m_mark = false;
    m_bin = false;
}

void kbLink::SetMark( bool value )
{
    m_mark = value;
}

//
// general purpose mark checker
//
bool kbLink::IsMarked() { return m_mark; }

void  kbLink::SetTopHole( bool value ) { m_hole_top = value; }

bool kbLink::IsTopHole() { return m_hole_top; }

//
// Calculates the merge/substact/exor/intersect flags
//
void kbLink::SetLineTypes()
{
    m_merge_R     =
        m_a_substract_b_R =
            m_b_substract_a_R =
                m_intersect_R =
                    m_exor_R      =
                        m_merge_L     =
                            m_a_substract_b_L =
                                m_b_substract_a_L =
                                    m_intersect_L =
                                        m_exor_L      = false;

    //if left side is in group A and B then it is for the merge
    m_merge_L   = m_LeftA || m_LeftB;
    m_merge_R   = m_RightA || m_RightB;
    //both in mean does not add to result.
    if ( m_merge_L && m_merge_R )
        m_merge_L = m_merge_R = false;

    m_a_substract_b_L = m_LeftA && !m_LeftB;
    m_a_substract_b_R = m_RightA && !m_RightB;
    //both in mean does not add to result.
    if ( m_a_substract_b_L && m_a_substract_b_R )
        m_a_substract_b_L = m_a_substract_b_R = false;

    m_b_substract_a_L = m_LeftB && !m_LeftA;
    m_b_substract_a_R = m_RightB && !m_RightA;
    //both in mean does not add to result.
    if ( m_b_substract_a_L && m_b_substract_a_R )
        m_b_substract_a_L = m_b_substract_a_R = false;

    m_intersect_L = m_LeftB && m_LeftA;
    m_intersect_R = m_RightB && m_RightA;
    //both in mean does not add to result.
    if ( m_intersect_L && m_intersect_R )
        m_intersect_L = m_intersect_R = false;

    m_exor_L = !( ( m_LeftB && m_LeftA ) || ( !m_LeftB && !m_LeftA ) );
    m_exor_R = !( ( m_RightB && m_RightA ) || ( !m_RightB && !m_RightA ) );
    //both in mean does not add to result.
    if ( m_exor_L && m_exor_R )
        m_exor_L = m_exor_R = false;
}


//put in direction with a_node as beginnode
void  kbLink::Redirect( kbNode* a_node )
{
    if ( a_node != m_beginnode )
    {
        // swap the begin- and endnode of the current link
        kbNode * dummy = m_beginnode;
        m_beginnode = m_endnode;
        m_endnode = dummy;

        bool swap = m_LeftA;
        m_LeftA = m_RightA;
        m_RightA = swap;

        swap = m_LeftB;
        m_LeftB = m_RightB;
        m_RightB = swap;

        swap = m_merge_L ;
        m_merge_L = m_merge_R;
        m_merge_R = swap;

        swap = m_a_substract_b_L;
        m_a_substract_b_L = m_a_substract_b_R;
        m_a_substract_b_R = swap;

        swap = m_b_substract_a_L;
        m_b_substract_a_L = m_b_substract_a_R;
        m_b_substract_a_R = swap;

        swap = m_intersect_L;
        m_intersect_L = m_intersect_R;
        m_intersect_R = swap;

        swap = m_exor_L;
        m_exor_L = m_exor_R;
        m_exor_R = swap;
    }
}
