doublench21

//
//  rbtree.h
//  rbtreee
//
//  Created by Lutfullin Ruslan on 23.04.15.
//  Copyright (c) 2015 Ruslan Lutfullin. All rights reserved.
//

#ifndef __rbtreee__rbtree__
#define __rbtreee__rbtree__

#include <stdio.h>

enum color { RED, BLACK };

class Node {
public:
  int data;
  color color;
  Node *left;
  Node *right;
  Node *parrent;

public:
  Node(int data)
      : left(NULL), right(NULL), parrent(NULL), color(RED), data(data){};

  virtual ~Node(){};

public:
  friend class RBtree;
};

class RBtree {
public:
  Node *root;
  Node *NIL;

public:
  RBtree();
  virtual ~RBtree();

public:
  void tree_insert(Node *n);
  void left_rotate(Node *n);
  void right_rotate(Node *n);
  void rb_insert(Node *n);
  Node *rb_delete(Node *n);
  void rb_delete_fixup(Node *n);
  Node *tree_successor(Node *n);
  Node *tree_predecessor(Node *n);
  void inorder_tree_walk(Node *n);
  Node *iterative_tree_search(Node *n, int data);
  Node *tree_minimum(Node *n);
  Node *tree_maximum(Node *n);

  class Iterator {};
};

#endif /* defined(__rbtreee__rbtree__) */

//
//  rbtree.cpp
//  rbtreee
//
//  Created by Lutfullin Ruslan on 23.04.15.
//  Copyright (c) 2015 Ruslan Lutfullin. All rights reserved.
//

#include "rbtree.h"
#include <iostream>

RBtree::RBtree() {
  this->NIL = new Node(-1);
  this->NIL->color = BLACK;
  this->NIL->left = this->NIL->right = this->NIL->parrent = this->NIL;

  this->root = this->NIL;
  this->root->color = BLACK;
}

RBtree::~RBtree() { delete this->root; }

void RBtree::inorder_tree_walk(Node *n) {
  if (n != this->NIL) {
    this->inorder_tree_walk(n->left);
    std::cout << n->data << " ";
    this->inorder_tree_walk(n->right);
  }
}

Node *RBtree::iterative_tree_search(Node *n, int data) {
  while (n != this->NIL && data != n->data) {
    if (data < n->data) {
      n = n->left;
    } else {
      n = n->right;
    }
  }
  return n;
}

Node *RBtree::tree_minimum(Node *n) {
  while (n->left != this->NIL) {
    n = n->left;
  }
  return n;
}

Node *RBtree::tree_maximum(Node *n) {
  while (n->right != this->NIL) {
    n = n->right;
  }
  return n;
}

Node *RBtree::tree_successor(Node *n) {
  if (n->right != this->NIL) {
    return this->tree_minimum(n->right);
  }
  Node *y = n->parrent;
  while (y != this->NIL && n == y->right) {
    n = y;
    y = y->parrent;
  }
  return y;
}

Node *RBtree::tree_predecessor(Node *n) {
  if (n->left != this->NIL) {
    return this->tree_minimum(n->left);
  }
  Node *y = n->parrent;
  while (y != this->NIL && n == y->left) {
    n = y;
    y = y->parrent;
  }
  return y;
}

void RBtree::tree_insert(Node *z) {
  Node *y = this->NIL, *x = this->root;
  while (x != this->NIL) {
    y = x;
    if (z->data < x->data)
      x = x->left;
    else
      x = x->right;
  }
  z->parrent = y;
  if (y == this->NIL) {
    this->root = z;
  } else {
    if (z->data < y->data) {
      y->left = z;
    } else {
      y->right = z;
    }
  }
}

void RBtree::left_rotate(Node *x) {
  Node *y;
  y = x->right;
  x->right = y->left;
  if (y->left != this->NIL) {
    y->left->parrent = x;
  }
  y->parrent = x->parrent;
  if (x->parrent == this->NIL) {
    this->root = y;
  } else {
    if (x == x->parrent->left) {
      x->parrent->left = y;
    } else {
      x->parrent->right = y;
    }
  }
  y->left = x;
  x->parrent = y;
}

void RBtree::right_rotate(Node *y) {
  Node *x;
  x = y->left;
  y->left = x->right;
  if (x->right != this->NIL) {
    x->right->parrent = y;
  }
  x->parrent = y->parrent;
  if (y->parrent == this->NIL) {
    this->root = x;
  } else {
    if (y == y->parrent->left) {
      y->parrent->left = x;
    } else {
      y->parrent->right= x;
    }
  }
  x->right = y;
  y->parrent = x;
}

