#ifndef _UnionList_h
#define _UnionList_h


#include <hash_map>
#include <list>

using namespace __gnu_cxx;

using std::list;

template< class Key, class Union = Key, class HashFcn = hash< Key> >
/*
CLASS
  UnionList

  Template defines a data structure to handle union finds. The structure
  can be used to collect elements into unions. The unions may be 
  represented by a different type from its elements.

KEYWORDS
  union, find, iterator, container

AUTHORS
  Meir Fuchs (meirfux@math.tau.ac.il).

  Copyright: SAMBA group, Tel-Aviv Univ. Israel, 1997.

CHANGES LOG
<UL>
<LI>
</UL>

GOALS
  UnionList was written as a data structure holding union elements and their
  representatives and implementing an efficient union-find algorithm. Elements
  may be clustered into unions. These unions may be represented by a single 
  element from its unions or by a union representative or a given type.

USAGE
  A UnionList template class must be declared using a union element type (Key)
  and union type (Union). Unions are clustered using the unite method. unite
  recieves two union elements and makes sure that all elements of the two
  unions to which the two elements belong, are now of the same union. (Check
  out UnionFind in any algorithms book).

  The union elements are called Keys since they are used to access the unions.
  Since the union elements are stored in a hash table a hash function object
  must be supplied as the 3rd template argument or defined as hash<Key>.
  hash<> is predefined in the standard C++ library for several basic data
  types (basically integers and strings) so you need not redefine it.

  The simplest UnionList:
  EXAMPLE
    typedef UnionList<int> IntUnion;
  END
  The following defines a UnionList of ints where each union is represented
  by a float (instead of the default int>. If the union elements and the union
  representative are not of the same type then the representative type must
  have a constructor taking a single union element (Key) as its argument.
  EXAMPLE
    typedef UnionList<int, float>
  END
  The following defines a UnionList of floats. In this case hash<float> must
  be defined.
  EXAMPLE
    struct hash<float>
    {
      size_t operator()(const float f) const { return (size_t)f; }
    };
    typedef UnionList<float> FloatsUnion;
  END

  The following example defines a int UnionList and uses it to create a single
  union for all non-prime numbers (whose repressentative is the integer 4) and
  a union for each prime number between 1 and 100:
  EXAMPLE
    UnionList<int> intUnion;
    for (int i=1; i<=10000; ++i)  // Define unions. This step is not necessary
      intUnion.addUnion(i);

    for(int i=100; i>=2; --i)  // unite all non-prime numbers.
      for(int j=2; j*i<=10000; ++j)
        intUnion.unite(j*i, i*2);
    
    for (UnionList<int>::iterator it = intUnion.begin(); // print results
         it != intUnion.end();
         ++it)
      cout << (*it) << ' ';
    cout << '\n' << '\n';
  END  
*/
class UnionList
{
public:

  // A list of all unions. This list can be used to iterate through all 
  // union representatives (i.e. root of union find tree).
  typedef list< Union> UnionContainer;
  typedef typename UnionContainer::const_iterator const_iterator;
  typedef typename UnionContainer::iterator iterator;
  typedef typename UnionContainer::size_type size_type;
  
  //// Constructor. Initialize an empty union list.
  UnionList();

  //// Add a union containing a single data element.
  iterator addUnion(const Key& key);

  //// Add a union containing a single data element.
  iterator addUnion(const Key& key, const Union& unionData);

  //// Unite the two unions which contain key1 and key2. If key1 or key2
  // are not found a new single union is created. If key1 or key2 are in the
  // same union no action is taken. The new representative of the new union
  // is always the one that was used to represent key2's union. key1's union
  // is deleted.
  bool unite(const Key& key1, const Key& key2);

  //// Gets the representative data element of the union which contains key.
  const_iterator getUnion(const Key& key) const;

  //// Gets the union which contains key. If key is not found returns end()
  iterator getUnion(const Key& key);
  
  //// Returns an iterator used to iterate over the list of union
  // representatives.
  const_iterator begin() const;
  
  //// Returns an iterator used to iterate over the list of union
  // representatives.
  iterator begin();
  
  //// Returns an iterator used to iterate over the list of union
  // representatives.
  const_iterator end() const;
  
  //// Returns an iterator used to iterate over the list of union
  // representatives.
  iterator end();
  
  //// Number of unions in the list.
  size_type size() const;

private:

  // This data type is held in a tree which is accessible with a Key
  // key. Each element contains a pointer which can be used to point to
  // the parent in a union tree. And an iterator pointing into the list
  // of unions.
  class UnionItem
  {
  public:
    UnionItem() : parent(NULL) {}
    UnionItem(UnionItem* p) : parent(p) {}
    UnionItem(iterator i) : parent(NULL), unionData(i) {}

    UnionItem* parent;
    iterator unionData;
  };

  // The data is held in a tree so that using a Key the matching UnionItem 
  // will be efficiently found. UnionItem's form trees among themselves.
  typedef hash_map< Key, UnionItem, HashFcn> ItemDirectory;

