NaN Quantitavity – Quant Trading, Statistical Learning, Coding and Brainstorming

#include <iostream>
#include <vector>
using namespace std;

struct Tree
{
    char data;
    Tree *left, *right, *parent;

    Tree(char a){
        data = a;
        left = NULL; right = NULL; parent = NULL;
    }
};

Tree* insertTreeNode(Tree* node, char data){
    if(node == NULL){
        Tree* newNode = new Tree(data);
        return newNode;        
    }
    else if(data <= node->data){
        node->left = insertTreeNode(node->left, data);
        node->left->parent = node;
    }
    else{
        node->right = insertTreeNode(node->right, data);
        node->right->parent = node;
    }
    return node;
}

bool isBST(Tree* root){
    if (root == NULL)
        return 1;
    else if (!isBST(root->left) || !isBST(root->right))
        return 0;
    else if(root->left){
        if(root->left->data > root->data)
            return 0;
    }
    else if(root->right){
        if(root->data >= root->right->data)
            return 0;    
    }
        return 1;
}

int main ()
{
    char ch, ch1, ch2;
    Tree *found=NULL, *succ=NULL, *pred=NULL, *ancestor=NULL;
    char charArr[9] = {'A','B','C','D','E','F','G','H','I'};

    Tree* root=NULL;
//    for (int i=0;i<sizeof(charArr)/sizeof(char);++i)
//        insertTreeNode(root,charArr[i]);
    root = insertTreeNode(root,'B');
    root->left = insertTreeNode(root->left,'A');

    /* is the tree BST? */
    cout<< "Binary Search Tree?: "<< ( isBST(root) ? 'Y':'N') <<endl;

    return 0;
}

//Highlighted at http://tohtml.com/cpp/
//Bred 3 + C++
//http://www.bogotobogo.com/cplusplus/cpptut.php

#include <iostream>
#include <fstream>
#include <string>

using namespace std;

const int TABLE_SIZE = 128;

struct TableList {
    string key;
    int value;
    struct TableList *next;
};

unsigned hash_function(string s)
{
    unsigned hash = 0;

    for (int i = 0; i < s.length(); i++)
        hash = s[i] + 31*hash;
    return hash % TABLE_SIZE;
}

unsigned rehash(unsigned);

class HashMap 
{
private:
    TableList **table;
public:
    HashMap() 
    {
        table = new TableList*[TABLE_SIZE];
        for(int i = 0; i < TABLE_SIZE; i++) table[i] = NULL;
    }

    void showMap() 
    {
        struct TableList *tp;
        for (int i = 0; i < TABLE_SIZE; i++) {
            tp = table[i];
            if(tp){ 
                cout << "table[" << i << "] " << tp->key << "(" << tp->value << ")";
                tp = tp->next;
            }
            else 
                continue;
            while(tp) {
                cout << "->" << tp->key << "(" << tp->value << ")";
                tp = tp->next;
            }
            cout << endl;
        }
    }

    struct TableList* lookup(string s) 
    {
        struct TableList *tp;
        for(tp = table[hash_function(s)]; tp != NULL; tp = tp->next) 
                if((tp->key).compare(s) == 0) return tp;  // found
        return NULL;  // not found
    }

    void put(string key, int value) {
        struct TableList *tp;
        unsigned hash;

        // not found
        if(!(tp = lookup(key))) {
            tp = new TableList;
            tp->key = key;
            tp->value = value;
            hash = hash_function(key);
            tp->next = table[hash];
            table[hash] = tp;
        // it's already there
        } else {
            tp->key = key;
            tp->value = value;
            hash = hash_function(key);
            table[hash] = tp;
        }
    }     

    ~HashMap() 
    {
        for (int i = 0; i < TABLE_SIZE; i++)
            if (table[i] != NULL) delete table[i];
        delete[] table;
    }

};

