tauzaman.calendricsystem.granularitylattice
Class GranularityLattice

java.lang.Object
  |
  +--tauzaman.calendricsystem.granularitylattice.GranularityLattice

public class GranularityLattice

extends java.lang.Object

Nested Class Summary

private class	GranularityLattice.LatticeEdge LatticeEdge class is a private inner class to GranularityLattice.
private class	GranularityLattice.LatticeNode LatticeNode class is a private inner class to GranularityLattice.
private class	GranularityLattice.SPElement SPElement class is a private inner class to GranularityLattice.

Field Summary

private static int	BLACK Constant used in DFS part of induce mappings to indicate a node has been fully explored.
private static boolean	BUILDPATH_DEBUG
static boolean	CACHE_DEBUG
private static int	CACHE_SIZE
private static int	COARSER
private tauzaman.calendricsystem.granularitylattice.cache.Cache	coarserSpTableCache Cache that maps particular granularities to an already computed table of shortest path information to coarser granularities.
private static int	CONGRUENT
private static int	FINER
private tauzaman.calendricsystem.granularitylattice.cache.Cache	finerSpTableCache Cache that maps particular granularities to an already computed table of shortest path information to finer granularities.
private static int	GRAY Constant used in DFS part of induce mappings to indicate a node is currently being explored.
private static java.lang.Integer	INFINITY
private tauzaman.calendricsystem.granularitylattice.cache.Cache	mappingCache Cache that maps a string representing the source granularity to the destination granularity ("sourceGranStr$destGranStr") to mapping paths.
private java.util.ArrayList	nodeList List of all the nodes in the lattice.
private java.util.HashMap	nodeTable This hashtable will contain a reference to all nodes in the granularity lattice by mapping Granularity -> LatticeNode.
private static boolean	SP_DEBUG
private static int	SPACES
private static int	WHITE Constant used in DFS part of induce mappings to indicate a node has not yet been explored.

Constructor Summary

GranularityLattice(Calendar[] calendars, Mapping[] interCalMappings)
Constructs a GranularityLattice object.

Method Summary

void	addCalendar(Calendar calendar) Adds an entire calendar to the lattice by going through each mapping in the calendar, adding any nodes that are not already in the lattice plus the edges connecting the nodes in each mapping.
void	addMapping(Mapping mapping) Creates an edge between the "from" granularity and the "to" granularity in the Mapping object with the Mapping object itself as the edge's label.
private java.util.ArrayList	buildMappingPath(java.util.HashMap spTable, GranularityLattice.LatticeNode s, GranularityLattice.LatticeNode v, int typeOfEdges) Given a particular predecessor list, builds a mapping path between two nodes.
private void	buildPathHelper(java.util.HashMap spTable, GranularityLattice.LatticeNode s, GranularityLattice.LatticeNode v, java.util.ArrayList path) Recursive helper method used to build the mapping path.
Granule	cast(Granule granule, Granularity toGranularity) Uses the lattice to cast the given granule from its granularity to another granularity.
void	clearCaches() Resets all of the lattice's caches.
private java.util.HashMap	dijkstraShortestPaths(GranularityLattice.LatticeNode s, int typeOfEdges) Using Djikstra's algorithm, computes all shortest paths starting from a given lattice node.
private java.util.ArrayList	findPath(Granularity sourceGranularity, Granularity destGranularity) Finds a path (made up of Mapping objects) that can be used to convert the given source granularity to the destination granularity.
private java.util.HashMap	getSpTable(GranularityLattice.LatticeNode s, int typeOfEdges) Returns a table of shortest path information for the given node and type (i.e. coarser/finer).
private tauzaman.calendricsystem.granularitylattice.minpriorityqueue.MinPriorityQueue	getSuccessors(GranularityLattice.LatticeNode node, int typeOfEdges) Returns a minimum priority queue of nodes that are reachable by the given node through the given type of edges (i.e. coarser/finer).
private void	induceMappings() Induces all regular mappings in the sets of coarser, finer and congruent edges in the lattice.
private void	induceMappings(int typeOfEdges) Performs a DFS search on each node looking for regular mappings that can be induced.
private void	induceMappingsDFSVisit(GranularityLattice.LatticeNode sourceNode, GranularityLattice.LatticeEdge sourceEdge, GranularityLattice.LatticeNode curNode, int typeOfEdges, java.util.HashMap colorTable) Recursive helper to the DFS part of the mapping induction.
private void	initializeSingleSource(GranularityLattice.LatticeNode s, java.util.HashMap spTable) Initializes the data structures used in Djiksta's algorithm.
boolean	isCoarser(Granularity g1, Granularity g2) Uses the lattice to determine if one granularity is coarser than another.
boolean	isEquivalent(Granularity g1, Granularity g2) Uses the lattice to determine if the two granularities are equivalent.
boolean	isFiner(Granularity g1, Granularity g2) Uses the lattice to determine if one granularity is finer than another.
boolean	isIncomparable(Granularity g1, Granularity g2) Uses the lattice to determine if the two granularities are equivalent.
private void	printSpTable(java.util.HashMap preds) Helper method used to debug findPath by printing out predecessor lists.
private void	relax(GranularityLattice.LatticeNode u, GranularityLattice.LatticeNode v, int w, java.util.HashMap spTable, tauzaman.calendricsystem.granularitylattice.minpriorityqueue.MinPriorityQueue Q) Tests whether or not we can improve the shortest path to v found so far by going through u, and, if so, updating the shortest path estimation table and the predecessor table.
java.lang.String	toString() Returns a string representation of the lattice.

