/*
* Copyright (c) 2010 Mathew Hall, University of Sheffield.
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or
* without modification, are permitted provided that the following conditions
* are met:
*
* Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* Redistributions in binary form must reproduce the above
* copyright notice, this list of conditions and the following
* disclaimer in the documentation and/or other materials provided
* with the distribution.
*
* Neither the name of the University of Sheffield nor the names of its
* contributors may be used to endorse or promote products derived
* from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
* CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
* INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
* MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
* OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
* EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
*/
package primitives.cluster;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.LinkedList;
import java.util.Set;
import java.util.HashSet;
import java.util.Stack;
import primitives.graph.Graph;
import primitives.graph.Node;
import primitives.util.UndefinedIndexException;
public abstract class ClusterUtils {
//move child from a to b
//if a becomes empty then delete a and add all its old ids to b
/***
* To becomes the new parent of node. This method migrates node to a new parent.
*
* @param node the node to move
* @param from the current parent of node
* @param to the new parent of mode
* @param tree the tree this operation takes part in. Will be modified.
* @param prune should empty clusters created as a result be removed?
* @return the modified tree. Does in-place so this is equal to tree parameter.
*/
public static ClusterHead move(IClusterLevel node, ClusterNode from, ClusterNode to, ClusterHead tree, boolean prune) {
if (to != null && to.encapsulates() && from != null && node != null) {
from.deleteChild(node);
to.addChild(node);
//if from has no clusterleaves, just copy all of its ids over to to.
if (prune && from.getSize() == 0) {
for (int i : from.getIDs()) {
to.setID(i);
}
deleteClusterLevelFromTree(from,tree);
}
}else{
System.err.println("ERROR");
}
return tree;
}
/**
* To becomes the new parent of node, empty nodes are removed. This is the equivalent
* of calling move with prune set to true.
* @see #move(primitives.cluster.IClusterLevel, primitives.cluster.ClusterNode, primitives.cluster.ClusterNode, primitives.cluster.ClusterHead, boolean prune)
* @param node
* @param from
* @param to
* @param tree
* @return
*/
public static ClusterHead move(IClusterLevel node, ClusterNode from, ClusterNode to, ClusterHead tree) {
return move( node, from, to, tree, true);
}
@Deprecated
public static ClusterHead explode(ClusterNode toSplit, ClusterNode parent, ClusterHead tree) {
Queue<ClusterNode> added = new LinkedList<ClusterNode>();
for (int id : toSplit.getIDs()) {
ClusterNode newC = new ClusterNode();
newC.setID(id);
parent.addChild(newC);
added.add(newC);
}
for (IClusterLevel c : toSplit.getChildren()) {
ClusterNode n = added.remove();
n.addChild(c);
added.add(n);
}
return ClusterUtils.deleteClusterLevelFromTree(toSplit, tree);
}
/**
* Add an empty ClusterNode below parent. This method creates a new ClusterNode
* and adds it to parent's children. It will search all IDs in the whole tree
* for the lowest unused ID.
* @return a new ClusterNode with an ID set to the lowest unused one.
*/
public static ClusterNode addEmpty(ClusterNode parent, ClusterHead tree) {
int i = 0;
HashSet<Integer> ids = new HashSet<Integer>(); ids.addAll(getIDs(tree));
do {
if (!ids.contains(i)) {
assert (parent.encapsulates());
ClusterNode c = new ClusterNode();
c.setID(i);
parent.addChild(c);
return tree;
}
i++;
} while (true);
}
/**
* Add a new ClusterNode below parent, without setting its ID. This method
* adds a new ClusterNode below parent but does so without assigning the lowest
* valid ID, instead setting it to -2.
* @return the new node added, with ID -2.
*/
public static ClusterNode addEmptyIgnoreID(ClusterNode parent, ClusterHead tree) {
assert (parent.encapsulates());
ClusterNode c = new ClusterNode();
c.setID(-2);
parent.addChild(c);
return c;
}
/**
* Remove a cluster from the tree. This removes toBeRemoved from the tree by finding
* its parent and calling deleteChild on it. The argument will not be modified, nor
* will any kind of migration occur for nodes within toBeRemoved. Don't use this method
* without dealing with the children. If toBeRemoved will be made the child of another node,
* {@link #move(primitives.cluster.IClusterLevel, primitives.cluster.ClusterNode, primitives.cluster.ClusterNode, primitives.cluster.ClusterHead)} should be used instead.
* @param toBeRemoved
* @param tree
* @return
*/
@Deprecated
public static ClusterHead deleteClusterLevelFromTree(IClusterLevel toBeRemoved, ClusterHead tree) {
IClusterLevel parent = findParent(toBeRemoved, tree);
if (parent != null && parent.encapsulates()) {
((ClusterNode) parent).deleteChild(toBeRemoved);
}
return tree;
}
/***
* Locates the parent of a node.
* @param searchterm a cluster whose parent is sought
* @param tree the tree in which the search takes place.
* @return the parent of searchterm or null if the parent could not be found or if tree == searchterm
*/
public static ClusterNode findParent(IClusterLevel searchterm, IClusterLevel tree) {
if (tree == searchterm) {
return null;
}
if (tree.encapsulates()) {
ClusterNode cast = (ClusterNode)tree;
if (cast.getChildren().contains(searchterm)) {
return cast;
}
for (IClusterLevel t : cast.getChildren()) {
ClusterNode res = findParent(searchterm, t);
if (res != null) {
return res;
}
}
}
return null;
}
/**
* Determines if a tree contains all nodes from a graph.
* @param tree the tree representation that should have all nodes from representation
* @param representation nodes to be searched for in tree
* @return true if all nodes from tree are present in representation and vice versa.
*/
public static boolean validTree(ClusterHead tree, Graph representation) {
///TODO: need to check for intercluster duplication as well as set size.
return (tree.getNodes().containsAll(representation.getNodes())
&& representation.getNodes().containsAll(tree.getNodes()));
//return false if:
// the tree has less nodes than the graph
// there are duplicated nodes between the child clusters
//otherwise return true.
}
/**
* Searches the tree for a subcluster with a given ID number.
* Subclusters are assigned a unique identifier which is used by
* programs the interpreter runs. The parameter should always
* be at most the size of the graph; identifiers start at 0
* and go to the initial size of the clustering which is always
* equal to the size of the set of nodes in the graph.
* This may require some adaptation in future.
* TODO: write code to snap a given non-found integer to a found one
* TODO: or just make clusters store IDs of their old merged ones.
* @param tree the tree to perform the lookupIndexInTree in
* @param index the ID number to search for
* @return the cluster node with that ID
* @throws UndefinedIndexException if the ID isn't found, which can be
* used to default to some valid node, the selection of it isn't defined.
*/
public static IClusterLevel lookupIndexInTree(int index, ClusterNode tree) throws UndefinedIndexException {
//TODO: make sure we don't accidentally assign tree to the result of this fn
Queue<IClusterLevel> toVisit = new LinkedList<IClusterLevel>();
toVisit.offer(tree);
while(!toVisit.isEmpty()){
IClusterLevel current = toVisit.remove();
if (current.knownAs(index)) {
return current;
}
Set<IClusterLevel> kids = ((ClusterNode)current).getChildren();
for (IClusterLevel c : kids) {
if (c.knownAs(index)) {
return c;
}
}
for (IClusterLevel c : kids) {
if (c.encapsulates() && c != tree) {
toVisit.offer(c);
}
}
}
throw new UndefinedIndexException("ClusterUtils.lookup - ID number " + index + " not found in tree.", tree);
}
/**
* Locates the ClusterNode containing n. This method will return the ClusterNode
* in the tree which has n as its child.
* @param n
* @param tree
* @return a ClusterNode containing n.
* @throws UndefinedIndexException if n cannot be found in the tree.
*/
public static IClusterLevel lookup(Node n, ClusterNode tree) throws UndefinedIndexException {
//TODO: make sure we don't accidentally assign tree to the result of this fn
boolean isParentOfLeaf = true;
Set<IClusterLevel> kids = tree.getChildren();
for (IClusterLevel c :kids){
if(c.encapsulates()) isParentOfLeaf = false;
}
if (tree.getNodes().contains(n) && isParentOfLeaf) {
return tree;
}
for (IClusterLevel c :kids) {
if (c.getNodes().contains(n)) {
try{return lookup(n, (ClusterNode)c);}catch(Exception e){}
}
}
throw new UndefinedIndexException("ClusterUtils.lookup - ID number " + n + " not found in tree.", tree);
}
/**
* Merges two cluster nodes to one node.
* Nodes from toberemoved will be placed in parent and toberemoved deleted from the tree.
* TODO: feed the old ID for toberemoved to parent.
* @param tree the tree in which to perform the operation
* @param parent the node which will adopt the children of toberemoved
* @param toberemoved the node to be removed from the tree.
* @return
*/
public static IClusterLevel merge(IClusterLevel toberemoved, IClusterLevel parent, ClusterNode tree) {
if (parent == toberemoved) {
return tree;
}
//if(parent.getID() == toberemoved.getID()) return tree;
//if(!toberemoved.encapsulates()) return tree;
//if(!parent.encapsulates()) return tree;
if (parent.equals(toberemoved)) {
return tree;
}
//if both encapsulate do whatever
//if one encapsulates make it inherit the other's Nodes
//if neither encapsulate add nodes to other
if (parent.encapsulates() && toberemoved.encapsulates()) {
Set<IClusterLevel> children = ((ClusterNode) toberemoved).getChildren();
tree.deleteChild(toberemoved); //?
//((ClusterNode) parent).deleteChild(toberemoved); //?
for (Integer i : toberemoved.getIDs()) {
parent.setID(i);
}
for (IClusterLevel c : children) {
if (c != parent) {
((ClusterNode) parent).addChild(c);
}
}
} else if (toberemoved.encapsulates() && !parent.encapsulates()) {
//if the parent doesn't encapsulate and toberemoved does then
//we should do the opposite and merge tobereomved with parent
Set<Node> children = parent.getNodes();
tree.deleteChild(parent);
//tree.deleteChild(toberemoved);
//parent = toberemoved;
for (Integer i : parent.getIDs()) {
toberemoved.setID(i);
}
for (Node node : children) {
parent.addNode(node);
}
} else {
tree.deleteChild(toberemoved);
for (Integer i : toberemoved.getIDs()) {
parent.setID(i);
}
for (Node n : toberemoved.getNodes()) {
parent.addNode(n);
}
}
return tree;
}
public static void prettyPrintTree(IClusterLevel tree) {
prettyPrintTree(tree, 0);
}
private static void prettyPrintTree(IClusterLevel tree, int tabIndex) {
for (int i = 0; i < tabIndex; i++) {
System.out.print("\t");
}
System.out.println("Cluster " + tree.getIDs() + "[");
if (tree.encapsulates()) {
for (IClusterLevel t : ((ClusterNode) tree).getChildren()) {
prettyPrintTree(t, tabIndex + 1);
}
} else {
for (int i = 0; i < tabIndex; i++) {
System.out.print("\t");
}
for (Node n : tree.getNodes()) {
System.out.print(" " + n);
}
System.out.println();
}
for (int i = 0; i < tabIndex; i++) {
System.out.print("\t");
}
System.out.println("]");
}
public static List<Integer> getIDs(IClusterLevel tree) {
ArrayList<Integer> ret = new ArrayList<Integer>();
getIDsInternal(tree,ret);
return ret;
}
private static List<Integer> getIDsInternal(IClusterLevel tree, ArrayList<Integer> list){
list.addAll(tree.getIDs());
if (tree.encapsulates()) {
Set<IClusterLevel> l = ((ClusterNode) tree).getChildren();
for (IClusterLevel c : l) {
getIDsInternal(c,list);
}
}
return list;
}
public static void printIDs(IClusterLevel tree) {
for (Integer i : tree.getIDs()) {
System.out.print(i + ",");
}
System.out.println();
if (tree.encapsulates()) {
for (IClusterLevel c : ((ClusterNode) tree).getChildren()) {
printIDs(c);
}
}
}
public static IClusterLevel getParentOfNodeInTree(Node node, ClusterHead tree){
Stack<IClusterLevel> toVisit = new Stack<IClusterLevel>();
toVisit.addAll(tree.getChildren());
while(!toVisit.isEmpty()){
IClusterLevel c = toVisit.pop();
if(c.contains(node)){
if(!c.encapsulates()){
//We've hit a ClusterLeaf so we've hit the bottom
//of the tree so it's time to stop
return c;
}else{
//current level's children will have node, so
//everything else on the stack won't, so empty the
//stack.
toVisit.removeAllElements();
for(IClusterLevel child:((ClusterNode) c).getChildren())
toVisit.push(child);
}
}
}
return tree; //this will never execute but we need to shut javac up
}
/**
* Remove all empty nodes. This method will locate and remove all nodes in the
* tree that contain nothing. The children of this empty node will replace it.
* @param ch
* @return the modified tree (does in place so can be ignored).
*/
public static ClusterHead prune(ClusterHead ch){
if(ch.getChildren().size() == 1){
IClusterLevel child = null;
for(IClusterLevel c: ch.getChildren()){
child = c;
}
if(child.encapsulates()){
ch.setChildren(((ClusterNode)child).getChildren());
ch.deleteChild(child);
return prune(ch);
}
}
return ch;
}
public static boolean isCyclic(IClusterLevel c){
Stack<IClusterLevel> toVisit = new Stack<IClusterLevel>();
Set<IClusterLevel> seen = new HashSet<IClusterLevel>();
toVisit.push(c);
while(!toVisit.isEmpty()){
IClusterLevel current = toVisit.pop();
if(!current.encapsulates()) continue; //ignore leaves - they can't be cyclic.
ClusterNode cast = (ClusterNode)current;
if(seen.contains(current)) return true;
seen.add(current);
for(IClusterLevel cn: cast.getChildren()){
toVisit.push(cn);
}
}
return false;
}
}