tnlib

C/C++ notes , Algorithms and data structures heavily used in programming competitions, implemented in C++.

###Content

Types
- fundamental_type
  - arithmetic_type
    - integral_type
      - bool
      - char
        
        narrow char
        
        wide_char
      - short
      - int
      - long
    - floating_points
      - float
      - double
    - size_type
      - size_t
    - difference_type
      - ptrdiff_t
- compound_type
  - reference_type
    - lvalue reference
    - rvalue reference
  - pointer_type
  - arithmetic_pointer
    - array_type
    - string_type
  - smart pointer
    - unique_ptr
    - shared_ptr
    - weak_ptr
    - auto_ptr
    - smartpointer wrapper implementation
  - function_type
  - enumeration_type
  - class_type
    - union
    - struct / class
      - struct vs class
      - Constructor
        
        Default constructor
        
        Class initialization
        
        Uniform initialization
        
        Delegate constructor
        
        explicit constructor
      - Copy constructor
      - move constructor
      - destructor
      - this
      - static
      - const
      - mutable
      - using
      - friend
      - delete
      - rule of three
      - rule of five
      - rule of zero
      - encapsulation
      - polymorthism
        
        Function binding
        
        virtual method
        
        override/final keywords
        
        virtual - common errors
        
        Pure virtual methods
        
        Abstract class and interface
      - operator overloading
        
        Operator <<
        
        Operator operator()
        
        Operator operator=
      - Special Objects
        
        Aggregate
        
        Trivial class
        
        Standard-layout class
        
        Plain old data type
      - interface
      - association
      - composition
      - agreggation
      - coupling
      - pimpl
  - wrapper_class
- deduction_type
  - auto
- generic_type
  - preprocessor_type
    - macro
    - type_alias
  - template
Stream
- type_info
  - sizeof
  - numeric_limits
  - typeid
  - aligned
- type_traits
- formats
  - istream / ostream
- persistents
  - file
    - ifstream / ofstream
    - file system
  - db
- check validations
- casting & numeric conversion
- assert & debugging
  - assertion
  - unit test
  - debugging technique
  - trace macro
  - trace file
  - finding memory leaks
- handle exception
  - tradetional error
  - throw exception & try{}catch()
  - exception handler
- statments
  - conditional
    - if / if_else
    - switch
  - iteration
    - wihle / do_while
    - for / for_each
- operator
functional
metaprogramming
- Function Templates
  - Template parameters
  - Default parameters
  - Template specialization
  - Template overloading
- Type Deduction
  - Pass-by-Reference
  - Pass-by-Pointer
  - Pass-by-Value
  - Array type deduction
- Compile-Time Utilities
  - static assert
  - decltype
  - declval
  - using
- Type Traits
  - Type trait library
  - Type manipulation
  - Type Relation and Transformation
- Class Templates
  - Full/Partial specialization
  - Class + function template specialization
  - virtual
  - friend
  - Template dependent names
  - Template template arguments
  - Template variable
- Template Meta-Programming
  - Factorial
  - Log
  - Unroll
- SFINAE : Substitution Failure Is Not An Error
  - Function
  - Class
- Variadic Template
  - Parameter recursion
  - Folding expression
  - sizeof...
  - Meta-programming
  - Specialization
- STD Template Utility
  - std::pair
  - std::tuple
  - std::variant
  - std::optional
  - std::any
Collection
- fixed 1-D array array implementation
- 2-D array : matrix
  - matrix class implementation
- dynamic_array
- stack
- queue
- deque
- linked_list
  - single linked list
  - double linked list
  - circular single linked list
  - circular double linked list
- Trees
- Sparse Table
- Disjoint-Sets Union
- SQRT Decomposition
- Mo's Algorithm
- Skiplist
- Indexable Skiplist
- Heavy-Light Decomposition
- Treaps
- STL Collection
  - adapter container
    - stack
    - queue
    - priorty_queue
  - sequence container
    - std::arrray
    - std::vector
    - std::deque
    - std::forward_list
    - std::list
  - associative_container
    - std::set / std::multiset
    - std::map / std::multimap
    - std::unorderd_set / std::unorderd_multiset
    - std::unorderd_map / std::unorderd_multimap
