c++ – doubly linked ring implementation

I was practicing c++ and data structures and wrote my own implementation of a doubly linked ring. I would love to improve my code a little bit more and would need help from the community.

Here is the implementation I have

#ifndef BIRING_H_INCLUDED
#define BIRING_H_INCLUDED

#include<iostream>
#include<string>

using namespace std;

template<typename Key, typename Value>
class Ring
{

private:

    struct Element
    {
        Key key;
        Value value;
        Element* next;
        Element* prev;
    };

    Element* head;
    Element* tail;


public:
    class iterator
    {

    private:
        Element* ptr;

    public:

        iterator()
        {
            ptr=NULL;
        };

        iterator(const iterator & copy)
        {
            ptr=copy.ptr;
        };

        iterator(Element* copy)
        {
            ptr=copy;
        };

        ~iterator() {};



        iterator& operator=(iterator & copy)
        {
            ptr=copy.ptr;
        };

        iterator& operator=(Element* copy)
        {
            ptr=copy;
            return *this;
        };

        Key & operator*()
        {
            return ptr->key;
        };

        const Key & getKey()
        {
            return ptr->key;
        };

        const Value & getValue()
        {
            return ptr->value;
        };

        iterator operator+(const int i)const
        {
            iterator newthis = *this;
            for(int j=0; j<i; j++)
                newthis++;
            return newthis;
        };

        iterator& operator+=(const int i)
        {
            for(int j=0; j<i; j++)
                ptr=ptr->next;
            return *this;
        };

        iterator& operator++()
        {
            iterator a(*this);
            ptr=ptr->next;
            return a;
        };

        iterator operator++(int)
        {
            ptr=ptr->next;
            return *this;
        };

        iterator operator-(const int i)const
        {
            iterator newthis = *this;
            for(int j=0; j<i; j++)
                newthis--;
            return newthis;
        };

        iterator& operator-=(const int i)
        {
            for(int j=0; j<i; j++)
                ptr=ptr->prev;
            return *this;
        };

        iterator& operator--()
        {
            iterator a(*this);
            ptr=ptr->prev;
            return a;
        };

        iterator operator--(int)
        {
            ptr=ptr->prev;
            return *this;
        };

        bool operator==(const iterator & comp)const
        {
            return ptr==comp.ptr;
        };

        bool operator!=(const iterator & comp)const
        {
            return ptr!=comp.ptr;
        };

        bool isNull()const
        {
            return !ptr;
        };
    };


    Ring();
    ~Ring();

    Ring(const Ring<Key,Value> & copy);
    Ring<Key,Value> & operator=(const Ring<Key,Value> & copy);

    Ring<Key,Value> operator+(const Ring<Key,Value> & add)const;
    Ring<Key,Value> operator-(const Ring<Key,Value> & subtract)const;

    Ring<Key,Value>& operator++();
    Ring<Key,Value> operator++(int);

    Ring<Key,Value>& operator--();
    Ring<Key,Value> operator--(int);

    Ring<Key,Value> & operator+=(const Ring<Key,Value> & add)
    {
        *this=*this+add;
        return *this;
    };
    Ring<Key,Value> & operator-=(const Ring<Key,Value> & subtract)
    {
        *this=*this-subtract;
        return *this;
    };

    void clear();
    void reverse();


    iterator begin() const
    {
        return iterator(head);
    };


    iterator end() const
    {
        return iterator(tail);
    };

    unsigned int size() const;
    bool empty()const
    {
        return !head;
    };

    bool insertAt(unsigned int pos, const Key&key, const Value &value);
    bool insertAfter(const Key&keypos, const Key&key, const Value &value);
    bool insertAfter(const iterator & iter, const Key&key, const Value &value);

    void push_front(const Key&key, const Value &value);
    void push_back(const Key&key, const Value &value);
    void pop_front()
    {
        iterator a(begin());
        remove(a);
    };
    void pop_back()
    {
        iterator a(end());
        remove(a);
    };

    bool remove(const Key&key);
    bool remove(iterator & iter);
    bool removeAllOf(const Key&key);

    bool exists(const Key&key);

    bool operator==(const Ring<Key,Value> & check)const;
    bool operator!=(const Ring<Key,Value> & check)const;


    template<typename u, typename i>
    friend ostream & operator<< (ostream & os, const Ring<u,i> & toprint);


    iterator find(const Key &where) const;//move to the position of the designated ID
    iterator findPlace(int place) const;//move to the position of designated startindex
    bool findNodePlace(int place) const;

};



template <typename Key, typename Value>
unsigned int Ring<Key, Value>::size() const
{
    int length=0;
    if(head!=NULL)
    {
        Element *current = head->next;
        length=1;
        while(current!=head)
        {
            length++;
            current=current->next;
        }
    }
    return length;
}


template<typename Key, typename Value>
Ring<Key,Value>::Ring()
{
    head=tail=NULL;
}

template<typename Key, typename Value>
Ring<Key,Value>::Ring(const Ring<Key,Value> & copy)
{
    head=tail=NULL;
    Element * temp = copy.head;
    while (temp)
    {
        this->push_back(temp->key, temp->value);
        if(temp==copy.tail)
            break;
        temp=temp->next;
    }
}

template<typename Key, typename Value>
Ring<Key,Value>::~Ring()
{
    clear();
}


