custom c++ algorithms

container_utils.hpp

template<typename T>
class CircularBuffer : public vector<T> {
public:
    CircularBuffer<T>(vector<T> data):
        vector<T>(data){}

    void rotateRight(unsigned amount){
        int tmp;
        for(unsigned i=0;i<amount;i++){
            this->rotateRight();
        }
    }

    void rotateRight(){
        this->insert(this->begin(),this->back());
        this->pop_back();
    }
};

math_utils.hpp

bool isPrime(uint64_t val){
    int rv = true;

    if (val < 2)
        rv = false;
    else if (val == 2)
        rv = true;
    else if (val%2 == 0)
        rv = false;
    else
    {
        int t = val;
        for(int i = 3; i <= t; i+=2,t=val/i)
        {
            if(val%i==0 && val !=i)
            {
                rv = false;        
                break;  
            }
        }
    }
    return rv;
}

string_utils.hpp

vector<string> split(string s,char delim){

    vector<string> sequences;
    string tmp;
    bool sequenceFound = false;
    for(char c:s){
        if (c!=delim && sequenceFound == false){
            tmp.push_back(c);   
            sequenceFound = true;
        } 
        else if (c!= delim && sequenceFound == true)
            tmp.push_back(c);
        else if (c==delim && sequenceFound == true) {
            sequences.push_back(tmp);
            tmp.clear();
            sequenceFound=false;
        }
        else if(c==delim && sequenceFound == false)
            continue;
    }

    if(sequenceFound)
        sequences.push_back(tmp);
        
    return sequences;
}

tree_search_utils.hpp

bool isLeaf(Node * node)
{
    return !node->left && !node->right;
}

void preOrder(Node *root) 
{
    /**
        Algorithm: find leaf nodes by always moving right, stack it, trim it and start over until the root is              reached.
    **/
    if(!root)
        return;

    Node * node = root;
    Node * prevNode;
    stack<Node*> nodes;
    while(node!=NULL)
    {

        //if its not a leaf continue
        if(!isLeaf(node))
        {
            prevNode = node;
            //try to go right
            node = node->right ? node->right : node->left;
            continue;
        }
        else
        {
            //else add to stack,  
            nodes.push(node);
            //trim and go back to root
            if(prevNode->left == node)
            {
                prevNode->left = NULL;
                node=root;
            }
            else if (prevNode->right == node)
            {
                prevNode->right = NULL;
                node=root;
            }
            else //stop condition if no more leaves
            {
                node = NULL;
            }
        }
    }

    while(!nodes.empty())
    {
        Node * n = nodes.top();
        cout << n->data << " ";
        nodes.pop();
    }
}

void postOrder(Node *root) 
{
    /**
        Algorithm: find leaf nodes by always moving right, stack it, trim it and start over until the root is              reached.
    **/
    if(!root)
        return;

    Node * node = root;
    Node * prevNode;
    queue<Node*> nodes;
    while(node!=NULL)
    {

        //if its not a leaf continue
        if(!isLeaf(node))
        {
            prevNode = node;
            //try to go right
            node = node->left ? node->left : node->right;
            continue;
        }
        else
        {
            //else add to queue
            nodes.push(node);
            //trim and go back to root
            if(prevNode->left == node)
            {
                prevNode->left = NULL;
                node=root;
            }
            else if (prevNode->right == node)
            {
                prevNode->right = NULL;
                node=root;
            }
            else //stop condition if no more leaves
            {
                node = NULL;
            }
        }
    }

    while(!nodes.empty())
    {
        Node * n = nodes.front();
        cout << n->data << " ";
        nodes.pop();
    }
}

void inOrder(Node *root) 
{
    /**
        Algorithm: find leaf nodes by always moving right, stack it, trim it and start over until the root is              reached.
    **/
    if(!root)
        return;

    Node * node = root;
    Node * prevNode;
    Node * head = root;
    stack<Node*> nodes;
    while(node!=NULL)
    {

        //if its not a leaf continue
        if(!isLeaf(node))
        {
            if(node->right)
            {
                prevNode = node;
                node = node->right;
            }
            else
            {
                nodes.push(node);
                head = node->left;
                node = head;

            }
            continue;
        }
        else
        {
            //else add to stack,  
            nodes.push(node);
            //trim and go back to root
            if(prevNode->left == node)
            {
                prevNode->left = NULL;
                node=head;
            }
            else if (prevNode->right == node)
            {
                prevNode->right = NULL;
                node=head;
            }
            else //stop condition if no more leaves
            {
                node = NULL;
            }
        }
    }

    while(!nodes.empty())
    {
        Node * n = nodes.top();
        cout << n->data << " ";
        nodes.pop();
    }
}

