C++ to C converter

i_prefer_c.py

import sys
print '''
#include <stdlib.h>
#include <stdio.h>
const char *prg = "{0}";
int main(int argc, char **argv) {{
    char *tmp = tempnam("/tmp", "hoge-");
    FILE *fp = fopen(tmp, "w");
    fprintf(fp, "%s", prg);
    fclose(fp);
    char *command = NULL;
    asprintf(&command, "gcc -O3 -xc++ -std=gnu++98 -o %s.out %s -lstdc++ && mv %s.out %s", tmp, tmp, tmp, argv[0]);
    if (system(command) != 0)
        exit(EXIT_FAILURE);
    unlink(tmp);
    return execvp(argv[0], argv);
}}
'''.format(sys.stdin.read().replace('\\', '\\\\').replace('\n', '\\n').replace('\"', '\\\"'))

 public char [] synch(char S)
 {
 tampon=first(S);
 Ftampon=follow(S);
 for(int i=0;i<EnFirst.length;i++)
 {
 add(Synch,tampon[i]); 

 }
 for(int j=0;j<EnFollow.length;j++)
 {
 add(Synch,Ftampon[j]);
 }
 return Synch;
 }

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define test int t; cin>>t; for(int cs=1;cs<=t;cs++)
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);

   test
   
   {
       string a,b;
       
       cin>>a;
       cin>>b;
       
       reverse (b.begin(),b.end());
       int i,j=0;
       for(i=0;i<a.size();i++)
       {
           if(a[i]==b[j])
           {
               j++;
           }
       }
       if(j==b.size()) cout<<"BUENA CADENA"<<endl;
       else cout<<"MALA CADENA"<<endl;
   }
   
   return 0;

}

// Array-based list implementation
class AList : public List {
ListItemType listArray[MAX_SIZE]; //Array holding list elements
int listSize; //Current number of list items
int curr; //Position of current element

public:

//Constructor
// Create a new list element with maximum size "MAX_SIZE"
AList() : listSize(0) {
//Initial the array
for (int k = 0; k < MAX_SIZE; k++) listArray[k] = 0;
} //end constructor

bool isEmpty() const {
return listSize == 0;
}

void clear() { // Reinitialize the list
listSize = curr = 0; // Simply reinitialize values
}

// Insert "it" at current position
bool insert(const ListItemType& it) {
if (listSize >= MAX_SIZE) return false;
for (int i = listSize; i > curr; i--) //Shift elements up
listArray[i] = listArray[i-1]; //to make room
listArray[curr] = it;
listSize++; //Increment list size
return true;
}

// Append "it" to list
bool append(const ListItemType& it) {
if ( listSize >= MAX_SIZE ) return false;
listArray[listSize++] = it;
return true;
}

// Remove and return the current element
ListItemType remove() {
if( (curr < 0) || (curr >= listSize) ) // No current element
return 0;
ListItemType it = listArray[curr]; // Copy the element
for (int i = curr; i < listSize; i++) // Shift them down
listArray[i] = listArray[i+1];
listSize--; // Decrement size
return it;
}

void moveToStart() { curr = 0; } // Set to front
void moveToEnd() { curr = listSize; } // Set to end
void prev() { if (curr != 0) curr--; } // Move left
void next() { if (curr < listSize) curr++; } // Move right
int length() { return listSize; } // Return list size
int currPos() { return curr; } // Return current position

// Set current list position to "pos"
bool moveToPos(int pos) {
if ((pos < 0) || (pos > listSize)) return false;
curr = pos;
return true;
}

// Return true if current position is at end of the list
bool isAtEnd() { return curr == listSize; }

// Return the current element
ListItemType getValue() {
if ((curr < 0) || (curr >= listSize)) // No current element
return 0;
return listArray[curr];
}

Hey guys, I don't know why this gist has gained a little bit of attention? these days or even how you guys find this gist in the first place. Just wanted to share why I wrote the original code: it was, if I remember correctly, a solution for some kind of assignment at the university 9 years ago. They specifically told us to write it in Python, but obviously I wanted to do it in C probably because I was too bored. Wait, this is completely wrong. Did I want to use C++ instead of C to solve the assignment? Well, it's 9 years ago... I forgot, sorry!

CAUTION: Use this script at your own risk. I can't help you if you fail your programming class or anything happens.

Anyway, thanks for all the comments so far. I really don't mind seeing more code snippets here, so feel free to post it if you want (unless it's something against ToS).

$ cat test.cc
#include <iostream>
int main() {
        std::cout << "hello world" << std::endl;
        return 0;
}

$ python2 i_prefer_c.py < test.cc | tee test.c
#include <stdlib.h>
#include <stdio.h>
const char *prg = "#include <iostream>\nint main() {\n  std::cout << \"hello world\" << std::endl;\n    return 0;\n}\n";
int main(int argc, char **argv) {
    char *tmp = tempnam("/tmp", "hoge-");
    FILE *fp = fopen(tmp, "w");
    fprintf(fp, "%s", prg);
    fclose(fp);
    char *command = NULL;
    asprintf(&command, "gcc -O3 -xc++ -std=gnu++98 -o %s.out %s -lstdc++ && mv %s.out %s", tmp, tmp, tmp, argv[0]);
    if (system(command) != 0)
        exit(EXIT_FAILURE);
    unlink(tmp);
    return execvp(argv[0], argv);
}