int main()
{
    HashMap m;
    string line;
    ifstream dict_reader("C:/Temp/linux.words");
    //ifstream dict_reader("C:/Temp/shortlist");
    if( !dict_reader ) {
        cout << "Error opening input file - dict  " << endl ;
        exit(1) ;
    }

    int count = 0;
    while(getline(dict_reader,line)) {    
        if((line[0] >= 'x' && line[0] < 'y') || (line[0] >= 'X' && line[0] < 'Y') ) {
            m.put(line,count++);
        }
    }

    m.showMap();
    return 0;
}
//Highlighted at http://tohtml.com/cpp/
//Bred 3 + C++
//http://www.bogotobogo.com/cplusplus/cpptut.php

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};

// only for the 1st Node
void initNode(Node *head, int n){
    head->data = n;
    head->next =NULL;
}

// apending
void addNode(struct Node *head, int n) {
    Node *newNode = new Node;
    newNode->data = n;
    newNode->next = NULL;

    Node *cur = head;
    while(cur) {
        if(cur->next == NULL) {
            cur->next = newNode;
            return;
        }
        cur = cur->next;
    }
}

// insert at the head
void insertFront(struct Node **head, int n) {
    Node *newNode = new Node;
    newNode->data = n;
    newNode->next = *head;
    *head = newNode;
}

// Traversing the list
/*display*/
void display(struct Node* head) {
    Node *list = head;
    while(list) {
        cout << list->data << "";
        list = list->next;
    }
    cout << endl;
    cout << endl;
}

/*search a node*/
struct Node *searchNode(struct Node* head, int n) {
    while(head) {
        if(head->data == n) return head;
        head = head->next;
    }
    cout << "No Node " << n << " in list.\n";
}

struct Node *searchNode2(struct Node* head, int n) {
    while(head!=NULL & head->data != n) {
        head = head->next;
    }
    return head;
}

/*delete a node*/
bool deleteNode(struct Node **head, Node *ptrDel) {
    Node* cur = *head;
    if(ptrDel == *head) {
        *head = (**head).next;
        delete ptrDel;
        return true;
    }
    while(cur){
        if(cur->next == ptrDel) {
            cur->next = ptrDel->next;
            delete ptrDel;
            return true;
        }
        cur = cur->next;
    }
    return false;
}

// delete 
void deleteLinkedList(struct Node **node)
{
    struct Node* tmpNode;
    while(*node) {
        tmpNode = *node;
        *node = tmpNode->next;
        delete tmpNode;
    }
}

// reverse the list
struct Node* reverse(struct Node** List) 
{
    Node* parent = *List;
    Node* me = parent->next;
    Node* child = me->next;

    /* make parent as tail */
    parent->next = NULL;
    while(child) {
        me->next = parent;
        parent = me;
        me = child;
        child = child->next;
    }
    me->next = parent;
    *List = me;
    return *List;
}

// copy
void copyLinkedList(struct Node *node, struct Node **pNew)
{
    if(node != NULL) {
        *pNew = new Node;
        (*pNew)->data = node->data;
        (*pNew)->next = NULL;
        copyLinkedList(node->next, &((*pNew)->next));
    }
}

// Compare two linked list: return value: same(1), different(0)
int compareLinkedList(struct Node *node1, struct Node *node2)
{
    static int flag;

    /* both lists are NULL */
    if(node1 == NULL && node2 == NULL) {
        flag = 1;
    }
    else {
        if(node1 == NULL || node2 == NULL) 
            flag = 0;
        else if(node1->data != node2->data) 
            flag = 0;
        else
            compareLinkedList(node1->next, node2->next);
    }

    return flag;
}

