#ifndef Ordered2DSet_CPP
#define Ordered2DSet_CPP

#include "Ordered2DSet.h"

template <class key, class value>
Btree<key,value>::Btree() {
root =0;
}

template <class key, class value>
Btree <key,value>::Btree(const Btree& orig) {
root = new Node<key,value>;
if (orig.root!= 0)
copy (orig.root, root);
else
root=0;
}

template <class key, class value>
Btree<key,value>::~Btree() {
clear_all (root);
root=0;
}

template <class key, class value>
void Btree<key,value>::copy (Node<key,value> *a, Node<key,value> *b){
Node<key,value> *p[2*n+1];

if (a !=0){
b->RAmount = a->RAmount;
for (int i=0; i < a->RAmount; i++){
b->klyuch[i].k = a->klyuch[i].k;
}
if ((a->RAmount >= 1) && (a->children!=0)){
p[0] = new Node<key,value>;
p[1] = new Node<key,value>;
}
else{
p[0]=0;
p[1]=0;
}
for(int i=1;i<2*n;i++){
if ((a->RAmount >=i+1) && (a->children!=0))
p[i+1]=new Node<key,value>;
else p[i+1]=0;
}
b->children = p[0];
for(int i=1;i<2*n+1;i++){
b->klyuch[i].p = p[i];
}
if (a->RAmount >= 1)
{
copy (a->children, p[0]);
copy (a->klyuch[0].p, p[1]);
}
for(int i=1;i<2*n;i++){
if (a->RAmount >=i+1) copy (a->klyuch[i].p, p[i+1]);
}
}
}

template <class key, class value>
void Btree<key,value>::Add (const key k,const value v){
bool grow;
Tochka<key,value> u;
Node<key,value> *bufer_root;
search_add_key (k,v, root, grow, u);
if (grow == true)
{
bufer_root = root;
root = new Node<key,value>;
root->children = 0;
for (int i=0;i<2*n+1;i++){
root->klyuch[i].p =0;
}
root->RAmount = 1;
root->children = bufer_root;
root->klyuch[0] = u;

}
}

template <class key, class value>
void Btree<key,value>::search_add_key (const key k,const value v, Node<key,value> *a, bool& grow, Tochka<key,value>& m) {
int i, L, R;
Node<key,value> *b;
Tochka<key,value> u;
if (a==0){
grow = true;
m.k=k; m.v=v;
m.p =0;
}
else{
L=0;
R=a->RAmount;
while (L<R){
i = (L+R)/2;
if (a->klyuch[i].k <=k)
L = i+1;
else
R=i;
}
R = R-1;
if ((R>=0) && (a->klyuch[R].k == k)){
grow=false;}
else{
if (R==-1){
search_add_key(k,v, a->children, grow, u);
}
else
search_add_key(k,v, a->klyuch[R].p, grow, u);
if (grow==true){
if (a->RAmount<2*n){
grow= false;
a->RAmount++;
for (i=a->RAmount-1;i>=R+2;i--)
a->klyuch[i] =a->klyuch[i-1];
a->klyuch[R+1]=u;
}
else{
b=new Node<key,value>;
b->children=0;
for(int c=0;c<2*n+1;c++){
b->klyuch[c].p=0;
}
if (R<=(n-1)){
if (R==(n-1))
m=u;
else{
m=a->klyuch[n-1];
for (i=n-1; i>=R+n-1; i--)
a->klyuch[i]=a->klyuch[i-1];
a->klyuch[R+1]=u;
}
for (i=0; i<=n; i++)
b->klyuch[i] = a->klyuch[i+n];

}
else{
R=R-n;
m=a->klyuch[n];
for (i=0; i<=R-1; i++)
b->klyuch[i] = a->klyuch[i+n+1];
                         b->klyuch[R]=u;
                         for (i=R+1; i<=n-1; i++)
                              b->klyuch[i] = a->klyuch[i+n];
                     }
                     a->RAmount = n;
                     b->RAmount = n;
                     //a->klyuch[b->RAmount-1]->  b->klyuch[b->RAmount-1]->parent=b;
                     b->children = m.p;
                     m.p=b;
}
}
}
}
}

template <class key, class value>
bool Btree<key,value>::Search (const key k){
return (search_key (k, root));
}

template <class key, class value>
bool Btree<key,value>::search_key (const key k,const Node<key,value> *a)const{
int i, L, R;
if (a==0){
return (false);
}
else{
L = 0;
R = a->RAmount;
while (L < R){
i = (L+R)/2;
if (a->klyuch[i].k <= k)
L = i+1;
else
R = i;
}
R = R-1;
if ((R >= 0) && (a->klyuch[R].k==k))
return (true);
else
if (R == -1)
return search_key (k,a->children);
else
return search_key (k,a->klyuch[R].p);
}
}

template <class key, class value>
value Btree<key,value>::Search_k (const key k) {
return (search_k_key (k, root));
}

