/*******************************************************************************
+
+  LEDA 3.5
+
+  partition.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_Partition_H
#define LEDA_Partition_H

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


//------------------------------------------------------------------------------
// partition   (union find)
//------------------------------------------------------------------------------

#include <LEDA/basic.h>


/*{\Manpage {partition} {} {Partitions} }*/

class partition_node {
/*{\Mdefinition
An instance  $P$ of the data type |partition| consists of a finite set of
items (|partition_item|) and a partition of this set
into blocks.}*/

friend class partition;

partition_node* father;
partition_node* next;
int size;
GenPtr info;

public:

partition_node(GenPtr x, partition_node* n)  
{ 
  father=0; size=1; info=x; next = n; 
 }

  LEDA_MEMORY(partition_node)

};


// a partition item is a pointer to a partition node:

typedef partition_node* partition_item;



class partition {

virtual void clear_inf(GenPtr&) const {}

partition_item used_items;                 // List of used partition items

public:

/*{\Mcreation P }*/

partition() { used_items = 0; }  
/*{\Mcreate creates an instance $P$ of type |partition| and initializes it to 
            the empty partition.}*/

virtual ~partition() { clear(); }

/*{\Moperations 3 4}*/

partition_item make_block(GenPtr x) 
{ used_items = new partition_node(x,used_items); 
  return used_items; 
 }

partition_item make_block() 
{ return make_block(nil);
}
/*{\Mop      returns a new |partition_item| $it$ and adds
	     the block |{it}| to partition $P$.}*/

partition_item find(partition_item p);
/*{\Mopl     returns a canonical item of the block that
	     contains item $p$, i.e., iff |P.same_block(p,q)|
	     then |P.find(p)| and |P.find(q)| return the same item.\\
	     \precond $p$ is an item in $P$. }*/

bool  same_block(partition_item p, partition_item q) 
{ return find(p)==find(q); }
/*{\Mopl      returns true if $p$ and $q$ belong to the same
	      block of partition $P$.\\
	      \precond $p$ and $q$ are items in $P$.}*/

void  union_blocks(partition_item p, partition_item q);
/*{\Mopl      unites the blocks of partition $P$ containing
	     items $p$ and $q$.\\
	     \precond $p$ and $q$ are items in $P$.}*/


void clear();                      // deletes all used items


partition_item first_item() const  { return used_items;  }
partition_item next_item(partition_item it) const  { return it->next; }


protected:

GenPtr& inf(partition_item a) { return find(a)->info; }


};

/*{\Mimplementation
Partitions are implemented by the union find algorithm with weighted union
and path compression (cf.~\cite{T83}).  Any sequence of $n$ make\_block and 
$m \ge n$ other operations takes time $O(m\alpha(m,n))$.}*/

/*{\Mexample
    Spanning Tree Algorithms (cf. section \ref{Graph Algorithms}).}*/


/*{\Mtext \newpage}*/

//------------------------------------------------------------------------------
// Partition  (parameterized partitions)
//-----------------------------------------------------------------------------

template <class E>

class Partition : private partition {

/*{\Manpage {Partition} {E} {Parameterized Partitions} }*/

/*{\Mdefinition
An instance  $P$ of the data type |\Mname| consists of a finite set of
items (|partition_item|) and a partition of this set
into blocks. Each item has an associated information of type |E|.}*/

void clear_inf(GenPtr& x) const { LEDA_CLEAR(E,x); }

public:

/*{\Mcreation P }*/

Partition()  {}  
/*{\Mcreate creates an instance $P$ of type |\Mname| and initializes it to 
            the empty partition.}*/

~Partition() {}


/*{\Moperations 3 4}*/

partition_item make_block(const E& x) 
{ return partition::make_block(leda_copy(x)); }
/*{\Mop      returns a new |partition_item| $it$, adds
	     the block |{it}| to partition $P$, and associates |x| with |it|.}*/

partition_item find(partition_item p) 
{ return partition::find(p); }
/*{\Mopl     returns a canonical item of the block that
	     contains item $p$, i.e., iff |P.same_block(p,q)| 
	     then |P.find(p)| and |P.find(q)| return the same item.\\
	     \precond $p$ is an item in $P$. }*/

bool  same_block(partition_item p, partition_item q)  
{ return partition::same_block(p,q); }
/*{\Mopl      returns true if $p$ and $q$ belong to the same
	      block of partition $P$.\\
	      \precond $p$ and $q$ are items in $P$.}*/

void  union_blocks(partition_item p, partition_item q)
{ partition::union_blocks(p,q); }
/*{\Mopl      unites the blocks of partition $P$ containing
	     items $p$ and $q$.\\
	     \precond $p$ and $q$ are items in $P$.}*/

E  inf(partition_item it)   { return LEDA_ACCESS(E,partition::inf(it)); }
/*{\Mop      returns the information associated with |it|.}*/




void  change_inf(partition_item it, const E& x) 
{ LEDA_ACCESS(E,partition::inf(it)) = x; }
/*{\Mop      changes the information associates with |it| to |x|.}*/


};



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

#endif
