de.lmu.ifi.dbs.elki.utilities.datastructures.hierarchy

Class HashMapHierarchy<O>

java.lang.Object

de.lmu.ifi.dbs.elki.utilities.datastructures.hierarchy.HashMapHierarchy<O>

Type Parameters:

O - Object type (arbitrary!)

All Implemented Interfaces:

Hierarchy<O>, ModifiableHierarchy<O>

Direct Known Subclasses:

ResultHierarchy, VisualizationTree

public class HashMapHierarchy<O>
extends Object
implements ModifiableHierarchy<O>

Centralized hierarchy implementation, using a HashMap of Lists.

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private class	HashMapHierarchy.ItrAll Iterator over all known elements, by insertion order.
private class	HashMapHierarchy.ItrAnc Iterator over all Ancestors.
private class	HashMapHierarchy.ItrDesc Iterator over all descendants.
protected static class	HashMapHierarchy.Rec<O> Hierarchy pointers for an object.

Nested classes/interfaces inherited from interface de.lmu.ifi.dbs.elki.utilities.datastructures.hierarchy.Hierarchy

Hierarchy.Iter<O>

Field Summary

Fields

Modifier and Type	Field and Description
(package private) Object[]	elems All elements, in insertion order (and will not fail badly if concurrent insertions happen).
private static Hierarchy.Iter<?>	EMPTY_ITERATOR Empty iterator.
private HashMap<O,HashMapHierarchy.Rec<O>>	graph Reference storage.
(package private) int	numelems Number of all elements.

Constructor Summary

Constructors

Constructor and Description
HashMapHierarchy() Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
boolean	add(O entry) Add an entry (initializes data structures).
boolean	add(O parent, O child) Add a parent-child relationship.
boolean	contains(O object) Check if an object is part of a hierarchy.
static <O> Hierarchy.Iter<O>	emptyIterator() Get an empty hierarchy iterator.
private HashMapHierarchy.Rec<O>	getRec(O obj) Get a record.
Hierarchy.Iter<O>	iterAll() Iterate over all members.
Hierarchy.Iter<O>	iterAncestors(O obj) Iterate ancestors (recursive parents)
Hierarchy.Iter<O>	iterAncestorsSelf(O obj) Iterate ancestors (recursive parents) and self.
Hierarchy.Iter<O>	iterChildren(O obj) Iterate over the (direct) children.
Hierarchy.Iter<O>	iterChildrenReverse(O obj) Iterate over the (direct) children in reverse order.
Hierarchy.Iter<O>	iterDescendants(O obj) Iterate descendants (recursive children)
Hierarchy.Iter<O>	iterDescendantsSelf(O obj) Iterate descendants (recursive children) and self.
Hierarchy.Iter<O>	iterParents(O obj) Iterate over the (direct) parents.
Hierarchy.Iter<O>	iterParentsReverse(O obj) Iterate over the (direct) parents in reverse order.
int	numChildren(O obj) Get number of children
int	numParents(O obj) Get number of (direct) parents
private void	putRec(O obj, HashMapHierarchy.Rec<O> rec) Put a record.
boolean	remove(O entry) Remove an entry and all its parent-child relationships.
boolean	remove(O parent, O child) Remove a parent-child relationship.
private void	removeRec(O obj) Remove a record.
boolean	removeSubtree(O entry) Remove an entry and it's whole subtree (unless the elements are reachable by a different path!)
int	size() Total size - number of objects contained.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

graph

private final HashMap<O,HashMapHierarchy.Rec<O>> graph

Reference storage.

elems

Object[] elems

All elements, in insertion order (and will not fail badly if concurrent insertions happen).

numelems

int numelems

Number of all elements.

EMPTY_ITERATOR

private static final Hierarchy.Iter<?> EMPTY_ITERATOR

Empty iterator.

Constructor Detail

HashMapHierarchy

public HashMapHierarchy()

Constructor.

Method Detail

contains

public boolean contains(O object)

Description copied from interface: Hierarchy

Check if an object is part of a hierarchy.

Specified by:

contains in interface Hierarchy<O>

Parameters:

object - Object to check

Returns:

true if part of the hierarchy

size

public int size()

Description copied from interface: Hierarchy

Total size - number of objects contained.

Specified by:

size in interface Hierarchy<O>

Returns:

Size

add

public boolean add(O parent,
          O child)

Description copied from interface: ModifiableHierarchy

Add a parent-child relationship.

Specified by:

add in interface ModifiableHierarchy<O>

Parameters:

parent - Parent

child - Child

Returns:

true if changed

add

public boolean add(O entry)

Description copied from interface: ModifiableHierarchy

