class GBN_LGRAPH [G,H]
  -- labelled directed graph possibly with multiple
  -- the_edges and self loops.  G is type for node labels,
  -- H for edge labels.  If the graph is undirected,
  -- then the list of the_edges contains just one directed
  -- edge for each pair of mutually inverse the_edges.
  -- Therefore in a undirected graph,
  -- edge_count is the number of undirected the_edges.

inherit
  GBN_PROTECTED
  GBN_GRAPH_TRUSTY
end

creation
  make_out, make_in, make_in_out, make_undirected

feature

  has_in_lists, has_out_lists, is_undirected : BOOLEAN

  is_empty : BOOLEAN is
    do
      Result := the_nodes.is_empty and the_edges.is_empty
    end

  has_node ( u : like last_node_added ) : BOOLEAN is
    do
      Result := u /= Void and then uf_marker = u.uf_marker
    end

  has_edge ( e : like last_edge_added ) : BOOLEAN is
    do
      Result := e /= Void and then uf_marker = e.uf_marker
    end

  node_count : INTEGER is
    do
      Result := the_nodes.count
    end

  edge_count : INTEGER is
    do
      Result := the_edges.count
    end

  out_list ( u : like last_node_added ):
            GBN_ROTUPLE [ like last_edge_added ] is
    require
      has_node : has_node ( u )
      out_exist: has_out_lists
    do
      Result := u.outlist
    end

  succ_out ( e : like last_edge_added ) : like last_edge_added is
    require
      exists : has_edge (e)
      out_lists : has_out_lists
    do
      Result := e.fr_node.outlist.item
        (e.fr_node.outlist.cyclic_succ(e.outlist_place))
    end

  pred_out ( e : like last_edge_added ) : like last_edge_added is
    require
      exists : has_edge (e)
      out_lists : has_out_lists
    do
      Result := e.fr_node.outlist.item
        (e.fr_node.outlist.cyclic_pred(e.outlist_place))
    end

  in_list ( u : like last_node_added ):
            GBN_ROTUPLE [ like last_edge_added ] is
    require
      has_node : has_node ( u )
      in_exist: has_in_lists
    do
      Result := u.inlist
    end

  succ_in ( e : like last_edge_added ) : like last_edge_added is
    require
      exists : has_edge (e)
      in_lists : is_undirected or else has_in_lists
    local
      u : like last_node_added
      list : GBN_DLIST [ like last_edge_added ]
    do
      if has_in_lists then
        u := e.fr_node
	list := u.inlist
	Result := list.item ( list.cyclic_succ ( e.inlist_place ) )
      else
        u := e.to_node
	list := u.outlist
        Result := list.item (list.cyclic_succ (e.outlist_place))
        Result := Result.inverse
      end
    end

  pred_in ( e : like last_edge_added ) : like last_edge_added is
    require
      exists : has_edge (e)
      in_lists : is_undirected or else has_in_lists
    do
      if has_in_lists then
        Result := e.fr_node.inlist.item
        (e.fr_node.inlist.cyclic_pred(e.inlist_place))
      else
        Result := e.fr_node.outlist.item
        (e.fr_node.outlist.cyclic_pred(e.outlist_place)).inverse
      end
    end


  inverse ( e : like last_edge_added ) : like last_edge_added is
    require
      has_edge : has_edge ( e )
      undirected : is_undirected
    do
      Result := e.inverse
    end

  to_node ( e : like last_edge_added ) : like last_node_added is
    require
      has_edge : has_edge ( e )
    do
      Result := e.to_node
    end

  fr_node ( e : like last_edge_added ) : like last_node_added is
    require
      has_edge : has_edge ( e )
    do
      Result := e.fr_node
    end

  nodes: GBN_ROTUPLE [ like last_node_added ] is
    do
      Result := the_nodes
    end

  edges: GBN_ROTUPLE [ like last_edge_added ] is
    do
      Result := the_edges
    end

  wipe_out is
   do
     the_nodes.wipe_out
     the_edges.wipe_out
     last_node_added := Void
     last_edge_added := Void
     !! uf_marker . make
   ensure
     gone : is_empty
   end

  node_put ( x : G; u : like last_node_added ) is
    require
      exists : has_node ( u )
    do
      u . put ( x )
    end

  node_item ( u : like last_node_added ) : G is
    require
      exists : has_node ( u )
    do
      Result := u.item
    end

  edge_put ( x : H; e : like last_edge_added ) is
    require
      exists : has_edge ( e )
    do
      e . put ( x )
      if is_undirected then
        e . inverse . put ( x )
      end
    end
      
  add_node is
    require
      unprotected : not is_protected
    local
      u : like last_node_added
    do
      if is_undirected then
        !! u.make ( true, false, Current )
      else
        !! u . make ( has_out_lists, has_in_lists, Current )
      end
      the_nodes.add_last ( u )
      last_node_added := u
    ensure
      last_node_added /= Void
    end

  edge_item ( e : like last_edge_added ) : H is
    require
      exists : has_edge ( e )
    do
      Result := e.item
    end

  remove_node ( u : like last_node_added ) is
    require
      exists : has_node ( u )
    local
      list : GBN_DLIST [ like last_edge_added ]
      e : like last_edge_added
    do
      if has_out_lists then
        list := u . outlist
      else
        list := u . inlist
      end
      from
      until
        list . is_empty
      loop
        e := list.first_item
        remove_edge ( e )
      end

      the_nodes.remove ( u . graph_place )
      u . wipe_out

    ensure
      gone : not has_node ( u )
    end

  insert_undirected_edge (u: like last_node_added;
  		uplace : GBN_DLIST_PLACE [ like last_edge_added ];
		v: like last_node_added;
  		vplace : GBN_DLIST_PLACE [ like last_edge_added ] ) is
    require
      unprotected : not is_protected
      undirected : is_undirected
      u_exists : has_node ( u )
      u_place : out_list (u) . has_place ( uplace )
      v_exists : has_node ( v )
      v_place : out_list (v) . has_place ( vplace )
    local
      e1, e2 : like last_edge_added
      unew, vnew : GBN_DLIST_PLACE [ like last_edge_added ]
    do
      !! e1.make ( u, v, uf_marker )
      !! e2.make ( v, u, uf_marker )
      u.outlist.add_after ( e1, uplace )
      if uplace = Void then
        unew := u.outlist.first_place
      else
        unew := u.outlist.succ ( uplace )
      end
      v.outlist.add_after ( e1, vplace )
      if vplace = Void then
        vnew := v.outlist.first_place
      else
        vnew := v.outlist.succ ( vplace )
      end
      e1.set_outlist_place ( unew )
      e2.set_outlist_place ( vnew )
      e1 . set_inverse ( e2 )
      e2 . set_inverse ( e1 )
      the_edges.add_last ( e1 )
      e1 . set_graph_place ( the_edges.last_place )
      last_edge_added := e1
    ensure
      last_edge_added /= Void
    end

