
/*
**  This file forms part of the GOBLIN C++ Class Library.
**
**  Written by Christian Fremuth-Paeger, January 2000.
**  
**  Copying, compiling, distribution and modification
**  of this source code is permitted only in accordance
**  with the GOBLIN general licence information.
*/             


#if !defined(_SHRFAM_H_)

#define _SHRFAM_H_

#include <absfam.h>


template <class TItem>
class shrinkingFamily : public goblinDisjointSetSystem<TItem>
{
private:

	TItem 			n;
        // Number of real elements.
	TItem 			m;
        // Maximum number of sets, i.e. virtual elements.
    bool            compress;        
        // Enables or diables path compression.

	TItem 			UNDEFINED;
 
    TItem*          B;
        // Pointer towards the canonical element of a toplevel set
	TItem*          depth;
        // If path compression is disabled, the maximum depth of the
        // subtree defined by the B-labels. Otherwise, the rank.

	TItem*          set;         
        // For canonical elements of toplevel sets, the actual set index.
	TItem*          canonical;
        // For fixed sets, the canonical element.

	TItem*          first;         
        // First element of a set.
	TItem*          next;         
        // Defines a linked list on the elements of a given set v
        // starting at first[v].

public:

	shrinkingFamily(TItem nn,TItem mm,
        goblinController &thisContext = goblinDefaultContext) throw();
	~shrinkingFamily() throw();

	void			Init() throw();
	unsigned long	Size() throw();
	unsigned long	Allocated() throw();
	bool			Reversible() throw() {return 1;};
    
    void            Display(TItem v) throw(ERRange);
        // Display the set family nested into v.
    char*           Display() throw();
        // Display the complete nested set family.

	void			Bud(TItem v) throw(ERRange,ERRejected);
        // Prepares a real element v for merge operations.
	TItem			MakeSet() throw(ERRejected);
        // Prepares a new toplevel set, returns the index.
	void			Merge(TItem s,TItem v) throw(ERRange,ERRejected);
        // Merges a toplevel element v into a set s which is not fixed yet.
	void			FixSet(TItem s) throw(ERRange,ERRejected);
        // Final operation after merging elements into s.
        // Assigns a canonical element to s.
	bool			Top(TItem v) throw(ERRange);
        // Decides wether v is a toplevel element.
	TItem			Set(TItem v) throw(ERRange);
        // Returns the toplevel set containing v.

	TItem			First(TItem v) throw(ERRange);
        // Public interface of the array first.
	TItem			Next(TItem v) throw(ERRange,ERRejected);
        // Public interface of the array next.

	void			Split(TItem v) throw(ERRange,ERRejected);
        // Destroy a toplevel set.
        // If path compression is enabled, re-arrange B-labels.
    
    void            Block(TItem v) throw(ERRange,ERRejected);
        // Like Split(TItem v), but reversible.
    void            UnBlock(TItem v) throw(ERRange,ERRejected);
        // Inverse operation of Block(TItem v).

private:

    void            Adjust(TItem s,TItem b) throw(ERRange);
        // Reset the B-labels after splitting a set.
	TItem			Find(TItem v) throw(ERRange);
        // Compute the canonical element of a set.
        // Ajust B[v] if path compression is enabled.

};
	

#endif
