Package com.jackmeng.stl

Class stl_Algos

java.lang.Object
com.jackmeng.stl.stl_Algos
public final class stl_Algos
extends java.lang.Object
A collection of algorithms implemented in Java.

This project aims to provide a general algorithm library for any Java Users (power or beginner).

Author:
Jack Meng

  • Nested Class Summary

    Nested Classes
    Modifier and Type Class Description
    private static class  stl_Algos.$freq_node_00  
    static class  stl_Algos.algos_Bias
    Bias -> Favor towards something.

  • Field Summary

    Fields
    Modifier and Type Field Description
    private static java.util.Random RNG0_1  

  • Constructor Summary

    Constructors
    Modifier Constructor Description
    private stl_Algos()  

  • Method Summary

    Modifier and Type Method Description
    private static <T> void $dfs_traverse0_1​(T node, java.util.Map<T,​java.util.List<T>> adjList, java.util.Set<T> visited, java.util.List<T> res)  
    private static <T extends java.lang.Comparable<T>>
    T    		 $floyd_rivest_select0_1​(java.util.List<T> list, int k)  
    private static void $huffman_table0_1​(stl_Algos.$freq_node_00 node, java.lang.String prefix, java.util.Map<java.lang.Character,​java.lang.String> table)  
    private static <T extends java.lang.Comparable<T>>
    T    		 $quick_select0_1​(T[] array, int left, int right, int k)  
    private static <T extends java.lang.Comparable<T>>
    int    		 $quick_select0_2​(T[] array, int left, int right, int pivot)  
    static <T extends java.lang.Comparable<T>>
    int    		 binary_search​(T[] toSearch, T target, stl_Algos.algos_Bias bias)
    Generic Biased Binary Search.
    static <T> T boyer_moore_vote​(T[] array)
    The Boyer-Moore majority vote algorithm is an algorithm that can be used to find the majority element in an array, if it exists.
    static <T> java.util.List<T> dfs_traverse​(T root, java.util.Map<T,​java.util.List<T>> adjList)  
    static <T extends java.lang.Comparable<T>>
    T    		 floyd_rivest_select​(T[] array, int k)  
    static java.util.Map<java.lang.Character,​java.lang.String> huffman_table​(java.lang.String text)  
    static double lagrange​(double[] x, double[] y, double x_input)  
    static double[] normalize​(double[] data)  
    static <T> java.util.List<T> optimal_eviction_policy​(java.util.List<T> accesses, int cache_sz)  
    static <T extends java.lang.Comparable<T>>
    T    		 quick_select​(T[] array, int k)  
    static <T> void swap​(T[] array, int i, int j)
    Generic Swap Element in array based on indices.

    Methods inherited from class java.lang.Object

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

  • Field Details

    • RNG0_1

      private static final java.util.Random RNG0_1

  • Constructor Details

    • stl_Algos

      private stl_Algos()

  • Method Details

    • normalize

      public static double[] normalize​(double[] data)

    • binary_search

      public static <T extends java.lang.Comparable<T>> int binary_search​(T[] toSearch, T target, stl_Algos.algos_Bias bias)
      Generic Biased Binary Search. If you wanted a regular Binary Search, you may use a package like Arrays or Collections.

      A biased binary search is a search algorithm that is biased towards one side of the input data. This means that it may have a higher probability of searching one side of the data before the other. This can occur if the algorithm is designed to prefer searching a certain side of the data or if the data itself is structured in such a way that one side is more likely to contain the target value. There are several possible reasons why an algorithm might be biased in this way. For example, the algorithm might be designed to take advantage of known patterns in the data, or it might be designed to optimize for certain types of searches. In some cases, a biased binary search may be more efficient than an unbiased search, but it can also lead to reduced performance if the bias is not appropriate for the data being searched.

      Type Parameters:
      T - A typed object extending comparable (Integer)
      Parameters:
      toSearch - Array of elements
      target - Element reference to find
      bias - Preferred Bias
      Returns:
      The index within toSearch
      See Also:
      stl_Algos.algos_Bias

    • huffman_table

      public static java.util.Map<java.lang.Character,​java.lang.String> huffman_table​(java.lang.String text)

    • boyer_moore_vote

      public static <T> T boyer_moore_vote​(T[] array)
      The Boyer-Moore majority vote algorithm is an algorithm that can be used to find the majority element in an array, if it exists. The majority element is defined as an element that occurs more than half of the time in the array. The algorithm works by maintaining a count of the current majority element and iterating through the array, updating the count as it goes. If the count ever reaches zero, the algorithm switches to considering the next element as the potential majority element and starts the count over again. When the algorithm reaches the end of the array, it checks the count to see if the current majority element is actually the true majority element. The Boyer-Moore majority vote algorithm has a worst-case time complexity of O(n), making it more efficient than other algorithms for finding the majority element, such as sorting the array and then scanning for the majority element, which has a time complexity of O(n log n). -> https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm
      Type Parameters:
      T - The type of the toSearch array
      Parameters:
      array - The array in question
      Returns:
      The end resultant reference

    • lagrange

      public static double lagrange​(double[] x, double[] y, double x_input)

    • optimal_eviction_policy

      public static <T> java.util.List<T> optimal_eviction_policy​(java.util.List<T> accesses, int cache_sz)

    • dfs_traverse

      public static <T> java.util.List<T> dfs_traverse​(T root, java.util.Map<T,​java.util.List<T>> adjList)

    • swap

      public static <T> void swap​(T[] array, int i, int j)
      Generic Swap Element in array based on indices.
      Type Parameters:
      T - The type of the array in question
      Parameters:
      array - The array of the elements
      i - The index of obj1
      j - The index of obj2

    • quick_select

      public static <T extends java.lang.Comparable<T>> T quick_select​(T[] array, int k)
      Type Parameters:
      T -
      Parameters:
      array - The array of the elements
      k -
      Returns:
      See Also:
      $quick_select0_1(Comparable[], int, int, int), $quick_select0_2(Comparable[], int, int, int)

    • floyd_rivest_select

      public static <T extends java.lang.Comparable<T>> T floyd_rivest_select​(T[] array, int k)

    • $huffman_table0_1

      private static void $huffman_table0_1​(stl_Algos.$freq_node_00 node, java.lang.String prefix, java.util.Map<java.lang.Character,​java.lang.String> table)

    • $quick_select0_1

      private static <T extends java.lang.Comparable<T>> T $quick_select0_1​(T[] array, int left, int right, int k)

    • $floyd_rivest_select0_1

      private static <T extends java.lang.Comparable<T>> T $floyd_rivest_select0_1​(java.util.List<T> list, int k)

    • $quick_select0_2

      private static <T extends java.lang.Comparable<T>> int $quick_select0_2​(T[] array, int left, int right, int pivot)

    • $dfs_traverse0_1

      private static <T> void $dfs_traverse0_1​(T node, java.util.Map<T,​java.util.List<T>> adjList, java.util.Set<T> visited, java.util.List<T> res)