feature {GBN_GRAPH_TRUSTY}

------------------------------------------------------------
-- insert_many_undir_edges
-- Used in Delaunay triangulation.  Reason is that it is
-- otherwise tricky to insert the edges in the correct gaps
-- in linear time.  It is assumed (and not checked!) that
-- the nne-triples are either of the form u,w,Void, indicating
-- a new edge to be added, or Void,Void,e, indicating an existing
-- edge.  The array indexing is based on an existent but here
-- undisclosed left-to-right order of the nodes.  
------------------------------------------------------------

  insert_many_undir_edges (
  	nbrs : GBN_DLIST [
	GBN_PAIR [ like last_node_added, GBN_DLIST [ like t_nne_anchor ] ] ])
    is
    require
      is_undirected
      not is_protected
    local
      triplist : GBN_DLIST [ like t_nne_anchor ]
      nbrs_it : GBN_ITERATOR [
        GBN_PAIR [ like last_node_added, GBN_DLIST [ like t_nne_anchor ]]]
      u : like last_node_added
      triple : like t_nne_anchor
      oul_place : GBN_DLIST_PLACE [ like last_edge_added ]
      edge, new_edge, new_inverse : like last_edge_added
      start_place, place : GBN_DLIST_PLACE [ like t_nne_anchor ]
    do
      from
        nbrs_it := nbrs.iterator
      until
        nbrs_it.finished
      loop
        -- first align the lists
        u := nbrs_it.item.item_1
 	oul_place := u.outlist.first_place
	edge := u.outlist.first_item
	triplist := nbrs_it.item.item_2

	from
	  place := triplist.first_place
        until
	  triplist.item(place).item_3 = edge
	loop
	  place := triplist.succ (place)
	end

         start_place := place
	 place := triplist.cyclic_succ (place)

	from
	  oul_place := u.outlist.succ ( oul_place )
	until
	  place = start_place
	loop
	  triple := triplist.item(place)
	  if triple.item_3 = u.outlist.item(oul_place) then
	    oul_place := u.outlist.cyclic_succ (oul_place)
	  elseif triple.item_3 = Void then
	    !! new_edge.make ( u, triple.item_2, uf_marker )
	    !! new_inverse.make ( triple.item_2, u, uf_marker )
	    new_edge.set_inverse ( new_inverse )
	    new_inverse.set_inverse ( new_edge )
	    u.outlist.add_before ( new_edge, oul_place )
	    new_edge.set_outlist_place (u.outlist.pred(oul_place))
	    triple.put_3 ( new_inverse )
            place := triplist.succ (place)
	  else
	    u.outlist.add_before ( new_edge, oul_place )
	    new_edge.set_outlist_place (u.outlist.pred(oul_place))
	  end
	  place := triplist.succ (place)
	end
	nbrs_it.forth
      end
    end