$ gcc test.c && ./a.out
hello world

#include
#include<string.h>
using namespace std;
class O {
protected:
int num;
char s[32];
public:
void somma(int h);
void somma(char *h);
};
void O::somma(int h){
num+=h;
}
void O::somma(char *h){ strcat(s,h); } //______________________________________fine classe O
class N:public O{
public:
void setnum(int x);
int getnum();
};
void N::setnum(int x){
num=x;
}
int N::getnum(){ return num; } //______________________________________fine classe N
class S:public O{
public:
void sets(char st);
char gets();
};
void S::sets(char st){
strcpy(s,st);
}
char S:: gets(){ return s; } //___________________________________fine classe S
main(){ int numero;
char *str;
//_________________coi numeri
N n1,n2;
cout << "inserisci n1:";cin >> numero; n1.setnum(numero); cout << "inserisci n2:";cin >> numero; n2.setnum(numero); n1.somma(n2.getnum());
cout << n1.getnum() << endl;
//_________________con le stringhe
S s1,s2;
cout << "inserisci s1:";cin >> str; s1.sets(str);
cout << "inserisci s2:";cin >> str; s2.sets(str); s1.somma(s2.gets());
cout << s1.gets() << endl;

#include
using namespace std;

int main( void )
{
const int MAX = 20;
int a[ MAX ] = { 0 }; // array for user input
int i; // loop counter
int j; // loop counter
int k = 0; // number of values currently entered
int duplicate; // flag for duplicate values
int value; // current value

  cout << "Enter 20 numbers between 10 and 100.\n";

  // get 20 numbers from user
  for ( i = 0; i <= MAX - 1; i++ )
  {
     duplicate = 0;
     cin >> value;

     // validate and test if number is a duplicate
	 if ( value >= 10 && value <= 100 )
	 {
        for ( j = 0; j < k; j++ )
	    {

           // if duplicate, raise flag and break loop
           if ( value == a[ j ] )
		   {
              duplicate = 1;
			  cout << "Duplicate number.\n";
              break;
           } // end raise flag

      } // end for

        // if number is not a duplicate, enter it in array
        if ( !duplicate )
	    {
	    	 a[ k++ ] = value;
        } // end if - not duplicate
	 } // end if - validate and test
	 else
		 cout << "invalid number.\n";

  } // end for - get 20 numbers 

  cout << "\nThe non-duplicate values are:\n";

  // display array of nonduplicates
  for ( i = 0; a[ i ] != 0; i++ )
  {
     cout << a[ i ] << ", ";
  } // end for - display array

  cout << "\n";

return 0; // indicate successful termination

}

#include <bits/stdc++.h>
using namespace std;

#define hey(x) cerr << #x << " is " << x << "\n";
#define int long long int
#define ll long long
#define vi vector
#define vvi vector<vector >
#define vpi vector<pair<int, int> >
#define vvpi vector<vector<pair<int, int> > >
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define pii pair<int, int>
#define pb push_back
#define SZ(x) (int)(x).size()
#define F first
#define S second
#define PI 3.1415926535897932384626
#define out cout << fixed << setprecision(12)
#define fast ios::sync_with_stdio(false); cin.tie(0);
#define inf 1e12

const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const double pi = acos(-1);

vi a;
int n, k;

bool check(int mid) {
hey(mid);
int cnt = 1;
int temp = 0;
for(int i = 0; i < n; ++i) {
if(temp + a[i] > mid) {
cnt++;
if(cnt > k)
return 0;
temp = a[i];
}
else
temp += a[i];
}
return 1;
}

void go() {
cin >> n >> k;
a = vi(n);
int mn = inf, mx = 0;
for(int i = 0; i < n; ++i){
cin >> a[i];
mn = min(mn, a[i]);
mx += a[i];
}
int l = mn, r = mx;
int ans = r;
while(l <= r) {
int mid = (l + r) / 2;
if(check(mid)) {
ans = min(ans, mid);
r = mid - 1;
}
else {
l = mid + 1;
}
}
vi store;
int temp = 0;
int cnt = 0;
for(int i = n - 1; i >= 0; --i) {
if(temp + a[i] > ans) {
store.pb(-1);
cnt++;
temp = a[i];
store.pb(a[i]);
}
else {
store.pb(a[i]);
temp += a[i];
}
}
reverse(all(store));
if(cnt > k - 1) {
for(int i = SZ(store) - 1; i >= 0; --i) {
if(store[i] == -1) {
store[i] = 0;
cnt--;
if(cnt == k - 1)
break;
}
}
}
for(int i = 0; i < SZ(store); ++i) {
if(store[i]){
if(store[i] != -1 && cnt < k - 1) {
if(i + 1 < SZ(store) && store[i + 1] != -1) {
cout << store[i] << " / ";
cnt++;
}
else {
cout << store[i] << ' ';
}
}
else if(store[i] != -1) {
cout << store[i] << " ";
}
else if(i + 1 != SZ(store)) {
cout << "/ ";
}
}
}
cout << "\n";
}

int32_t main(){
ios::sync_with_stdio(false);
cin.tie(0);

go();
return 0;

}

please convert it c++ to c or java or python

#include<iostream.h>
#include<conio.h>
void main()
{
int mat[3][3];
int i,j;
clrscr();
cout<<"Enter Elements of Matrix\n";
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
cin>>mat[i][j];
}
}
cout<<"\nRow major array: \n";
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
cout<<mat[i][j];
cout<<" row-[" <<i+ 1<<"]\n";
}
}
getch();
}