Predicate & functor
Allocator
- allocator implementation
Iterator Implement a Custom Iterator - Iterator semantic - input / output iterator - forward iterator - bidirectional iterator - random access iterator - Implementation example • Iterator Utility Methods - Iterator operations - std::advance - std::next - std::prev - std::distance - Range access methods
```
  - Iterator traits
```
Algorithms
- Recursion
- randomize
  - rand / seed
  - default_random_engin
  - uniform_distribution
  - random_generator_wrapper
  - shuffle
  - random_shuffle
- sorting
  - bubble sort
  - selection sort
  - insertion sort
  - merge sort
  - quick sort
  - heap sort
- searching
- divide_and_conquer
  - partition
  - merge
- dynamic_programming
  - button-up memozation
  - top-down tabulation
- greedy
- backtrack
- bitwise
- math
  - digits
  - number theory
  - combinatoris
    - permutation
      - permutation wrapper
    - combination
- geometry
  - Geometry Library (2D)
  - Point (2D)
  - Line (2D)
  - Circle (2D)
  - Triangle (2D)
  - Rectangle (2D)
  - Angles (2D)
  - Distances (2D)
  - Line Intersection (2D)
  - Circle Intersection (2D)
  - Polygon Sorting and Area
  - Point-in-Polygon (Ray Casting)
  - Convex Hull and Diametral Pair
  - Minimum Enclosing Circle
  - Closest Pair
  - Segment Intersection Finding
  - Convex Polygon Cut
  - Polygon Intersection and Union
  - Delaunay Triangulation (Simple)
  - Delaunay Triangulation (Fast)
  - all geomethry implementation reviews
- string
  - my C-style function implementation
- tree
  - Binary Heap
  - Randomized Mergeable Heap
  - Skew Heap
  - Pairing Heap
  - Binary Search Tree
  - Treap
  - AVL Tree
  - Red-Black Tree
  - Splay Tree
  - Size Balanced Tree
  - Interval Treap
  - Hash Map
  - Skip List
  - Sparse Table (Range Minimum Query)
  - Square Root Decomposition
  - Segment Tree (Point Update)
  - Segment Tree (Range Update)
  - Segment Tree (Compressed)
  - Implicit Treap
  - Quadtree (Point Update)
  - Quadtree (Range Update)
  - 2D Segment Tree
  - 2D Range Tree
  - K-d Tree (2D Range Query)
  - K-d Tree (Nearest Neighbor)
  - R-Tree (Nearest Segment)
  - Fenwick Tree (Simple)
  - Fenwick Tree (Range Update, Point Query)
  - Fenwick Tree (Point Update, Range Query)
  - Fenwick Tree (Range Update, Range Query)
  - Fenwick Tree (Compressed)
  - 2D Fenwick Tree (Simple)
  - 2D Fenwick Tree (Compressed)
  - Disjoint Set Forest (Simple)
  - Disjoint Set Forest (Compressed)
  - Lowest Common Ancestor (Sparse Table)
  - Lowest Common Ancestor (Segment Tree)
  - Heavy Light Decomposition
  - Link-Cut Tree