template<typename Key, typename Value>
Ring<Key,Value> & Ring<Key,Value>::operator=(const Ring<Key,Value> & copy)
{
    if(&copy==this)
        return *this;

    clear();

    Element * temp = copy.head;
    while (temp)
    {
        this->push_back(temp->key, temp->value);
        if(temp==copy.tail)
            break;
        temp=temp->next;
    }

    return *this;
}


template<typename Key, typename Value>
bool Ring<Key,Value>::operator==(const Ring<Key,Value> & check)const
{
    bool same = true;
    Element * temp1 = head;
    Element * temp2 = check.head;
    while(temp1&&temp2)
    {
        if(temp1->key!=temp2->key || temp1->value!=temp2->value)
            same = false;
        if(temp1==tail||temp2==check.tail)
            break;
        temp1=temp1->next;
        temp2=temp2->next;
    }
    return same;
}

template<typename Key, typename Value>
bool Ring<Key,Value>::operator!=(const Ring<Key,Value> & check)const
{
    return !(*this==check);
};


template<typename Key, typename Value>
Ring<Key,Value> Ring<Key,Value>::operator+(const Ring<Key,Value> & added)const
{
    Ring<Key,Value> tempseq;
    Element * temp = head;
    while(temp)
    {
        tempseq.push_back(temp->key,temp->value);
        if(temp==tail)
            break;
        temp=temp->next;
    }
    temp = added.head;
    while(temp)
    {
        tempseq.push_back(temp->key,temp->value);
        if(temp==added.tail)
            break;
        temp=temp->next;
    }
    return tempseq;
}

template<typename Key, typename Value>
Ring<Key,Value> Ring<Key,Value>::operator-(const Ring<Key,Value> & subtract)const
{
    Ring<Key,Value> tempseq;
    Element * temp = head;
    while(temp)
    {
        tempseq.push_back(temp->key,temp->value);
        if(temp==tail)
            break;
        temp=temp->next;
    }
    temp = subtract.head;
    while(temp)
    {
        tempseq.removeAllOf(temp->key);
        if(temp==subtract.tail)
            break;
        temp=temp->next;
    }
    return tempseq;
}

template<typename Key, typename Value>
Ring<Key,Value>& Ring<Key,Value>::operator++()
{
    if(head)
    {
        head=head->next;
        tail=tail->next;
    }
    return *this;
}

template<typename Key, typename Value>
Ring<Key,Value> Ring<Key,Value>::operator++(int)
{
    Ring a(*this);
    if(head)
    {
        head=head->next;
        tail=tail->next;
    }
    return a;
}

template<typename Key, typename Value>
Ring<Key,Value>& Ring<Key,Value>::operator--()
{
    if(head)
    {
        head=head->prev;
        tail=tail->prev;
    }
    return *this;
}

template<typename Key, typename Value>
Ring<Key,Value> Ring<Key,Value>::operator--(int)
{
    Ring a(*this);
    if(head)
    {
        head=head->prev;
        tail=tail->prev;
    }
    return a;
}


template<typename u, typename i>
ostream & operator<<(ostream & os, const Ring<u,i> & toprint)
{
    typename Ring<u,i>::Element* temp;
    temp = toprint.head;
    while(temp)
    {
        os << "Key: " << temp->key << endl << "Value: " << temp->value << endl;
        if(temp==toprint.tail)
            break;
        temp = temp->next;
    }
    return os;
}



template<typename Key,typename Value>
void Ring<Key,Value>::clear()
{
    Element * temp;
    temp=head;
    if(tail)
        tail->next=NULL;
    while(temp)
    {
        temp = temp->next;
        delete head;
        head = temp;
    }
    head=tail=NULL;

}

template<typename Key,typename Value>
void Ring<Key,Value>::reverse()
{
    Ring<Key,Value> tempseq;
    Element * temp = head;
    while(temp)
    {
        tempseq.push_front(temp->key,temp->value);
        if(temp==tail)
            break;
        temp=temp->next;
    }
    *this=tempseq;
}

template<typename Key,typename Value>
bool Ring<Key,Value>::insertAt(unsigned int pos, const Key&key, const Value &value)
{
    if(pos>size())
        return false;

    Element * temp = head;

    for(unsigned int i = 0; i<pos; i++)
    {
        temp=temp->next;
    }

    Element * newElement;
    newElement = new Element;

    newElement->key=key;
    newElement->value=value;
    newElement->next=newElement;
    newElement->prev=newElement;

    if(!temp)
    {
        head=tail=newElement;
    }
    else
    {
        newElement->next=temp;
        newElement->prev=temp->prev;

        temp->prev->next=newElement;
        temp->prev=newElement;
    }

    if(pos==0){
        head=newElement;
   }else if(pos==size()){
        tail=newElement;
   }
    return true;
}

template<typename Key,typename Value>
bool Ring<Key,Value>::insertAfter(const Key&keypos, const Key&key, const Value &value)
{
    Element * temp = head;
    bool found = false;

    while(temp)
    {
        if(temp->key==keypos)
        {
            found=true;
            break;
        }
        if(temp==tail)
            break;
        temp=temp->next;
    }

    if(!found)
        return false;

    Element * newElement;
    newElement = new Element;
    newElement->key=key;
    newElement->value=value;

    newElement->next=temp->next;
    newElement->prev=temp;

    temp->next->prev=newElement;
    temp->next=newElement;

    if(head==tail){
        head=tail=newElement;
    }else if(temp==tail){
        tail=newElement;
    }
    return true;
}