Methods inherited from class java.lang.Object

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

Field Detail

COARSER

private static final int COARSER

See Also:

Constant Field Values

FINER

private static final int FINER

See Also:

Constant Field Values

CONGRUENT

private static final int CONGRUENT

See Also:

Constant Field Values

SPACES

private static final int SPACES

See Also:

Constant Field Values

CACHE_SIZE

private static final int CACHE_SIZE

See Also:

Constant Field Values

BUILDPATH_DEBUG

private static final boolean BUILDPATH_DEBUG

See Also:

Constant Field Values

CACHE_DEBUG

public static boolean CACHE_DEBUG

SP_DEBUG

private static final boolean SP_DEBUG

See Also:

Constant Field Values

nodeTable

private java.util.HashMap nodeTable

This hashtable will contain a reference to all nodes in the granularity lattice by mapping Granularity -> LatticeNode.

finerSpTableCache

private tauzaman.calendricsystem.granularitylattice.cache.Cache finerSpTableCache

Cache that maps particular granularities to an already computed table of shortest path information to finer granularities.

coarserSpTableCache

private tauzaman.calendricsystem.granularitylattice.cache.Cache coarserSpTableCache

Cache that maps particular granularities to an already computed table of shortest path information to coarser granularities.

mappingCache

private tauzaman.calendricsystem.granularitylattice.cache.Cache mappingCache

Cache that maps a string representing the source granularity to the destination granularity ("sourceGranStr$destGranStr") to mapping paths.

nodeList

private java.util.ArrayList nodeList

List of all the nodes in the lattice.

WHITE

private static final int WHITE

Constant used in DFS part of induce mappings to indicate a node has not yet been explored.

See Also:

Constant Field Values

GRAY

private static final int GRAY

Constant used in DFS part of induce mappings to indicate a node is currently being explored.

See Also:

Constant Field Values

BLACK

private static final int BLACK

Constant used in DFS part of induce mappings to indicate a node has been fully explored.

See Also:

Constant Field Values

INFINITY

private static final java.lang.Integer INFINITY

Constructor Detail

GranularityLattice

public GranularityLattice(Calendar[] calendars,
                          Mapping[] interCalMappings)
                   throws CalendricSystemFormationException

Constructs a GranularityLattice object. The construction is done by: (1) For each calendar in calendars, get the calendar's mappings and set up LatticeNodes for each granularity encountered and connecting the nodes with the mappings themselves. (2) Connecting the granularities in different calendars using the mappings in the inter-calendar mappings array.

Parameters:

calendars - the array of all Calendar objects that are in this calendric system

Throws:

CalendricSystemFormationException - if any error occurs while forming GranularityLattice

Method Detail

addCalendar

public void addCalendar(Calendar calendar)
                 throws CalendricSystemFormationException

Adds an entire calendar to the lattice by going through each mapping in the calendar, adding any nodes that are not already in the lattice plus the edges connecting the nodes in each mapping.

Parameters:

calendar - Calendar to be added to the lattice

CalendricSystemFormationException

addMapping

public void addMapping(Mapping mapping)
                throws CalendricSystemFormationException

Creates an edge between the "from" granularity and the "to" granularity in the Mapping object with the Mapping object itself as the edge's label.

Parameters:

mapping - Mapping that is the edge's label

Throws:

NoSuchGranularityException - if either of the Granularities in the mapping are not recognized by the lattice (i.e., there is no node in the lattice that has this granularity)

