/*******************************************************************************
+
+  LEDA 3.5
+
+  _g_objects.c
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/
#include <LEDA/graph.h>


//------------------------------------------------------------------------------
// nodes and edges
//
// by S. Naeher  (1995)
//------------------------------------------------------------------------------


node_struct::node_struct(GenPtr inf) 
{ data[0] = inf; 
  owner = nil; 
  id = 0; 
  for(int j=0; j<2; j++)
  { first_adj_edge[j]= nil;
    last_adj_edge[j] = nil;
    adj_length[j] = 0;
  }
}

edge_struct::edge_struct(node v, node w, GenPtr i)
{ succ_adj_edge[0] = nil;
  succ_adj_edge[1] = nil;
  pred_adj_edge[0] = nil;
  pred_adj_edge[1] = nil;
  id = 0;
  term[0] = v;
  term[1] = w;
  rev = nil;
  data[0] = i;
}


face_struct::face_struct(GenPtr x) 
{ data[0] = x ; 
  id = 0;
  owner = nil;
  head = nil; 
  sz = 0;
 }



void node_struct::append_adj_edge(edge e,int i, int chain_e)
{ // append e to adj_list[i]
  // use succ/pred_adj_edge[chain_e] pointers for chaining of e

  edge last = last_adj_edge[i];

  e->succ_adj_edge[chain_e] = nil;

  if (last == 0) // empty list
  { first_adj_edge[i] = e;
    e->pred_adj_edge[chain_e] = nil;
   }
  else
  { e->pred_adj_edge[chain_e] = last;
    if (source(last) == target(last))  // loop
       last->succ_adj_edge[chain_e] = e;
    else
       last->succ_adj_edge[(this==source(last)) ? 0:1] = e;
   }

  last_adj_edge[i] = e;
  adj_length[i]++;

 }
   


void node_struct::insert_adj_edge(edge e, edge e1, int i, int chain_e, int dir)
{ 
  // insert e after (dir==0) or before (dir!=0) e1 into adj_list[i]
  // use succ/pred_adj_edge[chain_e] pointers for chaining


  if (e1 == nil) 
  { append_adj_edge(e,i,chain_e);
    return;
   }


  edge e2;       // successor (dir==0) or predecessor (dir!=0) of e1

  int  chain_e1; // chaining used for e1


  if (source(e1) == target(e1)) // e1 is a self-loop
      chain_e1 = chain_e;
  else
      chain_e1 = (this == source(e1)) ? 0 : 1;

  if (dir == 0)
  { e2 = e1->succ_adj_edge[chain_e1];
    e->pred_adj_edge[chain_e] = e1;
    e->succ_adj_edge[chain_e] = e2;
    e1->succ_adj_edge[chain_e1] = e;
    if (e2 == nil) 
       last_adj_edge[i] = e;
    else
     { if (source(e2) == target(e2)) //loop
          e2->pred_adj_edge[chain_e] = e;
       else
          e2->pred_adj_edge[(this==source(e2)) ? 0:1] = e;
      }
   }
  else
  { e2 = e1->pred_adj_edge[chain_e1];
    e->succ_adj_edge[chain_e] = e1;
    e->pred_adj_edge[chain_e] = e2;
    e1->pred_adj_edge[chain_e1] = e;
    if (e2 == nil) 
       first_adj_edge[i] = e;
    else
     { if (source(e2) == target(e2)) //loop
          e2->succ_adj_edge[chain_e] = e;
       else
          e2->succ_adj_edge[(this==source(e2)) ? 0:1] = e;
      }
   }

   adj_length[i]++;
}
  
  
void node_struct::del_adj_edge(edge e, int i, int chain_e)
{ 
  // remove e from adj_list[i] 
  // with respect to succ/pred_adj_edge[chain_e] pointers

  edge e_succ = e->succ_adj_edge[chain_e];
  edge e_pred = e->pred_adj_edge[chain_e];

  if (e_succ) 
      if (source(e_succ) == target(e_succ)) // loop
         e_succ->pred_adj_edge[chain_e] = e_pred;
      else
         e_succ->pred_adj_edge[(this==source(e_succ)) ? 0:1 ] = e_pred;
  else
      last_adj_edge[i] = e_pred;

  if (e_pred) 
      if (source(e_pred) == target(e_pred)) // loop
         e_pred->succ_adj_edge[chain_e] = e_succ;
      else
         e_pred->succ_adj_edge[(this==source(e_pred)) ? 0:1 ] = e_succ;
  else
      first_adj_edge[i] = e_succ;

  adj_length[i]--;
 }







void graph_obj_list::clear()
{ obj_list_head = 0; 
  obj_list_tail = 0; 
  obj_list_sz   = 0;
}


void graph_obj_list::append(graph_object* e)
{ 
  e->obj_list_succ = 0;

  if (obj_list_sz > 0)
     obj_list_tail->obj_list_succ = e;
  else
     obj_list_head = e;

  e->obj_list_pred = obj_list_tail;
  obj_list_tail = e;

  obj_list_sz++;
}


graph_object* graph_obj_list::pop()
{ graph_object* e = obj_list_head;
  if (e)
  { graph_object* s = e->obj_list_succ;
    obj_list_head = s;
    if (s)
       s->obj_list_pred = 0;
    else
       obj_list_tail = 0;
    obj_list_sz--;
   }
  return e;
}


void graph_obj_list::remove(graph_object* e)
{ 
  graph_object* s = e->obj_list_succ;
  graph_object* p = e->obj_list_pred;

  if (s)
    { e->obj_list_succ = s->obj_list_succ;
      s->obj_list_pred = p; }
  else
      obj_list_tail = p;

  if (p)
    { e->obj_list_pred = p->obj_list_pred;
      p->obj_list_succ = s; }
  else
      obj_list_head = s;

  obj_list_sz--;
}


void graph_obj_list::conc(graph_obj_list& L)
{ if (L.obj_list_sz ==0) return; 

  if (obj_list_sz > 0)
     obj_list_tail->obj_list_succ = L.obj_list_head;
  else
     obj_list_head = L.obj_list_head;
  L.obj_list_head->obj_list_pred = obj_list_tail;
  obj_list_tail = L.obj_list_tail;
  obj_list_sz += L.obj_list_sz;
  L.clear();
}