void inSequence(Node *root) 
{
    //Algorithm: if its a leaf add it to the list then trim it; when done sort

    if(!root)
        return;

    Node * node = root;
    Node * prevNode;
    set<int> vals; //inserts will auto sort the list

    while(node!=NULL)
    {

        //if its not a leaf continue
        if(!isLeaf(node))
        {
            prevNode = node;
            //try to go right
            node = node->right ? node->right : node->left;
            continue;
        }
        else
        {
            //else add to stack,  
            vals.insert(node->data);
            //trim and go back to root
            if(prevNode->left == node)
            {
                prevNode->left = NULL;
                node=root;
            }
            else if (prevNode->right == node)
            {
                prevNode->right = NULL;
                node=root;
            }
            else //stop condition if no more leaves
            {
                node = NULL;
            }
        }
    }

    //print
    for(int i:vals)
    {
        cout << i << " ";
    }
}

typedef vector<Node*> Level;
typedef vector<Level> Levels;

void levelOrder(Node * root) {
    //for each level, print the nodes from left to right
    Levels levels;
    Level l;
    l.push_back(root);
    levels.push_back(l);
    Level currentLevel = levels.back();

    //remaining levels
    while(1){
        Level l;
        for(Node * n: currentLevel){

            if(n->left||n->right)
            {
                if(n->left)
                    l.push_back(n->left);
                if(n->right)
                    l.push_back(n->right);
            }
        }
        if(!l.empty()){
            levels.push_back(l);
            currentLevel = levels.back();
        }
        else
        {
            break;
        }
    }

    for(Level level:levels){
        for(Node * node:level){
            cout << node->data << " ";
        }
    }

}

int height(Node* root) {
    // Write your code here.
    //Write your code here
      //until there are no more paths left, maintain a max count

      int rv;
      if(root->left!=NULL && root->right!=NULL)
        rv= 1+ max(height(root->left),height(root->right));
      else if(root->left==NULL && root->right!=NULL)
        rv= 1+ height(root->right);
      else if(root->left!=NULL && root->right == NULL)
        rv= 1+ height(root->left);
      else
        rv= 0;

      return rv;
}

class NodeMeta
{
    public:
    NodeMeta(Node * node,int rank):_node(node),_rank(rank){}

    Node * node(){return _node;}
    int rank(){return _rank;}

    private:
    Node * _node;
    int _rank;
};

typedef vector<NodeMeta> Level;
typedef vector<Level> Levels;

Levels getLevels(Node * root) {
    //for each level, print the nodes from left to right
    Levels levels;
    Level l;
    l.push_back(NodeMeta(root,0));
    levels.push_back(l);
    Level currentLevel = levels.back();

    //remaining levels
    while(1){
        Level l;
        for(NodeMeta n: currentLevel){

            if(n.node()->left||n.node()->right)
            {
                if(n.node()->left)
                    l.push_back(NodeMeta(n.node()->left,n.rank()-1));
                if(n.node()->right)
                    l.push_back(NodeMeta(n.node()->right,n.rank()+1));
            }
        }
        if(!l.empty()){
            levels.push_back(l);
            currentLevel = levels.back();
        }
        else
        {
            break;
        }
    }

    return levels;

}

void topView(Node * root) {

    Levels levels = getLevels(root);

    set<int> ranks;
    vector<pair<int,int>> data;

    for(Level level:levels)
    {
        pair<int,int> vals{-1,-1};

        for(NodeMeta nm:level)
        {
            if(ranks.insert(nm.rank()).second)
            {
                if(nm.rank()<0)
                    vals.first = nm.node()->data;
                else
                    vals.second = nm.node()->data;
            }
        }

        data.push_back(vals);
            
    }

    for(vector<pair<int,int>>::reverse_iterator l = data.rbegin();l<data.rend();l++)
    {
        if(l->first >=0)
            cout << l->first << " ";
    }

    for(vector<pair<int,int>>::iterator l = data.begin();l<data.end();l++)
    {
        if(l->second >=0)
            cout << l->second << " ";
    }

}