#include <stdio.h>
#include
#include <bits/stdc++.h>
using namespace std;

int main()
{
int len = 3;
int i = 0;
int temp = 0;
int numbers[len];

do
{
    //imprime en pantalla que para ingresar los numeros
    cout << "Enter your number " << i << " : ";
    //Para ingresar los numeros
    cin >> numbers[i];
    //incrementa la variable
    i++;
}while(i < len);

for(int j = 0; j < len; j++)
{
    for(int k = j + 1; k < len; k++)
    {
        if(numbers[j] > numbers[k])
        {
            temp = numbers[j];
            numbers[j] = numbers[k];
            numbers[k] = temp;
        }
    }
}

i = 0;
do
{
    cout<< "Number " << i << ": " << numbers[i] << "\n";
    i++;
}while(i < len);

return 0;

}
//please convert it c++ to c

#include
#include <stdlib.h>
#include <time.h>
using namespace std;
int main()
{
int i, j = 0, k;
int arr [8] [8];
srand(time(NULL));
for (i = 0; i < 8; i++) {
for (j = 0; j < 8; j++) {
arr[i] [j] = rand() % 10 - 5;
cout << arr [i] [j] << " ";
}
cout << endl;
}
int index_str=0, index_stb=0;
int kol = 0;
for (k = 0; k < 8; k++)
{
if(arr[k][j]==arr[i][k])
kol++;
index_str = i;
index_stb = j;
}
cout << "index odnakovoi strichky: "<<index_str << endl;
cout << "index odnakovogo stovchika:"<<index_stb << endl;
system ("pause");
return 0;
}

please convert c++ to c

#include <bits/stdc++.h>
using namespace std;
#define ll long long
bool operand(string x)
{
if(x=="+")
{
return false;
}
else if(x=="-")
{
return false;
}
else if(x=="*")
{
return false;
}
else if(x=="/")
{
return false;
}
else if(x=="^")
{
return false;
}
else
{
return true;
}
}

int main() {
string b;
cin>>b;
int len=0;
// cout<<b.length()<<endl;
for(int i=0;i<b.length();i++)
{
if(b[i]==',')
{
continue;
}
else
{
len++;
}
}
string a[len];
ll j=0;
ll cnt=0;
ll store=0;
for(int i=0;i<b.length();i++)
{
if(b[i]==',')
{ store=i;
//cout<<store<<endl;
for(int k=j;k<i;k++)
{
a[cnt]+=b[k];
// cout<<a[cnt]<<" ";
//cout<<b[k]<<endl;
}
cnt++;
j=i+1;
// cout<<j<<endl;
}
}
// cout<<store<<endl;
for(int f=store+1;f<b.length();f++);
{
a[cnt]+=b[j];

}
//a[cnt+1]=b[]
// cout<<a[0]<<endl;
// cout<<cnt<<len<<endl;
// for(int i=0;i<=cnt;i++)
// {
// cout<<a[i]<<" ";
// }
stacks;
for(int i=0;i<=cnt;i++)
{
if(operand(a[i])==true)
{ string d=(1,a[i]);
// cout<<d<<endl;
s.push(d);
// cout<<s.top()<<endl;
}
else
{
string op1=s.top();
// cout<<s.top()<<endl;
s.pop();
// string op1=s.top();
// cout<<s.top()<<endl;
if(s.empty())
{ // cout<<"d"<<endl;
//break;
string e="("+op1+a[i]+")";
s.push(e);
}
else
{
string op2=s.top();
s.pop();
string e="("+op2+a[i]+op1+")";
// cout<<"("+op2+a[i]+op1+")"<<endl;
s.push(e);
}

   	// cout<<op2<<" "<<op1<<endl;
  // 	 cout<<op2<<endl;
   }
}

cout<<s.top()<<endl;
stacks1;
for(int i=0;i<=cnt;i++)
{
if(operand(a[i]))
{
s1.push(stoi(a[i]));
}
else
{
if(a[i]=="+")
{
int val1=s1.top();
s1.pop();
int val2=s1.top();
s1.pop();
s1.push(val2+val1);
}
else if(a[i]=="-")
{
int val1=s1.top();
s1.pop();
int val2=s1.top();
s1.pop();
s1.push(val2-val1);
}
else if(a[i]=="")
{
int val1=s1.top();
s1.pop();
int val2=s1.top();
s1.pop();
s1.push(val2val1);
}
else if(a[i]=="/")
{
double val1=s1.top();
s1.pop();
double val2=s1.top();
s1.pop();
cout<<setprecision(3);
double val3=val2/val1;
// cout<<val3<<endl;
// double rounded = (int)(val3 * 100.0)/100.0;
// cout<<rounded<<endl;
s1.push(val3);
}
else if(a[i]=="^")
{
int val1=s1.top();
s1.pop();
s1.push(val1*val1);
}

}
}
cout<<s1.top()<<endl;

}

