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

//------------------------------------------------------------------------------
//
// partitions
//
// implementation: union find with weighted union rule and path compression
//
// S. N.  (1989)
//------------------------------------------------------------------------------

#include <LEDA/partition.h>


void partition::clear()
{ // free all used items
  partition_item p = used_items; 
  while (used_items)
  { p = used_items;
    used_items = used_items->next;
    clear_inf(p->info);
    delete p;
   }
 }
  


partition_item partition::find(partition_item y) 
{ // find with path compression

  register partition_item x = y->father;

  if (x==0) return y;

  register partition_item root = y;

  while (root->father) root = root->father;

  while (x!=root)
  { y->father = root;
    y = x;
    x = y->father;
   }
  return root;
 }

void partition::union_blocks(partition_item a, partition_item b)
{ // weighted union

  a = find(a);
  b = find(b);

  if (a==b) return;

  if (a->size > b->size)
       { b->father = a;
         a->size += b->size; }
  else { a->father = b;
         b->size += a->size; }

 }