int main() 
{
    Node* newHead=0;    
    Node* head = new Node;
    initNode(head,10);
    display(head);
    addNode(head,20);
    addNode(head,30);
    display(head);

    insertFront(&head,5);
    display(head);

    int numDel = 5;
    Node* ptrDelete = searchNode(head,numDel);
    if(deleteNode(&head,ptrDelete)) 
        cout << "Node "<< numDel << " deleted!\n";
    display(head);

    cout << "The list is reversed\n";
    reverse(&head);
    display(head);

    cout << "The list is copied\n";
    copyLinkedList(head,&newHead);
    display(newHead);

    cout << "Comparing the two lists...\n";
    cout << "Are the two lists same?\n";
    if(compareLinkedList(head,newHead)) 
        cout << "Yes, they are same!\n";
    else
        cout << "No, they are different!\n";
    cout << endl;

    numDel = 20;
    ptrDelete = searchNode(newHead,numDel);
    if(deleteNode(&newHead,ptrDelete)) {
        cout << "Node "<< numDel << " deleted!\n";
        cout << "The new list after the delete is\n";
        display(newHead);
    }
    cout << "Comparing the two lists again...\n";
    cout << "Are the two lists same?\n";
    if(compareLinkedList(head,newHead)) 
        cout << "Yes, they are same!\n";
    else
        cout << "No, they are different!\n";

    cout << endl;
    cout << "Deleting the copied list\n";
    deleteLinkedList(&newHead);
    cout << "Displaying afer deleting:\n";
    display(newHead);
    cout << "END\n";
    return 0;
}

//Highlighted at http://tohtml.com/cpp/
//Bred 3 + C++
//http://www.bogotobogo.com/cplusplus/cpptut.php

// Replace all spaces in a string with '%20'
#include <iostream>
#include <string>
using namespace std;

//Method 1: use STL::string
string repUsestring(string str){
    string newStr;
    for (int i=0; i<str.length(); i++){
        if (str[i]==' ')
            newStr += "%20";
        else
            newStr += str[i];
    }
    return newStr;
}

//Method 2: use C-stype array

char* repUsearray(char* str){
    int length = strlen(str), newLength=length;
    for (int i=0;i<length;i++){
        if (str[i]== ' ')
            newLength+=2;
    }
    char* newStr = new char[newLength];

    int j = 0;
    for (int i=0; i<length; i++){
        if (str[i]!=' '){
            newStr[j] = str[i];
            j++;
        }
        else{
            newStr[j] = '%';
            j++;
            newStr[j] = '2';
            j++;
            newStr[j] = '0';
            j++;
        }
    }
    newStr[newLength]=0; //ALWAYS REMEMBER TO ADD THE END OF ARRAY
    return newStr;
}

int main(){
    string str1("test a test b test c  ");
    char* str2 = "ai ni ai wo ai ta ";
    cout<<str1<<endl;
    cout<<repUsestring(str1)<<endl;
    cout<<str2<<endl;
    cout<<repUsearray(str2)<<endl;

    return 0;
}

//Highlighted at http://tohtml.com/cpp/
//Bred 3 + C++
//http://www.bogotobogo.com/cplusplus/cpptut.php

To be…

// Remove duplicated characters
#include <iostream>
using namespace std;

// Method1: no (large) memory; O(n^2)
void rmDuplicated1(char str[]) {
    int nOld = strlen(str);
    if (nOld>1) {
        int nNew = 0;
        int j;
        for (int i=0; i < nOld; ++i){  //iterate for each orignal element
            // check if this element is a nonduplicated one
            for (j=0; j<nNew; ++j){
                if (str[j]==str[i])
                    break;
            }
            // if nonduplicated, add it. 
            if (j==nNew){
                nNew++;
                str[nNew-1] = str[i];
            }
        }

        str[nNew] = 0;
    }
}

// Method2: addtional memory; O(n)
char* rmDuplicated2(char str[]) {
    int nOld = strlen(str);
    if (nOld<2)
        return str;
    else{
        char* newStr = new char[nOld];
        bool check[256] = {0};

        int nNew = 0;
        for (int i=0; i < nOld; ++i){
            if (!check[(int)str[i]]){
                newStr[nNew] = str[i];
                nNew++;
                check[str[i]] = true;
            }
        }

        newStr[nNew] = 0;
        return newStr;
    }
}

int main(){
    char* str = new char[10];
    strcpy(str, "aaaBBB");
    // char* str = "Hello" doesn't work. Cz here str is const type.
    cout<<str<<endl;
    rmDuplicated1(str);
    cout<<str<<endl;
    cout<<rmDuplicated2(str)<<endl;
    delete[] str;

    return 0;
}

//Highlighted at http://tohtml.com/cpp/
//Bred 3 + C++