// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey
// Author(s): Jonathan Berry

// This software is copyrighted by the DIMACS Center at Rutgers, The State
// University of New Jersey.  IT IS PROVIDED AS IS, AND THE AUTHORS, DIMACS, AND
// RUTGERS, THE STATE UNIVERSITY OF NEW JERSEY  DISCLAIM
// ALL LIABILITY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
// DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY
// DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.

// THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
// INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT.  THIS SOFTWARE
// IS PROVIDED ON AN "AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE
// NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
// MODIFICATIONS.

// The authors hereby grant permission to use, copy, modify, distribute,
// and license this software and its documentation for any purpose, provided
// that existing copyright notices are retained in all copies and that this
// notice is included verbatim in any distributions. No written agreement,
// license, or royalty fee is required for any of the authorized uses.
// Modifications to this software may be copyrighted by their authors
// and need not follow the licensing terms described here, provided that
// the new terms are clearly indicated on the first page of each file where
// they apply.

// Last File Update: 31-Jul-1996
// 

///////////////////////////////////////////////////////////////////////////
// LINK: Generic Graph Tool and Class Library
//     
//     Functoin name: Disjoint Set methods
//
//     Synopsis: Contains the implementations of Disjoint Set methods
//
//     Description: the user must catch a pointer that is returned 
//                  when a Set is created
//                  And when two sets of equal length are unioned the
//                  first set in the arguement list is parent by default
//
//     Creation: 1993 May 21, Daniel Liles, dliles@c3.lanl.gov
//
//     Routines used: None
//
//     Related Files: DJSet.h
//
//     Test suite: None
//
//     User documentation: None
//
//     Development History:
//
//     Testing History: tested with 10 sets unioned to
//                      two sets
//
//     Code Review:
//
//     Bugs and Deficiencies: The DJSet is a friend to all 
//                            DJSetNode's.  The compiler
//                            will only accept this notation
//
/////////////////////////////////////////////////////////////////////////

#include <LINK/basic/DJSet.h>


Bool
DJSet::operator!=(DJSet& passed_set)
{
    return (this != &passed_set) ? TRUE : FALSE;
}


//
// return the head parent
//
DJSet* 
DJSet::findSet()
{
    if (_parent != this) 
        _parent = _parent->findSet();

    return _parent;
}


void
DJSet::unionWith(DJSet* passed_set) 
{ 
    DJSet* parent_set = findSet();
    parent_set->joinWith(passed_set->findSet());
}


void
DJSet::joinWith(DJSet* passed_set)
{
    if (_rank > passed_set->_rank) {
        passed_set->_parent = this;
    } else if (passed_set->_rank > _rank) {
        _parent = passed_set;
    } else {
        passed_set->_parent = this;
        _rank++;
    }
}