SinglyLinkedNode.java

  1. package org.drip.spaces.graph;

  3. /*
  4.  * -*- mode: java; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
  5.  */

  7. /*!
  8.  * Copyright (C) 2020 Lakshmi Krishnamurthy
  9.  * Copyright (C) 2019 Lakshmi Krishnamurthy
  10.  * Copyright (C) 2018 Lakshmi Krishnamurthy
  11.  * 
  12.  *  This file is part of DROP, an open-source library targeting analytics/risk, transaction cost analytics,
  13.  *      asset liability management analytics, capital, exposure, and margin analytics, valuation adjustment
  14.  *      analytics, and portfolio construction analytics within and across fixed income, credit, commodity,
  15.  *      equity, FX, and structured products. It also includes auxiliary libraries for algorithm support,
  16.  *      numerical analysis, numerical optimization, spline builder, model validation, statistical learning,
  17.  *      and computational support.
  18.  *  
  19.  *      https://lakshmidrip.github.io/DROP/
  20.  *  
  21.  *  DROP is composed of three modules:
  22.  *  
  23.  *  - DROP Product Core - https://lakshmidrip.github.io/DROP-Product-Core/
  24.  *  - DROP Portfolio Core - https://lakshmidrip.github.io/DROP-Portfolio-Core/
  25.  *  - DROP Computational Core - https://lakshmidrip.github.io/DROP-Computational-Core/
  26.  * 
  27.  *  DROP Product Core implements libraries for the following:
  28.  *  - Fixed Income Analytics
  29.  *  - Loan Analytics
  30.  *  - Transaction Cost Analytics
  31.  * 
  32.  *  DROP Portfolio Core implements libraries for the following:
  33.  *  - Asset Allocation Analytics
  34.  *  - Asset Liability Management Analytics
  35.  *  - Capital Estimation Analytics
  36.  *  - Exposure Analytics
  37.  *  - Margin Analytics
  38.  *  - XVA Analytics
  39.  * 
  40.  *  DROP Computational Core implements libraries for the following:
  41.  *  - Algorithm Support
  42.  *  - Computation Support
  43.  *  - Function Analysis
  44.  *  - Model Validation
  45.  *  - Numerical Analysis
  46.  *  - Numerical Optimizer
  47.  *  - Spline Builder
  48.  *  - Statistical Learning
  49.  * 
  50.  *  Documentation for DROP is Spread Over:
  51.  * 
  52.  *  - Main                     => https://lakshmidrip.github.io/DROP/
  53.  *  - Wiki                     => https://github.com/lakshmiDRIP/DROP/wiki
  54.  *  - GitHub                   => https://github.com/lakshmiDRIP/DROP
  55.  *  - Repo Layout Taxonomy     => https://github.com/lakshmiDRIP/DROP/blob/master/Taxonomy.md
  56.  *  - Javadoc                  => https://lakshmidrip.github.io/DROP/Javadoc/index.html
  57.  *  - Technical Specifications => https://github.com/lakshmiDRIP/DROP/tree/master/Docs/Internal
  58.  *  - Release Versions         => https://lakshmidrip.github.io/DROP/version.html
  59.  *  - Community Credits        => https://lakshmidrip.github.io/DROP/credits.html
  60.  *  - Issues Catalog           => https://github.com/lakshmiDRIP/DROP/issues
  61.  *  - JUnit                    => https://lakshmidrip.github.io/DROP/junit/index.html
  62.  *  - Jacoco                   => https://lakshmidrip.github.io/DROP/jacoco/index.html
  63.  * 
  64.  *  Licensed under the Apache License, Version 2.0 (the "License");
  65.  *      you may not use this file except in compliance with the License.
  66.  *   
  67.  *  You may obtain a copy of the License at
  68.  *      http://www.apache.org/licenses/LICENSE-2.0
  69.  *  
  70.  *  Unless required by applicable law or agreed to in writing, software
  71.  *      distributed under the License is distributed on an "AS IS" BASIS,
  72.  *      WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  73.  *  
  74.  *  See the License for the specific language governing permissions and
  75.  *      limitations under the License.
  76.  */

  78. /**
  79.  * <i>SinglyLinkedNode</i> implements the Node behind a Singly Linked List. The References are:
  80.  *
  81.  * <br><br>
  82.  *  <ul>
  83.  *      <li>
  84.  *          Knuth, D. (1973): <i>The Art of Computer Programming</i> <b>Addison-Wesley</b>
  85.  *      </li>
  86.  *      <li>
  87.  *          Oracle (2018): LinkedList (Java Platform SE 7)
  88.  *              https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html
  89.  *      </li>
  90.  *      <li>
  91.  *          Wikipedia (2018a): Linked List https://en.wikipedia.org/wiki/Linked_list
  92.  *      </li>
  93.  *      <li>
  94.  *          Wikipedia (2018b): Doubly Linked List https://en.wikipedia.org/wiki/Doubly_linked_list
  95.  *      </li>
  96.  *      <li>
  97.  *          Wikipedia (2018c): Linked Data Structure https://en.wikipedia.org/wiki/Linked_data_structure
  98.  *      </li>
  99.  *  </ul>
  100.  *
  101.  * <br><br>
  102.  *  <ul>
  103.  *      <li><b>Module </b> = <a href = "https://github.com/lakshmiDRIP/DROP/tree/master/ComputationalCore.md">Computational Core Module</a></li>
  104.  *      <li><b>Library</b> = <a href = "https://github.com/lakshmiDRIP/DROP/tree/master/StatisticalLearningLibrary.md">Statistical Learning Library</a></li>
  105.  *      <li><b>Project</b> = <a href = "https://github.com/lakshmiDRIP/DROP/tree/master/src/main/java/org/drip/spaces/README.md">R<sup>1</sup> and R<sup>d</sup> Vector/Tensor Spaces (Validated and/or Normed), and Function Classes</a></li>
  106.  *      <li><b>Package</b> = <a href = "https://github.com/lakshmiDRIP/DROP/tree/master/src/main/java/org/drip/spaces/graph/README.md">Graph Representation and Traversal Algorithms</a></li>
  107.  *  </ul>
  108.  * <br><br>
  109.  *
  110.  * @author Lakshmi Krishnamurthy
  111.  */

  113. public class SinglyLinkedNode
  114. {
  115.     private SinglyLinkedNode _tail = null;
  116.     private SinglyLinkedNode _adjacent = null;
  117.     private double _value = java.lang.Double.NaN;

  119.     /**
  120.      * Generate a FIFO Linked List from the Value Array
  121.      * 
  122.      * @param valueArray The Value Array
  123.      * 
  124.      * @return The FIFO Linked List
  125.      */

  127.     public static final SinglyLinkedNode FIFOListFromArray (
  128.         final double[] valueArray)
  129.     {
  130.         if (null == valueArray)
  131.         {
  132.             return null;
  133.         }

  135.         SinglyLinkedNode singlyLinkedNode = null;
  136.         int arraySize = valueArray.length;

  138.         if (0 == arraySize)
  139.         {
  140.             return null;
  141.         }

  143.         try
  144.         {
  145.             for (int valueIndex = 0; valueIndex < arraySize; ++valueIndex)
  146.             {
  147.                 if (null == singlyLinkedNode)
  148.                 {
  149.                     singlyLinkedNode = new SinglyLinkedNode (
  150.                         valueArray[valueIndex],
  151.                         null
  152.                     );
  153.                 }
  154.                 else
  155.                 {
  156.                     if (null == singlyLinkedNode.addToTail (
  157.                         new SinglyLinkedNode (
  158.                             valueArray[valueIndex],
  159.                             null
  160.                         )
  161.                     ))
  162.                     {
  163.                         return null;
  164.                     }
  165.                 }
  166.             }
  167.         }
  168.         catch (java.lang.Exception e)
  169.         {
  170.             e.printStackTrace();
  171.         }

  173.         return null;
  174.     }

  176.     /**
  177.      * Generate a LIFO Linked List from the Value Array
  178.      * 
  179.      * @param valueArray The Value Array
  180.      * 
  181.      * @return The LIFO Linked List
  182.      */

  184.     public static final SinglyLinkedNode lIFOListFromArray (
  185.         final double[] valueArray)
  186.     {
  187.         if (null == valueArray)
  188.         {
  189.             return null;
  190.         }

  192.         SinglyLinkedNode singlyLinkedNode = null;
  193.         int arraySize = valueArray.length;

  195.         if (0 == arraySize)
  196.         {
  197.             return null;
  198.         }

  200.         try
  201.         {
  202.             for (int valueIndex = 0; valueIndex < arraySize; ++valueIndex)
  203.             {
  204.                 if (null == singlyLinkedNode)
  205.                 {
  206.                     singlyLinkedNode = new SinglyLinkedNode (
  207.                         valueArray[valueIndex],
  208.                         null
  209.                     );
  210.                 }
  211.                 else
  212.                 {
  213.                     if (null == singlyLinkedNode.addToHead (
  214.                         new SinglyLinkedNode (
  215.                             valueArray[valueIndex],
  216.                             null
  217.                         )
  218.                     ))
  219.                     {
  220.                         return null;
  221.                     }
  222.                 }
  223.             }
  224.         }
  225.         catch (java.lang.Exception e)
  226.         {
  227.             e.printStackTrace();
  228.         }

  230.         return null;
  231.     }

  233.     /**
  234.      * SinglyLinkedNode Constructor
  235.      * 
  236.      * @param value The Linked Node Value
  237.      * @param adjacent The Adjacent Node
  238.      * 
  239.      * @throws java.lang.Exception Thrown if the Inputs are Invalid
  240.      */

  242.     public SinglyLinkedNode (
  243.         final double value,
  244.         final SinglyLinkedNode adjacent)
  245.         throws java.lang.Exception
  246.     {
  247.         if (!org.drip.numerical.common.NumberUtil.IsValid (_value = value))
  248.         {
  249.             throw new java.lang.Exception ("SinglyLinkedNodeConstructor => Invalid Inputs");
  250.         }

  252.         _adjacent = adjacent;
  253.         _tail = this;
  254.     }

  256.     /**
  257.      * Retrieve the Linked Node Value
  258.      * 
  259.      * @return The Linked Node Value
  260.      */

  262.     public double value()
  263.     {
  264.         return _value;
  265.     }

  267.     /**
  268.      * Retrieve the Adjacent Node
  269.      * 
  270.      * @return The Adjacent Node
  271.      */

  273.     public SinglyLinkedNode adjacent()
  274.     {
  275.         return _adjacent;
  276.     }

  278.     /**
  279.      * Retrieve the Head Node
  280.      * 
  281.      * @return The Head Node
  282.      */

  284.     public SinglyLinkedNode head()
  285.     {
  286.         return this;
  287.     }

  289.     /**
  290.      * Retrieve the Tail Node
  291.      * 
  292.      * @return The Tail Node
  293.      */

  295.     public SinglyLinkedNode tail()
  296.     {
  297.         return _tail;
  298.     }

  300.     /**
  301.      * Append "This" to the Tail of the "Other"
  302.      * 
  303.      * @param otherList The "Other"
  304.      * 
  305.      * @return Appending/Addition successfully done
  306.      */

  308.     public SinglyLinkedNode addToHead (
  309.         final SinglyLinkedNode otherList)
  310.     {
  311.         if (null == otherList)
  312.         {
  313.             return null;
  314.         }

  316.         SinglyLinkedNode otherTail = otherList.tail();

  318.         otherTail._tail = this;
  319.         return otherTail;
  320.     }

  322.     /**
  323.      * Add "Other" to the Tail of "This"
  324.      * 
  325.      * @param otherList The "Other"
  326.      * 
  327.      * @return Appending/Addition successfully done
  328.      */

  330.     public SinglyLinkedNode addToTail (
  331.         final SinglyLinkedNode otherList)
  332.     {
  333.         _tail = otherList;
  334.         return this;
  335.     }

  337.     /**
  338.      * Locate the Node that contains the specified Value
  339.      * 
  340.      * @param value The Value to Search for
  341.      * 
  342.      * @return The Node
  343.      */

  345.     public SinglyLinkedNode locate (
  346.         final double value)
  347.     {
  348.         if (!org.drip.numerical.common.NumberUtil.IsValid (value))
  349.         {
  350.             return null;
  351.         }

  353.         SinglyLinkedNode node = this;

  355.         while (null != node)
  356.         {
  357.             if (node.value() == value)
  358.             {
  359.                 return node;
  360.             }

  362.             node = node.adjacent();
  363.         }

  365.         return null;
  366.     }

  368.     /**
  369.      * Check if the Node that containing the specified Value Exists
  370.      * 
  371.      * @param value The Value to Check for
  372.      * 
  373.      * @return TRUE - The Node Exists
  374.      */

  376.     public boolean containsValue (
  377.         final double value)
  378.     {
  379.         if (!org.drip.numerical.common.NumberUtil.IsValid (value))
  380.         {
  381.             return false;
  382.         }

  384.         SinglyLinkedNode node = this;

  386.         while (null != node)
  387.         {
  388.             if (node.value() == value)
  389.             {
  390.                 return true;
  391.             }

  393.             node = node.adjacent();
  394.         }

  396.         return false;
  397.     }

  399.     /**
  400.      * Insert the given Value after the Specified Location Node
  401.      * 
  402.      * @param locationNodeValue The Location Node's Value
  403.      * @param insertionNodeValue The Value to be inserted
  404.      * 
  405.      * @return TRUE - The Value was successfully inserted
  406.      */

  408.     public boolean insertAfter (
  409.         final double locationNodeValue,
  410.         final double insertionNodeValue)
  411.     {
  412.         if (!org.drip.numerical.common.NumberUtil.IsValid (locationNodeValue) ||
  413.             !org.drip.numerical.common.NumberUtil.IsValid (insertionNodeValue))
  414.         {
  415.             return false;
  416.         }

  418.         SinglyLinkedNode locationNode = locate (locationNodeValue);

  420.         if (null == locationNode)
  421.         {
  422.             return false;
  423.         }

  425.         SinglyLinkedNode locationNodeAdjacent = locationNode.adjacent();

  427.         try
  428.         {
  429.             locationNode._adjacent = new SinglyLinkedNode (
  430.                 insertionNodeValue,
  431.                 locationNodeAdjacent
  432.             );
  433.         }
  434.         catch (java.lang.Exception e)
  435.         {
  436.             e.printStackTrace();

  438.             return false;
  439.         }

  441.         return true;
  442.     }

  444.     /**
  445.      * Remove the Node at the specified Value
  446.      * 
  447.      * @param removalNodeValue The Node to be removed
  448.      * 
  449.      * @return The "Removed"
  450.      */

  452.     public SinglyLinkedNode removeAt (
  453.         final double removalNodeValue)
  454.     {
  455.         if (!org.drip.numerical.common.NumberUtil.IsValid (removalNodeValue))
  456.         {
  457.             return null;
  458.         }

  460.         boolean nodeFound = false;
  461.         SinglyLinkedNode priorNode = null;
  462.         SinglyLinkedNode currentNode = this;

  464.         while (null != currentNode)
  465.         {
  466.             if (currentNode.value() == removalNodeValue)
  467.             {
  468.                 nodeFound = true;
  469.                 break;
  470.             }

  472.             priorNode = currentNode;

  474.             currentNode = currentNode.adjacent();
  475.         }

  477.         if (!nodeFound)
  478.         {
  479.             return null;
  480.         }

  482.         if (null == priorNode)
  483.         {
  484.             try
  485.             {
  486.                 return addToHead (
  487.                     new SinglyLinkedNode (
  488.                         removalNodeValue,
  489.                         currentNode.adjacent()
  490.                     )
  491.                 );
  492.             }
  493.             catch (java.lang.Exception e)
  494.             {
  495.                 e.printStackTrace();
  496.             }

  498.             return null;
  499.         }

  501.         try
  502.         {
  503.             priorNode._adjacent = new SinglyLinkedNode (
  504.                 removalNodeValue,
  505.                 currentNode.adjacent()
  506.             );
  507.         }
  508.         catch (java.lang.Exception e)
  509.         {
  510.             e.printStackTrace();

  512.             return null;
  513.         }

  515.         return this;
  516.     }

  518.     /**
  519.      * Convert the Linked List to an Array List
  520.      * 
  521.      * @return The Array List
  522.      */

  524.     public java.util.List<java.lang.Double> toList()
  525.     {
  526.         java.util.List<java.lang.Double> valueList = new java.util.ArrayList<java.lang.Double>();

  528.         SinglyLinkedNode node = this;

  530.         while (null != node)
  531.         {
  532.             valueList.add (node.value());

  534.             node = node.adjacent();
  535.         }

  537.         return valueList;
  538.     }
  539. }
Created with JaCoCo 0.7.9.201702052155