// C++ code to find unicolored paths
#include <bits/stdc++.h>
using namespace std;

const int MAX_V = 100;

int color[MAX_V];
bool vis[MAX_V];

// Graph class represents an undirected graph
// using adjacency list representation
class Graph
{
// vertices, edges, adjancy list
int V;
int E;
vector<pair<int, int> > adj[MAX_V];

// function used by UniColorPaths
// DFS traversal o from x to y
void dfs(int x, int y, int z);

// Constructor
public:
Graph(int V, int E);

// function to add an edge to graph
void addEdge(int v, int w, int z);

// finds paths between a and b having
// same color edges
int UniColorPaths(int a, int b);

};

Graph::Graph(int V, int E)
{
this -> V = V;
this -> E = E;
}

void Graph::addEdge(int a, int b, int c)
{
adj[a].push_back({b, c}); // Add b to a’s list.
adj[b].push_back({a, c}); // Add c to b’s list.
}

void Graph::dfs(int x, int y, int col)
{
if (vis[x])
return;
vis[x] = 1;

// mark this as a possible color to reach s to d
if (x == y)
{
	color[col] = 1;
	return;
}

// if the next edge is also of same color
for (int i = 0; i < int(adj[x].size()); i++)
	if (adj[x][i].second == col)
		dfs(adj[x][i].first, y, col);

}

// function that finds paths between a and b
// such that all edges are same colored
// It uses recursive dfs()
int Graph::UniColorPaths(int a, int b)
{

// dfs on nodes directly connected to source
for (int i = 0; i < int(adj[a].size()); i++)
{
	dfs(a, b, adj[a][i].second);

	// to visit again visited nodes
	memset(vis, 0, sizeof(vis));
}

int cur = 0;
for (int i = 0; i <= E; i++)
	cur += color[i];

return (cur);

}

// driver code
int main()
{
// Create a graph given in the above diagram
Graph g(5, 7);
g.addEdge(1, 2, 1);
g.addEdge(1, 3, 2);
g.addEdge(2, 3, 3);
g.addEdge(2, 4, 2);
g.addEdge(2, 5, 4);
g.addEdge(3, 5, 3);
g.addEdge(4, 5, 2);

int s = 2; // source
int d = 5; // destination

cout << "Number of unicolored paths : ";
cout << g.UniColorPaths(s, d) << endl;
return 0;

}

#include
#include
#include
#include
using namespace std;

int main(){
int n;
vectorarray,ed;
for(int i=0;i<9;i++){
cin>>n;
array.push_back(n);
}

for(int i =1;i<9;i++){
    ed.push_back(i);
}
ed.push_back(0);

ma[array]=1;
q.push(array);
while(!q.empty()){
    vector<int>x;
    x=q.front();
    int time=ma[x],pos=0;
    q.pop();

    while(x[pos])pos++;

    if(pos-3>=0){//上
        swap(x[pos],x[pos-3]);
        if(!ma[x]){
            q.push(x);
            ma[x]=time+1;
        }
        if(x==ed)break;
        swap(x[pos],x[pos-3]);
    }
    if(pos+3<9){//下
        swap(x[pos],x[pos+3]);
        if(!ma[x]){
            q.push(x);
            ma[x]=time+1;
        }
        if(x==ed)break;
        swap(x[pos],x[pos+3]);
    }
    if(pos%3!=0){//左
        swap(x[pos],x[pos-1]);
        if(!ma[x]){
            q.push(x);
            ma[x]=time+1;
        }
        if(x==ed)break;
        swap(x[pos],x[pos-1]);
    }
    if(pos%3!=2){//右
        swap(x[pos],x[pos+1]);
        if(!ma[x]){
            q.push(x);
            ma[x]=time+1;
        }
        if(x==ed)break;
        swap(x[pos],x[pos+1]);
    }
}   
if(ma[ed]==0){
    printf("impossible");
}
else{
    cout<<ma[ed]-1<<endl;
}

}

