/*******************************************************************************
+
+  LEDA 3.5
+
+  graph_objects.h
+
+  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.
+ 
*******************************************************************************/
#ifndef LEDA_GRAPH_OBJECTS_H
#define LEDA_GRAPH_OBJECTS_H

#if !defined(LEDA_ROOT_INCL_ID)
#define LEDA_ROOT_INCL_ID 350057
#include <LEDA/REDEFINE_NAMES.h>
#endif


//------------------------------------------------------------------------------
// basic objects for graphs (nodes and edges)
//
// S. Naeher (1995)
//------------------------------------------------------------------------------


#include <LEDA/impl/olist.h>


//------------------------------------------------------------------------------
// class graph_object: base class for all graph objects
//------------------------------------------------------------------------------

class graph_object {
friend class graph_obj_list;
protected:
  graph_object* obj_list_succ;
  graph_object* obj_list_pred;
};



class node_struct;
typedef node_struct* node;

class edge_struct;
typedef edge_struct* edge;


class face_struct;
typedef face_struct* face;



//------------------------------------------------------------------------------
// class node_struct: internal representation of nodes
//------------------------------------------------------------------------------

class node_struct : public graph_object,
                              public obj_link  // used by node_list
{  
   friend class graph;
   friend class graph_map;
   friend class ugraph;
   friend class node_list;
   friend class GraphWin;
   
   graph*    owner;              // pointer to graph of node 
   unsigned  id;                 // internal id (index)  
   edge      first_adj_edge[2];  // head of adj/in list
   edge      last_adj_edge[2];   // tail of adj/in list
   int       adj_length[2];      // outdeg/indeg
   GenPtr    data[1];            // data[0]: GRAPH

public:


void append_adj_edge(edge e,int i, int chain_e);
void insert_adj_edge(edge e, edge e1, int i, int chain_e, int dir);
void del_adj_edge(edge e, int i, int chain_e);

node_struct(GenPtr i=0);

LEDA_MEMORY(node_struct)

friend inline graph* graph_of(node);
friend inline graph* graph_of(edge);
friend inline int    indeg(node);
friend inline int    outdeg(node);
friend inline int    degree(node);
friend inline int    index(node);

friend inline edge   First_Adj_Edge(node,int);
friend inline edge   Last_Adj_Edge(node,int);

friend void init_node_data(const graph&,int,GenPtr);

};



//------------------------------------------------------------------------------
// class edge_struct: internal representation of edges
//------------------------------------------------------------------------------

class edge_struct  : public graph_object
{ 
   friend class node_struct;
   friend class graph;
   friend class ugraph;
   friend class graph_map;
   friend class GraphWin;

   edge      succ_adj_edge[2];   // chaining of adjacent out/in-edges
   edge      pred_adj_edge[2];   //
   node      term[2];            // term[0] = source and term[1] = target
   unsigned  id;                 // internal id (index)  
   edge      rev;                // reverse edge
   GenPtr    data[1];            // space for data (data[0] used by GRAPH)

public:

edge_struct(node v=0, node w=0, GenPtr i=0);

LEDA_MEMORY(edge_struct)

friend inline graph* graph_of(edge);
friend inline node   terminal(edge,int);
friend inline node   source(edge);
friend inline node   target(edge);
friend inline node   opposite(node,edge);
friend inline int    index(edge);

friend inline edge   First_Adj_Edge(node,int);
friend inline edge   Last_Adj_Edge(node,int);
friend inline edge   Succ_Adj_Edge(edge,int);
friend inline edge   Pred_Adj_Edge(edge,int);
friend inline edge   Succ_Adj_Edge(edge,node);
friend inline edge   Pred_Adj_Edge(edge,node);

friend bool is_hidden(edge e) { return e->id & 0x80000000; }

};



//------------------------------------------------------------------------------
// class face_struct: internal representation of faces
//------------------------------------------------------------------------------

class face_struct : public graph_object {

friend class graph;
friend class graph_map;
friend class planar_map;
friend class GraphWin;

 unsigned  id;       // internal id (index)  
 edge      head;     // first edge of face
 int       sz;       // size of face (# edges)
 graph*    owner;
 GenPtr    data[1];  // space for data (data[0] used by PLANAR_MAP)

 face_struct(GenPtr);


 LEDA_MEMORY(face_struct)

 friend index(face f)                { return f->id & 0x7fffffff;  }
 friend graph*      graph_of(face f) { return f->owner; }
 friend planar_map* map_of(face f)   { return (planar_map*)f->owner; }

};



inline int    outdeg(node v) { return v->adj_length[0]; }
inline int    indeg(node v)  { return v->adj_length[1];  }
inline int    degree(node v) { return indeg(v) + outdeg(v); }

inline int    index(node v)    { return v->id & 0x7fffffff;  }
inline graph* graph_of(node v) { return v->owner; }


inline node   terminal(edge e, int i) { return e->term[i]; }
inline node   source(edge e)   { return e->term[0]; }
inline node   target(edge e)   { return e->term[1]; }

inline node   opposite(node v, edge e) 
{ return (v==source(e)) ? target(e) : source(e); }

inline int    index(edge e)    { return e->id & 0x7fffffff;  }
inline graph* graph_of(edge e) { return source(e)->owner; }


// parameterized access of adjacent edges
// outgoing (i=0) or incoming (i=1) edges


inline edge First_Adj_Edge(node v,int i) { return v->first_adj_edge[i]; }
inline edge Last_Adj_Edge(node v, int i) { return v->last_adj_edge[i];  }
inline edge Succ_Adj_Edge(edge e, int i) { return e->succ_adj_edge[i];  }
inline edge Pred_Adj_Edge(edge e, int i) { return e->pred_adj_edge[i];  }


// successor or predecessor of e in adjacency list of node v
// precond: v = source(e) or v = target(e)

inline edge Succ_Adj_Edge(edge e, node v) 
{ return Succ_Adj_Edge(e,(v==source(e)) ? 0:1); }

inline edge Pred_Adj_Edge(edge e, node v) 
{ return Pred_Adj_Edge(e,(v==source(e)) ? 0:1); }




class graph_obj_list
{ 
  friend class graph;

  graph_object* obj_list_head;
  graph_object* obj_list_tail;
  int  obj_list_sz;

  void append(graph_object*);
  void remove(graph_object*);
  graph_object* pop();
  void conc(graph_obj_list&);
  void clear();

  graph_object* head() const { return obj_list_head; }
  graph_object* tail() const { return obj_list_tail; }
  graph_object* succ(graph_object* e) const { return e->obj_list_succ; }
  graph_object* pred(graph_object* e) const { return e->obj_list_pred; }
  bool empty()  const { return obj_list_head == 0; }
  int  length() const { return obj_list_sz; }

  graph_obj_list() { clear(); }
};



// default compare

inline int compare(const node& v, const node& w) 
{ return  int(long(v) - long(w)); }

inline int compare(const edge& x, const edge& y) 
{ return  int(long(x) - long(y)); }

inline int compare(const face& x, const face& y) 
{ return  int(long(x) - long(y)); }

// type id

inline int leda_type_id(const node*) { return PTR_TYPE_ID; }
inline int leda_type_id(const edge*) { return PTR_TYPE_ID; }
inline int leda_type_id(const face*) { return PTR_TYPE_ID; }


#if LEDA_ROOT_INCL_ID == 350057
#undef LEDA_ROOT_INCL_ID
#include <LEDA/UNDEFINE_NAMES.h>
#endif

#endif
