Ahoy, fellow coders! Today, let’s embark on a thrilling journey into the realm of singleton classes in C++. If you’re not familiar with the term, fear not! A singleton class is like that one legendary sword in a game—you can only wield one of its kind at a time. In other words, it ensures there’s only ever one instance of a class floating around in your code.

The Singleton Quest Begins…

Picture this: you’re building a mighty castle of code, and you stumble upon a need for a class that must exist in a single, glorious instance. That’s where the singleton pattern comes into play!

Step 1: Raise the Drawbridge with a Private Constructor

In the land of singletons, the first rule is simple yet crucial: make the constructor private! This prevents any mischievous outsider from creating instances of your class willy-nilly.

1
2
3
4
5

class Singleton {
private:
    Singleton() {}  // Private constructor to prevent instantiation
    // Additional implementation goes here...
};

Method 1: Meyers’ Singleton - The Heroic Approach

Now, let’s dive into the magical realm of static member functions. Behold, the power of static! With this enchanting keyword, we can summon a single instance of our class.

1
2
3
4
5
6
7
8
9

class Singleton {
private:
    Singleton() {}  // Private constructor to prevent instantiation
public:
    static Singleton& getInstance() {
        static Singleton instance;
        return instance;
    }
};

Here’s how it works: whenever you call getInstance(), it conjures up a static instance if one doesn’t already exist. Otherwise, it simply returns the existing instance, ensuring there’s only one to rule them all! Meyers’ Singleton leverages the mystical properties of static local variables, ensuring that the instance is forged with utmost care and thread safety.

Method 2: The Static Pointer to Glory

But wait, our adventure isn’t over yet! There’s one more method to explore: the static pointer approach. Brace yourselves as we delve deeper into the arcane arts of C++!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Singleton {
private:
    Singleton() {}  // Private constructor to prevent instantiation
    static Singleton* instancePtr;  // Static pointer to the instance

public:
    static Singleton* getInstance() {
        if (!instancePtr) {
            instancePtr = new Singleton();
        }
        return instancePtr;
    }
};

Singleton* Singleton::instancePtr = nullptr;  // Initializing the static pointer

This method employs a static pointer to the singleton instance, ensuring lazy initialization and a journey free of unnecessary overhead.

Final Step : Complete Code

Copy the below code in a .cpp file and compile the code below using

g++ -s ./c++/cpp_codes/singleton.cpp -o singleton.out

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include<iostream>
#include<bits/stdc++.h>

using namespace std;

class Singleton {
private:
    Singleton() {}  // Private constructor to prevent instantiation
public:
    static Singleton& getInstance() {
        static Singleton instance;
        return instance;
    }
    void print(){
        cout << "hello world" << endl;
    }
};



int main(){
    Singleton obj = Singleton::getInstance();
    obj.print();
    return 0;
}

Special Keyword and

In C++, the static keyword has special significance when applied to member variables and functions:

• Static Member Variables: When a member variable is declared as static, it means there is only one instance of that variable shared among all instances of the class.
• Static Member Functions: A static member function is a function that belongs to the class rather than instances of the class. It can be called without an object of the class.

Steps to Implement a Singleton Class:

• Private Constructor: Ensure that the class has a private constructor to prevent external instantiation.
• Static Member Function/Object: Provide a static member function or object that returns a reference to the singleton instance.
• Lazy Initialization: The singleton instance should be created on-demand to conserve resources.
• Thread Safety (Optional): If the singleton will be accessed by multiple threads, ensure thread safety during initialization. Meyers’ Singleton automatically handles thread safety.

Epilogue: The Singleton Legacy Lives On

And there you have it, intrepid adventurers! By mastering the arcane arts of singleton classes, you’ve unlocked the secrets of controlling class instantiation like a true coding wizard. Whether you choose the static sorcery, the mystical member object, Meyers’ elegance, or the static pointer to glory, remember to wield your singleton powers responsibly in your coding quests!

Morris Traversal is a method for traversing binary trees without using any extra space for storing information about nodes. It allows for the traversal of a binary tree in Inorder, Preorder, and Postorder without recursion or using a stack.

Introduction

Morris Traversal is an elegant and efficient algorithm for traversing binary trees. It was introduced by J. H. Morris in 1979. The key idea behind Morris Traversal is to modify the tree as we traverse it so that we can navigate through the nodes without using any additional space for a stack or recursion. This method helps to reduce the space complexity of tree traversal algorithms.

Pseudo Code

The general idea behind Morris Traversal is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

1. Initialize current as root
2. While current is not NULL
    a. If current does not have a left child
        i. Print current's data
        ii. Move to the right child (current = current->right)
    b. Else
        i. Find the inorder predecessor of current (say it's the rightmost node in current's left subtree, and cannot be current node)
        ii. If the right child of the predecessor is NULL
            1. Set the right child of the predecessor to current (Creating temp links)
            2. Move current to its left child (current = current->left)
        iii. Else
            1. Set the right child of the predecessor back to NULL (Removing temp links)
            2. Print current's data
            3. Move current to its right child (current = current->right)

Inorder Traversal using Morris Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

void morrisInorderTraversal(Node* root) {
    Node* current = root;
    while (current != nullptr) {
        if (current->left == nullptr) {
            std::cout << current->data << " ";
            current = current->right;
        } else {
            Node* predecessor = current->left;
            while (predecessor->right != nullptr && predecessor->right != current) {
                predecessor = predecessor->right;
            }
            if (predecessor->right == nullptr) {
                predecessor->right = current;
                current = current->left;
            } else {
                predecessor->right = nullptr;
                std::cout << current->data << " ";
                current = current->right;
            }
        }
    }
}

