RepositionCache.java
/*
** Module : RepositionCache.java
** Abstract : Cache used for quick repositioning by primary key IDs
**
** Copyright (c) 2006-2023, Golden Code Development Corporation.
**
** -#- -I- --Date-- --JPRM-- ------------------Description---------------------------------------
** 001 ECF 20061203 @31562 Created initial version. Cache used for quick
** repositioning by primary key IDs.
** 002 ECF 20090306 @42976 Added debugging features. Implemented toString()
** methods at the cache and node levels.
** 003 SVL 20141015 Added ability to remove entries.
** 004 SVL 20191218 For a partial match (number of provided IDs is less than the number
** of query tables) the *last* row in the subset is returned.
** 005 AL2 20230608 Lazily initialize the children of each node.
*/
/*
** 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 may find a copy of the GNU Affero GPL version 3 at the following
** location: https://www.gnu.org/licenses/agpl-3.0.en.html
**
** Additional terms under GNU Affero GPL version 3 section 7:
**
** Under Section 7 of the GNU Affero GPL version 3, the following additional
** terms apply to the works covered under the License. These additional terms
** are non-permissive additional terms allowed under Section 7 of the GNU
** Affero GPL version 3 and may not be removed by you.
**
** 0. Attribution Requirement.
**
** You must preserve all legal notices or author attributions in the covered
** work or Appropriate Legal Notices displayed by works containing the covered
** work. You may not remove from the covered work any author or developer
** credit already included within the covered work.
**
** 1. No License To Use Trademarks.
**
** This license does not grant any license or rights to use the trademarks
** Golden Code, FWD, any Golden Code or FWD logo, or any other trademarks
** of Golden Code Development Corporation. You are not authorized to use the
** name Golden Code, FWD, or the names of any author or contributor, for
** publicity purposes without written authorization.
**
** 2. No Misrepresentation of Affiliation.
**
** You may not represent yourself as Golden Code Development Corporation or FWD.
**
** You may not represent yourself for publicity purposes as associated with
** Golden Code Development Corporation, FWD, or any author or contributor to
** the covered work, without written authorization.
**
** 3. No Misrepresentation of Source or Origin.
**
** You may not represent the covered work as solely your work. All modified
** versions of the covered work must be marked in a reasonable way to make it
** clear that the modified work is not originating from Golden Code Development
** Corporation or FWD. All modified versions must contain the notices of
** attribution required in this license.
*/
package com.goldencode.p2j.persist;
import java.io.*;
import java.util.*;
/**
* A cache which logically maps arrays of primary key IDs to query result set
* row numbers. An array of primary key IDs represents the IDs of joined
* database records in a virtual, composite record. Each ID array has one
* element per table involved in the join.
* <p>
* For fast lookup, entries are actually stored in a tree structure, where
* each node in the tree stores a single primary key ID and a result set row
* number. An individual node represents a record within a single table.
* Its children represent associated records in joined tables, and so on.
*/
final class RepositionCache
{
/** Root node which does not actually represent a record */
private Node root = new Node(null, null, -1);
/** Number of virtual record entries stored in the cache */
private int size = 0;
/**
* Default constructor.
*/
RepositionCache()
{
}
/**
* Produce a string representation of the cache, which dumps each node in
* the tree.
*
* @return String representation of the cache.
*/
public String toString()
{
StringBuilder buf = new StringBuilder();
buf.append(size);
buf.append(" entries");
if (size > 0)
{
buf.append(":\n");
dumpNode(0, root, buf);
}
return buf.toString();
}
/**
* Dump a string representation of the node into the given string builder.
* Recursively performs a depth-first iteration of the node's descendants.
*
* @param indent
* Number of characters to indent the current node's information
* in the string builder.
* @param node
* Node being visited and dumped.
* @param buf
* Target string builder.
*/
private void dumpNode(int indent, Node node, StringBuilder buf)
{
for (int i = 0; i < indent; i++)
{
buf.append(" ");
}
buf.append(node);
if (node.children != null)
{
Iterator<Node> iter = node.children.values().iterator();
while (iter.hasNext())
{
buf.append("\n");
Node child = iter.next();
dumpNode(indent + 1, child, buf);
}
}
}
/**
* Add a single entry to the cache.
*
* @param ids
* Array of primary keys which represent a virtual, joined row of
* results in the associated query's result set.
* @param row
* Zero-based index of the virtual row in the result set.
*/
void add(Serializable[] ids, int row)
{
Node next = root;
int len = ids.length;
for (int i = 0; i < len; i++)
{
Serializable id = ids[i];
Node child = next.findChild(id);
if (child == null)
{
child = new Node(next, id, row);
next.putChild(child);
if (i + 1 == len)
{
size++;
}
}
next = child;
}
}
/**
* Remove the single entry from the cache. For other entries which have associated row indexes
* greater than the deleted entry had, row indexes are decremented by 1.
*
* @param ids
* Array of primary keys which represent a virtual, joined row of results in the
* associated query's result set that should be deleted.
*
* @return <code>true</code> if the entry was deleted, <code>false</code> if there is no entry
* associated with the given IDs.
*/
boolean remove(Serializable[] ids)
{
Node next = root;
int len = ids.length;
for (int i = 0; next != null && i < len; i++)
{
next = next.findChild(ids[i]);
if (next != null && i == len - 1)
{
int row = next.getRow();
// delete the leaf and all parents with no leaves
while(next.getChildCount() == 0)
{
Node parent = next.getParent();
if (parent == null)
break;
parent.removeChild(next);
next = parent;
}
size--;
// decrement row number for all remaining leaves
decrementRowIndexes(root, row);
return true;
}
}
return false;
}
/**
* Retrieve the row number associated with the given array of primary key
* IDs. If the array contains fewer elements than there are tables in the
* virtual row of joined records in the associated query's result set, the
* first row which matches all of the given IDs for its outermost tables
* is returned. If more than one matching row exists, there is no
* guarantee as to which one will be returned.
*
* @param ids
* Array of primary keys which represent a virtual, joined row of
* results in the associated query's result set. This array may
* contain fewer elements than there are records represented by a
* virtual row in the result set; however, it may not be
* <code>null</code>.
*
* @return Zero-based row index associated with the given primary key
* IDs, or -1 if no match was found.
*/
int getRow(Serializable[] ids)
{
int row = -1;
Node next = root;
int len = ids.length;
for (int i = 0; next != null && i < len; i++)
{
next = next.findChild(ids[i]);
if (next != null)
{
row = next.getLastRow();
}
else
{
return -1;
}
}
return row;
}
/**
* Return the number of entries currently stored in the cache.
*
* @return Size of the cache.
*/
int size()
{
return size;
}
/**
* Clear all entries from the cache.
*/
void clear()
{
root = new Node(null, null, -1);
size = 0;
}
/**
* Decrement by 1 row indexes for all entries stored under the specified node which have row
* index greater than the specified lower limit.
*
* @param node
* Root node to be processed.
* @param lowerLimit
* Row numbers greater than this number will be decremented.
*/
private void decrementRowIndexes(Node node, int lowerLimit)
{
int row = node.getRow();
if (row > lowerLimit)
node.setRow(--row);
if (node.children != null)
{
for (Node child : node.children.values())
{
decrementRowIndexes(child, lowerLimit);
}
}
}
/**
* Internal data structure which represents a single record ID and an
* associated result set row index for the virtual, composite row
* containing that record. A node may contain child nodes, each of which
* represents a record in another table associated with the parent node's
* record via a database join.
*/
private static class Node
{
/** Primary key ID */
private final Serializable id;
/** Zero-based index of virtual result set row */
private int row;
/**
* Map of child nodes, indexed by their primary key IDs.
* Lazy set to avoid instantiating lots of empty maps.
*/
private Map<Serializable, Node> children = null;
/** Parent node. */
private final Node parent;
/**
* Constructor.
*
* @param parent
* Parent node or <code>null</code> if it is the root node.
* @param id
* Primary key ID.
* @param row
* Zero-based index of virtual result set row.
*/
Node(Node parent, Serializable id, int row)
{
this.parent = parent;
this.id = id;
this.row = row;
}
/**
* Produce a string representation of the node, which includes the
* primary key and associated row number.
*
* @return String representation of the node.
*/
public String toString()
{
StringBuilder buf = new StringBuilder("id#");
buf.append(id);
buf.append("-->row#");
buf.append(row);
return buf.toString();
}
/**
* Get the row index associated with this node.
*
* @return Zero-based row index.
*/
int getRow()
{
return row;
}
/**
* Get the index of the last child row parented by this node. If there are no children,
* the row index associated with this node is returned.
*
* @return Zero-based index of the last child row.
*/
int getLastRow()
{
if (children != null && children.size() > 0)
{
Iterator<Node> iter = children.values().iterator();
Node lastChild;
do
{
lastChild = iter.next();
}
while (iter.hasNext());
return lastChild.getLastRow();
}
return getRow();
}
/**
* Set the row index associated with this node.
*
* @param row
* Row index associated with this node.
*/
public void setRow(int row)
{
this.row = row;
}
/**
* Add a child node representing a record associated with this node's
* record by a database (right) join. The child is mapped by its
* primary key ID.
*
* @param child
* Node to add to this node's children.
*/
void putChild(Node child)
{
if (children == null)
{
children = new LinkedHashMap<>();
}
children.put(child.id, child);
}
/**
* Find the child node associated with the given primary key ID.
*
* @param id
* Primary key of child node's record.
*
* @return Child node, or <code>null</code> if none exists.
*/
Node findChild(Serializable id)
{
return children == null ? null : children.get(id);
}
/**
* Remove the specified child node,
*
* @param child
* Child node to remove,
*/
void removeChild(Node child)
{
if (children != null)
{
children.remove(child.id);
}
}
/**
* Get the number of children.
*
* @return number of children.
*/
int getChildCount()
{
return children == null ? 0 : children.size();
}
/**
* Get parent node.
*
* @return parent node.
*/
Node getParent()
{
return parent;
}
}
}