Avl.h
 
//-------------------------------------------------------------------------------------------------------------
//-------------------------------------------------------------------------------------------------------------
class cUser; // Add a class to store
 
typedef cUser* element;
 
struct AVL_Node 
{   
  int key;
  element data;
  AVL_Node      *parent,
  *left, 
  *right;
 
  AVL_Node()
  {
    left = right = parent = NULL;
  }
 
  char factor; //byte
};
//-------------------------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------------------------- s
class AVL_Tree 
{
public:
  AVL_Tree();
  void insert(int key);
  void erase(int key);
  element find(int key);  
  void dfs();   
  int size;
  inline int height(AVL_Node * pos) const;  
  AVL_Node *root;   
 
private:
protected:  
  AVL_Node *tmp;   
  AVL_Node *K1, *K2, *K3, *newnode;   
  cUser * tmpdata;
  bool h;
 
  inline int max(int a, int b) const;
 
  AVL_Node * singleRotateLeft(AVL_Node *K2);
  AVL_Node * singleRotateRight(AVL_Node *K2);
 
  AVL_Node * doubleRotateLeft(AVL_Node *K2);
  AVL_Node * doubleRotateRight(AVL_Node *K2);
 
  AVL_Node * _insert(int key, AVL_Node * node);
  AVL_Node * _erase(int key, AVL_Node * node);
  void _dfs(AVL_Node * v) const;
};
 
Avl.cpp
 
