package de.lmu.ifi.dbs.elki.utilities.datastructures.hierarchy;
/*
This file is part of ELKI:
Environment for Developing KDD-Applications Supported by Index-Structures
Copyright (C) 2012
Ludwig-Maximilians-Universität München
Lehr- und Forschungseinheit für Datenbanksysteme
ELKI Development Team
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU Affero General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU Affero General Public License for more details.
You should have received a copy of the GNU Affero General Public License
along with this program. If not, see .
*/
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import de.lmu.ifi.dbs.elki.logging.LoggingUtil;
import de.lmu.ifi.dbs.elki.utilities.iterator.EmptyIterator;
/**
* Centralized hierarchy implementation, using a HashMap of Lists.
*
* @author Erich Schubert
*
* @param Object type (arbitrary!)
*/
public class HierarchyHashmapList implements ModifiableHierarchy {
/**
* The data storage for parents
*/
final private HashMap> pmap;
/**
* The data storage for children
*/
final private HashMap> cmap;
/**
* Constructor
*/
public HierarchyHashmapList() {
super();
this.pmap = new HashMap>();
this.cmap = new HashMap>();
}
@Override
public void add(O parent, O child) {
// Add child to parent.
{
List pchi = this.cmap.get(parent);
if(pchi == null) {
pchi = new LinkedList();
this.cmap.put(parent, pchi);
}
if(!pchi.contains(child)) {
pchi.add(child);
} else {
LoggingUtil.warning("Result added twice: "+parent+" -> "+child);
}
}
// Add child to parent
{
List cpar = this.pmap.get(child);
if(cpar == null) {
cpar = new LinkedList();
this.pmap.put(child, cpar);
}
if(!cpar.contains(parent)) {
cpar.add(parent);
} else {
LoggingUtil.warning("Result added twice: "+parent+" <- "+child);
}
}
}
@Override
public void remove(O parent, O child) {
// Remove child from parent.
{
List pchi = this.cmap.get(parent);
if(pchi != null) {
while(pchi.remove(child)) {
// repeat - remove all instances
}
if(pchi.size() == 0) {
this.cmap.remove(parent);
}
}
}
// Remove parent from child
{
List cpar = this.pmap.get(child);
if(cpar != null) {
while(cpar.remove(parent)) {
// repeat - remove all instances
}
if(cpar.size() == 0) {
this.pmap.remove(child);
}
}
}
}
/**
* Put an object along with parent and child lists.
*
* @param obj Object
* @param parents Parent list
* @param children Child list
*/
public void put(O obj, List parents, List children) {
this.pmap.put(obj, parents);
this.cmap.put(obj, children);
}
@Override
public int numChildren(O obj) {
List children = this.cmap.get(obj);
if(children == null) {
return 0;
}
return children.size();
}
@Override
public List getChildren(O obj) {
List children = this.cmap.get(obj);
if(children == null) {
return Collections.emptyList();
}
return children;
}
@Override
public Iterator iterDescendants(O obj) {
return new ItrDesc(obj);
}
@Override
public int numParents(O obj) {
List parents = this.pmap.get(obj);
if(parents == null) {
return 0;
}
return parents.size();
}
@Override
public List getParents(O obj) {
List parents = this.pmap.get(obj);
if(parents == null) {
return Collections.emptyList();
}
return parents;
}
@Override
public Iterator iterAncestors(O obj) {
return new ItrAnc(obj);
}
/**
* Iterator to collect into the descendants.
*
* @author Erich Schubert
*
* @apiviz.exclude
*/
private class ItrDesc implements Iterator {
/**
* Starting object (for cloning);
*/
final O start;
/**
* Iterator over children
*/
final Iterator childiter;
/**
* Iterator of current child
*/
Iterator subiter;
public ItrDesc(O start) {
this.start = start;
List children = getChildren(start);
if(children != null) {
this.childiter = children.iterator();
}
else {
this.childiter = EmptyIterator.STATIC();
}
this.subiter = null;
}
@Override
public boolean hasNext() {
if(subiter != null && subiter.hasNext()) {
return true;
}
return childiter.hasNext();
}
@Override
public O next() {
// Try nested iterator first ...
if(subiter != null && subiter.hasNext()) {
return subiter.next();
}
// Next direct child, update subiter.
final O child = childiter.next();
subiter = iterDescendants(child);
return child;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
/**
* Iterator over all Ancestors.
*
* @author Erich Schubert
*
* @apiviz.exclude
*/
private class ItrAnc implements Iterator {
/**
* Starting object (for cloning);
*/
final O start;
/**
* Iterator over parents
*/
final Iterator parentiter;
/**
* Iterator of current parent
*/
Iterator subiter;
public ItrAnc(O start) {
this.start = start;
List parents = getParents(start);
if(parents != null) {
this.parentiter = parents.iterator();
}
else {
this.parentiter = EmptyIterator.STATIC();
}
this.subiter = null;
}
@Override
public boolean hasNext() {
if(subiter != null && subiter.hasNext()) {
return true;
}
return parentiter.hasNext();
}
@Override
public O next() {
// Try nested iterator first ...
if(subiter != null && subiter.hasNext()) {
return subiter.next();
}
// Next direct parent, update subiter.
final O parent = parentiter.next();
subiter = iterAncestors(parent);
return parent;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
}