void RBtree::rb_insert(Node *z) {

  this->tree_insert(z);
  Node *y;
  z->left = z->right = this->NIL;
  z->color = RED;
  while (z != this->root && z->parrent->color == RED) {
    if (z->parrent == z->parrent->parrent->left) {
      y = z->parrent->parrent->right;
      if (y->color == RED) {
        z->parrent->color = BLACK;
        y->color = BLACK;
        z->parrent->parrent->color = RED;
        z = z->parrent->parrent;
      } else {
        if (z == z->parrent->right) {
          z = z->parrent;
          this->left_rotate(z);
        }
        z->parrent->color = BLACK;
        z->parrent->parrent->color = RED;
        this->right_rotate(z->parrent->parrent);
      }
    } else {
      y = z->parrent->parrent->left;
      if (y->color == RED) {
        z->parrent->color = BLACK;
        y->color = BLACK;
        z->parrent->parrent->color = RED;
        z = z->parrent->parrent;
      } else {
        if (z == z->parrent->left) {
          z = z->parrent;
          this->right_rotate(z);
        }
        z->parrent->color = BLACK;
        z->parrent->parrent->color = RED;
        this->left_rotate(z->parrent->parrent);
      }
    }
  }
  this->root->color = BLACK;
}

Node *RBtree::rb_delete(Node *z) {
  Node *x, *y;
  if (z->left == this->NIL || z->right == this->NIL) {
    y = z;
  } else {
    y = this->tree_successor(z);
  }
  if (y->left != this->NIL) {
    x = y->left;
  } else {
    x = y->right;
  }
  x->parrent = y->parrent;
  if (y->parrent == this->NIL) {
    this->root = x;
  } else {
    if (y == y->parrent->left) {
      y->parrent->left = x;
    } else {
      y->parrent->right = x;
    }
  }
  if (y != z) {
    z->data = y->data;
  }
  if (y->color == BLACK) {
    this->rb_delete_fixup(x);
  }
  return y;
}

void RBtree::rb_delete_fixup(Node *x) {
  Node *w;
  while (x != this->root && x->color == BLACK) {
    if (x == x->parrent->left) {
      w = x->parrent->right;
      if (w->color == RED) {
        w->color = BLACK;
        x->parrent->color = RED;
        this->left_rotate(x->parrent);
        w = x->parrent->right;
      }
      if (w->left->color == BLACK && w->right->color == BLACK) {
        w->color = RED;
        x = x->parrent;
      } else {
        if (w->right->color == BLACK) {
          w->left->color = BLACK;
          w->color = RED;
          this->right_rotate(w);
          w = x->parrent->right;
        }
        w->color = x->parrent->color;
        x->parrent->color = BLACK;
        w->right->color = BLACK;
        this->left_rotate(x->parrent);
        x = this->root;
      }
    } else {
      w = x->parrent->left;
      if (w->color == RED) {
        w->color = BLACK;
        x->parrent->color = RED;
        this->left_rotate(x->parrent);
        w = x->parrent->left;
      }
      if (w->right->color == BLACK && w->left->color == BLACK) {
        w->color = RED;
        x = x->parrent;
      } else {
        if (w->left->color == BLACK) {
          w->right->color = BLACK;
          w->color = RED;
          this->right_rotate(w);
          w = x->parrent->left;
        }
        w->color = x->parrent->color;
        x->parrent->color = BLACK;
        w->left->color = BLACK;
        this->left_rotate(x->parrent);
        x = this->root;
      }
    }
  }
  x->color = BLACK;
}

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>

int main(int argc, char const *argv[])
{
    int fd[2], fork_status1, fork_status2;
    char buff[20], str_[32];


    if(pipe(fd) == -1) {
        fprintf(stderr, "pipe - error!\n");
        exit(-1);
    } else {
        fork_status1 = fork();
        if(fork_status1 == -1) {
            fprintf(stderr, "fork1 - error!\n");
            exit(-2);
        } else if(fork_status1 == 0) {
            fork_status2 = fork();

            if(fork_status2 == -1) {
                fprintf(stderr, "fork2 - error!\n");
                exit(-2);
            } else if(fork_status2 == 0) { // Child process(2)
                printf("Write smth(2)...\n");
                while(strcmp(str_, "exit")) {
                    fgets(str_, 30, stdin);
                    write(fd[1], str_, strlen(str_));
                }
                exit(0);
            } else { // Child process(1)
                printf("Write smth(1)...\n");
                while(strcmp(str_, "exit")) {
                    fgets(str_, 30, stdin);
                    printf("%s", str_);  //<-----------------------------------
                    write(fd[1], str_, strlen(str_));
                }
                exit(0);
            }

        } else { // Parent process
            while(strcmp(buff, "exit")) {
                read(fd[0], buff, strlen(str_));
                if(strcmp(buff, "exit")) {
                    //printf("%s\n", buff);
                }
            }
            close(fd[0]);
            close(fd[1]);
            exit(0);
        }
    }


    return 0;
}