template<typename Key,typename Value>
bool Ring<Key,Value>::insertAfter(const iterator & iter, const Key&key, const Value &value)
{
    Element * temp = head;
    bool found = false;
    iterator comp;

    while(temp)
    {
        comp=temp;
        if(comp==iter)
        {
            found=true;
            break;
        }
        if(temp==tail)
            break;
        temp=temp->next;
    }

    if(!found)
        return false;

    Element * newElement;
    newElement = new Element;
    newElement->key=key;
    newElement->value=value;

    newElement->next=temp->next;
    newElement->prev=temp;

    temp->next->prev=newElement;
    temp->next=newElement;

    if(head==tail)
        head=tail=newElement;
    else if(temp==tail)
        tail=newElement;

    return true;
}


template<typename Key, typename Value>
void Ring<Key,Value>::push_front(const Key&key, const Value &value)
{
    Element * newElement;

    newElement = new Element;
    newElement->key = key;
    newElement->value = value;

    if(head)
    {
        newElement->next = head;
        newElement->prev = tail;
        tail->next=newElement;
        head->prev=newElement;
        head=newElement;
    }
    else
    {
        newElement->next = newElement;
        newElement->prev = newElement;
        head=tail=newElement;
    }
}

template<typename Key, typename Value>
void Ring<Key,Value>::push_back(const Key&key,  const Value &value)
{
    Element * newElement;

    newElement = new Element;
    newElement->key = key;
    newElement->value = value;

    if(head)
    {
        newElement->next = head;
        newElement->prev = tail;
        tail->next=newElement;
        head->prev=newElement;
        tail=newElement;
    }
    else
    {
        newElement->next = newElement;
        newElement->prev = newElement;
        head=tail=newElement;
    }
}


template<typename Key, typename Value>
bool Ring<Key,Value>::remove(const Key&key)
{
    Element* temp = head;
    while(temp)
    {
        if(temp->key==key)
        {
            if(head==tail)
            {
                delete temp;
                head = tail = NULL;
                size--;
                return;
            }
            else
            {
                temp->next->prev=temp->prev;
                temp->prev->next=temp->next;
                size--;
                delete temp;
                return;
            }
        }
        if(temp==tail)
            break;
        temp=temp->next;
    }
}

template<typename Key, typename Value>
bool Ring<Key,Value>::remove(iterator& iter)
{
    if(iter.isNull())
        return false;
    Element* temp = head;
    iterator comp;
    while(temp)
    {
        comp = temp;
        if(comp==iter)
        {
            iter++;
            if(head==tail)
            {
                delete temp;
                head = tail = NULL;
                return true;
            }
            else
            {
                if(temp==head)
                    head=temp->next;
                else if(temp==tail)
                    tail=temp->prev;
                temp->next->prev=temp->prev;
                temp->prev->next=temp->next;
                delete temp;
                return true;
            }
        }
        if(temp==tail)
            break;
        temp=temp->next;
    }
    return false;
}

template<typename Key, typename Value>
bool Ring<Key,Value>::removeAllOf(const Key&key)
{
    Element* temp = head;
    bool deleted = false;
    while(temp)
    {
        if(temp->key==key)
        {
            deleted=true;
            if(head==tail)
            {
                delete temp;
                head = tail = NULL;
                return deleted;
            }
            else
            {
                if(temp==head)
                    head=temp->next;
                else if(temp==tail)
                    tail=temp->prev;
                temp->next->prev=temp->prev;
                temp->prev->next=temp->next;
                delete temp;
            }
        }
        if(temp==tail)
            break;
        temp=temp->next;
    }
    return deleted;
}




template<typename Key, typename Value>
bool Ring<Key,Value>::exists(const Key&key)
{
    Element * temp = head;
    while(temp)
    {
        if(temp->key==key)
            return true;
        temp=temp->next;
    }
    return false;
}


template<typename Key, typename Info>
typename Ring<Key, Info>::iterator Ring<Key, Info>::find(const Key &where) const
{
    iterator iter = begin();
    if (head != NULL)
    {
        do
        {
            if (iter.getKey() == where)
            {
                return iter;
            }
            iter++;
        }
        while (iter != begin());
    }
    return NULL;
}


template <typename Key, typename Info>
typename Ring<Key, Info>::iterator Ring<Key, Info>::findPlace(int place) const
{
    iterator iter = begin();
    int position = 0;
    if (head != NULL)
    {

        do
        {
            if (position == place)
            {
                return iter;
            }
            iter++;
            position++;
        }
        while (iter != begin());
    }
    return NULL;
}


template <typename Key, typename Info>
bool Ring<Key, Info>::findNodePlace(int place) const
{
    iterator iter = find(place);
    if (iter == NULL)
    {
        return false;
    }
    else
    {
        return true;
    }
}


#endif // BIRING_H_INCLUDED

Thanks for reading!

plugins – Drupal : Difference between webservice (api) implementation with REST and routing

actually to create a wbesrvice endpoitns in Drupal 8 we need to activate one of or both of this 2 modules :

  1. JSON:API module (best one):

after the activation of this module you can
access to all Drupal entities (user , node , taxonomy ) throw a dynamic endpoints that have this structure http://{host}/json_api/{entity_type}/{bundle}?Parameters, with the ability to fitter the result + built in pagination + sorting ex of endpoints :

  • /jsonapi/node/article : get a json contains all node article.

  • /jsonapi/node/article,sort=-created : get a json contains all node article and order them with e created field in DESC
    order.article.

  • /jsonapi/taxojomy_term/article : get a json contains all taxnomy term category.

