/*******************************************************************************
+
+  LEDA 3.5
+
+  edge_array.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_EDGE_ARRAY_H
#define LEDA_EDGE_ARRAY_H

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


//------------------------------------------------------------------------------
// edge arrays
//
// S. Naeher (1995)
//------------------------------------------------------------------------------

#include <LEDA/graph.h>


/*{\Manpage {edge_array} {E} {Edge Arrays}}*/

template <class E>
class edge_array : public graph_map
{

/*{\Mdefinition
An instance $A$ of the parameterized data type $edge\_array\<E\>$
is a partial mapping from the edge set of a graph $G$ to the set of 
variables of type $E$, called the element type of the array. The domain 
$I$ of $A$ is called the index set of $A$ and $A(e)$ is called the element 
at position $e$. $A$ is said to be valid for all edges in $I$.}*/

E def;

void clear_entry(GenPtr& x) const { LEDA_CLEAR(E,x); }
void copy_entry(GenPtr& x)  const { LEDA_COPY(E,x);  }
void init_entry(GenPtr& x)  const { x = leda_copy(def); }
/*
void read_entry(istream& i, GenPtr& x) { LEDA_READ(E,x,i); }
void write_entry(ostream& o, GenPtr& x) const { LEDA_PRINT(E,x,o);}
*/
  
public:

int elem_type_id() const { return LEDA_TYPE_ID(E); }

/*{\Mcreation A }*/

edge_array() : graph_map(nil,0,1) {}
/*{\Mcreate creates an instance $A$ of type $edge\_array\<E\>$ with empty
            index set.}*/

edge_array(const graph& G) : graph_map(&G,G.max_edge_index()+1,1) { init_table(); }
/*{\Mcreate creates an instance $A$ of type $edge\_array\<E\>$ and initializes
            the index set of $A$ to be the current edge set of graph $G$. }*/


edge_array(const graph& G, E x) : graph_map(&G,G.max_edge_index()+1,1) { def = x; init_table(); }
/*{\Mcreate creates an instance $A$ of type $edge\_array\<E\>$, sets the
            index set of $A$ to the current edge set of graph $G$ and 
            initializes $A(v)$ with $x$ for all edges $v$ of $G$. }*/


edge_array(const graph& G, int n, E x) : graph_map(&G,n,1) { def = x; init_table(); }
/*{\Mcreate creates an instance $A$ of type $edge\_array\<E\>$ valid for
            up to $n$ edges of graph $G$ and initializes $A(e)$ with $x$
            for all edges $e$ of $G$.\\
	    \precond $n \ge \Labs{E}$.\\
	    $A$ is also
            valid for the next $n - \Labs{E}$ edges added to $G$. }*/


edge_array(const edge_array<E>& A) : graph_map(A)   {}
edge_array<E>& operator=(const edge_array<E>& A) 
{ graph_map::operator=(A);  
  return *this;
 }
~edge_array() { clear_table(); }



/*{\Moperations 1.3 4.7 }*/

const E&  operator[](edge e) const 
{  return LEDA_CONST_ACCESS(E,graph_map::array_read(e)); }

E& operator[](edge e) {  return LEDA_ACCESS(E,graph_map::array_access(e)); }
/*{\Marrop    returns the variable $A(e)$.\\
	      \precond $A$ must be valid for $e$.}*/


E& entry(int i)            { return LEDA_ACCESS(E,graph_map::access(i));}
E  inf(int i)  const { return LEDA_ACCESS(E,graph_map::read(i));}

E& entry(edge e)           { return LEDA_ACCESS(E,graph_map::array_access(e)); }
E  inf(edge e) const { return LEDA_ACCESS(E,graph_map::array_read(e)); }


void init()  { graph_map::init(nil,1,1); }

void init(const graph& G)      
{ graph_map::init(&G,G.max_edge_index()+1,1); 
  init_table();
 }
/*{\Mop       sets the index set $I$ of $A$ to the edge  
	      set of $G$, i.e., makes $A$ valid for all edges 
              of $G$.}*/

void init(const graph& G, E x) 
{ graph_map::init(&G,G.max_edge_index()+1,1); 
  def = x;
  init_table();
}
/*{\Mop       makes $A$ valid for all edges of $G$
	      and sets $A(e) = x$ for all edges $e$ of $G$. }*/

void init(const graph& G, int n, E x) 
{ graph_map::init(&G,n,1); 
  def = x;
  init_table();
}
/*{\Mopl      makes $A$ valid for at most $n$ edges  
	      of $G$ and sets $A(e) = x$ for all edges $e$  
	      of $G$.\\
	      \precond $n \ge \Labs{E}$.\\
	      $A$ is also
              valid for the next $n - \Labs{E}$ edges added to $G$. }*/


/*{\Mimplementation
Edge arrays for a graph $G$ are implemented by \CC vectors and an
internal numbering of the nodes and edges of $G$. The access operation
takes constant time, $init$ takes time $O(n)$, where $n$ is the number of
edges in $G$. The space requirement is $O(n)$.
    
{\bf Remark}: An edge array is only valid for a bounded number of
edges of $G$. This number is either the number
of edges of $G$ at the moment of creation of the array or it is explicitely 
set by the user.  Dynamic edge arrays can be realized by edge 
maps (cf. section \ref{Edge Maps}). }*/

};



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

#endif