template <class key, class value>
value Btree<key,value>::search_k_key (const key k,const Node<key,value> *a)const{
int i, L, R;
L = 0;
R = a->RAmount;
while (L < R){
i = (L+R)/2;
if (a->klyuch[i].k <= k)
L = i+1;
else
R = i;
}
R = R-1;
if ((R >= 0) && (a->klyuch[R].k==k))
return (a->klyuch[R].v);
else
if (R == -1)
return search_k_key (k,a->children);
else
return search_k_key (k,a->klyuch[R].p);

}

template <class key, class value>
void Btree<key,value>::Delete (const key k){
bool smallsize;
Node<key,value> *bufer_root;
delete_key (k, root, smallsize);
if (smallsize==true){
if (root->RAmount == 0){
bufer_root = root;
root = bufer_root->children;
bufer_root=0;
}
}
}

template <class key, class value>
void Btree<key,value>::delete_key (const key k, Node<key,value> *a, bool& smallsize){
int i, L, R;
Node<key,value> *q;
if (a==0)
smallsize=false;
else{
L=0;
R=a->RAmount;
while (L < R){
i = (L+R)/2;
if (a->klyuch[i].k< k)
L = i+1;
else R = i;
}
if (R == 0)
q = a->children;
else
q = a->klyuch[R-1].p;
if ((R <= a->RAmount-1) && (a->klyuch[R].k==k)){
if (q==0){
a->RAmount--;
smallsize = (a->RAmount < n);
for (i=R; i<a->RAmount; i++)
a->klyuch[i] = a->klyuch[i+1];
}
else{
del(R, a, q, smallsize);
if (smallsize==true)
fusion (a, q, R-1, smallsize);
}
}
else{
delete_key (k, q, smallsize);
if (smallsize == true)
fusion (a, q, R-1, smallsize);
}
}
}

template <class key, class value>
void Btree<key,value>::del (int R, Node<key,value> *a, Node<key,value> *q, bool& smallsize){
Node<key,value> *b;
b = q->klyuch[q->RAmount-1].p;
if (b !=0){
del (R, a, b, smallsize);
if (smallsize==true)
fusion (q, b, q->RAmount-1, smallsize);
}
else{q->klyuch[q->RAmount-1].p = a->klyuch[R].p;
a->klyuch[R] = q->klyuch[q->RAmount-1];
q->RAmount--;
smallsize = (q->RAmount < n);
}
}

template <class key, class value>
void Btree<key,value>::fusion (Node<key,value> *father, Node<key,value> *son, int R, bool& smallsize)
{
Node<key,value> *b;
int i, k, RAb, RAfather;
RAfather = father->RAmount;
if (R < RAfather-1){
R++;
b = father->klyuch[R].p;
RAb = b->RAmount;
k = (RAb-n+1)/2;
son->klyuch[n-1] = father->klyuch[R];
son->klyuch[n-1].p = b->children;
if (k > 0){
for (i=0; i <= k-1; i++)
son->klyuch[i+n] = b->klyuch[i];
father->klyuch[R] = b->klyuch[k];
father->klyuch[R].p = b;
b->children = b->klyuch[k].p;
RAb = RAb-k-1;
for (i=0; i < RAb; i++)
b->klyuch[i] = b->klyuch[i+k+1];
b->RAmount = RAb;
son->RAmount = n-1+(k+1);
smallsize = false;
}
else{
for (i=0; i < n; i++)
son->klyuch[i+n] = b->klyuch[i];
for (i=R; i < RAfather-1; i++)
father->klyuch[i] = father->klyuch[i+1];
son->RAmount = 2*n;
father->RAmount--;
smallsize = (father->RAmount < n);
b=0;
}
}
else{
if (R == 0)
b = father->children;
else
b = father->klyuch[R-1].p;
RAb = b->RAmount+1;
k = (RAb-n)/2;
if (k > 0){
son->klyuch[k] = son->klyuch[0];
son->klyuch[k-1] = father->klyuch[R];
son->klyuch[k-1].p = son->children;
RAb = RAb-k-1;
son->children = b->klyuch[RAb].p;
father->klyuch[R] = b->klyuch[RAb];
father->klyuch[R].p = son;
b->RAmount--;
son->RAmount = n-1+k;
smallsize = false;
}
else{
b->klyuch[RAb-1] = father->klyuch[R];
b->klyuch[RAb-1].p = son->children;
b->klyuch[RAb] = son->klyuch[0];
b->RAmount = 2*n;
father->RAmount--;
smallsize = (father->RAmount < n);
son=0;
}
}
}


template <class key, class value>
int Btree<key,value>::Amount_key() const{
return amount_allkey(root, 0);
}

template <class key, class value>
int Btree<key,value>::amount_allkey(Node<key,value> *a,int b)const{
int i;
if (a!=0){
for (i=0; i<a->RAmount; i++)
b++;
b=b+amount_allkey(a->children,0);
for (i=0; i<a->RAmount; i++)
b=b+amount_allkey(a->klyuch[i].p,0);
}
return b;
}

template <class key, class value>
void Btree<key,value>::Clear (){
clear_all (root);
root=0;

}

