import java.util.LinkedList;
import java.util.List;
/**
*
* @author energy1010
*
* @param <T>
*/
public class DisjointSet<T> {
public List<HeadNode<T> > setList;
public int size;
public static class HeadNode<T>{
public List<T> itemsList;
public T val;
public int num;
public LinkNode<T> first;
public LinkNode<T> tail;
public HeadNode() {
}
public HeadNode(T val) {
this.val = val;
num+=1;
if(itemsList==null){
itemsList = new LinkedList<T>();
itemsList.add(val);
first = new LinkNode<T>(val, this);
tail= first;
}
}
public HeadNode(T[] val) {
if(val.length>0){
this.val = val[0];
if(this.itemsList==null){
this.itemsList = new LinkedList<T>();
for(int i=0; i<val.length; i++){
if(i==0){
this.itemsList.add(val[i]);
this.first = new LinkNode<T>(this.val, this);
this.tail = first;
this.num+=1;
}else{
addLinkNode(val[i]);
}
}
}else{
}
}
}
public boolean contain(T val){
if(itemsList!=null && itemsList.size()>0){
return itemsList.contains(val);
}
return false;
}
public void addLinkNode(T val){
if(itemsList==null){
itemsList = new LinkedList<T>();
first = new LinkNode<T>(val, this);
tail= first;
}else{
LinkNode<T> newLinkNode = new LinkNode<T>(val, this);
tail.next = newLinkNode;
tail = newLinkNode;
}
itemsList.add(val);
num+=1;
}
public void delLinkNode(T val){
//TODO:
}
public void delHeadNode(){
this.num =0 ;
this.val = null;
itemsList.clear();
itemsList=null;
first = null;
tail = null;
}
public void printHeadNode(){
System.out.printf("val: %s items:%s num:%s first:%s tail:%s
", val, itemsList, num, first.val, tail.val);
}
// @Override
// public String toString() {
// return String.format(", args)
//// return super.toString();
// }
}//HeadNode
public boolean delHeadNode(HeadNode<T> headNode){
if(this.setList!=null && this.setList.contains(headNode)){
this.setList.remove(headNode);
headNode.first.delLinkNode(headNode.first);
headNode.delHeadNode();
size-=1;
return true;
}else{
return false;
}
}
public static class LinkNode<T>{
public HeadNode<T> headNode;
public LinkNode<T> next;
public T val;
public LinkNode(T val, HeadNode<T> headNode){
this.headNode = headNode;
this.val= val;
}
public LinkNode<T> getTail(){
LinkNode<T> tail = this;
while(tail.getTail()!=null){
tail = tail.next;
}
return tail;
}
public void delLinkNode(LinkNode<T> linknode){
linknode.headNode = null;
linknode.val = null;
while(linknode.next!=null){
delLinkNode(linknode.next);
linknode= linknode.next;
}
}
@Override
public String toString() {
return String.format("val:%s head:%s", val, headNode.val );
// return super.toString();
}
}//LinkNode
public DisjointSet() {
}
public HeadNode<T> MakeSet(T val){
HeadNode<T> newHeadNode = new HeadNode<T>(val);
this.setList.add(newHeadNode);
this.size+=1;
return newHeadNode;
}
public HeadNode<T> MakeSet(T[] val){
HeadNode<T> newHeadNode = null;
if(val.length>0){
newHeadNode = new HeadNode(val);
this.setList.add(newHeadNode);
this.size+=1;
}
return newHeadNode;
}
public HeadNode<T> FindSet(T val){
if(setList!=null && size>0 && setList.size()>0 ){
for(HeadNode<T> head : setList){
if(head.contain(val)){
return head;
}
}
}
return null;
}
public boolean isConnected(T a , T b){
if(setList!=null ){
for(HeadNode<T> h: setList){
if(h.contain(a)&& h.contain(b)){
return true;
}
}
// return false;
}
return false;
}
public int contain(T a){
int index = -1;
boolean contain = false;
if(setList!=null ){
for(HeadNode<T> h: setList){
index++;
if(h.contain(a)){
contain = true;
break;
}
}
if(!contain){
index= -1;
}
}
return index;
}
public HeadNode<T> add(T val){
int index = contain(val);
if( index ==-1){
HeadNode<T> newHeadNode = MakeSet(val);
this.setList.add(newHeadNode);
this.size++;
}
return this.setList.get(index);
}
public void UnionVal(T t1, T t2){
System.out.printf("union val %s %s
", t1, t2);
if(this.setList==null || this.size==0){
this.setList = new LinkedList<DisjointSet.HeadNode<T>>();
HeadNode<T> newHeadNode =MakeSet(t1);
newHeadNode.addLinkNode(t2);
// this.setList.add(newHeadNode);
// this.size++;
}else{
int h1 = contain(t1);
int h2 = contain(t2);
if( h1==-1 && h2==-1){
HeadNode<T> newHeadNode =MakeSet(t1);
newHeadNode.addLinkNode(t2);
// this.setList.add(newHeadNode);
// this.size++;
}else{
if(h1!=-1 && h2!=-1){
if(h1!=h2){
UnionSet(this.setList.get(h1), this.setList.get(h2));
}
}else{
if(h1!=-1){
this.setList.get(h1).addLinkNode(t2);
}else{
this.setList.get(h2).addLinkNode(t1);
}
}
}
}
}
public void UnionSet(HeadNode<T> set1, HeadNode<T> set2) {
if(set1!=null && set2!=null){
int s1 = set1.num;
int s2 = set2.num;
if(s1<s2){
// set2.itemsList.addAll(c)
for(T t: set1.itemsList){
if(!set2.itemsList.contains(t)){
set2.addLinkNode(t);
}
}
delHeadNode(set1);
}else{
for(T t: set2.itemsList){
if(!set1.itemsList.contains(t)){
set1.addLinkNode(t);
}
}
delHeadNode(set2);
}
}else{
// throw new Exception("UnionSet error");
}
}
public void printDisJointSet(){
if(setList==null){
System.out.println("null disjointSet" );
return;
}
System.out.printf("set size:%s %s
", size, setList.size() );
for(HeadNode<T> h : setList){
h.printHeadNode();
}
}
// @Override
// public String toString() {
// return super.toString();
// }
/**
* @param args
*/
public static void main(String[] args) {
DisjointSet<String> disjointSet = new DisjointSet<String>();
disjointSet.UnionVal("1", "2");
disjointSet.printDisJointSet();
disjointSet.UnionVal("3", "4");
disjointSet.printDisJointSet();
disjointSet.UnionVal("3", "6");
disjointSet.printDisJointSet();
disjointSet.UnionVal("1", "4");
disjointSet.printDisJointSet();
// disjointSet.MakeSet(new String[]{"a", "b"});
// disjointSet.add("a");
// disjointSet.add("c");
}
}