Add an entry (initializes data structures).

Specified by:

add in interface ModifiableHierarchy<O>

Parameters:

entry - Entry

Returns:

true if changed

remove

public boolean remove(O parent,
             O child)

Description copied from interface: ModifiableHierarchy

Remove a parent-child relationship.

Specified by:

remove in interface ModifiableHierarchy<O>

Parameters:

parent - Parent

child - Child

Returns:

true if changed

remove

public boolean remove(O entry)

Description copied from interface: ModifiableHierarchy

Remove an entry and all its parent-child relationships.

Specified by:

remove in interface ModifiableHierarchy<O>

Parameters:

entry - Entry

Returns:

true if changed

removeSubtree

public boolean removeSubtree(O entry)

Description copied from interface: ModifiableHierarchy

Remove an entry and it's whole subtree (unless the elements are reachable by a different path!)

Specified by:

removeSubtree in interface ModifiableHierarchy<O>

Parameters:

entry - Entry

Returns:

true if changed

numChildren

public int numChildren(O obj)

Description copied from interface: Hierarchy

Get number of children

Specified by:

numChildren in interface Hierarchy<O>

Parameters:

obj - object to get number of children for

Returns:

number of children

iterChildren

public Hierarchy.Iter<O> iterChildren(O obj)

Description copied from interface: Hierarchy

Iterate over the (direct) children.

Specified by:

iterChildren in interface Hierarchy<O>

Parameters:

obj - object to get children for

Returns:

iterator for children

iterChildrenReverse

public Hierarchy.Iter<O> iterChildrenReverse(O obj)

Description copied from interface: Hierarchy

Iterate over the (direct) children in reverse order.

Specified by:

iterChildrenReverse in interface Hierarchy<O>

Parameters:

obj - object to get children for

Returns:

iterator for children

iterDescendants

public Hierarchy.Iter<O> iterDescendants(O obj)

Description copied from interface: Hierarchy

Iterate descendants (recursive children)

Specified by:

iterDescendants in interface Hierarchy<O>

Parameters:

obj - object to get descendants for

Returns:

iterator for descendants

iterDescendantsSelf

public Hierarchy.Iter<O> iterDescendantsSelf(O obj)

Description copied from interface: Hierarchy

Iterate descendants (recursive children) and self.

Specified by:

iterDescendantsSelf in interface Hierarchy<O>

Parameters:

obj - object to get descendants for

Returns:

iterator for descendants

numParents

public int numParents(O obj)

Description copied from interface: Hierarchy

Get number of (direct) parents

Specified by:

numParents in interface Hierarchy<O>

Parameters:

obj - reference object

Returns:

number of parents

iterParents

public Hierarchy.Iter<O> iterParents(O obj)

Description copied from interface: Hierarchy

Iterate over the (direct) parents.

Specified by:

iterParents in interface Hierarchy<O>

Parameters:

obj - object to get parents for

Returns:

iterator of parents

iterParentsReverse

public Hierarchy.Iter<O> iterParentsReverse(O obj)

Description copied from interface: Hierarchy

Iterate over the (direct) parents in reverse order.

Specified by:

iterParentsReverse in interface Hierarchy<O>

Parameters:

obj - object to get parents for

Returns:

iterator of parents

iterAncestors

public Hierarchy.Iter<O> iterAncestors(O obj)

Description copied from interface: Hierarchy

Iterate ancestors (recursive parents)

Specified by:

iterAncestors in interface Hierarchy<O>

Parameters:

obj - object to get ancestors for

Returns:

iterator for ancestors

iterAncestorsSelf

public Hierarchy.Iter<O> iterAncestorsSelf(O obj)

Description copied from interface: Hierarchy

Iterate ancestors (recursive parents) and self.

Specified by:

iterAncestorsSelf in interface Hierarchy<O>

Parameters:

obj - object to get ancestors for

Returns:

iterator for ancestors

iterAll

public Hierarchy.Iter<O> iterAll()

Description copied from interface: Hierarchy

Iterate over all members.

Specified by:

iterAll in interface Hierarchy<O>

Returns:

Iterator over all members.

getRec

private HashMapHierarchy.Rec<O> getRec(O obj)

Get a record.

Parameters:

obj - Key

Returns:

Record

putRec

private void putRec(O obj,
          HashMapHierarchy.Rec<O> rec)

Put a record.

Parameters:

obj - Key

rec - Record

removeRec

private void removeRec(O obj)

Remove a record.

Parameters:

obj - Key

emptyIterator

public static <O> Hierarchy.Iter<O> emptyIterator()

Get an empty hierarchy iterator.

Returns:

Empty iterator