/*******************************************************************************
+
+  LEDA 3.5
+
+  _g_sort.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>

//--------------------------------------------------------------------------
// sorting
//
// by S. Naeher  (1995)
//------------------------------------------------------------------------------


static const graph_map*  NA;

static graph* GGG;


/*
static int array_cmp_nodes(const node& x, const node& y) 
{ return NA->cmp_entry(NA->array_read(x),NA->array_read(y)); }

static int array_cmp_edges(const edge& x, const edge& y) 
{ return NA->cmp_entry(NA->array_read(x),NA->array_read(y)); }
*/

static int int_array_cmp_nodes(const node& x, const node& y) 
{ return LEDA_COMPARE(int,NA->array_read(x),NA->array_read(y)); }

static int int_array_cmp_edges(const edge& x, const edge& y) 
{ return LEDA_COMPARE(int,NA->array_read(x),NA->array_read(y)); }

static int float_array_cmp_nodes(const node& x, const node& y) 
{ return LEDA_COMPARE(float,NA->array_read(x),NA->array_read(y)); }

static int float_array_cmp_edges(const edge& x, const edge& y) 
{ return LEDA_COMPARE(float,NA->array_read(x),NA->array_read(y)); }

static int double_array_cmp_nodes(const node& x, const node& y) 
{ return LEDA_COMPARE(double,NA->array_read(x),NA->array_read(y)); }

static int double_array_cmp_edges(const edge& x, const edge& y) 
{ return LEDA_COMPARE(double,NA->array_read(x),NA->array_read(y)); }




static int graph_cmp_nodes(const node& x, const node& y)
{ return GGG->cmp_node_entry(x,y); }

static int graph_cmp_edges(const edge& x, const edge& y)
{ return GGG->cmp_edge_entry(x,y); }


void graph::sort_nodes(const list<node>& vl)
{ 
  if (vl.length() != number_of_nodes())
       error_handler(1,"graph::sort_nodes(list<node>): illegal node list");

  v_list.clear();

  node v;
  forall(v,vl) 
  { if (v->owner != this)
       error_handler(1,"graph::sort_nodes(list<node>): illegal node list");
    v_list.append(v);
   }
 }



void graph::sort_nodes(int (*f)(const node&, const node&))
{ list<node> vl = all_nodes();
  vl.sort(f); 
  sort_nodes(vl);
}


void graph::sort_edges(const list<edge>& el)
{ 
  node v;
  edge e;

  if (el.length() != number_of_edges())
      error_handler(1,"graph::sort_edges(list<edge>): illegal edge list");


  // clear all adjacency lists
  forall_nodes(v,*this)
    for(int i=0; i<2; i++)
    { v->first_adj_edge[i] = 0;
      v->last_adj_edge[i] = 0;
      v->adj_length[i] = 0;
     }

  e_list.clear();

  forall(e,el)
  { 
    if (e->term[0]->owner != this)
        error_handler(1,"graph::sort_edges(list<edge>): edge not in graph");

    e_list.append(e);

    source(e)->append_adj_edge(e,0,0);
    if (undirected)
       target(e)->append_adj_edge(e,0,1);
    else
       target(e)->append_adj_edge(e,1,1);
   }
 }


void graph::sort_edges(int (*f)(const edge&, const edge&))
{ list<edge> el = all_edges();
  el.sort(f);
  sort_edges(el);
 }


void graph::sort_nodes(const graph_map& A) 
{ NA = &A; 
  switch (A.elem_type_id()) {

  case INT_TYPE_ID: sort_nodes(int_array_cmp_nodes); 
                    break;
  case FLOAT_TYPE_ID:  
                    sort_nodes(float_array_cmp_nodes); 
                    break;
  case DOUBLE_TYPE_ID:  
                    sort_nodes(double_array_cmp_nodes); 
                    break;
  default:
          error_handler(1,"G.sort_nodes(node_array<T>): T must be numerical.");
  }
 }


void graph::sort_edges(const graph_map& A) 
{ NA = &A; 
  switch (A.elem_type_id()) {

  case INT_TYPE_ID: sort_edges(int_array_cmp_edges); 
                    break;
  case FLOAT_TYPE_ID:  
                    sort_edges(float_array_cmp_edges); 
                    break;
  case DOUBLE_TYPE_ID:  
                    sort_edges(double_array_cmp_edges); 
                    break;
  default:
          error_handler(1,"G.sort_edges(node_array<T>): T must be numerical.");
  }
 }


void graph::sort_nodes() 
{ GGG = this; 
  sort_nodes(graph_cmp_nodes); 
 }

void graph::sort_edges() 
{ GGG = this; 
  sort_edges(graph_cmp_edges); 
 }




// bucket sort

static int array_ord_node(const node& x) 
{ return LEDA_ACCESS(int,NA->array_read(x)); }

static int array_ord_edge(const edge& x) 
{ return LEDA_ACCESS(int,NA->array_read(x)); }


void graph::bucket_sort_nodes(int l, int h, int (*ord)(const node&))
{ list<node> vl = all_nodes();
  vl.bucket_sort(l,h,ord);
  sort_nodes(vl);
}

void graph::bucket_sort_edges(int l, int h, int (*ord)(const edge&))
{ list<edge> el = all_edges();
  el.bucket_sort(l,h,ord);
  sort_edges(el);
 }

void graph::bucket_sort_nodes(int (*ord)(const node&))
{ list<node> vl = all_nodes();
  vl.bucket_sort(ord);
  sort_nodes(vl);
}

void graph::bucket_sort_edges(int (*ord)(const edge&))
{ list<edge> el = all_edges();
  el.bucket_sort(ord);
  sort_edges(el);
 }


void graph::bucket_sort_nodes(const graph_map& A) 
{ NA = &A; 
  switch (A.elem_type_id()) {

  case INT_TYPE_ID: bucket_sort_nodes(array_ord_node); 
                    break;
  default:
    error_handler(1,"G.bucket_sort_nodes(node_array<T>): T must be integer.");
  }
 }


void graph::bucket_sort_edges(const graph_map& A) 
{ NA = &A; 
  switch (A.elem_type_id()) {

  case INT_TYPE_ID: bucket_sort_edges(array_ord_edge); 
                    break;
  default:
    error_handler(1,"G.bucket_sort_edges(edge_array<T>): T must be integer.");
  }
 }