#include
#include
using namespace std;
enum COLOR { RED, BLACK };
class Node {
public:
int val; COLOR color; Node *left, *right, *parent;
Node(int val) : val(val) { parent = left = right = NULL; color = RED; }
Node *uncle() { if (parent == NULL or parent->parent == NULL) return NULL; if (parent->isOnLeft()) return parent->parent->right; else return parent->parent->left; }
bool isOnLeft() { return this == parent->left; }
Node *sibling() { if (parent == NULL) return NULL; if (isOnLeft()) return parent->right; return parent->left; }
void moveDown(Node *nParent) { if (parent != NULL) { if (isOnLeft()) { parent->left = nParent; } else { parent->right = nParent; } } nParent->parent = parent; parent = nParent; }
bool hasRedChild() { return (left != NULL and left->color == RED) or (right != NULL and right->color == RED); }
};
class RBTree {
Node *root;
void leftRotate(Node *x) { Node *nParent = x->right; if (x == root) root = nParent; x->moveDown(nParent); x->right = nParent->left; if (nParent->left != NULL) nParent->left->parent = x; nParent->left = x; }
void rightRotate(Node *x) { Node *nParent = x->left; if (x == root) root = nParent; x->moveDown(nParent); x->left = nParent->right; if (nParent->right != NULL) nParent->right->parent = x; nParent->right = x; }
void swapColors(Node *x1, Node *x2) { COLOR temp; temp = x1->color; x1->color = x2->color; x2->color = temp; }
void swapValues(Node *u, Node *v) { int temp; temp = u->val; u->val = v->val; v->val = temp; }
void fixRedRed(Node *x) { if (x == root) { x->color = BLACK; return; } Node *parent = x->parent, *grandparent = parent->parent, *uncle = x->uncle();
if (parent->color != BLACK) { if (uncle != NULL && uncle->color == RED) { parent->color = BLACK; uncle->color = BLACK; grandparent->color = RED; fixRedRed(grandparent); } else {
if (parent->isOnLeft()) { if (x->isOnLeft()) { swapColors(parent, grandparent); } else { leftRotate(parent); swapColors(x, grandparent); } rightRotate(grandparent); }
else { if (x->isOnLeft()) { rightRotate(parent); swapColors(x, grandparent); } else { swapColors(parent, grandparent); } leftRotate(grandparent); } } } }
Node *successor(Node *x) { Node *temp = x; while (temp->left != NULL) temp = temp->left; return temp; }
Node BSTreplace(Node x) { if (x->left != NULL and x->right != NULL) return successor(x->right); if (x->left == NULL and x->right == NULL) return NULL; if (x->left != NULL) return x->left; else return x->right; }
void deleteNode(Node v) { /... truncated for brevity .../}
void fixDoubleBlack(Node x) { /... truncated for brevity .../}
void levelOrder(Node *x) { if (x == NULL) return; queue<Node *> q; Node *curr; q.push(x); while (!q.empty()) { curr = q.front(); q.pop(); cout << curr->val << " "; if (curr->left != NULL) q.push(curr->left); if (curr->right != NULL) q.push(curr->right); } }
void inorder(Node *x) { if (x == NULL) return; inorder(x->left); cout << x->val << " "; inorder(x->right); }
public:
RBTree() { root = NULL; }
Node *getRoot() { return root; }
Node *search(int n) { Node *temp = root; while (temp != NULL) { if (n < temp->val) { if (temp->left == NULL) break; else temp = temp->left; } else if (n == temp->val) break; else { if (temp->right == NULL) break; else temp = temp->right; } } return temp; }
void insert(int n) { Node *newNode = new Node(n); if (root == NULL) { newNode->color = BLACK; root = newNode; } else { Node *temp = search(n); if (temp->val == n) return; if (n < temp->val) temp->left = newNode; else temp->right = newNode; newNode->parent = temp; fixRedRed(newNode); }
}
void deleteByVal(int n) { if (root == NULL) return; Node *v = search(n), *u = BSTreplace(v); bool uvBlack = ((u == NULL or u->color == BLACK) and (v->color == BLACK)); Node *parent = v->parent; if (u == NULL) { if (v == root) root = NULL; else { if (uvBlack) { fixDoubleBlack(v); } else { if (v->sibling() != NULL) v->sibling()->color = RED; } if (v->isOnLeft()) parent->left = NULL; else parent->right = NULL; } delete v; return; } if (v->left == NULL or v->right == NULL) { if (v == root) { v->val = u->val; v->left = v->right = NULL; delete u; } else { if (v->isOnLeft()) parent->left = u; else parent->right = u; delete v; u->parent = parent; if (uvBlack) fixDoubleBlack(u); else u->color = BLACK; } return; } swapValues(u, v); delete u; }
void printInOrder() { cout << "Inorder: "; inorder(root); cout << endl; }
void printLevelOrder() { cout << "Level order: "; levelOrder(root); cout << endl; }
};
int main() {
RBTree tree; tree.insert(7); tree.insert(3); tree.insert(18); tree.insert(10); tree.insert(22); tree.insert(8); tree.insert(11); tree.insert(26); tree.insert(2); tree.insert(6); tree.insert(13); tree.printInOrder(); tree.printLevelOrder(); return 0;
}

