/****************************************************
          *                                                  *
          *     link_geometry.cpp:  initializes all the      *
          *     objects representing geometric aspects of    *
          *     the link diagram:  crossings, edges etc.     *
          *                                                  *
          ****************************************************/




#include "link_diagram.h"
#include <cstdio>


bool Link::make_geometry()
{
    int i, j, k, m, n, nn, t, r0, r1, r2, r3, r4, r5, r6, r7;
    
    /*
     *  Allocate memory for crossings and edges
     */
    
    num_sides.reserve( crossing_number + 3 );
    region_color.reserve( crossing_number + 3 );
    
    for (i=0; i<=crossing_number; ++i)
    {
        Crossing *c = new Crossing;
        crossingList.push_back( c );
    }
    
    {
        Crossing *c = crossingList[0];
        c->north = new Crossing_ray;
        c->west  = new Crossing_ray;
        c->south = new Crossing_ray;
        c->east  = new Crossing_ray;
        c->ne = new Quadrant;
        c->nw = new Quadrant;
        c->sw = new Quadrant;
        c->se = new Quadrant;
    }
   
    for (i=0; i<=2*crossing_number; ++i)
    {
        Edge *e = new Edge;
        edgeList.push_back( e );
    }
       
    for (i=0; i<=2*crossing_number; ++i)
    {
        edgeList[i]->black_side = new Edge_side;
        edgeList[i]->white_side = new Edge_side;
    }
    
    for (i=0; i<=2*crossing_number; ++i)
    {
        Pass *p = new Pass;
        passList.push_back( p );
    }

    
    /*
     *  Begin making the link diagram data structure; components are numbered
     *  from 0, whereas crossings, edges, regions are numbered from 1.
     */     
    
    for (i=0; i<num_components; ++i) for ( j=comp_start[i]; j<=comp_end[i]; ++j )
    {
        Pass *p = passList[j];
        
        p->index = j;
        p->component = i;
        p->partner = passList[ dowker[j] ];
        
        p->next = passList[ next_index[j] ];
        p->prev = passList[ prev_index[j] ];
        p->circuit_index = -1;
        p->tangle_index = -1;
    }
        
    /*
     *  Set up integer members of crossings,
     *  and allocate memory for the four crossing rays at each crossing
     */
     
    for (i=1; i<=crossing_number; ++i)
    {   
        Crossing *c = crossingList[i];
                 
        c->index = i;
        c->sign = crossing_sign[2*i-1];
        c->alt_sign = alt_sign[2*i-1];
        c->orientation = c->sign * c->alt_sign;
        
        c->north = new Crossing_ray;
        c->west  = new Crossing_ray;
        c->south = new Crossing_ray;
        c->east  = new Crossing_ray;
        
        c->odd = passList[2*i-1];
        c->even = passList[dowker[2*i-1]];
        c->over = ( c->alt_sign == 1 ) ? c->odd : c->even;
        c->under = ( c->alt_sign == 1 ) ? c->even : c->odd;
        c->over->crossing = c;
        c->under->crossing = c;
        c->over->alt_sign = c->alt_sign;
        c->under->alt_sign = c->alt_sign;
        c->over->level = over;
        c->under->level = under;
    }
    
    /*
     *  Construct the crossing rays
     */
    
    for (i=1; i<=crossing_number; ++i)
    {
        Crossing *c = crossingList[i];
        
        c->north->crossing = c;
        c->north->edge = edgeList[2*i-1];
        c->north->mode = forwards;
        c->north->compass_dir = north;
        c->north->next = c->west;
        c->north->prev = c->east;
        
        c->south->crossing = c;
        c->south->edge = edgeList[ prev_index[2*i-1] ];
        c->south->mode = backwards;
        c->south->compass_dir = south;
        c->south->next = c->east;
        c->south->prev = c->west;
        
        c->east->crossing = c;
        c->east->compass_dir = east;
        c->east->next = c->north;
        c->east->prev = c->south;
        c->west->crossing = c;
        c->west->compass_dir = west;
        c->west->next = c->south;
        c->west->prev = c->north;
        
        Crossing_ray *r1 = ( c->sign == -1 ) ? c->east : c->west;
        Crossing_ray *r2 = ( c->sign == -1 ) ? c->west : c->east;
        
        int tmp = dowker[2*i-1];
        
        r1->edge = edgeList[ tmp ];
        r1->mode = forwards;
        r2->edge = edgeList[ prev_index[ tmp ] ];
        r2->mode = backwards;
        
        c->north->pass = c->south->pass = c->odd;
        c->east->pass = c->west->pass = c->even;
    }


    /*
     *  Determine the four crossing ray neighbors at each crossing
     */
     
    for (i=1; i<=crossing_number; ++i)
    {
        Crossing *c = crossingList[i], *c1;
        
        c1 = c->odd->next->crossing;
        c->n_neighbor = ( c1->sign == 1 ) ? c1->east : c1->west;
        
        c1 = c->odd->prev->crossing;
        c->s_neighbor = ( c1->sign == 1 ) ? c1->west : c1->east;
        
        if ( c->sign == 1 )
        {
            c1 = c->even->next->crossing;
            c->w_neighbor = c1->south;
            c1 = c->even->prev->crossing;
            c->e_neighbor = c1->north;
        }
        else
        {
            c1 = c->even->prev->crossing;
            c->w_neighbor = c1->north;
            c1 = c->even->next->crossing;
            c->e_neighbor = c1->south;
        }
    }
    
   
    /*
     *  Construct the four quadrants at each crossing
     */
    
    for (i=1; i<=crossing_number; ++i)
    {
        Crossing *c = crossingList[i];
        
        c->ne = new Quadrant;
        c->nw = new Quadrant;
        c->sw = new Quadrant;
        c->se = new Quadrant;
        
        c->ne->region_index = 0;
        c->nw->region_index = 0;
        c->sw->region_index = 0;
        c->se->region_index = 0;
        
        c->ne->color = white;
        c->nw->color = black;
        c->sw->color = white;
        c->se->color = black;
        
        c->ne->crossing = c;
        c->nw->crossing = c;
        c->sw->crossing = c;
        c->se->crossing = c;
        
        c->ne->tree = false;
        c->nw->tree = false;
        c->sw->tree = false;
        c->se->tree = false;
        
        c->ne->clockwise = c->se;
        c->ne->counterclockwise = c->nw;
        c->nw->clockwise = c->ne;
        c->nw->counterclockwise = c->sw;
        c->sw->clockwise = c->nw;
        c->sw->counterclockwise = c->se;
        c->se->clockwise = c->sw;
        c->se->counterclockwise = c->ne;
        
        int m_n = (c->north->mode==forwards) ? 1 : 0;
        int m_w = (c->west ->mode==forwards) ? 1 : 0;
        int m_s = (c->south->mode==forwards) ? 1 : 0;
        int m_e = (c->east ->mode==forwards) ? 1 : 0;
        
        c->ne->arrow_type = i_to_a( (m_e + m_n)%2 );
        c->nw->arrow_type = i_to_a( (m_n + m_w)%2 );
        c->sw->arrow_type = i_to_a( (m_w + m_s)%2 );
        c->se->arrow_type = i_to_a( (m_s + m_e)%2 );
        
    }
    
    /*
     *  These speak for themselves
     */
    
    for (i=1; i<=crossing_number; ++i)
    {
        Crossing *c = crossingList[i];
        
        c->north->left_quadrant  = c->nw;
        c->west ->left_quadrant  = c->sw;
        c->south->left_quadrant  = c->se;
        c->east ->left_quadrant  = c->ne;
        c->north->right_quadrant = c->ne;
        c->west ->right_quadrant = c->nw;
        c->south->right_quadrant = c->sw;
        c->east ->right_quadrant = c->se;
        
        c->nw->left_ray  = c->west;
        c->nw->right_ray = c->north;
        c->sw->left_ray  = c->south;
        c->sw->right_ray = c->west;
        c->se->left_ray  = c->east;
        c->se->right_ray = c->south;
        c->ne->left_ray  = c->north;
        c->ne->right_ray = c->east;
        
        c->nw->twist = ( c->nw->right_ray->pass->level == over ) ? 1 : -1;
        c->ne->twist = ( c->ne->right_ray->pass->level == over ) ? 1 : -1;
        c->se->twist = ( c->se->right_ray->pass->level == over ) ? 1 : -1;
        c->sw->twist = ( c->sw->right_ray->pass->level == over ) ? 1 : -1;
    }
    
    /*
     *  Construct doubly linked lists of quadrants, constituting regions
     */    
    
    for (i=1; i<=crossing_number; ++i)
    {
        Crossing *c = crossingList[i];
        
        c->ne->next = c->n_neighbor->left_quadrant;  // go clockwise around region
        c->nw->next = c->w_neighbor->left_quadrant;
        c->sw->next = c->s_neighbor->left_quadrant;
        c->se->next = c->e_neighbor->left_quadrant;
        
        c->ne->prev = c->e_neighbor->right_quadrant;
        c->nw->prev = c->n_neighbor->right_quadrant;
        c->sw->prev = c->w_neighbor->right_quadrant;
        c->se->prev = c->s_neighbor->right_quadrant;
    }
    
    for (i=1; i<=crossing_number; ++i)
    {
        Crossing *c = crossingList[i];
        
        t = 0;
        Quadrant *q0 = c->nw;
        
        for ( Quadrant *q=q0; q!=q0 || t==0; q=q->clockwise )
        {
            t=1;
            
            if ( q->left_ray->mode == forwards && q->right_ray->mode == forwards )
            {
                q->detailed_arrow_type = source;
                q->seifert_next = NULL;
            }
            else if ( q->left_ray->mode == forwards && q->right_ray->mode == backwards )
            {
                q->detailed_arrow_type = turn_right;
                q->seifert_next = ( q->next->arrow_type==flow_through ) ? q->next : q->next->clockwise;
            }
            else if ( q->left_ray->mode == backwards && q->right_ray->mode == forwards )
            {
                q->detailed_arrow_type = turn_left;
                q->seifert_next = ( q->prev->arrow_type==flow_through ) ? q->prev : q->prev->counterclockwise;
            }
            else if ( q->left_ray->mode == backwards && q->right_ray->mode == backwards )
            {
                q->detailed_arrow_type = sink;
                q->seifert_next = NULL;
            }
        
        //if ( q->seifert_next != NULL ) printf( "%4d%4d\n", q->arrow_type, q->seifert_next->arrow_type );
        }
    
      
    }
    
    
    
    /*
     *  Assign region indices to quadrants
     */
    
    int current_index = 0;
    Quadrant *q;
    baseQuadrantList.push_back( q ); //  dummy quadrant at index 0
    num_sides.push_back( 0 );        //  because numbering starts at 1
    
    for (i=1; i<=crossing_number; ++i) if (current_index < crossing_number + 2)
    {
        Quadrant *current_quadrant;
        int ns;
        
        if (crossingList[i]->ne->region_index == 0)
        {
            current_quadrant = crossingList[i]->ne;
            ++current_index;
            region_color[current_index] = white;
            baseQuadrantList.push_back( current_quadrant );
            ns = 0;
            do {
                ++ns;
                current_quadrant->region_index = current_index;
                current_quadrant = current_quadrant->next;
            } while (current_quadrant->crossing->index != i);
            num_sides.push_back( ns );            
        }

        if (current_index == crossing_number + 2) continue;
        
        if (crossingList[i]->nw->region_index == 0)
        {
            current_quadrant = crossingList[i]->nw;
            ++current_index;
            region_color[current_index] = black;
            baseQuadrantList.push_back( current_quadrant );
            ns = 0;
            do {
                ++ns;
                current_quadrant->region_index = current_index;
                current_quadrant = current_quadrant->next;
            } while (current_quadrant->crossing->index != i);
            num_sides.push_back( ns );
        }

        if (current_index == crossing_number + 2) continue;
    
        if (crossingList[i]->sw->region_index == 0)
        {
            current_quadrant = crossingList[i]->sw;
            ++current_index;
            region_color[current_index] = white;
            baseQuadrantList.push_back( current_quadrant );
            ns = 0;
            do {
                ++ns;
                current_quadrant->region_index = current_index;
                current_quadrant = current_quadrant->next;
            } while (current_quadrant->crossing->index != i);
            num_sides.push_back( ns );
        }

        if (current_index == crossing_number + 2) continue;
    
        if (crossingList[i]->se->region_index == 0)
        {
            current_quadrant = crossingList[i]->se;
            ++current_index;
            region_color[current_index] = black;
            baseQuadrantList.push_back( current_quadrant );
            ns = 0;
            do {
                ++ns;
                current_quadrant->region_index = current_index;
                current_quadrant = current_quadrant->next;
            } while (current_quadrant->crossing->index != i);
            num_sides.push_back( ns );
        }
    
    }
    
    
    for (i=1; i<=crossing_number; ++i)
    {
        Crossing *c = crossingList[i];
        
        c->ne->region_num_sides = num_sides[c->ne->region_index];
        c->nw->region_num_sides = num_sides[c->nw->region_index];
        c->sw->region_num_sides = num_sides[c->sw->region_index];
        c->se->region_num_sides = num_sides[c->se->region_index];
    }
        

    /*
     *  Construct edges and edge-sides
     */
    
    for (i=1; i<=2*crossing_number-1; i+=2)
    {        
        edgeList[i]->index = i;

        edgeList[i]->rear  = crossingList[(i+1)/2]->north;
        edgeList[i]->front = crossingList[(i+1)/2]->n_neighbor;
    }
    
    for (i=2; i<=2*crossing_number; i+=2)
    {
        Edge *e = edgeList[i];
        
        e->index = i;
        e->front = crossingList[ ( next_index[i] + 1 )/2 ]->south;
        e->rear  = crossingList[ ( next_index[i] + 1 )/2 ]->s_neighbor;
    }

    
    for (i=1; i<=2*crossing_number; ++i)
    {
        int rri, lri;
        Edge *e = edgeList[i];
        
        rri = e->rear->right_quadrant->region_index;
        lri = e->rear->left_quadrant->region_index;
        
        e->right_region_index = rri;
        e->left_region_index  = lri;
        
        e->right_color = region_color[rri];
        e->left_color  = region_color[lri];
        
        /*
         *  We take the convention that the edge_sense of an edge is 1 if its direction
         *  is clockwise as seen from the incident black region, and is -1 otherwise.
         */
        
        if (e->right_color==black)
        {
            e->black_side->region_index = e->right_region_index;
            e->white_side->region_index = e->left_region_index;
            e->edge_sense = 1;
            e->black_side->edge_sense = 1;
            e->white_side->edge_sense = 1;
        }
        else
        {
            e->black_side->region_index = e->left_region_index;
            e->white_side->region_index = e->right_region_index;
            e->edge_sense = -1;
            e->black_side->edge_sense = -1;
            e->white_side->edge_sense = -1;
        }
       
        e->black_side->edge_index = e->white_side->edge_index = i;
        e->black_side->edge = e->white_side->edge = e;
        
        e->black_side->color = black;
        e->white_side->color = white;
        
    }
        
         
    setup_local_indices();


}