template <class key, class value>
void Btree<key,value>::clear_all (Node<key,value> *a){
Node<key,value> *p[2*n+1];
if (a!=0){
if (a->RAmount >=1){
p[0] = a->children;
p[1] = a->klyuch[0].p;
}
else{
p[0]=0;
p[1]=0;
}
for(int i=1;i<2*n;i++){
if (a->RAmount >= i+1)
p[i+1]=a->klyuch[i].p;
else
p[i+1]=0;
}
a=0;
for(int i=0;i<2*n+1;i++) clear_all(p[i]);
}
}


template <class key, class value>
Tochka<key, value> Btree<key,value>::getFirst()const{
if (root!=0)
return getFirst_key(root);
}
template <class key, class value>
Tochka<key, value> Btree<key,value>::getFirst_key(const Node<key,value> *a)const{
if ((a->children)!= NULL)
return getFirst_key (a->children);
else return a->klyuch[0];
}

template <class key, class value>
Tochka<key, value> Btree<key,value>::NextKey(const key k) const{
//predmin=k;
Tochka<key, value> *next=&this->getFirst();
next_key(root,k,&next);
return *next;
}
template <class key, class value>
void Btree<key,value>::next_key(const Node<key,value> *a,const key k, Tochka<key, value> **b) const{
int i;
if (a!=0){
for(i=0; i<a->RAmount;i++){
if (a->klyuch[i].k>k){
if ((*b)->k<=k) {
**b=a->klyuch[i];
if (i==0)  next_key(a->children,k,b);
else next_key(a->klyuch[i-1].p,k,b);
}
if ((*b)->k>k){
if (a->klyuch[i].k<(*b)->k){
**b=a->klyuch[i];
}
if (i==0)  next_key(a->children,k,b);
else next_key(a->klyuch[i-1].p,k,b);

}
}
}
if (a->klyuch[a->RAmount-1].k<=k){
next_key(a->klyuch[a->RAmount-1].p,k,b);
}

/*L = 0;
R = a->RAmount;
while (L < R){
i = (L+R)/2;
if (a->klyuch[i].k <= k)
L = i+1;
else
R = i;
}
//R = R-1;
if ((R >=1) && (a->klyuch[R].k>k)){
if (predmin>=k) {
predmin=a->klyuch[R].k;
next=a->klyuch[R];
}
next_key (a->klyuch[R].p,k);
}
else
if (R ==0)
next_key (a->children,k);
else
next_key (a->klyuch[R+1].p,k);*/
}
}

/*template <class key, class value>
Tochka<key, value> Btree<key,value>::next_key(const Node<key,value> *a,const key k)const{
}*/



template <class key, class value>
void Btree<key,value>::Print (){
print_b_Node (root, 0);
}

template <class key, class value>
void Btree<key,value>::print_b_Node (Node<key,value> *a, int level){
int i;
if (a != NULL){
for (i=0; i<level; i++)
cout << "---";
for (i=0; i<a->RAmount; i++)
{
cout << a->klyuch[i].k;
if (i != a->RAmount-1)
cout << ", ";
}
cout << endl;
print_b_Node (a->children, level+1);
for (i=0; i<a->RAmount; i++)
print_b_Node (a->klyuch[i].p, level+1);
}
}
bool operator>(const Point &o1, const Point &o2)
{if((o1.x>o2.x)||((o1.x==o2.x)&&(o1.y>o2.y))) return 1;
else return 0;
}
bool operator<(const Point &o1, const Point &o2){
if((o1.x<o2.x)||((o1.x==o2.x)&&(o1.y<o2.y))) return 1;
else return 0;
}
bool operator==(const Point &o1, const Point &o2){
if((o1.x==o2.x)&&(o1.y==o2.y)) return 1;
else return 0;
}
bool operator>=(const Point &o1, const Point &o2){
if((o1>o2)||(o1==o2)) return 1;
else return 0;
}
bool operator<=(const Point &o1, const Point &o2){
if((o2>o1)||(o1==o2)) return 1;
else return 0;
}
ostream& operator<<(ostream& out, const Point& k){
out<<"(";
out<<k.x;
out<<" , ";
out<<k.y;
out<<")";
return out;
}
istream& operator>>(istream& in, Point& k){
in>>k.x;
in>>k.y;
return in;
};
Ordered2DSet::Ordered2DSet(){
;
}
Ordered2DSet::Ordered2DSet(const Ordered2DSet& orig){
k.Btree(orig.k);
}
Ordered2DSet::~Ordered2DSet()
{k.~Btree();
}
void Ordered2DSet ::Delete (const Point l){
k.Delete(l);
}
void Ordered2DSet ::Add (const Point l){
k.Add(l,l);
}
bool Ordered2DSet ::Search (const Point l){
k.Search(l);
}
int Ordered2DSet ::Amount_key()const{
k.Amount_key();
}
void Ordered2DSet ::Clear(){
k.Clear();
}
void Ordered2DSet::Print(){
k.Print();
}
#endif  /* Ordered2DSet_CPP */