CalendricSystemFormationException

cast

public Granule cast(Granule granule,
                    Granularity toGranularity)
             throws CalendricSystemServiceException

Uses the lattice to cast the given granule from its granularity to another granularity.

Parameters:

granule - the granule to cast from its granularity to another granularity

toGranularity - the granularity to which to cast the given granule

Returns:

a Granule that represent the given granule converted to the given granularity

Throws:

CalendricSystemServiceException - if either the Granularity of the given granule or the toGranularity are not recognized by the lattice (i.e., there is no node in the lattice that has this granularity)

findPath

private java.util.ArrayList findPath(Granularity sourceGranularity,
                                     Granularity destGranularity)
                              throws CalendricSystemServiceException

Finds a path (made up of Mapping objects) that can be used to convert the given source granularity to the destination granularity. This method works by first finding all shortest paths between the source granularity and all other granularities. If after this step, a path has been found from the source granularity to the destination granularity, the mapping path is built and returned. However, if no shortest path has been found, all shortest paths between the destination granularity and all other granularities is found. With these two lists of shortest paths, the greatest common granularity from which both the source and destination granularities can be reached is found and a V-path is built.

Parameters:

sourceGranularity - the starting granularity

destGranularity - the destination granularity

Returns:

the list of mappings that can be used to convert from the source granularity to the destination granularity

Throws:

CalendricSystemServiceException - if either the Granularity of the given granule or the destGranularity are not recognized by the lattice (i.e., there is no node in the lattice that has this granularity)

getSpTable

private java.util.HashMap getSpTable(GranularityLattice.LatticeNode s,
                                     int typeOfEdges)

Returns a table of shortest path information for the given node and type (i.e. coarser/finer). First the caches are checked for a match then if no match is found in the cache Djikstra's algorithm is used to calculate the shortest path information.

Parameters:

s - the node for which to get shortest path information

typeOfEdges - the type of edges (FINER/COARSER/CONGRUENT) to use to get the shortest path information

Returns:

a table that maps granularities -> (predecessors, cost to reach source)

getSuccessors

private tauzaman.calendricsystem.granularitylattice.minpriorityqueue.MinPriorityQueue getSuccessors(GranularityLattice.LatticeNode node,
                                                                                                    int typeOfEdges)

Returns a minimum priority queue of nodes that are reachable by the given node through the given type of edges (i.e. coarser/finer). The minimum priority queue is organized according to closest --> furthest nodes away from the given node. This serves as a "sorted" list of successors from the given node.

Parameters:

node - the node for which to get successor information

typeOfEdges - the type of edges (FINER/COARSER/CONGRUENT) to use to get the successor information

Returns:

minimum priority queue that contains all reachable nodes from closest --> furthest

printSpTable

private void printSpTable(java.util.HashMap preds)

Helper method used to debug findPath by printing out predecessor lists.

Parameters:

preds - the hash of predecessors for a particular granularity

isCoarser

public boolean isCoarser(Granularity g1,
                         Granularity g2)
                  throws CalendricSystemServiceException

Uses the lattice to determine if one granularity is coarser than another.

Parameters:

g1 - the first granule to be compared

g2 - the second granule to be compared

Returns:

true if g1 is coarser than g2, false if g1 is finer than g2 or if g1 and g2 cannot be compared

Throws:

NoSuchGranularityException - if either of the granularities passed in are not recognized by the lattice (i.e., there is no node in the lattice that has this granularity)

CalendricSystemServiceException

isEquivalent

public boolean isEquivalent(Granularity g1,
                            Granularity g2)
                     throws CalendricSystemServiceException

Uses the lattice to determine if the two granularities are equivalent.

Parameters:

g1 - the first granule to be compared for equivalence

g2 - the second granule to be compared for equivalence

Returns:

true if g1 is equivalent to g2, false if g1 is not equivalent to g2

Throws:

NoSuchGranularityException - if either of the granularities passed in are not recognized by the lattice (i.e., there is no node in the lattice that has this granularity)

CalendricSystemServiceException

isIncomparable

public boolean isIncomparable(Granularity g1,
                              Granularity g2)
                       throws CalendricSystemServiceException

Uses the lattice to determine if the two granularities are equivalent.

Parameters:

g1 - the first granule to be compared for equivalence

g2 - the second granule to be compared for equivalence

Returns:

true if g1 is equivalent to g2, false if g1 is not equivalent to g2

Throws:

NoSuchGranularityException - if either of the granularities passed in are not recognized by the lattice (i.e., there is no node in the lattice that has this granularity)

CalendricSystemServiceException

isFiner

public boolean isFiner(Granularity g1,
                       Granularity g2)
                throws CalendricSystemServiceException

Uses the lattice to determine if one granularity is finer than another.

Parameters:

g1 - the first granule to be compared

g2 - the second granule to be compared

Returns:

true if g1 is finer than g2, false if g1 is coarser than g2 or if g1 and g2 cannot be compared

Throws:

NoSuchGranularityException - if either of the granularities passed in are not recognized by the lattice (i.e., there is no node in the lattice that has this granularity)

CalendricSystemServiceException

clearCaches

public void clearCaches()

Resets all of the lattice's caches.

toString

public java.lang.String toString()

Returns a string representation of the lattice.

Overrides:

toString in class java.lang.Object

Returns:

a String representation of the lattice.

induceMappings

private void induceMappings()

Induces all regular mappings in the sets of coarser, finer and congruent edges in the lattice.

induceMappings

private void induceMappings(int typeOfEdges)

Performs a DFS search on each node looking for regular mappings that can be induced.

Parameters:

typeOfEdges - the type of edges (FINER/COARSER/CONGRUENT) from which the regular mappings should be induced

induceMappingsDFSVisit

private void induceMappingsDFSVisit(GranularityLattice.LatticeNode sourceNode,
                                    GranularityLattice.LatticeEdge sourceEdge,
                                    GranularityLattice.LatticeNode curNode,
                                    int typeOfEdges,
                                    java.util.HashMap colorTable)

Recursive helper to the DFS part of the mapping induction. Visits all reachable nodes from the given node.

Parameters:

typeOfEdges - the relationship we want to do the sort on (FINER/ COARSER/CONGRUENT)

dijkstraShortestPaths

private java.util.HashMap dijkstraShortestPaths(GranularityLattice.LatticeNode s,
                                                int typeOfEdges)

Using Djikstra's algorithm, computes all shortest paths starting from a given lattice node.

Parameters:

s - the node from which we want all shortest paths in the lattice

typeOfEdges - the relationship from which we want to find the shortest path on (FINER/COARSER/CONGRUENT)

Returns:

a table containing all shortest path information in the form of [LatticeNode --> (predecessor, cost to source)]

initializeSingleSource

private void initializeSingleSource(GranularityLattice.LatticeNode s,
                                    java.util.HashMap spTable)

Initializes the data structures used in Djiksta's algorithm. The shortest path estimation table begins with all the estimates being infinity. The predecessor table begins with all entries' predecessors being null. Then the source node's estimation starts at 0.

Parameters:

s - the node from which we want all shortest paths in the lattice

spTable - the table that maps [node --> sp est, predecessor in shortest path to source]

relax

private void relax(GranularityLattice.LatticeNode u,
                   GranularityLattice.LatticeNode v,
                   int w,
                   java.util.HashMap spTable,
                   tauzaman.calendricsystem.granularitylattice.minpriorityqueue.MinPriorityQueue Q)

Tests whether or not we can improve the shortest path to v found so far by going through u, and, if so, updating the shortest path estimation table and the predecessor table.

Parameters:

u - the new node that we can now use to get a shortest path

v - the destination node of relaxation process

w - the weight of the edge between u and v

spTable - the table that maps [node --> sp est, predecessor in shortest path to source]

Q - the minimum priority queue that is used in Djiksta's algorithm - needed in this method to decrease priority of v if path is improved

buildMappingPath

private java.util.ArrayList buildMappingPath(java.util.HashMap spTable,
                                             GranularityLattice.LatticeNode s,
                                             GranularityLattice.LatticeNode v,
                                             int typeOfEdges)

Given a particular predecessor list, builds a mapping path between two nodes.

Parameters:

spTable - the predecessor list composing ests. & shortest paths

s - the source node

v - the destination node

typeOfEdges - the relationship from which we want to build the path (FINER/COARSER/CONGRUENT)

Returns:

a list of mappings to follow to convert from s to v

buildPathHelper

private void buildPathHelper(java.util.HashMap spTable,
                             GranularityLattice.LatticeNode s,
                             GranularityLattice.LatticeNode v,
                             java.util.ArrayList path)

Recursive helper method used to build the mapping path.

Parameters:

spTable - the predecessor list composing ests. & shortest paths

s - the source node

v - the destination node

path - the path being built