#include <cstdio>
#include <iostream>
#include "Avl.h"
//-------------------------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------------------------- 
AVL_Tree::AVL_Tree()
{
  size=0;
 
  root=NULL;
}
//-------------------------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------------------------- 
element AVL_Tree::find(int key)
{
  if(size==0)
    return NULL;
  tmp=root;
  while(tmp!=NULL)
  {
    if(key<tmp->key)
      tmp=tmp->left;
    else if(key>tmp->key)
      tmp=tmp->right;
    else 
      return tmp->data;
  }
  return NULL;
}
//-------------------------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------------------------- 
inline int AVL_Tree::height( AVL_Node * pos ) const
{
  if( pos == NULL )
    return -1;
  else
    return pos->factor;
}
//-------------------------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------------------------- 
inline int AVL_Tree::max( int a, int b ) const
{
  return a > b ? a : b;
}
//-------------------------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------------------------- 
AVL_Node * AVL_Tree::singleRotateLeft(AVL_Node *K2)
{
  K1 = K2->left;
  K2->left = K1->right;
  K1->right = K2;
 
  K2->factor = max(height(K2->left), height(K2->right))+1;
  K1->factor = max(height(K1->left), K2->factor)+1;
 
 
  return K1;  // new root
}   
//-------------------------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------------------------- 
AVL_Node * AVL_Tree::singleRotateRight(AVL_Node *K1)
{
  K2 = K1->right;
  K1->right = K2->left;
  K2->left = K1;
 
  K1->factor = max(height(K1->left), height(K1->right))+1;
  K2->factor = max(height(K2->right), K1->factor)+1;
 
 
  return K2;  // new root
}   
//-------------------------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------------------------- 
AVL_Node * AVL_Tree::doubleRotateLeft(AVL_Node *K3)
{
  K3->left = singleRotateRight(K3->left);
 
  return singleRotateLeft(K3);
}   
//-------------------------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------------------------- 
AVL_Node * AVL_Tree::doubleRotateRight(AVL_Node *K1)
{
  K1->right = singleRotateLeft(K1->right);
 
  return singleRotateRight(K1);
}   
//-------------------------------------------------------------------------------------------------------------
//-------------------------------------------------------------------------------------------------------------     
void AVL_Tree::insert(int key)
{
  size++;
  root=_insert(key,root);
}     
//-------------------------------------------------------------------------------------------------------------
//-------------------------------------------------------------------------------------------------------------     
AVL_Node * AVL_Tree::_insert(int key, AVL_Node * node)
{
  if (node==NULL)
  {
    node = new AVL_Node;
    node->factor=0;
    node->key=key;
    node->data=tmpdata;
    node->left=NULL;
    node->right=NULL;
  }
  else if(key < node->key)
  {
    node->left= _insert(key,node->left);
    if(height(node->left) - height(node->right) == 2)
    {
      if(key < node->left->key)
        node = singleRotateLeft(node);
      else
        node = doubleRotateLeft(node);
    }
  }      
  else if(key > node->key)      
  {
    node->right= _insert(key,node->right);
    if(height(node->right) - height(node->left) == 2)
    {
      if(key > node->right->key)
        node = singleRotateRight(node);
      else              
        node = doubleRotateRight(node);         
    }
  }  
  node->factor = max(height(node->left ),height(node->right))+1;
  return node;
 
}
//-------------------------------------------------------------------------------------------------------------
//-------------------------------------------------------------------------------------------------------------     
void AVL_Tree::erase(int key)
{
  root=_erase(key,root);
}
//-------------------------------------------------------------------------------------------------------------
//-------------------------------------------------------------------------------------------------------------
AVL_Node * AVL_Tree::_erase(int key, AVL_Node * node)
{
  bool done=false;
  if (node==NULL) 
  {   
    h=false;  
    done=true;
  }
  else
    if (key < node->key) //delee from left subtree  
    {
      newnode=_erase(key,node->left);
      node->left=newnode;
      if(h)
      {
        if(height(node->right) - height(node->left) == 2)
        {
          if(height(node->right) > height(node->left))
            node = singleRotateLeft(node);
          else              
            node = singleRotateRight(node);         
        }
 
        node->factor = max(height(node->left ),height(node->right))+1;
 
 
        //          if (node->factor >= 0)
        //                  {
        //                     node->factor=root->factor-1;
        //                 if (node->factor==-1)
        //                      h=false;
        //                  }
        //                  else if (node->right->factor==-1)
        //                      singleRotateRight(node); 
        //                  else 
        //                      singleRotateLeft(node);                     
 
        done=true;      
        return node;
      }
 
 
    }
    else if (key == node->key) //del node
    {
      if (node->left==NULL || node->right==NULL)  // one or no children 
      {
        if (node->left == NULL) 
          K1=node->right;
        else 
          K1=node->left;
 
        delete node;
 
        h=true; done=true;
 
        return(K1);                         
 
      }
      else // both of children
      {
        K2=node->right;
        while (K2->left != NULL) 
          K2=K2->left;
 
        node->key=K2->key;
        key=node->key;
      }
    }
 
  if (!done && key >= node->key) // delete from right subtree 
  {
    newnode=_erase(key, node->right);
    node->right=newnode;
    if (h)
    {               
      if(height(node->right) - height(node->left) == 2)
      {
        if(height(node->right) > height(node->left))
          node = singleRotateLeft(node);
        else                
          node = singleRotateRight(node);           
      }
      node->factor = max(height(node->left ),height(node->right))+1;
      //
      /*                if (node->factor <= 0) 
            {
                node->factor=node->factor+1;
                if (node->factor ==1) 
                  h=false;
            }   
            else if (node->right->factor==1) 
              singleRotateLeft(node);
            else                
                singleRotateRight(node);*/
      return node;
    }
  }
 
 
}
//-------------------------------------------------------------------------------------------------------------
//-------------------------------------------------------------------------------------------------------------     
void AVL_Tree::dfs()
{
  _dfs(root);
}
//-------------------------------------------------------------------------------------------------------------
//-------------------------------------------------------------------------------------------------------------     
void AVL_Tree::_dfs(AVL_Node * v) const
{
 
 
  if(v->left!=NULL)
    _dfs(v->left);
 
  std::cout << v->key << std::endl; 
  if(v->right!=NULL)
    _dfs(v->right); 
}
//-------------------------------------------------------------------------------------------------------------
//---------------------------------