Preorder Traversal using Morris Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

void morrisPreorderTraversal(Node* root) {
    Node* current = root;
    while (current != nullptr) {
        if (current->left == nullptr) {
            std::cout << current->data << " ";
            current = current->right;
        } else {
            Node* predecessor = current->left;
            while (predecessor->right != nullptr && predecessor->right != current) {
                predecessor = predecessor->right;
            }
            if (predecessor->right == nullptr) {
                std::cout << current->data << " ";
                predecessor->right = current;
                current = current->left;
            } else {
                predecessor->right = nullptr;
                current = current->right;
            }
        }
    }
}

Postorder Traversal using Morris Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

void reverseNodes(Node* start, Node* end) {
    if (start == end) return;
    Node* x = start;
    Node* y = start->right;
    Node* z;
    while (x != end) {
        z = y->right;
        y->right = x;
        x = y;
        y = z;
    }
}

void printReverse(Node* start, Node* end) {
    reverseNodes(start, end);
    Node* current = end;
    while (true) {
        std::cout << current->data << " ";
        if (current == start) break;
        current = current->right;
    }
    reverseNodes(end, start);
}

void morrisPostorderTraversal(Node* root) {
    Node dummy;
    dummy.left = root;
    dummy.right = nullptr;
    Node* current = &dummy;
    while (current != nullptr) {
        if (current->left == nullptr) {
            current = current->right;
        } else {
            Node* predecessor = current->left;
            while (predecessor->right != nullptr && predecessor->right != current) {
                predecessor = predecessor->right;
            }
            if (predecessor->right == nullptr) {
                predecessor->right = current;
                current = current->left;
            } else {
                printReverse(current->left, predecessor);
                predecessor->right = nullptr;
                current = current->right;
            }
        }
    }
}

Main Driver Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include <iostream>

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

// Function prototypes
void morrisInorderTraversal(Node* root);
void morrisPreorderTraversal(Node* root);
void morrisPostorderTraversal(Node* root);

int main() {
    // Constructing a sample binary tree
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    std::cout << "Inorder traversal: ";
    morrisInorderTraversal(root);
    std::cout << std::endl;

    std::cout << "Preorder traversal: ";
    morrisPreorderTraversal(root);
    std::cout << std::endl;

    std::cout << "Postorder traversal: ";
    morrisPostorderTraversal(root);
    std::cout << std::endl;

    // Deallocate memory
    delete root->left->right;
    delete root->left->left;
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}

This main driver code constructs a binary tree, then applies each of the Morris Traversal methods (inorder, preorder, postorder) to print the traversals. Finally, it deallocates the memory allocated for the tree nodes.

Practice

• https://www.geeksforgeeks.org/problems/flatten-binary-tree-to-linked-list/1

Writing a Comprehensive Self-Paced Roadmap for NLP with research papers, for my personal development.

Prerequisites:

• Basic understanding of Python programming language

• Familiarity with Machine and Deep Learning algorithms

• Knowledge of libraries used in NLP such as Natural Language Toolkit (NLTK), spaCy, Core NLP, Te Blob, PyNLPI, Gensim, Pattern, etc

Text Preprocessing Level

• Tokenization, Lemmatization, Stemming, Parts of Speech (POS), Stopwords removal, Punctuation removal

• Understanding that textual data isn’t directly compatible with Machine Learning algorithms, so it needs to be preprocessed before feeding it into our Machine Learning models

• Research Paper: “A Neural Probabilistic Language Model”

Advanced level Text Cleaning

• Normalization, Correction of Typos

• Mapping and Replacement. This involves mapping words to standardized language equivalents

• Correction of Typos: Written text often contains errors

Research Paper: “A Unified Architecture for Natural Language Processing: Deep Neural Networks with Multitask Learning”

Language Modeling

• Understanding of how to convert text data into numerical form

• Types of Language Models: Statistical Language Models, Rule-based Language Models, and Neural Language Models

• Research Paper: “The Unreasonable Effectiveness of Recurrent Neural Networks.”

Text Classification

• Naive Bayes, Logistic Regression, Support Vector Machines (SVM), Random Forest

• Understanding of how to classify text data.

• Research Paper: “Convolutional Neural Networks for Sentence Classification”

Deep Learning for NLP

• Recurrent Neural Networks (RNN), Long Short-Term Memory (LSTM), Gated Recurrent Unit (GRU), Transformer Models

• Understanding of how to use deep learning models for NLP

• Research Paper: “Sequence to Sequence Learning with Neural Networks”

Advanced NLP Concepts

• Named Entity Recognition (NER), Part-of-Speech tagging (POS), Sentiment Analysis

• Understanding of advanced NLP concepts

• Research Paper: “Named Entity Recognition with Bidirectional LSTM-CNNs”

Attention Mechanisms

• Understanding of attention mechanisms

• Types of Attention Mechanisms: Scaled-Dot Product Attention Mechanism, Multi-Head Attention Mechanism

• Research Paper: “Attention is All You Need”

State-of-the-Art NLP Models

• BERT, GPT-3, T5, ELECTRA

• Understanding of state-of-the-art NLP models

• Research Paper: “BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding”.

NLP Libraries and Frameworks

• Hugging Face Transformers, AllenNLP

• Understanding of various NLP libraries and frameworks

• Research Paper: “Transformers: State-of-the-Art Natural Language Processing”.

NLP Projects

• Text Classification, Sentiment Analysis, Chatbot Development.

• Hands-on experience with NLP projects

• Research Paper: “A Dataset for Document Grounded Conversations”.