deq.h 1.2 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465
  1. struct deq{
  2. size_t cap;
  3. int *left;
  4. int *right;
  5. int cont[1];
  6. };
  7. struct deq* makeDeq(size_t cap){
  8. struct deq* ans=(struct deq*)R_alloc(sizeof(struct deq)+(sizeof(int)*(cap-1)),1);
  9. if(!ans) return(ans);
  10. ans->cap=cap;
  11. ans->left=ans->right=NULL;
  12. return(ans);
  13. }
  14. void pushLeftDeq(struct deq *Q,int x){
  15. if(!Q->left){
  16. (Q->left=Q->right=Q->cont)[0]=x;
  17. return;
  18. }
  19. size_t cap=Q->cap;
  20. Q->left=Q->cont+((cap+(Q->left-Q->cont)-1)%cap);
  21. if(Q->right==Q->left) error("Deque overflow");
  22. Q->left[0]=x;
  23. }
  24. void pushRightDeq(struct deq *Q,int x){
  25. if(!Q->right){
  26. (Q->left=Q->right=Q->cont)[0]=x;
  27. return;
  28. }
  29. size_t cap=Q->cap;
  30. Q->right=Q->cont+(((Q->right-Q->cont)+1)%cap);
  31. if(Q->right==Q->left) error("Deque overflow");
  32. Q->right[0]=x;
  33. }
  34. int popLeftDeq(struct deq *Q){
  35. if(!Q->left) error("Pop from an empty deque");
  36. int ans=*(Q->left);
  37. size_t cap=Q->cap;
  38. if(Q->left==Q->right){
  39. //Empty again!
  40. Q->left=Q->right=NULL;
  41. return(ans);
  42. }
  43. Q->left=Q->cont+(((Q->left-Q->cont)+1)%cap);
  44. return(ans);
  45. }
  46. int popRightDeq(struct deq *Q){
  47. if(!Q->right) error("Pop from an empty deque");
  48. int ans=*(Q->right);
  49. size_t cap=Q->cap;
  50. if(Q->left==Q->right){
  51. Q->left=Q->right=NULL;
  52. return(ans);
  53. }
  54. Q->right=Q->cont+((cap+(Q->right-Q->cont)-1)%cap);
  55. return(ans);
  56. }