  // Returns the matching UnionItem for a given Key by searching in
  // ItemDirectory. Returns NULL if no such map entry exists.
  UnionItem* node(const Key& data) const;

  // Given a pointer to UnionItem root returns the UnionItem representing
  // the root of the union tree. root also short-circuits all the elements
  // it passes along and connects them directly to the root.
  static UnionItem* root(UnionItem* node);

  UnionContainer unionList;
  ItemDirectory itemDirectory;
};


/***********************
 **  Implementation   **
 ***********************/

template< class Key, class Union, class HashFcn>
UnionList< Key, Union, HashFcn>::UnionList() 
  : unionList(), itemDirectory()
{}

template< class Key, class Union, class HashFcn>
typename UnionList< Key, Union, HashFcn>::iterator
UnionList< Key, Union, HashFcn>::addUnion(const Key& key)
{
  return addUnion(key, Union(key));
}

template< class Key, class Union, class HashFcn>
typename UnionList< Key, Union, HashFcn>::iterator
UnionList< Key, Union, HashFcn>::addUnion(const Key& key, 
                                         const Union& unionData)
{
  iterator result;

  // if new element has to be added....
  UnionItem* nd = node(key);
  if (nd == NULL) {
    // add a new union to the list of unions.
    unionList.push_front(unionData);
    // register this union in the ItemDirectory.
    itemDirectory[key] = UnionItem(unionList.begin());
    result = unionList.begin();
  }
  else
    result = root(nd)->unionData;

  return result;
}

template< class Key, class Union, class HashFcn>
bool
UnionList< Key, Union, HashFcn>::unite(const Key& key1, const Key& key2)
{
  bool result;

  // make sure UnionItems exist for each of the key pointers. find roots of
  // these elements.
  UnionItem* node1 = root(node(key1));
  UnionItem* node2 = root(node(key2));

  // if the roots of the elements are different unite and return pointer to the
  // new root. 
  result = (node1 != node2 && node1 != NULL && node2 != NULL);
  if (result) {
    node1->parent = node2;
    unionList.erase(node1->unionData);
  }
  return result;
} 

template< class Key, class Union, class HashFcn>
typename UnionList< Key, Union, HashFcn>::iterator 
UnionList< Key, Union, HashFcn>::getUnion(const Key& key)
{
  // find UnionItem od key pointer.
  UnionItem* nd = node(key);
  // if such an item exist find its union representative (root) and return it
  // otherwise return a NULL pointer.
  iterator unionData;
  if (nd != NULL) {
    nd = root(nd);
    unionData = nd->unionData;
  }
  else
    unionData = unionList.end();
  return unionData;
}

template< class Key, class Union, class HashFcn>
typename UnionList< Key, Union, HashFcn>::const_iterator UnionList< Key, Union, HashFcn>::getUnion(const Key& key) const
{
  UnionItem* nd = node(key);
  const_iterator rootKey;
  if (nd != NULL) {
    nd = root(nd);
    rootKey = nd->key;
  }
  else
    rootKey = unionList.end();
  return rootKey;  
}

template< class Key, class Union, class HashFcn>
typename UnionList< Key, Union, HashFcn>::const_iterator 
UnionList< Key, Union, HashFcn>::begin() const
{
  return unionList.begin();
}

template< class Key, class Union, class HashFcn>
typename UnionList< Key, Union, HashFcn>::const_iterator 
UnionList< Key, Union, HashFcn>::end() const
{
  return unionList.end();
}

template< class Key, class Union, class HashFcn>
typename UnionList< Key, Union, HashFcn>::iterator UnionList< Key, Union, HashFcn>::begin()
{
  return unionList.begin();
}

template< class Key, class Union, class HashFcn>
typename UnionList< Key, Union, HashFcn>::iterator
UnionList< Key, Union, HashFcn>::end()
{
  return unionList.end();
}

template< class Key, class Union, class HashFcn>
typename UnionList< Key, Union, HashFcn>::size_type 
UnionList< Key, Union, HashFcn>::size() const
{
  return unionList.size();
}

template< class Key, class Union, class HashFcn>
typename UnionList< Key, Union, HashFcn>::UnionItem* 
UnionList< Key, Union, HashFcn>::node(const Key& key) const
{
  // use the find method because operator[] may create an element within the
  // tree.
  typename ItemDirectory::const_iterator it = itemDirectory.find(key);
  UnionItem* node = NULL;
  if (it != itemDirectory.end())
    node = (UnionItem*)&((*it).second);
  return node;
}

template< class Key, class Union, class HashFcn>
typename UnionList< Key, Union, HashFcn>::UnionItem* 
UnionList< Key, Union, HashFcn>::root(UnionItem* nd)
{
  UnionItem* rootNd = nd;
  if (rootNd != NULL) {
    UnionItem* temp;
    // Use rootNd to iterate from nd to root.
    while (rootNd->parent != NULL)
      rootNd = rootNd->parent;
    // Go back to nd and short circuit tree so that all nodes are pointing to
    // the root.
    while ((temp = nd->parent) != NULL) {
      nd->parent = rootNd;
      nd = temp;
    }
  }
  return rootNd;
}
#endif