CkF2bC5oCgovLy0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KLy8tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCmNsYXNzIGNVc2VyOyAvLyBBZGQgYSBjbGFzcyB0byBzdG9yZQoKdHlwZWRlZiBjVXNlciogZWxlbWVudDsKCnN0cnVjdCBBVkxfTm9kZSAKeyAgIAogIGludCBrZXk7CiAgZWxlbWVudCBkYXRhOwogIEFWTF9Ob2RlICAgICAgKnBhcmVudCwKICAqbGVmdCwgCiAgKnJpZ2h0OwoKICBBVkxfTm9kZSgpCiAgewogICAgbGVmdCA9IHJpZ2h0ID0gcGFyZW50ID0gTlVMTDsKICB9CgogIGNoYXIgZmFjdG9yOyAvL2J5dGUKfTsKLy8tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCi8vLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLSBzCmNsYXNzIEFWTF9UcmVlIAp7CnB1YmxpYzoKICBBVkxfVHJlZSgpOwogIHZvaWQgaW5zZXJ0KGludCBrZXkpOwogIHZvaWQgZXJhc2UoaW50IGtleSk7CiAgZWxlbWVudCBmaW5kKGludCBrZXkpOyAgCiAgdm9pZCBkZnMoKTsgICAKICBpbnQgc2l6ZTsKICBpbmxpbmUgaW50IGhlaWdodChBVkxfTm9kZSAqIHBvcykgY29uc3Q7ICAKICBBVkxfTm9kZSAqcm9vdDsgICAKCnByaXZhdGU6CnByb3RlY3RlZDogIAogIEFWTF9Ob2RlICp0bXA7ICAgCiAgQVZMX05vZGUgKksxLCAqSzIsICpLMywgKm5ld25vZGU7ICAgCiAgY1VzZXIgKiB0bXBkYXRhOwogIGJvb2wgaDsKCiAgaW5saW5lIGludCBtYXgoaW50IGEsIGludCBiKSBjb25zdDsKCiAgQVZMX05vZGUgKiBzaW5nbGVSb3RhdGVMZWZ0KEFWTF9Ob2RlICpLMik7CiAgQVZMX05vZGUgKiBzaW5nbGVSb3RhdGVSaWdodChBVkxfTm9kZSAqSzIpOwoKICBBVkxfTm9kZSAqIGRvdWJsZVJvdGF0ZUxlZnQoQVZMX05vZGUgKksyKTsKICBBVkxfTm9kZSAqIGRvdWJsZVJvdGF0ZVJpZ2h0KEFWTF9Ob2RlICpLMik7CgogIEFWTF9Ob2RlICogX2luc2VydChpbnQga2V5LCBBVkxfTm9kZSAqIG5vZGUpOwogIEFWTF9Ob2RlICogX2VyYXNlKGludCBrZXksIEFWTF9Ob2RlICogbm9kZSk7CiAgdm9pZCBfZGZzKEFWTF9Ob2RlICogdikgY29uc3Q7Cn07CgpBdmwuY3BwCgojaW5jbHVkZSA8Y3N0ZGlvPgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlICJBdmwuaCIKLy8tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCi8vLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLSAKQVZMX1RyZWU6OkFWTF9UcmVlKCkKewogIHNpemU9MDsKCiAgcm9vdD1OVUxMOwp9Ci8vLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQovLy0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0gCmVsZW1lbnQgQVZMX1RyZWU6OmZpbmQoaW50IGtleSkKewogIGlmKHNpemU9PTApCiAgICByZXR1cm4gTlVMTDsKICB0bXA9cm9vdDsKICB3aGlsZSh0bXAhPU5VTEwpCiAgewogICAgaWYoa2V5PHRtcC0+a2V5KQogICAgICB0bXA9dG1wLT5sZWZ0OwogICAgZWxzZSBpZihrZXk+dG1wLT5rZXkpCiAgICAgIHRtcD10bXAtPnJpZ2h0OwogICAgZWxzZSAKICAgICAgcmV0dXJuIHRtcC0+ZGF0YTsKICB9CiAgcmV0dXJuIE5VTEw7Cn0KLy8tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCi8vLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLSAKaW5saW5lIGludCBBVkxfVHJlZTo6aGVpZ2h0KCBBVkxfTm9kZSAqIHBvcyApIGNvbnN0CnsKICBpZiggcG9zID09IE5VTEwgKQogICAgcmV0dXJuIC0xOwogIGVsc2UKICAgIHJldHVybiBwb3MtPmZhY3RvcjsKfQovLy0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KLy8tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tIAppbmxpbmUgaW50IEFWTF9UcmVlOjptYXgoIGludCBhLCBpbnQgYiApIGNvbnN0CnsKICByZXR1cm4gYSA+IGIgPyBhIDogYjsKfQovLy0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KLy8tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tIApBVkxfTm9kZSAqIEFWTF9UcmVlOjpzaW5nbGVSb3RhdGVMZWZ0KEFWTF9Ob2RlICpLMikKewogIEsxID0gSzItPmxlZnQ7CiAgSzItPmxlZnQgPSBLMS0+cmlnaHQ7CiAgSzEtPnJpZ2h0ID0gSzI7CgogIEsyLT5mYWN0b3IgPSBtYXgoaGVpZ2h0KEsyLT5sZWZ0KSwgaGVpZ2h0KEsyLT5yaWdodCkpKzE7CiAgSzEtPmZhY3RvciA9IG1heChoZWlnaHQoSzEtPmxlZnQpLCBLMi0+ZmFjdG9yKSsxOwoKCiAgcmV0dXJuIEsxOyAgLy8gbmV3IHJvb3QKfSAgIAovLy0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KLy8tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tIApBVkxfTm9kZSAqIEFWTF9UcmVlOjpzaW5nbGVSb3RhdGVSaWdodChBVkxfTm9kZSAqSzEpCnsKICBLMiA9IEsxLT5yaWdodDsKICBLMS0+cmlnaHQgPSBLMi0+bGVmdDsKICBLMi0+bGVmdCA9IEsxOwoKICBLMS0+ZmFjdG9yID0gbWF4KGhlaWdodChLMS0+bGVmdCksIGhlaWdodChLMS0+cmlnaHQpKSsxOwogIEsyLT5mYWN0b3IgPSBtYXgoaGVpZ2h0KEsyLT5yaWdodCksIEsxLT5mYWN0b3IpKzE7CgoKICByZXR1cm4gSzI7ICAvLyBuZXcgcm9vdAp9ICAgCi8vLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQovLy0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0gCkFWTF9Ob2RlICogQVZMX1RyZWU6OmRvdWJsZVJvdGF0ZUxlZnQoQVZMX05vZGUgKkszKQp7CiAgSzMtPmxlZnQgPSBzaW5nbGVSb3RhdGVSaWdodChLMy0+bGVmdCk7CgogIHJldHVybiBzaW5nbGVSb3RhdGVMZWZ0KEszKTsKfSAgIAovLy0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KLy8tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tIApBVkxfTm9kZSAqIEFWTF9UcmVlOjpkb3VibGVSb3RhdGVSaWdodChBVkxfTm9kZSAqSzEpCnsKICBLMS0+cmlnaHQgPSBzaW5nbGVSb3RhdGVMZWZ0KEsxLT5yaWdodCk7CgogIHJldHVybiBzaW5nbGVSb3RhdGVSaWdodChLMSk7Cn0gICAKLy8tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCi8vLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLSAgICAgCnZvaWQgQVZMX1RyZWU6Omluc2VydChpbnQga2V5KQp7CiAgc2l6ZSsrOwogIHJvb3Q9X2luc2VydChrZXkscm9vdCk7Cn0gICAgIAovLy0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KLy8tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tICAgICAKQVZMX05vZGUgKiBBVkxfVHJlZTo6X2luc2VydChpbnQga2V5LCBBVkxfTm9kZSAqIG5vZGUpCnsKICBpZiAobm9kZT09TlVMTCkKICB7CiAgICBub2RlID0gbmV3IEFWTF9Ob2RlOwogICAgbm9kZS0+ZmFjdG9yPTA7CiAgICBub2RlLT5rZXk9a2V5OwogICAgbm9kZS0+ZGF0YT10bXBkYXRhOwogICAgbm9kZS0+bGVmdD1OVUxMOwogICAgbm9kZS0+cmlnaHQ9TlVMTDsKICB9CiAgZWxzZSBpZihrZXkgPCBub2RlLT5rZXkpCiAgewogICAgbm9kZS0+bGVmdD0gX2luc2VydChrZXksbm9kZS0+bGVmdCk7CiAgICBpZihoZWlnaHQobm9kZS0+bGVmdCkgLSBoZWlnaHQobm9kZS0+cmlnaHQpID09IDIpCiAgICB7CiAgICAgIGlmKGtleSA8IG5vZGUtPmxlZnQtPmtleSkKICAgICAgICBub2RlID0gc2luZ2xlUm90YXRlTGVmdChub2RlKTsKICAgICAgZWxzZQogICAgICAgIG5vZGUgPSBkb3VibGVSb3RhdGVMZWZ0KG5vZGUpOwogICAgfQogIH0gICAgICAKICBlbHNlIGlmKGtleSA+IG5vZGUtPmtleSkgICAgICAKICB7CiAgICBub2RlLT5yaWdodD0gX2luc2VydChrZXksbm9kZS0+cmlnaHQpOwogICAgaWYoaGVpZ2h0KG5vZGUtPnJpZ2h0KSAtIGhlaWdodChub2RlLT5sZWZ0KSA9PSAyKQogICAgewogICAgICBpZihrZXkgPiBub2RlLT5yaWdodC0+a2V5KQogICAgICAgIG5vZGUgPSBzaW5nbGVSb3RhdGVSaWdodChub2RlKTsKICAgICAgZWxzZSAgICAgICAgICAgICAgCiAgICAgICAgbm9kZSA9IGRvdWJsZVJvdGF0ZVJpZ2h0KG5vZGUpOyAgICAgICAgIAogICAgfQogIH0gIAogIG5vZGUtPmZhY3RvciA9IG1heChoZWlnaHQobm9kZS0+bGVmdCApLGhlaWdodChub2RlLT5yaWdodCkpKzE7CiAgcmV0dXJuIG5vZGU7Cgp9Ci8vLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQovLy0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0gICAgIAp2b2lkIEFWTF9UcmVlOjplcmFzZShpbnQga2V5KQp7CiAgcm9vdD1fZXJhc2Uoa2V5LHJvb3QpOwp9Ci8vLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQovLy0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KQVZMX05vZGUgKiBBVkxfVHJlZTo6X2VyYXNlKGludCBrZXksIEFWTF9Ob2RlICogbm9kZSkKewogIGJvb2wgZG9uZT1mYWxzZTsKICBpZiAobm9kZT09TlVMTCkgCiAgeyAgIAogICAgaD1mYWxzZTsgIAogICAgZG9uZT10cnVlOwogIH0KICBlbHNlCiAgICBpZiAoa2V5IDwgbm9kZS0+a2V5KSAvL2RlbGVlIGZyb20gbGVmdCBzdWJ0cmVlICAKICAgIHsKICAgICAgbmV3bm9kZT1fZXJhc2Uoa2V5LG5vZGUtPmxlZnQpOwogICAgICBub2RlLT5sZWZ0PW5ld25vZGU7CiAgICAgIGlmKGgpCiAgICAgIHsKICAgICAgICBpZihoZWlnaHQobm9kZS0+cmlnaHQpIC0gaGVpZ2h0KG5vZGUtPmxlZnQpID09IDIpCiAgICAgICAgewogICAgICAgICAgaWYoaGVpZ2h0KG5vZGUtPnJpZ2h0KSA+IGhlaWdodChub2RlLT5sZWZ0KSkKICAgICAgICAgICAgbm9kZSA9IHNpbmdsZVJvdGF0ZUxlZnQobm9kZSk7CiAgICAgICAgICBlbHNlICAgICAgICAgICAgICAKICAgICAgICAgICAgbm9kZSA9IHNpbmdsZVJvdGF0ZVJpZ2h0KG5vZGUpOyAgICAgICAgIAogICAgICAgIH0KCiAgICAgICAgbm9kZS0+ZmFjdG9yID0gbWF4KGhlaWdodChub2RlLT5sZWZ0ICksaGVpZ2h0KG5vZGUtPnJpZ2h0KSkrMTsKCgogICAgICAgIC8vICAgICAgICAgIGlmIChub2RlLT5mYWN0b3IgPj0gMCkKICAgICAgICAvLyAgICAgICAgICAgICAgICAgIHsKICAgICAgICAvLyAgICAgICAgICAgICAgICAgICAgIG5vZGUtPmZhY3Rvcj1yb290LT5mYWN0b3ItMTsKICAgICAgICAvLyAgICAgICAgICAgICAgICAgaWYgKG5vZGUtPmZhY3Rvcj09LTEpCiAgICAgICAgLy8gICAgICAgICAgICAgICAgICAgICAgaD1mYWxzZTsKICAgICAgICAvLyAgICAgICAgICAgICAgICAgIH0KICAgICAgICAvLyAgICAgICAgICAgICAgICAgIGVsc2UgaWYgKG5vZGUtPnJpZ2h0LT5mYWN0b3I9PS0xKQogICAgICAgIC8vICAgICAgICAgICAgICAgICAgICAgIHNpbmdsZVJvdGF0ZVJpZ2h0KG5vZGUpOyAKICAgICAgICAvLyAgICAgICAgICAgICAgICAgIGVsc2UgCiAgICAgICAgLy8gICAgICAgICAgICAgICAgICAgICAgc2luZ2xlUm90YXRlTGVmdChub2RlKTsgICAgICAgICAgICAgICAgICAgICAKCiAgICAgICAgZG9uZT10cnVlOyAgICAgIAogICAgICAgIHJldHVybiBub2RlOwogICAgICB9CgoKICAgIH0KICAgIGVsc2UgaWYgKGtleSA9PSBub2RlLT5rZXkpIC8vZGVsIG5vZGUKICAgIHsKICAgICAgaWYgKG5vZGUtPmxlZnQ9PU5VTEwgfHwgbm9kZS0+cmlnaHQ9PU5VTEwpICAvLyBvbmUgb3Igbm8gY2hpbGRyZW4gCiAgICAgIHsKICAgICAgICBpZiAobm9kZS0+bGVmdCA9PSBOVUxMKSAKICAgICAgICAgIEsxPW5vZGUtPnJpZ2h0OwogICAgICAgIGVsc2UgCiAgICAgICAgICBLMT1ub2RlLT5sZWZ0OwoKICAgICAgICBkZWxldGUgbm9kZTsKCiAgICAgICAgaD10cnVlOyBkb25lPXRydWU7CgogICAgICAgIHJldHVybihLMSk7ICAgICAgICAgICAgICAgICAgICAgICAgIAoKICAgICAgfQogICAgICBlbHNlIC8vIGJvdGggb2YgY2hpbGRyZW4KICAgICAgewogICAgICAgIEsyPW5vZGUtPnJpZ2h0OwogICAgICAgIHdoaWxlIChLMi0+bGVmdCAhPSBOVUxMKSAKICAgICAgICAgIEsyPUsyLT5sZWZ0OwoKICAgICAgICBub2RlLT5rZXk9SzItPmtleTsKICAgICAgICBrZXk9bm9kZS0+a2V5OwogICAgICB9CiAgICB9CgogIGlmICghZG9uZSAmJiBrZXkgPj0gbm9kZS0+a2V5KSAvLyBkZWxldGUgZnJvbSByaWdodCBzdWJ0cmVlIAogIHsKICAgIG5ld25vZGU9X2VyYXNlKGtleSwgbm9kZS0+cmlnaHQpOwogICAgbm9kZS0+cmlnaHQ9bmV3bm9kZTsKICAgIGlmIChoKQogICAgeyAgICAgICAgICAgICAgIAogICAgICBpZihoZWlnaHQobm9kZS0+cmlnaHQpIC0gaGVpZ2h0KG5vZGUtPmxlZnQpID09IDIpCiAgICAgIHsKICAgICAgICBpZihoZWlnaHQobm9kZS0+cmlnaHQpID4gaGVpZ2h0KG5vZGUtPmxlZnQpKQogICAgICAgICAgbm9kZSA9IHNpbmdsZVJvdGF0ZUxlZnQobm9kZSk7CiAgICAgICAgZWxzZSAgICAgICAgICAgICAgICAKICAgICAgICAgIG5vZGUgPSBzaW5nbGVSb3RhdGVSaWdodChub2RlKTsgICAgICAgICAgIAogICAgICB9CiAgICAgIG5vZGUtPmZhY3RvciA9IG1heChoZWlnaHQobm9kZS0+bGVmdCApLGhlaWdodChub2RlLT5yaWdodCkpKzE7CiAgICAgIC8vCiAgICAgIC8qICAgICAgICAgICAgICAgIGlmIChub2RlLT5mYWN0b3IgPD0gMCkgCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIG5vZGUtPmZhY3Rvcj1ub2RlLT5mYWN0b3IrMTsKICAgICAgICAgICAgICAgIGlmIChub2RlLT5mYWN0b3IgPT0xKSAKICAgICAgICAgICAgICAgICAgaD1mYWxzZTsKICAgICAgICAgICAgfSAgIAogICAgICAgICAgICBlbHNlIGlmIChub2RlLT5yaWdodC0+ZmFjdG9yPT0xKSAKICAgICAgICAgICAgICBzaW5nbGVSb3RhdGVMZWZ0KG5vZGUpOwogICAgICAgICAgICBlbHNlICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgc2luZ2xlUm90YXRlUmlnaHQobm9kZSk7Ki8KICAgICAgcmV0dXJuIG5vZGU7CiAgICB9CiAgfQoKCn0KLy8tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCi8vLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLSAgICAgCnZvaWQgQVZMX1RyZWU6OmRmcygpCnsKICBfZGZzKHJvb3QpOwp9Ci8vLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQovLy0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0gICAgIAp2b2lkIEFWTF9UcmVlOjpfZGZzKEFWTF9Ob2RlICogdikgY29uc3QKewoKCiAgaWYodi0+bGVmdCE9TlVMTCkKICAgIF9kZnModi0+bGVmdCk7CgogIHN0ZDo6Y291dCA8PCB2LT5rZXkgPDwgc3RkOjplbmRsOyAKICBpZih2LT5yaWdodCE9TlVMTCkKICAgIF9kZnModi0+cmlnaHQpOyAKfQovLy0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KLy8tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0=