unionfindset.java

来自「<算法导论>第二版大部分算法实现. 1. 各类排序和顺序统计学相关」· Java 代码 · 共 178 行

/*
 * Copyright (C) 2003-2008 Wang Pengcheng <[e-mail]>
 * Permission is granted to copy, distribute and/or modify this
 * document under the terms of the GNU Free Documentation License,
 * Version 2.0 or any later version published by the Free Software Foundation;
 * with no Invariant Sections.
 * You may obtain a copy of the License at
 *   http://www.gnu.org/licenses/lgpl.txt
 */
//9 Apr 2008
package cn.edu.whu.iss.algorithm.unit21;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

import cn.edu.whu.iss.algorithm.unit10.StackLink;

public class UnionFindSet<T> implements UnionFind<T>,Set<T> {

	private HashMap<T, UnionFindSetNode<T>> map;
	
	
	public UnionFindSet () {
		super();
		map = new HashMap<T, UnionFindSetNode<T>>();
	}

	public boolean add(T e) {
		return makeSet(e);
	}

	public boolean addAll(Collection<? extends T> c) {
		// TODO Auto-generated method stub
		return false;
	}
	
	public void clear() {
		map.clear();
	}
	
	public boolean contains(Object o) {
		return map.containsKey(o);
	}
	
	public boolean containsAll(Collection<?> c) {
		// TODO Auto-generated method stub
		return false;
	}
	
	public T findSetRepresent(T item) {
		UnionFindSetNode<T> node = map.get(item);
		if(node==null){
			return null;
		}else{
			node = findSetRepresent(node);
			return node.getItem();
		}
	}

	private UnionFindSetNode<T> findSetRepresent(UnionFindSetNode<T> node){
		if(node.getParent()!=node){
			node.setParent(findSetRepresent(node.getParent()));
		}
		return node.getParent();
	}

	private UnionFindSetNode<T> findSetRepresentIterator(UnionFindSetNode<T> node){
		StackLink<UnionFindSetNode<T>> s = new StackLink<UnionFindSetNode<T>>();
		while(node!=node.getParent()){
			s.push(node);
			node = node.getParent();
		}
		while(!s.isEmpty()){
			UnionFindSetNode<T> temp = s.pop();
			temp.setParent(node);
		}
		return node;
	}

	public T[] getItemsInSetOf(T item) {
		UnionFindSetNode<T> node = map.get(item);
		if(node==null){
			return null;
		}else{
			node = findSetRepresentIterator(node);
			List<T> list = new ArrayList<T>();
			for(UnionFindSetNode<T> n:map.values()){
				if(findSetRepresentIterator(n)==node){
					list.add(n.getItem());
				}
			}
			return (T[]) list.toArray();
		}
	}

	public boolean isEmpty() {
		return map.isEmpty();
	}

	public Iterator<T> iterator() {
		return map.keySet().iterator();
	}

	private boolean link(UnionFindSetNode<T> x,UnionFindSetNode<T> y){
		if(x.getRank()>y.getRank()){
			y.setParent(x);
		}else{
			x.setParent(y);
			if(x.getRank()==y.getRank()){
				y.incRank();
			}
		}
		return true;
	}

	public boolean makeSet(T item) {
		if(map.containsKey(item)){
			return false;
		}
		UnionFindSetNode<T> node = new UnionFindSetNode<T>(item);
		node.makeSet();
		map.put(item, node);
		return true;
	}

	public boolean remove(Object o) {
		return false;
	}

	public boolean removeAll(Collection<?> c) {
		// TODO Auto-generated method stub
		return false;
	}

	public boolean retainAll(Collection<?> c) {
		// TODO Auto-generated method stub
		return false;
	}

	public int size() {
		return map.size();
	}

	public Object[] toArray() {
		// TODO Auto-generated method stub
		return null;
	}

	public <T> T[] toArray(T[] a) {
		// TODO Auto-generated method stub
		return null;
	}

	public boolean union(T iteml, T itemr) {
		UnionFindSetNode<T> x=map.get(iteml),y=map.get(itemr);
		if(x==null||y==null){
			return false;
		}else{
			return union(x, y);
		}
	}

	private boolean union(UnionFindSetNode<T> x,UnionFindSetNode<T> y){
		return link(findSetRepresentIterator(x),findSetRepresentIterator(y));
	}
	
	@Override
	public String toString() {
		// TODO Auto-generated method stub
		return super.toString();
	}
}