understand the Drupal entity type first will be better :
https://www.youtube.com/watch?v=FrSjwe8bh7I

then use the JSON:api using this videos :
https://www.youtube.com/watch?v=–ZL3EAhnwc&list=PLZOQ_ZMpYrZsyO-3IstImK1okrpfAjuMZ

  1. RESTful Web Services

    • Exposing Views using the RESTful Web Services module( Do you need an easy configuration from backoffice to set up and endpoint ?) https://www.youtube.com/watch?v=TMvNwRVJSEQ.
    • Creating a Custom REST Resources to expose data that can’t be exposed by the previous solution – when to use this solution when none of the previous solution can expose this data (Does JSON:API and View exposing can’t expose this type of data ?)

note : the methos in this url https://www.chapterthree.com/blog/custom-restful-api-drupal-8 never use it because we get out of the context of drupal, and you waon’t be able to use a hiddne power of Rest module ex :l by default any custom rest endpoint will display i if rest ui (https://www.drupal.org/project/restui) module installed .

python – Binary Search Tree (BST) Implementation

First Time implementing a Binary Search Tree, based on how it works from visualgo website. I made this algorithm purely based on what i saw, and the remove method was quite challenging. How can i improve the speed/efficiency and make the code look better?

Methods:

Inorder: basically an inorder traversal through the BST Ex: 1 3 4 6 19 25

Insert: inserts a node with a certain value

lookup: returns the value if it exists in the bst else returns None

getMin: returns the min value in the specified node

remove: removes a value, and if current_node is not specified then, it starts from the root node, a bit recursive, even though i wanted to implement a way without recursion, but i couldn’t see it working without it in any way.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def inorder(self, current_node):
        if current_node:  
            self.inorder(current_node.left)
            print(current_node.value, end=' ')
            self.inorder(current_node.right)

    def insert(self, value):
        NewNode = Node(value) 
        current_node = self.root
        if current_node is None:
            self.root = NewNode
        else:
            while True:
                if value < current_node.value:
                    #Left
                    if not current_node.left:
                        current_node.left = NewNode
                        return self
                    current_node = current_node.left
                else:
                    if not current_node.right:
                        current_node.right = NewNode
                        return self
                    current_node = current_node.right

    def lookup(self, value):
        current_node = self.root
        if current_node is None:
            return None
        while current_node:
            current_value = current_node.value
            if value < current_value:
                current_node = current_node.left
            elif value > current_value:
                current_node = current_node.right
            else:
                return current_node

    def getMin(self, current_node):
        while current_node.left is not None:
            current_node = current_node.left
        return current_node.value

    def remove(self, value, current_node=False):
        if not current_node:
            current_node = self.root

        if not current_node: # if the root is None
            return None

        parent_node = None
        while current_node:
            current_value = current_node.value
            if value < current_value:   
                parent_node = current_node
                current_node = current_node.left
            elif value > current_value:
                parent_node = current_node
                current_node = current_node.right
            else:
                # No Child
                if not current_node.left and not current_node.right:
                    if current_node == parent_node.left:
                        parent_node.left = None
                    else:
                        parent_node.right = None

                # One Child
                elif current_node.right and not current_node.left:
                    if current_node == parent_node.left:
                        parent_node.left = current_node.right
                    else:
                        parent_node.right = current_node.left

                elif current_node.left and not current_node.right:
                    if current_node == parent_node.left:
                        parent_node.left = current_node.left
                    else:
                        parent_node.right = current_node.left

                # Two Child
                else:
                    in_order_successor = self.getMin(current_node.right)

                    self.remove(in_order_successor, current_node)
                    if self.root == current_node:
                        self.root.value = in_order_successor
                    elif current_node == parent_node.left:
                        parent_node.left.value = in_order_successor
                    else:
                        parent_node.right.value = in_order_successor
                return True # if removed

        return False # if value doesnt exist

c – Implementation of system() function in Linux using fork() , exec() and waipid() system calls

I have written the code for implementation of system() function in Linux using fork(), exec() and waitpid(). Could someone review the code and provide feedback. Thanks a lot.


#include<stdio.h>
#include<string.h>
#include<unistd.h>
#include<sys/types.h>
#include<sys/wait.h>
#include<error.h>
#include<errno.h>
#define size 30

char *get_command(int argc, char *argv());
int my_system(const char *command);

int my_system(const char *command)
{
    pid_t pid;
    int wstatus  = 0;
    int ret = 0;

    if (command == NULL)
        return 1;
    pid = fork();
    if (pid == -1) {
        return -1;
    } else if (pid == 0) {
        ret = execle("/bin/sh", "sh", "-c",command, (char *)NULL);
        if (ret == -1)
            return wstatus;

    } else {
        ret = waitpid(-1, &wstatus, 0);
        if (ret == -1)
            return -1;
    }
    return wstatus;
}

char *get_command(int argc, char **argv)
{
    int i = 0;
    static char command(size);

    if (argc == 1)
        return NULL;

    strcpy(command, argv(1));
    for (i = 2; i < argc; i++) {
        strcat(command, " ");
        strcat(command, argv(i));
    }
    return command;
}

