Package io.crums.util.mrkl.index

Class TreeIndex<N extends AbstractNode>

java.lang.Object
io.crums.util.mrkl.index.TreeIndex<N>
public class TreeIndex<N extends AbstractNode>
extends java.lang.Object
A breadth-first view of the structure of a Merkle tree. In this view each node is represented by 2 coordinates (level, index). Levels are counted up from the leaf nodes, with the leaves at level zero; index is just an index into nodes at that level. Instances are immutable and safe under concurrent access.

Terminology

Most expositions use the term "promoted" to describe how the last odd node at a level is stitched up the higher node levels to root. (Note in our zero-based index, the index of this last odd node is in fact even; the count is odd.) Here, we use the term carry to represent this special type of joining of two lower level nodes to form a higher level parent. Except for the edge case involving such carries, a node's children are always at adjacent indices at the level just below; for carries, however, a node's children may be from different levels (with the left child always at the same or higher level than the right child).

  • Carry. The parent node formed from 2 child nodes at different levels, or a parent node formed if one or more of its descendants have been so formed. There can only be one such node at any level, and then it may only be the node at the last index at that level. Another way to think of a carry is an existing node whose value would necessarily change if another (single) leaf node had been added.
  • Joins Carry. A child node of a carry. The child node itself may or may not be a carry.

Note, the root node is itself usually a carry. The only times it's not is when the number of leaves is an exact power of 2 in which case there are no carries in the tree. Conversely, if a node is a carry, then every ancestor of it (including the root node), every is another carry.