feature {ANY}

  remove_edge ( e : like last_edge_added ) is
    require
      exists : has_edge ( e )
    local
      u, v : like  last_node_added
      e1 , e2 :  like last_edge_added
    do
      e1 := e
      if is_undirected then
	e2 := e.inverse
      end
      u := e1.fr_node
      v := e1.to_node
      if is_undirected then
        u.outlist.remove ( e1.outlist_place )
	v.outlist.remove ( e2.outlist_place )
      else
	if has_in_lists then
	  v.inlist.remove ( e.inlist_place )
	end
	if has_out_lists then
	  u.outlist.remove ( e.outlist_place )
	end
      end
      if e1.graph_place /= Void then
        the_edges.remove ( e1.graph_place )
      end
      if e2 /= Void and then e2.graph_place /= Void then
        the_edges.remove ( e2.graph_place )
      end
      e1.wipe_out
      if e2 /= Void then
        e2.wipe_out
      end
    ensure
      gone : not has_edge ( e )
    end

  absorb_graph ( other : like Current ) is
    require
      exists : other /= Void
      different : other /= Current
      in_lists : has_in_lists = other.has_in_lists
      out_lists : has_out_lists = other.has_out_lists
      undirected : is_undirected = other.is_undirected
    do
      uf_marker . unite ( other . uf_marker )
      the_nodes.absorb_suffix ( other . the_nodes )
      the_edges.absorb_suffix ( other . the_edges )
      other . wipe_out
    ensure
      gone : other . is_empty
    end
      

feature { GBN_LGRAPH, GBN_LNODE }

  uf_marker : GBN_UF_ELEMENT
  the_nodes : GBN_DLIST [ like last_node_added ]
  the_edges : GBN_DLIST [ like last_edge_added ]

feature { NONE }

 make_out is
   do
     !! the_nodes.make_protecting ( Current )
     !! the_edges.make_protecting ( Current )
     has_out_lists := true
   end

 make_in is
   do
     !! the_nodes.make_protecting ( Current )
     !! the_edges.make_protecting ( Current )
     has_in_lists := true
   end

 make_in_out is
   do
     !! the_nodes.make_protecting ( Current )
     !! the_edges.make_protecting ( Current )
     has_in_lists := true
     has_out_lists := true
   end

 make_undirected is
   do
     !! the_nodes.make_protecting ( Current )
     !! the_edges.make_protecting ( Current )
     has_out_lists := true
     is_undirected := true
   end

feature { ANY }

  last_node_added : GBN_LNODE [ G, H ]
  last_edge_added : GBN_LEDGE [ G, H ]
  t_nne_anchor : GBN_TRIPLE [ like last_node_added, like last_node_added,
  			      like last_edge_added ]
  
end -- class GBN_LGRAPH