#include
#include
using namespace std;
enum COLOR { RED, BLACK };
class Node {
public:
int val; COLOR color; Node *left, *right, *parent;
Node(int val) : val(val) { parent = left = right = NULL; color = RED; }
Node *uncle() { if (parent == NULL or parent->parent == NULL) return NULL; if (parent->isOnLeft()) return parent->parent->right; else return parent->parent->left; }
bool isOnLeft() { return this == parent->left; }
Node *sibling() { if (parent == NULL) return NULL; if (isOnLeft()) return parent->right; return parent->left; }
void moveDown(Node *nParent) { if (parent != NULL) { if (isOnLeft()) { parent->left = nParent; } else { parent->right = nParent; } } nParent->parent = parent; parent = nParent; }
bool hasRedChild() { return (left != NULL and left->color == RED) or (right != NULL and right->color == RED); }
};
class RBTree {
Node *root;
void leftRotate(Node *x) { Node *nParent = x->right; if (x == root) root = nParent; x->moveDown(nParent); x->right = nParent->left; if (nParent->left != NULL) nParent->left->parent = x; nParent->left = x; }
void rightRotate(Node *x) { Node *nParent = x->left; if (x == root) root = nParent; x->moveDown(nParent); x->left = nParent->right; if (nParent->right != NULL) nParent->right->parent = x; nParent->right = x; }
void swapColors(Node *x1, Node *x2) { COLOR temp; temp = x1->color; x1->color = x2->color; x2->color = temp; }
void swapValues(Node *u, Node *v) { int temp; temp = u->val; u->val = v->val; v->val = temp; }
void fixRedRed(Node *x) { if (x == root) { x->color = BLACK; return; } Node *parent = x->parent, *grandparent = parent->parent, *uncle = x->uncle();
if (parent->color != BLACK) { if (uncle != NULL && uncle->color == RED) { parent->color = BLACK; uncle->color = BLACK; grandparent->color = RED; fixRedRed(grandparent); } else {
if (parent->isOnLeft()) { if (x->isOnLeft()) { swapColors(parent, grandparent); } else { leftRotate(parent); swapColors(x, grandparent); } rightRotate(grandparent); }
else { if (x->isOnLeft()) { rightRotate(parent); swapColors(x, grandparent); } else { swapColors(parent, grandparent); } leftRotate(grandparent); } } } }
Node *successor(Node *x) { Node *temp = x; while (temp->left != NULL) temp = temp->left; return temp; }
Node BSTreplace(Node x) { if (x->left != NULL and x->right != NULL) return successor(x->right); if (x->left == NULL and x->right == NULL) return NULL; if (x->left != NULL) return x->left; else return x->right; }
void deleteNode(Node v) { /... truncated for brevity .../}
void fixDoubleBlack(Node x) { /... truncated for brevity .../}
void levelOrder(Node *x) { if (x == NULL) return; queue<Node *> q; Node *curr; q.push(x); while (!q.empty()) { curr = q.front(); q.pop(); cout << curr->val << " "; if (curr->left != NULL) q.push(curr->left); if (curr->right != NULL) q.push(curr->right); } }
void inorder(Node *x) { if (x == NULL) return; inorder(x->left); cout << x->val << " "; inorder(x->right); }
public:
RBTree() { root = NULL; }
Node *getRoot() { return root; }
Node *search(int n) { Node *temp = root; while (temp != NULL) { if (n < temp->val) { if (temp->left == NULL) break; else temp = temp->left; } else if (n == temp->val) break; else { if (temp->right == NULL) break; else temp = temp->right; } } return temp; }
void insert(int n) { Node *newNode = new Node(n); if (root == NULL) { newNode->color = BLACK; root = newNode; } else { Node *temp = search(n); if (temp->val == n) return; if (n < temp->val) temp->left = newNode; else temp->right = newNode; newNode->parent = temp; fixRedRed(newNode); }
}
void deleteByVal(int n) { if (root == NULL) return; Node *v = search(n), *u = BSTreplace(v); bool uvBlack = ((u == NULL or u->color == BLACK) and (v->color == BLACK)); Node *parent = v->parent; if (u == NULL) { if (v == root) root = NULL; else { if (uvBlack) { fixDoubleBlack(v); } else { if (v->sibling() != NULL) v->sibling()->color = RED; } if (v->isOnLeft()) parent->left = NULL; else parent->right = NULL; } delete v; return; } if (v->left == NULL or v->right == NULL) { if (v == root) { v->val = u->val; v->left = v->right = NULL; delete u; } else { if (v->isOnLeft()) parent->left = u; else parent->right = u; delete v; u->parent = parent; if (uvBlack) fixDoubleBlack(u); else u->color = BLACK; } return; } swapValues(u, v); delete u; }
void printInOrder() { cout << "Inorder: "; inorder(root); cout << endl; }
void printLevelOrder() { cout << "Level order: "; levelOrder(root); cout << endl; }
};
int main() {
RBTree tree; tree.insert(7); tree.insert(3); tree.insert(18); tree.insert(10); tree.insert(22); tree.insert(8); tree.insert(11); tree.insert(26); tree.insert(2); tree.insert(6); tree.insert(13); tree.printInOrder(); tree.printLevelOrder(); return 0;
}

