#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int val;
struct node* lnext;
struct node* rnext;
}node;
void push(node *, int);
int pop(node *);
node * find(node *, int);
void doing(node *, int, int);
long cnt=1;
int main()
{
int a,b;
char ch[6];
node * findnode;
node head;
printf("초기값 설정 ㄱㄱ\n");
scanf("%d",&head.val);
head.lnext=NULL;
head.rnext=NULL;
for(;;)
{
printf("push나 pop이나 find나 doing이나 exit 입력(push/pop/find/doing/exit)\n");
scanf("%s",ch);
if(ch[0]=='e' && ch[1]=='x' && ch[2]=='i' && ch[3]=='t') break;
else if(ch[0]=='f' && ch[1]=='i' && ch[2]=='n' && ch[3]=='d')
{
printf("인덱스 입력 ㄱㄱ : ");
scanf("%d",&a);
findnode=find(&head,a);
printf("니가 찾는거 : %d\n",findnode->val);
}
else if(ch[0]=='d' && ch[1]=='o' && ch[2]=='i' && ch[3]=='n' && ch[4]=='g')
{
printf("인덱스 입력 ㄱㄱ : ");
scanf("%d",&a);
printf("넣을 숫자 입력 ㄱㄱ(자연수만) : ");
scanf("%d",&b);
doing(&head,a,b);
}
else if(ch[0]=='p' && ch[1]=='u' && ch[2]=='s' && ch[3]=='h')
{
printf("넣을 숫자 입력 ㄱㄱ(자연수만) : ");
scanf("%d",&a);
push(&head,a);
}
else if(ch[0]=='p' && ch[1]=='o' && ch[2]=='p')
{
a=pop(&head);
if(a==-1) printf("숫자 없음 ㅂㅅ아\n");
else printf("%d가 있었다 ㅂㅅ아\n",a);
}
else
{
printf("push나 pop이나 exit만 입력하라고...\n");
}
}
return 0;
}
void push(node * target, int newval)
{
node * newnode=(node *)malloc(sizeof(node));
int a=1,c,i;
int * b;
cnt++;
for(c=1;;c++)
{
if(a<=cnt && cnt<2*a) break;
a*=2;
}
a=cnt;
b=(int *)malloc((sizeof(int))*c);
for(i=0;i<c;i++)
{
if(a%2==0) b[i]=0;
else b[i]=1;
a/=2;
}
for(i=c-2;i>=1;i--)
{
if(b[i]==0)
target=target->lnext;
else
target=target->rnext;
}
newnode->val=newval;
newnode->lnext=NULL;
newnode->rnext=NULL;
if(b[0]==0) target->lnext=newnode;
else target->rnext=newnode;
free(b);
}
int pop(node * target)
{
int a=1,c,i;
int * b;
if(cnt==0) return -1;
if(cnt==1)
{
cnt--;
return target->val;
}
for(c=1;;c++)
{
if(a<=cnt && cnt<2*a) break;
a*=2;
}
a=cnt;
b=(int *)malloc((sizeof(int))*c);
for(i=0;i<c;i++)
{
if(a%2==0) b[i]=0;
else b[i]=1;
a/=2;
}
for(i=c-2;i>=1;i--)
{
if(b[i]==0)
target=target->lnext;
else
target=target->rnext;
}
if(b[0]==0)
{
a=target->lnext->val;
free(target->lnext);
target->lnext=NULL;
}
else
{
a=target->rnext->val;
free(target->rnext);
target->rnext=NULL;
}
free(b);
cnt--;
return a;
}
node * find(node * root,int index)
{
int a=1,c,i;
int * b;
if(index==0)
{
return root;
}
index++;
for(c=1;;c++)
{
if(a<=index && index<2*a) break;
a*=2;
}
a=index;
b=(int *)malloc((sizeof(int))*c);
for(i=0;i<c;i++)
{
if(a%2==0) b[i]=0;
else b[i]=1;
a/=2;
}
for(i=c-2;i>=0;i--)
{
if(b[i]==0)
root=root->lnext;
else
root=root->rnext;
}
return root;
}
void doing(node * root,int index,int val)
{
int a=1,c,i;
int * b;
node * newnode=(node *)malloc(sizeof(node));
node * temp;
newnode->val=val;
if(index==0)
{
newnode->lnext=root;
root=newnode;
return;
}
if(index==1)
{
temp=root;
newnode->lnext=root->lnext;
root->lnext=newnode;
return;
}
if(index==2)
{
temp=root;
newnode->rnext=root->rnext;
root->rnext=newnode;
return;
}
index++;
for(c=1;;c++)
{
if(a<=index && index<2*a) break;
a*=2;
}
a=index;
b=(int *)malloc((sizeof(int))*c);
for(i=0;i<c;i++)
{
if(a%2==0) b[i]=0;
else b[i]=1;
a/=2;
}
for(i=c-2;i>0;i--)
{
if(b[i]==0)
root=root->lnext;
else
root=root->rnext;
}
if(b[0]==0)
{
temp=root;
newnode->lnext=root->lnext;
root->lnext=newnode;
}
else
{
temp=root;
newnode->rnext=root->rnext;
root->rnext=newnode;
}
return;
}