int main(int argc, char *argv())
{
    int ret;
    char *command;

    command = get_command(argc, argv);
    ret = my_system(command);
    if (ret == 1)
        printf("Command is NULL, shell is availablen");
    else if (ret == -1)
        printf("Child process could not be created or error in the wait system calln");
    else if (ret == 127)
        printf("The Child process could not be executed in the shelln");
    else
        printf("The status of the child process is :%dn", ret);
    return 0;
}
```

algorithm – Fibonacci Heap Implementation In Java

From my repository.

This is my first time implementing a Fibonacci Heap, and since it’s pretty complicated (at least to me), I would like to check if it is all correct.

import java.util.HashMap;
import java.util.HashSet;
import java.util.Objects;

public class FibonacciHeap {

  private final HashMap<Integer, Node> references;
  private Node min;

  public FibonacciHeap() {
    references = new HashMap<>();
  }

  public void insert(int val) {
    Node newNode = new Node(val);
    references.put(val, newNode);

    if (min == null) {
      min = newNode;
      min.left = min;
      min.right = min;
    } else {
      min.insert(newNode);
      if (newNode.val < min.val) {
        min = newNode;
      }
    }
  }

  public int extractMin() {
    int toReturn = min.val;
    references.remove(toReturn);

    if (min.left == min && min.child == null) {
      min = null;
    } else {
      min.safeUnlink();
      min = min.left;
      consolidate();
    }

    return toReturn;
  }

  public void delete(int val) {
    Node nodeForm = references.get(val);
    nodeForm.val = Integer.MIN_VALUE;
    min = nodeForm;
    extractMin();
  }

  public boolean isEmpty() {
    return min == null;
  }

  private void consolidate() {
    Node() degrees = new Node(45);
    Node dummy = min;
    HashSet<Node> visited = new HashSet<>();

    do {
      if (visited.contains(dummy)) {
        break;
      }

      if (dummy.val < min.val) {
        min = dummy;
      }

      while (degrees(dummy.degree) != null) {
        Node other = degrees(dummy.degree);

        if (other.val < dummy.val) {
          Node temp = other;
          other = dummy;
          dummy = temp;
        }

        dummy.link(other);
        degrees(dummy.degree - 1) = null;
      }

      degrees(dummy.degree) = dummy;
      visited.add(dummy);
      dummy = dummy.right;
    } while (dummy != min);
  }

  @Override
  public String toString() {
    StringBuilder sb = new StringBuilder();

    if (min != null) {
      Node dummy = min;

      do {
        sb.append(dummy.val).append(" ");
        dummy = dummy.right;
      } while (dummy != min);
    }

    return sb.toString();
  }

  private static class Node {

    public int val;
    public Node left, right, child;
    public int degree;
    public boolean mark;

    public Node(int _val) {
      val = _val;
    }

    public void insert(Node other) {
      if (left == this) {
        left = other;
        right = other;
        left.right = this;
        left.left = this;
      } else {
        Node temp = left;
        left = other;
        left.right = this;
        left.left = temp;
        temp.right = left;
      }
    }

    public void unlink() {
      left.right = right;
      right.left = left;
    }

    public void safeUnlink() {
      saveChildren();
      unlink();
    }

    public void link(Node other) {
      other.unlink();
      if (child == null) {
        child = new Node(other.val);
        child.left = child;
        child.right = child;
      } else {
        child.insert(other);
      }

      other.mark = false;
      degree++;
    }

    public void saveChildren() {
      if (child != null) {
        Node dummy = child;

        do {
          Node tempNext = dummy.right;
          insert(dummy);
          dummy = tempNext;
        } while (dummy != child);

        child = null;
      }
    }

    @Override
    public boolean equals(Object o) {
      if (this == o) return true;
      if (o == null || getClass() != o.getClass()) return false;
      Node node = (Node) o;
      return val == node.val
          && degree == node.degree
          && mark == node.mark
          && Objects.equals(left, node.left)
          && Objects.equals(right, node.right)
          && Objects.equals(child, node.child);
    }

    @Override
    public int hashCode() {
      return Objects.hash(val);
    }

    @Override
    public String toString() {
      return val + "";
    }
  }
}

beginner – Caesar-Cipher Implementation – Code Review Stack Exchange

Background

I am a total beginner in Haskell, so after reading the Starting out-chapter of “Learn you a Haskell”, I wanted to create my first program that actually does something.

I decided to to the famous Caesar-Cipher.

Code

import Data.Char

encryptChar :: Char -> Int -> Int
encryptChar char shift = if ord char > 64 && ord char < 91    --Only encrypt A...Z
                           then (if ord char + shift > 90     --"Z" with shift 3 becomes "C" and not ")" 
                                  then ord char + shift - 26
                                  else ord char + shift)
                         else ord char

decryptChar :: Char -> Int -> Int
decryptChar char shift = if ord char > 64 && ord char < 91
                            then (if ord char - shift < 65
                                   then ord char - shift + 26
                                   else ord char - shift)
                         else ord char

encrypt :: String -> Int -> String
encrypt string shift = (chr (encryptChar (toUpper x) shift) | x <- string)    --"Loop" through string to encrypt char by char

decrypt :: String -> Int -> String
decrypt string shift = (chr (decryptChar (toUpper x) shift) | x <- string)

main = print(decrypt "KHOOR, ZRUOG!" 3)

(The code does work as intended.)

Question(s)

  • How can this code be improved in general?
  • Do I follow the style guide of Haskell (indentation, etc.)?
  • I have a background in imperative languages. Did I do something that is untypical for functional programming languages?

I would appreciate any suggestions.

binary search tree – BST implementation using smart pointers in C++

This BST implementation seems to work, I would appreciate an advice on how to improve the code. I am also interested in the following:

  • rule-of-5 methods, are all of them necessary (e.g. is destructor necessary when using smart pointers)? Are they implemented correctly?
  • Does Node class need rule-of-5 methods?
  • is clear() method implemented correctly? I think that if I set the root to nullptr, the rest of the Nodes will be deleted by the smart pointer’s destructor when the BinarySearchTree and therefore the Node go out of scope, is it correct?
  • Is the use of smart/raw pointers correct? I want to use raw pointers everywhere, where they don’t need to own the object, right?
  • const correctness

Any other advice will be appreciated too.

BinarySearchTree.hpp

#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H

#include <iostream>
#include <vector>
#include <queue>

class BinarySearchTree {

public:
    BinarySearchTree();
    BinarySearchTree(const int& value);
    BinarySearchTree(const BinarySearchTree& other_tree);
    BinarySearchTree(BinarySearchTree&& other_tree);
    BinarySearchTree& operator=(const BinarySearchTree& other_tree);
    BinarySearchTree& operator=(BinarySearchTree&& other_tree);
    ~BinarySearchTree();

    void build_from_vector(std::vector<int>& values);
    void build_from_vector_balanced(std::vector<int>& values);
    void insert_node(const int& value);
    void remove_node(const int& value);
    void clear();

    int min_val() const;
    int max_val() const;
    bool contains(const int& val) const;

    int max_depth() const;
    bool balanced() const;

    std::vector<int> get_inorder_vals() const;
    std::vector<int> get_preorder_vals() const;
    std::vector<int> get_postorder_vals() const;
    std::vector<int> get_level_order_vals() const;

    inline int size() const {
        return tree_size;
    }
    inline bool empty() const {
        return tree_size == 0;
    }

private:
    struct Node {
        int val;
        std::unique_ptr<Node> left = nullptr;
        std::unique_ptr<Node> right = nullptr;

        Node(const int value) :
        val{value},
        left{nullptr},
        right{nullptr}
        {}
    };

    std::unique_ptr<Node> root;
    int tree_size;

    void deep_copy_tree(std::unique_ptr<Node>& dest_node, const std::unique_ptr<Node>& source_node);

    void build_from_vector_balanced(std::vector<int>::iterator it_b, std::vector<int>::iterator it_e);
    void insert_node(const int& value, std::unique_ptr<Node>& curr_node);
    void remove_node(const int value, std::unique_ptr<Node>& curr_node);

    Node* find_min_node(const std::unique_ptr<Node>& curr_node) const;
    Node* find_max_node(const std::unique_ptr<Node>& curr_node) const;
    bool contains(const int& value, const std::unique_ptr<Node>& curr_node) const;

    bool balanced(const std::unique_ptr<Node>& curr_node, int& height) const;
    int max_depth(const std::unique_ptr<Node>& curr_node) const;

    void get_inorder_vals(std::vector<int>& vals, const std::unique_ptr<Node>& curr_node) const;
    void get_preorder_vals(std::vector<int>& vals, const std::unique_ptr<Node>& curr_node) const;
    void get_postorder_vals(std::vector<int>& vals, const std::unique_ptr<Node>& curr_node) const;
    void get_level_order_vals(std::vector<int>& vals, const std::unique_ptr<Node>& curr_node) const;

};

#endif /* BINARYSEARCHTREE_H */

BinarySearchTree.cpp

#include "BinarySearchTree.hpp"

BinarySearchTree::BinarySearchTree() : root{nullptr}, tree_size{0}
{}

BinarySearchTree::BinarySearchTree(const int& value) : root{std::make_unique<Node>(value)}, tree_size{1}
{}

BinarySearchTree::BinarySearchTree(const BinarySearchTree& other_tree) {
    if (other_tree.tree_size == 0) return;
    tree_size = other_tree.tree_size;
    deep_copy_tree(root, other_tree.root);
}

BinarySearchTree::BinarySearchTree(BinarySearchTree&& other_tree) :
root(std::exchange(other_tree.root, nullptr)), tree_size(std::exchange(other_tree.tree_size, 0))
{
}

BinarySearchTree& BinarySearchTree::operator=(const BinarySearchTree& other_tree) {
    tree_size = other_tree.tree_size;
    deep_copy_tree(root, other_tree.root);
    clear();
    return *this;
}

BinarySearchTree& BinarySearchTree::operator=(BinarySearchTree&& other_tree) {
    std::swap(tree_size, other_tree.tree_size);
    std::swap(root, other_tree.root);
    return *this;
}

BinarySearchTree::~BinarySearchTree() {
    clear();
}

void BinarySearchTree::build_from_vector(std::vector<int>& values) {
    for (const int& value : values) {
        insert_node(value);
    }
}

void BinarySearchTree::build_from_vector_balanced(std::vector<int>& values) {
    std::sort(values.begin(), values.end());
    std::vector<int>::iterator it_b = values.begin();
    std::vector<int>::iterator it_e = values.end() - 1;
    build_from_vector_balanced(it_b, it_e);
}

void BinarySearchTree::insert_node(const int& value) {
    insert_node(value, root);
}

void BinarySearchTree::remove_node(const int& value) {
    remove_node(value, root);
}

void BinarySearchTree::clear() {
    root = nullptr;
    tree_size = 0;
}

int BinarySearchTree::min_val() const {
    return find_min_node(root)->val;
}

int BinarySearchTree::max_val() const {
    return find_max_node(root)->val;
}

bool BinarySearchTree::contains(const int& val) const {
    return contains(val, root);
}

int BinarySearchTree::max_depth() const {
    return max_depth(root);
}

bool BinarySearchTree::balanced() const {
    int height = 0;
    return balanced(root, height);
}

std::vector<int> BinarySearchTree::get_inorder_vals() const {
    std::vector<int> vals;
    get_inorder_vals(vals, root);
    return vals;
}

std::vector<int> BinarySearchTree::get_preorder_vals() const {
    std::vector<int> vals;
    get_preorder_vals(vals, root);
    return vals;
}

std::vector<int> BinarySearchTree::get_postorder_vals() const {
    std::vector<int> vals;
    get_postorder_vals(vals, root);
    return vals;
}

std::vector<int> BinarySearchTree::get_level_order_vals() const {
    std::vector<int> vals;
    get_level_order_vals(vals, root);
    return vals;
}

void BinarySearchTree::deep_copy_tree(std::unique_ptr<Node>& dest_node, const std::unique_ptr<Node>& source_node) {
    if (!source_node) return;
    dest_node = std::make_unique<Node>(source_node->val);
    deep_copy_tree(dest_node->left, source_node->left);
    deep_copy_tree(dest_node->right, source_node->right);
}

void BinarySearchTree::build_from_vector_balanced(std::vector<int>::iterator it_b, std::vector<int>::iterator it_e) {
    if (it_b > it_e) return;

    int range = std::distance(it_b, it_e);
    std::vector<int>::iterator it_m = it_b + range / 2;

    insert_node(*it_m);

    build_from_vector_balanced(it_b, it_m - 1);
    build_from_vector_balanced(it_m + 1, it_e);
}

void BinarySearchTree::insert_node(const int& value, std::unique_ptr<Node>& curr_node) {        
    if (!curr_node) {
        curr_node = std::make_unique<Node>(value);
        tree_size++;
        return;
    }

    if (value == curr_node->val) 
        return;

    if (value < curr_node->val)
        insert_node(value, curr_node->left);
    else // (value > curr_node->val)
        insert_node(value, curr_node->right);
}

void BinarySearchTree::remove_node(const int value, std::unique_ptr<Node>& curr_node) {
    if (!curr_node) return;

    if (value < curr_node->val) {
        remove_node(value, curr_node->left);
    } else if (value > curr_node->val) {
        remove_node(value, curr_node->right);
    } else { // (value == curr_node->val)
        // remove it
        if (!curr_node->left && !curr_node->right) { // leaf
            tree_size--;
            curr_node = nullptr;
        } else if (curr_node->left && !curr_node->right) { // only left child
            tree_size--;
            curr_node = std::move(curr_node->left);
        } else if (!curr_node->left && curr_node->right) { // only right child
            tree_size--;
            curr_node = std::move(curr_node->right);
        } else {
            // both right and left children: replace val by left subtree's max value
            Node* temp = find_max_node(curr_node->left); // ok to have raw pointer here?
            curr_node->val = temp->val;
            // then remove left subtree's max node
            remove_node(temp->val, curr_node->left);
        }
    }
}

BinarySearchTree::Node* BinarySearchTree::find_min_node(const std::unique_ptr<Node>& curr_node) const {
    if (!curr_node) return nullptr;
    if (!curr_node->left) return curr_node.get();
    return find_min_node(curr_node->left);
}

BinarySearchTree::Node* BinarySearchTree::find_max_node(const std::unique_ptr<Node>& curr_node) const {
    if (!curr_node) return nullptr;
    if (!curr_node->right) return curr_node.get();
    return find_max_node(curr_node->right);
}

bool BinarySearchTree::contains(const int& value, const std::unique_ptr<Node>& curr_node) const {
    if (!curr_node) return false;
    if (value == curr_node->val) return true;
    if (value < curr_node->val) return contains(value, curr_node->left);
    return contains(value, curr_node->right);
}

bool BinarySearchTree::balanced(const std::unique_ptr<Node>& curr_node, int& height) const {
    if (!curr_node) {
        height = -1;
        return true;
    }
    int left = 0;
    int right = 0;
    if (balanced(curr_node->left, left)
        && balanced(curr_node->right, right)
        && std::abs(left - right) < 2) {
        height = std::max(left, right) + 1;
        return true;
    }
    return false;
}

int BinarySearchTree::max_depth(const std::unique_ptr<Node>& curr_node) const {
    if (!curr_node) return -1;
    return std::max(max_depth(curr_node->left), max_depth(curr_node->right)) + 1;
}

void BinarySearchTree::get_inorder_vals(std::vector<int>& vals,
                                        const std::unique_ptr<Node>& curr_node) const {
    if (!curr_node) return;
    get_inorder_vals(vals, curr_node->left);
    vals.push_back(curr_node->val);
    get_inorder_vals(vals, curr_node->right);
}

void BinarySearchTree::get_preorder_vals(std::vector<int>& vals,
                                         const std::unique_ptr<Node>& curr_node) const {
    if (!curr_node) return;
    vals.push_back(curr_node->val);
    get_preorder_vals(vals, curr_node->left);
    get_preorder_vals(vals, curr_node->right);
}

void BinarySearchTree::get_postorder_vals(std::vector<int>& vals,
                                          const std::unique_ptr<Node>& curr_node) const {
    if (!curr_node) return;
    get_postorder_vals(vals, curr_node->left);
    get_postorder_vals(vals, curr_node->right);
    vals.push_back(curr_node->val);
}

void BinarySearchTree::get_level_order_vals(std::vector<int>& vals,
                                            const std::unique_ptr<Node>& curr_node) const {
    if (!curr_node) return;

    std::queue<Node*> nodes_by_level;
    nodes_by_level.push(curr_node.get());
    while (!nodes_by_level.empty()) {
        Node* temp_node = nodes_by_level.front();
        nodes_by_level.pop();

        if (temp_node->left) nodes_by_level.push(temp_node->left.get());
        if (temp_node->right) nodes_by_level.push(temp_node->right.get());

        vals.push_back(temp_node->val);
    }
}

MultiDictionary C # Implementation – Code Review Stack Swap

Because C # .NET does not come with a MultiDictionaryI implemented one based on this StackOverflow answer.

the MultiDictionary You should be able to keep multiple values ​​for a key and delete the key, if no value is assigned to the key anymore.

I wanted to implement almost all the methods, that the standard Dictionary provides:

void Add(TKey key, TValue value);
bool Remove(TKey key);
void Clear();
bool ContainsKey(TKey key);
bool TryGetValue(TKey key, out TValue value);

Use the MultiDictionary correctly some signatures needed to be changed. This is my implementation:

public class MultiDictionary
{
    private readonly Dictionary> _Data = new Dictionary>();

    public Dictionary>.ValueCollection Values => _Data.Values;
    public Dictionary>.KeyCollection Keys => _Data.Keys;
    public void Add(TKey key, TValue value) { this(key).Add(value); }
    public bool Remove(TKey key, TValue value) { return this(key).Remove(value); }
    public void Clear() { _Data.Clear(); }
    public bool ContainsKey(TKey key) { return _Data.ContainsKey(key); }
    public bool TryGetValue(TKey key, out List value) { return _Data.TryGetValue(key, out value); }

    private struct Entry : IEnumerable
    {
        private readonly MultiDictionary _Dictionary;
        private TKey Key { get; }

        internal void Add(TValue value)
        {
            if (!_Dictionary._Data.TryGetValue(Key, out var list))
                list = new List();
            list.Add(value);
            _Dictionary._Data(Key) = list;
        }

        internal bool Remove(TValue value)
        {
            if (!_Dictionary._Data.TryGetValue(Key, out var list))
                return false;
            var result = list.Remove(value);
            if (list.Count == 0)
                _Dictionary._Data.Remove(Key);
            return result;
        }

        internal Entry(MultiDictionary dictionary, TKey key)
        {
            _Dictionary = dictionary;
            Key        = key;
        }

        public IEnumerator GetEnumerator()
        {
            return !_Dictionary._Data.TryGetValue(Key, out var list) ? Enumerable.Empty().GetEnumerator() : list.GetEnumerator();
        }
        IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }
    }

    private Entry this(TKey key) => new Entry(this, key);
}

I wanted to know if this implementation is valid (works as expected) and if it has improvements regarding coding style, security etc.

Thanks in advance!

docker – error in basic ci implementation in gitlab fatal: remote reference could not be found

I set up the new gitlab docker, then I set up a broker docker with the docer performer based on microsoft / dotnet: last
then i added a simple project to gitlab just a dotnet core hello world
then i create a ci file as follows:

image:  microsoft/dotnet:latest

stages:
  - build


variables:
  project: "ConsoleApp"

before_script:
  - "dotnet restore"

build:
  stage: build
  variables:
    build_path: "$ConsoleApp"
  script:
    - "cd $build_path"
    - "dotnet build"

so in pipleline I get this output:

Preparing environment
 Running on runner-vtysysr-project-2-concurrent-0 via e189cc9d1c60...
Getting source from Git repository
00:07
 Fetching changes with git depth set to 50...
 Reinitialized existing Git repository in /builds/root/gitlabcitest/.git/
 fatal: couldn't find remote ref refs/pipelines/18
Uploading artifacts for failed job
00:06
 ERROR: Job failed: exit code 1

I looked for an error, but all the answers are about projects that have branches, but I have no branch, just a simple hello world project.

c ++ – Is this stack implementation ok?

I recently started teaching myself basic C ++ and decided to implement a simple stack with pointers.

#include 

using namespace std;

struct StackElement {
    char value;
    StackElement* next;

    StackElement(char value, StackElement* next) : value(value), next(next) {}
};

struct Stack {
    StackElement* top = NULL;

    bool isEmpty() { return top == NULL; }

    void push(char value) {
        StackElement* newElement = new StackElement(value, top);

        top = newElement;
    }

    StackElement pop() {
        StackElement* toBeDeleted = top;
        StackElement toBeReturned = *top;

        top = top->next;
        delete toBeDeleted;
        return toBeReturned;
    }
};

int main() {
    Stack* stack = new Stack();
    cout << "Created a stack at " << &stack << endl;

    int number_of_inputs;
    cout << "Enter the number of elements you want to push at the stack: ";
    cin >> number_of_inputs;

    for (int i = 0; i < number_of_inputs; i++) {
        char input;
        cin >> input;
        stack->push(input);
    }

    cout << "- - - - - - - - - - - - - - - - " << endl;
    cout << "Displaying content of the stack: " << endl;

    while (!stack->isEmpty()) {
        cout << stack->pop().value << endl;
    }

    return 0;
}

My questions are:
- What can be usually done better here?
- is he pop() method spelled correctly? Does it create any memory leak? Is there a way to write it shorter?

Thanks in advance! (And forgive the use of using namespace std)