See Also:
AbstractNode

  • Nested Class Summary

    Nested Classes
    Modifier and Type Class Description
    static interface  TreeIndex.NodeFactory<N extends AbstractNode>  

  • Constructor Summary

    Constructors
    Constructor Description
    TreeIndex​(int count, TreeIndex.NodeFactory<N> factory)  

  • Method Summary

    Modifier and Type Method Description
    int count()
    Returns the number leaf nodes (data items) in the tree.
    int count​(int level)
    Returns the number of nodes at the given level.
    int countSansCarry​(int level)
    Returns the numbern of nodes at the given level excluding the carry (if it has one).
    boolean equals​(java.lang.Object o)
    Determines whether an instance is structurally equivalent to another.
    java.util.List<N> getFrontier()
    Returns the frontier nodes.
    N getLeftChild​(int level, int index)  
    N getLeftChild​(AbstractNode parent)  
    N getNode​(int serialIndex)  
    N getNode​(int level, int index)  
    N getParent​(int level, int index)  
    N getParent​(AbstractNode node)
    Convenience method.
    N getRightChild​(int level, int index)  
    N getRightChild​(AbstractNode parent)  
    N getSibling​(int level, int index)  
    N getSibling​(AbstractNode node)
    Convenience method.
    boolean hasCarry​(int level)
    Determines whether the last node is a carry.
    int hashCode()  
    int height()
    Returns the height of the root of the tree relative to its base (the leaves).
    boolean isCarry​(int level, int index)
    Determines whether node at the given coordinates is a carry.
    boolean isLeft​(int level, int index)
    Determines if the node at the given coordinates is the left child of its parent node.
    boolean isRight​(int level, int index)
    Determines if the node at the given coordinates is the right child of its parent node.
    boolean isRoot​(AbstractNode node)  
    int maxIndex​(int level)
    Returns the maximum allowed index at the given level.
    boolean maxIndexJoinsCarry​(int level)  
    static TreeIndex<?> newGeneric​(int count)  
    static int rootHeightForCount​(int count)
    Returns the height of the Merkle tree root node with count-many leaf elements.
    int serialIndex​(int level, int index)  
    java.lang.String toString()  
    int totalCarries()
    Returns the total number of carries (otherwise known as promoted nodes).
    int totalCount()
    Returns the total number of nodes in the tree.
    int totalCountSansCarries()
    Returns the total number of nodes in the tree excluding the carries.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

  • Method Details

    • newGeneric

      public static TreeIndex<?> newGeneric​(int count)

    • count

      public final int count()
      Returns the number leaf nodes (data items) in the tree.

    • totalCount

      public final int totalCount()
      Returns the total number of nodes in the tree.
      Returns:
      2 * count() - 1

    • totalCarries

      public final int totalCarries()
      Returns the total number of carries (otherwise known as promoted nodes).

    • totalCountSansCarries

      public final int totalCountSansCarries()
      Returns the total number of nodes in the tree excluding the carries.
      Returns:
      the difference of totalCount() and totalCarries()

    • serialIndex

      public final int serialIndex​(int level, int index) throws java.lang.IndexOutOfBoundsException
      Throws:
      java.lang.IndexOutOfBoundsException

    • height

      public final int height()
      Returns the height of the root of the tree relative to its base (the leaves). In this terminology, the leaves are at level zero, and the root is at the level with maximum height.
      See Also:
      rootHeightForCount(int)

    • count

      public final int count​(int level) throws java.lang.IndexOutOfBoundsException
      Returns the number of nodes at the given level.
      Throws:
      java.lang.IndexOutOfBoundsException

    • countSansCarry

      public final int countSansCarry​(int level)
      Returns the numbern of nodes at the given level excluding the carry (if it has one).

    • maxIndex

      public final int maxIndex​(int level) throws java.lang.IndexOutOfBoundsException
      Returns the maximum allowed index at the given level.
      Returns:
      count(level) - 1
      Throws:
      java.lang.IndexOutOfBoundsException

    • maxIndexJoinsCarry

      public final boolean maxIndexJoinsCarry​(int level) throws java.lang.IndexOutOfBoundsException
      Throws:
      java.lang.IndexOutOfBoundsException

    • hasCarry

      public final boolean hasCarry​(int level) throws java.lang.IndexOutOfBoundsException
      Determines whether the last node is a carry. There is at most one carry in each level.
      Throws:
      java.lang.IndexOutOfBoundsException

    • isCarry

      public final boolean isCarry​(int level, int index)
      Determines whether node at the given coordinates is a carry.
      Parameters:
      level -
      index -
      Returns:

    • isRoot

      public final boolean isRoot​(AbstractNode node)

    • getNode

      public final N getNode​(int level, int index) throws java.lang.IndexOutOfBoundsException
      Throws:
      java.lang.IndexOutOfBoundsException

    • getNode

      public final N getNode​(int serialIndex) throws java.lang.IndexOutOfBoundsException
      Throws:
      java.lang.IndexOutOfBoundsException

    • getParent

      public final N getParent​(AbstractNode node) throws java.lang.IndexOutOfBoundsException
      Convenience method.
      Throws:
      java.lang.IndexOutOfBoundsException
      See Also:
      getParent(int, int)

    • getParent

      public final N getParent​(int level, int index) throws java.lang.IndexOutOfBoundsException
      Throws:
      java.lang.IndexOutOfBoundsException

    • getLeftChild

      public final N getLeftChild​(AbstractNode parent) throws java.lang.IndexOutOfBoundsException
      Throws:
      java.lang.IndexOutOfBoundsException

    • getLeftChild

      public final N getLeftChild​(int level, int index) throws java.lang.IndexOutOfBoundsException
      Throws:
      java.lang.IndexOutOfBoundsException

    • getRightChild

      public final N getRightChild​(AbstractNode parent) throws java.lang.IndexOutOfBoundsException
      Throws:
      java.lang.IndexOutOfBoundsException

    • getRightChild

      public final N getRightChild​(int level, int index) throws java.lang.IndexOutOfBoundsException
      Throws:
      java.lang.IndexOutOfBoundsException

    • getSibling

      public final N getSibling​(AbstractNode node) throws java.lang.IndexOutOfBoundsException
      Convenience method.
      Throws:
      java.lang.IndexOutOfBoundsException
      See Also:
      getSibling(int, int)

    • getSibling

      public final N getSibling​(int level, int index) throws java.lang.IndexOutOfBoundsException
      Parameters:
      level - 0 ≤ level < height()
      index - 0 ≤ index < count(level)
      Throws:
      java.lang.IndexOutOfBoundsException

    • isRight

      public final boolean isRight​(int level, int index) throws java.lang.IndexOutOfBoundsException
      Determines if the node at the given coordinates is the right child of its parent node. The root level is defined to be left (tho, in principle, it should be undefined).
      Parameters:
      level - between zero and height() (inclusive)
      index - the zero-based node index at the given level
      Throws:
      java.lang.IndexOutOfBoundsException
      See Also:
      maxIndex(int)

    • isLeft

      public final boolean isLeft​(int level, int index) throws java.lang.IndexOutOfBoundsException
      Determines if the node at the given coordinates is the left child of its parent node. The root level is defined to be left (tho, in principle, it should be undefined).
      Parameters:
      level - between zero and height() (inclusive)
      index - the zero-based node index at the given level
      Throws:
      java.lang.IndexOutOfBoundsException
      See Also:
      maxIndex(int), AbstractNode.isLeft()

    • getFrontier

      public final java.util.List<N> getFrontier()
      Returns the frontier nodes. If you grow this tree (that is if you append more leaves) then part of new tree will contain exactly the same nodes. Unused meta at this time.

    • equals

      public final boolean equals​(java.lang.Object o)
      Determines whether an instance is structurally equivalent to another. I.e. it doesn't care about individual node values. As we know, only 1 parameter determines the structure: the leaf count.
      Overrides:
      equals in class java.lang.Object

    • hashCode

      public final int hashCode()
      Overrides:
      hashCode in class java.lang.Object

    • toString

      public java.lang.String toString()
      Overrides:
      toString in class java.lang.Object

    • rootHeightForCount

      public static int rootHeightForCount​(int count) throws java.lang.IllegalArgumentException
      Returns the height of the Merkle tree root node with count-many leaf elements. (The height of the leaves is zero.)
      Parameters:
      count - ≥ 2
      Returns:
      ceil(log2(count)
      Throws:
      java.lang.IllegalArgumentException