org.kit.furia.fragment
Class OBFragment

java.lang.Object
  org.kit.furia.fragment.OBFragment

All Implemented Interfaces:

org.ajmm.obsearch.OB, org.ajmm.obsearch.ob.OBShort, org.ajmm.obsearch.Storable

public final class OBFragment
extends java.lang.Object
implements org.ajmm.obsearch.ob.OBShort

Implementation of the mtd algorithm. This algorithm exploits hash codes from string representation of the tree and its complete subtrees. Additionally, it exploits the fact that once two complete subtrees j and m that belong respectively to trees T1 and T2, the intersection of j and m and all their complete subtrees can be calculated in linear time. This requires to have a value of multiplicity in each node of T1 and T2. So the expected running time is around O(|T1|) (where |T1| the size of the smallest tree)

Author:

Arnoldo Jose Muller Molina

Constructor Summary

OBFragment()

OBFragment(java.lang.String x)

Method Summary

short	distance(org.ajmm.obsearch.ob.OBShort other)
int	dn(OBFragment other)
int	ds(OBFragment other)
boolean	equals(java.lang.Object obj) Returns true of this.tree.equals(obj.tree).
MTDFragmentAST	getTree()
int	hashCode() A hashCode based on the string representation of the tree.
void	load(com.sleepycat.bind.tuple.TupleInput in) Re-creates this object from the given byte stream
short	mtd(OBFragment other)
static MTDFragmentAST	parseTree(java.lang.String x)
void	setTree(MTDFragmentAST tree)
int	size() Returns the size (in nodes) of the tree.
void	store(com.sleepycat.bind.tuple.TupleOutput out) Stores this object into the given byte stream.
java.lang.String	toString()
protected void	updateTree(java.lang.String x) Internal method that updates the Tree from the String

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

OBFragment

public OBFragment()

OBFragment

public OBFragment(java.lang.String x)
           throws org.ajmm.obsearch.exception.OBException

Throws:

org.ajmm.obsearch.exception.OBException

Method Detail

updateTree

protected final void updateTree(java.lang.String x)
                         throws org.ajmm.obsearch.exception.OBException

Internal method that updates the Tree from the String

Throws:

org.ajmm.obsearch.exception.OBException

parseTree

public static final MTDFragmentAST parseTree(java.lang.String x)
                                      throws FragmentParseException

Throws:

FragmentParseException

size

public final int size()
               throws org.ajmm.obsearch.exception.OBException

Returns the size (in nodes) of the tree.

Returns:

The size of the tree.

Throws:

org.ajmm.obsearch.exception.OBException - If something goes wrong.

toString

public final java.lang.String toString()

Overrides:

toString in class java.lang.Object

Returns:

A String representation of the tree.

load

public final void load(com.sleepycat.bind.tuple.TupleInput in)
                throws org.ajmm.obsearch.exception.OBException

Re-creates this object from the given byte stream

Specified by:

load in interface org.ajmm.obsearch.Storable

Parameters:

in - A byte stream with the data that must be loaded.

Throws:

org.ajmm.obsearch.exception.OBException

See Also:

Storable.load(com.sleepycat.bind.tuple.TupleInput)

store

public final void store(com.sleepycat.bind.tuple.TupleOutput out)

Stores this object into the given byte stream.

Specified by:

store in interface org.ajmm.obsearch.Storable

Parameters:

out - The byte stream to be used

See Also:

Storable.store(com.sleepycat.bind.tuple.TupleOutput)

distance

public final short distance(org.ajmm.obsearch.ob.OBShort other)

Specified by:

distance in interface org.ajmm.obsearch.ob.OBShort

mtd

public final short mtd(OBFragment other)

ds

public int ds(OBFragment other)

dn

public int dn(OBFragment other)

getTree

public MTDFragmentAST getTree()

setTree

public void setTree(MTDFragmentAST tree)

equals

public final boolean equals(java.lang.Object obj)

Returns true of this.tree.equals(obj.tree). For this distance function this.distance(obj) == 0 implies that this.equals(obj) == true

Overrides:

equals in class java.lang.Object

Parameters:

obj - Object to compare.

Returns:

true if this == obj

hashCode

public final int hashCode()

A hashCode based on the string representation of the tree.

Overrides:

hashCode in class java.lang.Object

Returns:

a hash code of the string representation of this tree.