summaryrefslogtreecommitdiff
path: root/recordmydesktop/src/rectinsert.c
diff options
context:
space:
mode:
Diffstat (limited to 'recordmydesktop/src/rectinsert.c')
-rw-r--r--recordmydesktop/src/rectinsert.c469
1 files changed, 469 insertions, 0 deletions
diff --git a/recordmydesktop/src/rectinsert.c b/recordmydesktop/src/rectinsert.c
new file mode 100644
index 0000000..4caf1b8
--- /dev/null
+++ b/recordmydesktop/src/rectinsert.c
@@ -0,0 +1,469 @@
+/*********************************************************************************
+* recordMyDesktop *
+**********************************************************************************
+* *
+* Copyright (C) 2006 John Varouhakis *
+* *
+* *
+* This program is free software; you can redistribute it and/or modify *
+* it under the terms of the GNU General Public License as published by *
+* the Free Software Foundation; either version 2 of the License, or *
+* (at your option) any later version. *
+* *
+* This program is distributed in the hope that it will be useful, *
+* but WITHOUT ANY WARRANTY; without even the implied warranty of *
+* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
+* GNU General Public License for more details. *
+* *
+* You should have received a copy of the GNU General Public License *
+* along with this program; if not, write to the Free Software *
+* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA *
+* *
+* *
+* *
+* For further information contact me at biocrasher@gmail.com *
+**********************************************************************************/
+
+
+#include <recordmydesktop.h>
+//return 1 and null if geom1 in geom2 ,2 and null if geom2 in geom1,0 if they don't collide
+//-1 and two geoms if they collide and geom1 is broken.//-2 and one or two geoms if they collide and geom2 is broken.
+//-10 if group and replace is possible
+int CollideRects(WGeometry *wgeom1,WGeometry *wgeom2,WGeometry **wgeom_return,int *ngeoms){
+ //1 fits in 2
+ if((wgeom1->x>=wgeom2->x)&&
+ (wgeom1->x+wgeom1->width<=wgeom2->x+wgeom2->width)&&
+ (wgeom1->y>=wgeom2->y)&&
+ (wgeom1->y+wgeom1->height<=wgeom2->y+wgeom2->height)){
+ *ngeoms=0;
+ return 1;
+ }
+ //2 fits in 1
+ else if((wgeom2->x>=wgeom1->x)&&
+ (wgeom2->x+wgeom2->width<=wgeom1->x+wgeom1->width)&&
+ (wgeom2->y>=wgeom1->y)&&
+ (wgeom2->y+wgeom2->height<=wgeom1->y+wgeom1->height)){
+ *ngeoms=0;
+ return 2;
+ }
+ //no collision
+ else if((wgeom1->x+wgeom1->width<wgeom2->x)||
+ (wgeom2->x+wgeom2->width<wgeom1->x)||
+ (wgeom1->y+wgeom1->height<wgeom2->y)||
+ (wgeom2->y+wgeom2->height<wgeom1->y)){
+ *ngeoms=0;
+ return 0;
+ }
+ else{
+//overlapping points are considered enclosed
+//this happens because libxdamage may generate many events for one change
+//and some of them may be in the the exact same region
+//so identical rects would be considered not colliding
+//in order though to avoid endless recursion on the RectInsert
+//function should always start at the next element(which is logical since
+//if any rect makes it to a points none of it's part collides with previous
+//nodes on the list, too)
+ int x1[2]={wgeom1->x,wgeom1->x+wgeom1->width};
+ int y1[2]={wgeom1->y,wgeom1->y+wgeom1->height};
+ int x2[2]={wgeom2->x,wgeom2->x+wgeom2->width};
+ int y2[2]={wgeom2->y,wgeom2->y+wgeom2->height};
+ int enclosed[2][4],tot1,tot2;
+ enclosed[0][0]=(((x1[0]>=x2[0])&&(x1[0]<=x2[1])&&
+ (y1[0]>=y2[0])&&(y1[0]<=y2[1]))?1:0);
+ enclosed[0][1]=(((x1[1]>=x2[0])&&(x1[1]<=x2[1])&&
+ (y1[0]>=y2[0])&&(y1[0]<=y2[1]))?1:0);
+ enclosed[0][2]=(((x1[0]>=x2[0])&&(x1[0]<=x2[1])&&
+ (y1[1]>=y2[0])&&(y1[1]<=y2[1]))?1:0);
+ enclosed[0][3]=(((x1[1]>=x2[0])&&(x1[1]<=x2[1])&&
+ (y1[1]>=y2[0])&&(y1[1]<=y2[1]))?1:0);
+ enclosed[1][0]=(((x2[0]>=x1[0])&&(x2[0]<=x1[1])&&
+ (y2[0]>=y1[0])&&(y2[0]<=y1[1]))?1:0);
+ enclosed[1][1]=(((x2[1]>=x1[0])&&(x2[1]<=x1[1])&&
+ (y2[0]>=y1[0])&&(y2[0]<=y1[1]))?1:0);
+ enclosed[1][2]=(((x2[0]>=x1[0])&&(x2[0]<=x1[1])&&
+ (y2[1]>=y1[0])&&(y2[1]<=y1[1]))?1:0);
+ enclosed[1][3]=(((x2[1]>=x1[0])&&(x2[1]<=x1[1])&&
+ (y2[1]>=y1[0])&&(y2[1]<=y1[1]))?1:0);
+ tot1=enclosed[0][0]+enclosed[0][1]+enclosed[0][2]+enclosed[0][3];
+ tot2=enclosed[1][0]+enclosed[1][1]+enclosed[1][2]+enclosed[1][3];
+ if((tot1==2)&&(tot2==2)){//same width or height, which is the best case
+ //group
+ if((enclosed[1][0]&&enclosed[1][1])&&(wgeom1->width==wgeom2->width)){
+ wgeom_return[0]=(WGeometry *)malloc(sizeof(WGeometry));
+ *ngeoms=1;
+ wgeom_return[0]->x=wgeom1->x;
+ wgeom_return[0]->y=wgeom1->y;
+ wgeom_return[0]->width=wgeom1->width;
+ wgeom_return[0]->height=wgeom2->height+wgeom2->y-wgeom1->y;
+ return -10;
+ }
+ else if((enclosed[1][0]&&enclosed[1][2])&&(wgeom1->height==wgeom2->height)){
+// wgeom_return[0]=(WGeometry *)malloc(sizeof(WGeometry));
+ *ngeoms=1;
+ wgeom_return[0]->x=wgeom1->x;
+ wgeom_return[0]->y=wgeom1->y;
+ wgeom_return[0]->width=wgeom2->width+wgeom2->x-wgeom1->x;
+ wgeom_return[0]->height=wgeom1->height;
+ return -10;
+ }
+ else if((enclosed[1][3]&&enclosed[1][1])&&(wgeom1->height==wgeom2->height)){
+// wgeom_return[0]=(WGeometry *)malloc(sizeof(WGeometry));
+ *ngeoms=1;
+ wgeom_return[0]->x=wgeom2->x;
+ wgeom_return[0]->y=wgeom2->y;
+ wgeom_return[0]->width=wgeom1->width+wgeom1->x-wgeom2->x;
+ wgeom_return[0]->height=wgeom2->height;
+ return -10;
+ }
+ else if((enclosed[1][3]&&enclosed[1][2])&&(wgeom1->width==wgeom2->width)){
+// wgeom_return[0]=(WGeometry *)malloc(sizeof(WGeometry));
+ *ngeoms=1;
+ wgeom_return[0]->x=wgeom2->x;
+ wgeom_return[0]->y=wgeom2->y;
+ wgeom_return[0]->width=wgeom2->width;
+ wgeom_return[0]->height=wgeom1->height+wgeom1->y-wgeom2->y;
+ return -10;
+ }
+ //if control reaches here therewasn't a group and we go on
+ }
+ if(tot2==2){
+ //break geom2
+// wgeom_return[0]=(WGeometry *)malloc(sizeof(WGeometry));
+ wgeom_return[0]->x=wgeom2->x;
+ wgeom_return[0]->y=wgeom2->y;
+ wgeom_return[0]->width=wgeom2->width;
+ wgeom_return[0]->height=wgeom2->height;
+ *ngeoms=1;
+ if(enclosed[1][0]&&enclosed[1][1]){
+ wgeom_return[0]->y=y1[1];
+ wgeom_return[0]->height-=y1[1]-y2[0];
+ }
+ else if(enclosed[1][0]&&enclosed[1][2]){
+ wgeom_return[0]->x=x1[1];
+ wgeom_return[0]->width-=x1[1]-x2[0];
+ }
+ else if(enclosed[1][3]&&enclosed[1][1])
+ wgeom_return[0]->width-=x2[1]-x1[0];
+ else if(enclosed[1][3]&&enclosed[1][2])
+ wgeom_return[0]->height-=y2[1]-y1[0];
+ return -2;
+ }
+ else if(tot1==2){
+ //if the first one breaks(which is already inserted)
+ //then we reenter the part that was left and the one
+ //that was to be inserted
+ wgeom_return[1]=wgeom2;
+// wgeom_return[0]=(WGeometry *)malloc(sizeof(WGeometry));
+ wgeom_return[0]->x=wgeom1->x;
+ wgeom_return[0]->y=wgeom1->y;
+ wgeom_return[0]->width=wgeom1->width;
+ wgeom_return[0]->height=wgeom1->height;
+ *ngeoms=1;
+ if(enclosed[0][0]&&enclosed[0][1]){
+ wgeom_return[0]->y=y2[1];
+ wgeom_return[0]->height-=y2[1]-y1[0];
+ }
+ else if(enclosed[0][0]&&enclosed[0][2]){
+ wgeom_return[0]->x=x2[1];
+ wgeom_return[0]->width-=x2[1]-x1[0];
+ }
+ else if(enclosed[0][3]&&enclosed[0][1])
+ wgeom_return[0]->width-=x1[1]-x2[0];
+ else if(enclosed[0][3]&&enclosed[0][2])
+ wgeom_return[0]->height-=y1[1]-y2[0];
+ return -1;
+
+ }
+ else if(tot2==1){//in which case there is also tot1==1 but we rather not break that
+ //break geom2 in two
+// wgeom_return[0]=(WGeometry *)malloc(sizeof(WGeometry));
+// wgeom_return[1]=(WGeometry *)malloc(sizeof(WGeometry));
+ *ngeoms=2;
+ if(enclosed[1][0]){
+//first
+ wgeom_return[0]->x=x1[1];
+ wgeom_return[0]->y=y2[0];
+ wgeom_return[0]->width=wgeom2->width-x1[1]+x2[0];
+ wgeom_return[0]->height=wgeom2->height;
+//second
+ wgeom_return[1]->x=x2[0];
+ wgeom_return[1]->y=y1[1];
+ wgeom_return[1]->width=x1[1]-x2[0];
+ wgeom_return[1]->height=wgeom2->height-y1[1]+y2[0];
+ }
+ else if(enclosed[1][1]){
+//first
+ wgeom_return[0]->x=x2[0];
+ wgeom_return[0]->y=y2[0];
+ wgeom_return[0]->width=wgeom2->width-x2[1]+x1[0];
+ wgeom_return[0]->height=wgeom2->height;
+//second
+ wgeom_return[1]->x=x1[0];
+ wgeom_return[1]->y=y1[1];
+ wgeom_return[1]->width=x2[1]-x1[0];
+ wgeom_return[1]->height=wgeom2->height-y1[1]+y2[0];
+ }
+ else if(enclosed[1][2]){
+//first(same as [1][0])
+ wgeom_return[0]->x=x1[1];
+ wgeom_return[0]->y=y2[0];
+ wgeom_return[0]->width=wgeom2->width-x1[1]+x2[0];
+ wgeom_return[0]->height=wgeom2->height;
+//second
+ wgeom_return[1]->x=x2[0];
+ wgeom_return[1]->y=y2[0];
+ wgeom_return[1]->width=x1[1]-x2[0];
+ wgeom_return[1]->height=wgeom2->height-y2[1]+y1[0];
+ }
+ else if(enclosed[1][3]){
+//first(same as [1][1])
+ wgeom_return[0]->x=x2[0];
+ wgeom_return[0]->y=y2[0];
+ wgeom_return[0]->width=wgeom2->width-x2[1]+x1[0];
+ wgeom_return[0]->height=wgeom2->height;
+//second
+ wgeom_return[1]->x=x1[0];
+ wgeom_return[1]->y=y2[0];
+ wgeom_return[1]->width=x2[1]-x1[0];
+ wgeom_return[1]->height=wgeom2->height-y2[1]+y1[0];
+ }
+ return -2;
+ }
+ else{//polygons collide but no point of one is in the other
+ //so we just keep the two parts of geom2 that are outside geom1
+
+ //break geom2 in two
+ //two cases:
+ //geom2 crossing vertically geom1
+ //and geom2 crossing horizontally geom1
+ //The proper one can be found by simply checking x,y positions
+// wgeom_return[0]=(WGeometry *)malloc(sizeof(WGeometry));
+// wgeom_return[1]=(WGeometry *)malloc(sizeof(WGeometry));
+ *ngeoms=2;
+ if(wgeom2->y<wgeom1->y){
+ //common
+ wgeom_return[0]->x=wgeom_return[1]->x=x2[0];
+ wgeom_return[0]->width=wgeom_return[1]->width=wgeom2->width;
+
+ wgeom_return[0]->y=y2[0];
+ wgeom_return[0]->height=wgeom2->height-y2[1]+y1[0];
+ wgeom_return[1]->y=y1[1];
+ wgeom_return[1]->height=y2[1]-y1[1];
+ }
+ else{
+ //common
+ wgeom_return[0]->y=wgeom_return[1]->y=y2[0];
+ wgeom_return[0]->height=wgeom_return[1]->height=wgeom2->height;
+
+ wgeom_return[0]->x=x2[0];
+ wgeom_return[0]->width=wgeom2->width-x2[1]+x1[0];
+ wgeom_return[1]->x=x1[1];
+ wgeom_return[1]->width=x2[1]-x1[1];
+ }
+ return -2;
+ }
+ }
+}
+
+int RectInsert(RectArea **root,WGeometry *wgeom){
+
+ int total_insertions=0;
+ RectArea *temp,*newnode=(RectArea *)malloc(sizeof(RectArea));
+ newnode->geom.x=wgeom->x;
+ newnode->geom.y=wgeom->y;
+ newnode->geom.width=wgeom->width;
+ newnode->geom.height=wgeom->height;
+ newnode->prev=newnode->next=NULL;
+ if(*root==NULL){
+ *root=newnode;
+ total_insertions=1;
+ }
+ else{
+ WGeometry *wgeom_return[2];
+ wgeom_return[0]=(WGeometry *)malloc(sizeof(WGeometry));
+ wgeom_return[1]=(WGeometry *)malloc(sizeof(WGeometry));
+
+ int ngeoms=0,insert_ok=1,i=0;
+ temp=*root;
+ while(insert_ok){//if something is broken list does not procceed(except on -1 collres case)
+ int collres/*=0;//*/=CollideRects(&(temp->geom),wgeom,wgeom_return,&ngeoms);
+ if((!collres))
+ insert_ok=1;
+ else{
+ insert_ok=0;
+ switch(collres){
+ case 1://remove current node,reinsert new one
+ total_insertions--;
+ if(temp->prev!=NULL){//no root
+ if(temp->next!=NULL){//
+ temp->prev->next=temp->next;
+ temp->next->prev=temp->prev;
+ temp=temp->next;
+ if((wgeom->width>0)&&(wgeom->height>0))
+ total_insertions+=RectInsert(&temp,wgeom);
+ }
+ else{
+ temp->prev->next=newnode;
+ newnode->prev=temp->prev;
+ total_insertions++;
+ free(temp);
+ }
+ }
+ else{//root
+ if((*root)->next!=NULL){
+ (*root)=(*root)->next;
+ (*root)->prev=NULL;
+ if((wgeom->width>0)&&(wgeom->height>0))
+ total_insertions+=RectInsert(root,wgeom);
+ }
+ else if((wgeom->width>0)&&(wgeom->height>0)){
+ *root=newnode;
+ total_insertions++;
+ }
+ else{
+ *root=NULL;
+ total_insertions++;
+ }
+ free(temp);
+ }
+ break;
+ case 2://done,area is already covered
+ break;
+ case -1://current node is broken and reinserted(in same pos)
+ //newnode is also reinserted
+ if((wgeom_return[0]->width>0)&&(wgeom_return[0]->height>0)){
+ temp->geom.x=wgeom_return[0]->x;
+ temp->geom.y=wgeom_return[0]->y;
+ temp->geom.width=wgeom_return[0]->width;
+ temp->geom.height=wgeom_return[0]->height;
+ if(temp->next==NULL){
+ temp->next=newnode;
+ newnode->prev=temp;
+ total_insertions++;
+ }
+ else{
+ insert_ok=1;
+ }
+ }
+ else{//it might happen that the old and now broken node
+ //is of zero width or height(so it isn't reinserted)
+ /*TODO this may cause lines to be left not updated
+ so maybe it is needed to increase the size by one
+ pixel(zero width or height cause BadValue*/
+ if((temp->prev==NULL)&&(temp->next!=NULL)){
+ *root=(*root)->next;
+ (*root)->prev=NULL;
+ }
+ else if((temp->next==NULL)&&(temp->prev!=NULL)){
+ temp->prev->next=newnode;
+ newnode->prev=temp->prev;
+ }
+ else if((temp->next==NULL)&&(temp->prev==NULL))
+ (*root)=newnode;
+ else{
+ total_insertions--;
+ temp->next->prev=temp->prev;
+ temp->prev->next=temp->next;
+ total_insertions+=RectInsert(&temp->next,wgeom);
+ }
+ }
+ break;
+ case -2://new is broken and reinserted
+ if(temp->next==NULL){
+ total_insertions+=ngeoms;
+ newnode->geom.x=wgeom_return[0]->x;
+ newnode->geom.y=wgeom_return[0]->y;
+ newnode->geom.width=wgeom_return[0]->width;
+ newnode->geom.height=wgeom_return[0]->height;
+ temp->next=newnode;
+ newnode->prev=temp;
+ if(ngeoms>1){
+ RectArea *newnode1=(RectArea *)malloc(sizeof(RectArea));
+ newnode1->geom.x=wgeom_return[1]->x;
+ newnode1->geom.y=wgeom_return[1]->y;
+ newnode1->geom.width=wgeom_return[1]->width;
+ newnode1->geom.height=wgeom_return[1]->height;
+ newnode->next=newnode1;
+ newnode1->prev=newnode;
+ newnode1->next=NULL;
+ }
+ }
+ else{
+ for(i=0;i<ngeoms;i++){
+ if((wgeom_return[i]->width>0)&&(wgeom_return[i]->height>0))
+ total_insertions+=RectInsert(&temp->next,wgeom_return[i]);
+ }
+ }
+ break;
+ case -10://grouped
+ if(temp->prev==NULL){
+ if(temp->next==NULL){//empty list
+ newnode->geom.x=wgeom_return[0]->x;
+ newnode->geom.y=wgeom_return[0]->y;
+ newnode->geom.width=wgeom_return[0]->width;
+ newnode->geom.height=wgeom_return[0]->height;
+ *root=newnode;
+ }
+ else{
+ total_insertions--;
+ *root=temp->next;
+ (*root)->prev=NULL;
+ free(temp);
+ if((wgeom_return[0]->width>0)&&(wgeom_return[0]->height>0))
+ total_insertions+=RectInsert(root,wgeom_return[0]);
+ }
+ }
+ else if(temp->next==NULL){//last, enter anyway
+ newnode->geom.x=wgeom_return[0]->x;
+ newnode->geom.y=wgeom_return[0]->y;
+ newnode->geom.width=wgeom_return[0]->width;
+ newnode->geom.height=wgeom_return[0]->height;
+ temp->prev->next=newnode;
+ newnode->prev=temp->prev;
+ free(temp);
+ }
+ else{//remove node and reinsert, starting where we were
+ total_insertions--;
+ temp->prev->next=temp->next;
+ temp->next->prev=temp->prev;
+ temp=temp->next;
+ if((wgeom_return[0]->width>0)&&(wgeom_return[0]->height>0))
+ total_insertions+=RectInsert(&temp,wgeom_return[0]);
+ }
+ break;
+ }
+ }
+ if(insert_ok){
+ if(temp->next==NULL){
+ temp->next=newnode;
+ newnode->prev=temp;
+ total_insertions++;
+ break;
+ }
+ else{
+ temp=temp->next;
+ }
+ }
+ else{
+ break;
+ }
+ };
+ }
+ return total_insertions;
+}
+
+void ClearList(RectArea **root){
+
+ RectArea *temp;
+ temp=*root;
+ if(temp!=NULL){
+ while(temp->next!=NULL){
+ temp=temp->next;
+ free(temp->prev);
+
+ }
+ free(temp);
+ *root=NULL;
+ }
+}
+
© All Rights Reserved