- graph
  - Graph Class and Depth-First Search
  - Topological Sorting (DFS)
  - Eulerian Cycles (DFS)
  - Unweighted Tree Centers (DFS)
  - Shortest Path (BFS)
  - Shortest Path (Dijkstra's)
  - Shortest Path (Bellman-Ford)
  - Shortest Path (Floyd-Warshall)
  - Strongly Connected Components (Kosaraju's)
  - Strongly Connected Components (Tarjan's)
  - Bridges, Cut-points, and Biconnectivity
  - Minimal Spanning Tree (Prim's)
  - Minimal Spanning Tree (Kruskal's)
  - Max Flow (Ford-Fulkerson)
  - Max Flow (Edmonds-Karp)
  - Max Flow (Dinic's)
  - Max Flow (Push-Relabel)
  - Backtracking - Max Clique (Bron-Kerbosch)
  - Backtracking - Graph Coloring
  - Maximum Bipartite Matching (Kuhn's)
  - Maximum Bipartite Matching (Hopcroft-Karp)
  - Maximum Graph Matching (Edmonds's)
  - Shortest Hamiltonian Cycle (TSP)
  - Shortest Hamiltonian Path
- STL Algorithms
  - non-modifing
    - all_of
    - any_of
    - none_of
    - for_each
    - find
    - find_if
    - find_if_not
    - find_end
    - find_first_of
    - adjacent_find
    - count
    - count_if
    - mismatch
    - equal
    - is_permutation
    - search
    - search_n
  - modifing
    - copy
    - copy_n
    - copy_if
    - copy_backward
    - move
    - move_backward
    - swap
    - swap_ranges
    - iter_swap
    - transform
    - replace
    - replace_if
    - replace_copy
    - replace_copy_if
    - fill
    - fill_n
    - generate
    - generate_n
    - remove
    - remove_if
    - remove_copy
    - remove_copy_if
    - unique
    - unique_copy
    - reverse
    - reverse_copy
    - rotate
    - rotate_copy
  - partition
    - is_partition
    - stable_partition
    - partition_copy partation_point
  - merging
    - merge
    - implace_merge
    - includes
    - set_unions
    - set_intersections
    - set_difference
    - set_symmetric_difference
  - sort
    - sort
    - stable_sort
    - partial_sort
    - partial_sort_copy
    - is_sorted
    - is_sorted_until
    - nth_elements
  - search
    - lower_bound
    - upper_bound
    - equel_range
    - binary_range
  - heap
    - push_heap
    - pop_heap
    - make_heap
    - sort_heap
    - is_heap
    - is_heap_until
  - numeric
    - min_element
    - max_element
    - minmax_element
    - accumulate
    - adjacent_difference
    - inner_product
    - partial_sum
    - iota
  - others
    - lexicographical_compare
    - next_permutation
    - prev_permutation
concurrency
SOLID
Design Pattern
- creational
  - beginner
    - factory method
    - factory kit
    - prototype
    - proporty
    - singelton
    - module
    - monoState
    - object pool (concurreny)
    - object mother
    - value object
  - intermediate
    - abstruct factory
    - builder
    - Setp builder
    - twin
- structural pattern
  - beginner
    - adapter
    - decorator
    - event aggregator
    - facad
    - proxy
    - service locator
  - intermediate
    - abstract document : flexible way to organize domain in tree structure
    - ambasador
    - bridge
    - composite
    - flyweight
- behaviral pattern
  - beginner
    - delegation
    - dependency injection
    - future togle
    - iterator
    - null object
    - observe
    - specification
    - strategy
    - template
    - throttling
  - intermediate
    - visitor
    - asyinc visitor
    - chain of responsabilty
    - extension object
    - intercepting filter
    - interpreter
    - mediator
    - memonto
    - state
- concurrency pattern
  - Beginner
    - balken
    - double check lock
    - guarded suspension
  - intermediate
    - async method invocation
    - half sync / half async
    - mutex
    - producer / consumer
    - promise
    - read writer lock
    - semaphore
    - thread local storage
    - thread pool
  - expert
    - reactor
- testing pattern
  - page object
- others idioms patterns
  - RAII
  - caching
  - callback
  - dirty flag
  - double dispatch
  - lazy loading
  - fluent interface
  - marker interface
  - mute idiom
architecture pattern : high level scope (how compoment are organized)
- Beginner
  - Data transfer object
  - partial responce
  - unit of work
- intermediate
  - API Gateway
  - CQRS
  - data bus
  - event driven architecture
  - layred
  - serverless
  - service layer
- Expert
  - hexagonal architecture
  - naked object

tahanebti/tnlib

tnlib