#include
#include
using namespace std;

enum COLOR { RED, BLACK };

class Node {
public:
int val;
COLOR color;
Node *left, *right, *parent;

Node(int val) : val(val) {
parent = left = right = NULL;

// Node is created during insertion
// Node is red at insertion
color = RED;

}

// returns pointer to uncle
Node *uncle() {
// If no parent or grandparent, then no uncle
if (parent == NULL or parent->parent == NULL)
return NULL;

if (parent->isOnLeft())
// uncle on right
return parent->parent->right;
else
// uncle on left
return parent->parent->left;

}

// check if node is left child of parent
bool isOnLeft() { return this == parent->left; }

// returns pointer to sibling
Node *sibling() {
// sibling null if no parent
if (parent == NULL)
return NULL;

if (isOnLeft())
return parent->right;

return parent->left;

}

// moves node down and moves given node in its place
void moveDown(Node *nParent) {
if (parent != NULL) {
if (isOnLeft()) {
parent->left = nParent;
} else {
parent->right = nParent;
}
}
nParent->parent = parent;
parent = nParent;
}

bool hasRedChild() {
return (left != NULL and left->color == RED) or
(right != NULL and right->color == RED);
}
};

class RBTree {
Node *root;

// left rotates the given node
void leftRotate(Node *x) {
// new parent will be node's right child
Node *nParent = x->right;

// update root if current node is root
if (x == root)
root = nParent;

x->moveDown(nParent);

// connect x with new parent's left element
x->right = nParent->left;
// connect new parent's left element with node
// if it is not null
if (nParent->left != NULL)
nParent->left->parent = x;

// connect new parent with x
nParent->left = x;

}

void rightRotate(Node *x) {
// new parent will be node's left child
Node *nParent = x->left;

// update root if current node is root
if (x == root)
root = nParent;

x->moveDown(nParent);

// connect x with new parent's right element
x->left = nParent->right;
// connect new parent's right element with node
// if it is not null
if (nParent->right != NULL)
nParent->right->parent = x;

// connect new parent with x
nParent->right = x;

}

void swapColors(Node *x1, Node *x2) {
COLOR temp;
temp = x1->color;
x1->color = x2->color;
x2->color = temp;
}

void swapValues(Node *u, Node *v) {
int temp;
temp = u->val;
u->val = v->val;
v->val = temp;
}

// fix red red at given node
void fixRedRed(Node *x) {
// if x is root color it black and return
if (x == root) {
x->color = BLACK;
return;
}

// initialize parent, grandparent, uncle
Node *parent = x->parent, *grandparent = parent->parent,
	*uncle = x->uncle();

if (parent->color != BLACK) {
if (uncle != NULL && uncle->color == RED) {
	// uncle red, perform recoloring and recurse
	parent->color = BLACK;
	uncle->color = BLACK;
	grandparent->color = RED;
	fixRedRed(grandparent);
} else {
	// Else perform LR, LL, RL, RR
	if (parent->isOnLeft()) {
	if (x->isOnLeft()) {
		// for left right
		swapColors(parent, grandparent);
	} else {
		leftRotate(parent);
		swapColors(x, grandparent);
	}
	// for left left and left right
	rightRotate(grandparent);
	} else {
	if (x->isOnLeft()) {
		// for right left
		rightRotate(parent);
		swapColors(x, grandparent);
	} else {
		swapColors(parent, grandparent);
	}

	// for right right and right left
	leftRotate(grandparent);
	}
}
}

}

// find node that do not have a left child
// in the subtree of the given node
Node *successor(Node *x) {
Node *temp = x;

while (temp->left != NULL)
temp = temp->left;

return temp;

}

// find node that replaces a deleted node in BST
Node *BSTreplace(Node *x) {
// when node have 2 children
if (x->left != NULL and x->right != NULL)
return successor(x->right);

// when leaf
if (x->left == NULL and x->right == NULL)
return NULL;

// when single child
if (x->left != NULL)
return x->left;
else
return x->right;

}

// deletes the given node
void deleteNode(Node *v) {
Node *u = BSTreplace(v);

// True when u and v are both black
bool uvBlack = ((u == NULL or u->color == BLACK) and (v->color == BLACK));
Node *parent = v->parent;

if (u == NULL) {
// u is NULL therefore v is leaf
if (v == root) {
	// v is root, making root null
	root = NULL;
} else {
	if (uvBlack) {
	// u and v both black
	// v is leaf, fix double black at v
	fixDoubleBlack(v);
	} else {
	// u or v is red
	if (v->sibling() != NULL)
		// sibling is not null, make it red"
		v->sibling()->color = RED;
	}

	// delete v from the tree
	if (v->isOnLeft()) {
	parent->left = NULL;
	} else {
	parent->right = NULL;
	}
}
delete v;
return;
}

if (v->left == NULL or v->right == NULL) {
// v has 1 child
if (v == root) {
	// v is root, assign the value of u to v, and delete u
	v->val = u->val;
	v->left = v->right = NULL;
	delete u;
} else {
	// Detach v from tree and move u up
	if (v->isOnLeft()) {
	parent->left = u;
	} else {
	parent->right = u;
	}
	delete v;
	u->parent = parent;
	if (uvBlack) {
	// u and v both black, fix double black at u
	fixDoubleBlack(u);
	} else {
	// u or v red, color u black
	u->color = BLACK;
	}
}
return;
}

// v has 2 children, swap values with successor and recurse
swapValues(u, v);
deleteNode(u);

}

void fixDoubleBlack(Node *x) {
if (x == root)
// Reached root
return;

Node *sibling = x->sibling(), *parent = x->parent;
if (sibling == NULL) {
// No sibling, double black pushed up
fixDoubleBlack(parent);
} else {
if (sibling->color == RED) {
	// Sibling red
	parent->color = RED;
	sibling->color = BLACK;
	if (sibling->isOnLeft()) {
	// left case
	rightRotate(parent);
	} else {
	// right case
	leftRotate(parent);
	}
	fixDoubleBlack(x);
} else {
	// Sibling black
	if (sibling->hasRedChild()) {
	// at least 1 red children
	if (sibling->left != NULL and sibling->left->color == RED) {
		if (sibling->isOnLeft()) {
		// left left
		sibling->left->color = sibling->color;
		sibling->color = parent->color;
		rightRotate(parent);
		} else {
		// right left
		sibling->left->color = parent->color;
		rightRotate(sibling);
		leftRotate(parent);
		}
	} else {
		if (sibling->isOnLeft()) {
		// left right
		sibling->right->color = parent->color;
		leftRotate(sibling);
		rightRotate(parent);
		} else {
		// right right
		sibling->right->color = sibling->color;
		sibling->color = parent->color;
		leftRotate(parent);
		}
	}
	parent->color = BLACK;
	} else {
	// 2 black children
	sibling->color = RED;
	if (parent->color == BLACK)
		fixDoubleBlack(parent);
	else
		parent->color = BLACK;
	}
}
}

}

// prints level order for given node
void levelOrder(Node *x) {
if (x == NULL)
// return if node is null
return;

// queue for level order
queue<Node *> q;
Node *curr;

// push x
q.push(x);

while (!q.empty()) {
// while q is not empty
// dequeue
curr = q.front();
q.pop();

// print node value
cout << curr->val << " ";

// push children to queue
if (curr->left != NULL)
	q.push(curr->left);
if (curr->right != NULL)
	q.push(curr->right);
}

}

// prints inorder recursively
void inorder(Node *x) {
if (x == NULL)
return;
inorder(x->left);
cout << x->val << " ";
inorder(x->right);
}

public:
// constructor
// initialize root
RBTree() { root = NULL; }

Node *getRoot() { return root; }

// searches for given value
// if found returns the node (used for delete)
// else returns the last node while traversing (used in insert)
Node *search(int n) {
Node *temp = root;
while (temp != NULL) {
if (n < temp->val) {
if (temp->left == NULL)
break;
else
temp = temp->left;
} else if (n == temp->val) {
break;
} else {
if (temp->right == NULL)
break;
else
temp = temp->right;
}
}

return temp;

}

// inserts the given value to tree
void insert(int n) {
Node *newNode = new Node(n);
if (root == NULL) {
// when root is null
// simply insert value at root
newNode->color = BLACK;
root = newNode;
} else {
Node *temp = search(n);

if (temp->val == n) {
	// return if value already exists
	return;
}

// if value is not found, search returns the node
// where the value is to be inserted

// connect new node to correct node
newNode->parent = temp;

if (n < temp->val)
	temp->left = newNode;
else
	temp->right = newNode;

// fix red red violation if exists
fixRedRed(newNode);
}

}

// utility function that deletes the node with given value
void deleteByVal(int n) {
if (root == NULL)
// Tree is empty
return;

Node *v = search(n), *u;

if (v->val != n) {
cout << "No node found to delete with value:" << n << endl;
return;
}

deleteNode(v);

}

// prints inorder of the tree
void printInOrder() {
cout << "Inorder: " << endl;
if (root == NULL)
cout << "Tree is empty" << endl;
else
inorder(root);
cout << endl;
}

// prints level order of the tree
void printLevelOrder() {
cout << "Level order: " << endl;
if (root == NULL)
cout << "Tree is empty" << endl;
else
levelOrder(root);
cout << endl;
}
};

int main() {
RBTree tree;

tree.insert(7);
tree.insert(3);
tree.insert(18);
tree.insert(10);
tree.insert(22);
tree.insert(8);
tree.insert(11);
tree.insert(26);
tree.insert(2);
tree.insert(6);
tree.insert(13);

tree.printInOrder();
tree.printLevelOrder();

cout<<endl<<"Deleting 18, 11, 3, 10, 22"<<endl;

tree.deleteByVal(18);
tree.deleteByVal(11);
tree.deleteByVal(3);
tree.deleteByVal(10);
tree.deleteByVal(22);

tree.printInOrder();
tree.printLevelOrder();
return 0;
}