1 /* ***** BEGIN LICENSE BLOCK *****
2 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
4 * The contents of this file are subject to the Mozilla Public License Version
5 * 1.1 (the "License"); you may not use this file except in compliance with
6 * the License. You may obtain a copy of the License at
7 * http://www.mozilla.org/MPL/
9 * Software distributed under the License is distributed on an "AS IS" basis,
10 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
11 * for the specific language governing rights and limitations under the
14 * The Original Code is mozilla.org code.
16 * The Initial Developer of the Original Code is
17 * Dainis Jonitis, <Dainis_Jonitis@swh-t.lv>.
18 * Portions created by the Initial Developer are Copyright (C) 2001
19 * the Initial Developer. All Rights Reserved.
23 * Alternatively, the contents of this file may be used under the terms of
24 * either of the GNU General Public License Version 2 or later (the "GPL"),
25 * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
26 * in which case the provisions of the GPL or the LGPL are applicable instead
27 * of those above. If you wish to allow use of your version of this file only
28 * under the terms of either the GPL or the LGPL, and not to allow others to
29 * use your version of this file under the terms of the MPL, indicate your
30 * decision by deleting the provisions above and replace them with the notice
31 * and other provisions required by the GPL or the LGPL. If you do not delete
32 * the provisions above, a recipient may use your version of this file under
33 * the terms of any one of the MPL, the GPL or the LGPL.
35 * ***** END LICENSE BLOCK ***** */
39 #include "nsISupportsImpl.h"
43 * The SENTINEL values below guaranties that a < or >
44 * comparison with it will be false for all values of the
45 * underlying nscoord type. E.g. this is always false:
46 * aCoord > NS_COORD_GREATER_SENTINEL
47 * Setting the mRectListHead dummy rectangle to these values
48 * allows us to loop without checking for the list end.
50 #ifdef NS_COORD_IS_FLOAT
51 #define NS_COORD_LESS_SENTINEL nscoord_MIN
52 #define NS_COORD_GREATER_SENTINEL nscoord_MAX
54 #define NS_COORD_LESS_SENTINEL PR_INT32_MIN
55 #define NS_COORD_GREATER_SENTINEL PR_INT32_MAX
58 // Fast inline analogues of nsRect methods for nsRegion::nsRectFast.
59 // Check for emptiness is not required - it is guaranteed by caller.
61 inline PRBool
nsRegion::nsRectFast::Contains (const nsRect
& aRect
) const
63 return (PRBool
) ((aRect
.x
>= x
) && (aRect
.y
>= y
) &&
64 (aRect
.XMost () <= XMost ()) && (aRect
.YMost () <= YMost ()));
67 inline PRBool
nsRegion::nsRectFast::Intersects (const nsRect
& aRect
) const
69 return (PRBool
) ((x
< aRect
.XMost ()) && (y
< aRect
.YMost ()) &&
70 (aRect
.x
< XMost ()) && (aRect
.y
< YMost ()));
73 inline PRBool
nsRegion::nsRectFast::IntersectRect (const nsRect
& aRect1
, const nsRect
& aRect2
)
75 const nscoord xmost
= PR_MIN (aRect1
.XMost (), aRect2
.XMost ());
76 x
= PR_MAX (aRect1
.x
, aRect2
.x
);
78 if (width
<= 0) return PR_FALSE
;
80 const nscoord ymost
= PR_MIN (aRect1
.YMost (), aRect2
.YMost ());
81 y
= PR_MAX (aRect1
.y
, aRect2
.y
);
83 if (height
<= 0) return PR_FALSE
;
88 inline void nsRegion::nsRectFast::UnionRect (const nsRect
& aRect1
, const nsRect
& aRect2
)
90 const nscoord xmost
= PR_MAX (aRect1
.XMost (), aRect2
.XMost ());
91 const nscoord ymost
= PR_MAX (aRect1
.YMost (), aRect2
.YMost ());
92 x
= PR_MIN (aRect1
.x
, aRect2
.x
);
93 y
= PR_MIN (aRect1
.y
, aRect2
.y
);
100 // Custom memory allocator for nsRegion::RgnRect structures.
101 // Entries are allocated from global memory pool.
102 // Memory pool can grow in size, but it can't shrink.
104 #define INIT_MEM_CHUNK_ENTRIES 100
105 #define INCR_MEM_CHUNK_ENTRIES 100
107 class RgnRectMemoryAllocator
109 nsRegion::RgnRect
* mFreeListHead
;
110 PRUint32 mFreeEntries
;
111 void* mChunkListHead
;
115 void InitLock () { mLock
= PR_NewLock (); }
116 void DestroyLock () { PR_DestroyLock (mLock
); }
117 void Lock () { PR_Lock (mLock
); }
118 void Unlock () { PR_Unlock (mLock
); }
119 #elif defined (DEBUG)
122 void InitLock () { NS_ASSERT_OWNINGTHREAD (RgnRectMemoryAllocator
); }
123 void DestroyLock () { NS_ASSERT_OWNINGTHREAD (RgnRectMemoryAllocator
); }
124 void Lock () { NS_ASSERT_OWNINGTHREAD (RgnRectMemoryAllocator
); }
125 void Unlock () { NS_ASSERT_OWNINGTHREAD (RgnRectMemoryAllocator
); }
128 void DestroyLock () { }
133 void* AllocChunk (PRUint32 aEntries
, void* aNextChunk
, nsRegion::RgnRect
* aTailDest
)
135 PRUint8
* pBuf
= new PRUint8
[aEntries
* sizeof (nsRegion::RgnRect
) + sizeof (void*)];
136 *reinterpret_cast<void**>(pBuf
) = aNextChunk
;
137 nsRegion::RgnRect
* pRect
= reinterpret_cast<nsRegion::RgnRect
*>(pBuf
+ sizeof (void*));
139 for (PRUint32 cnt
= 0 ; cnt
< aEntries
- 1 ; cnt
++)
140 pRect
[cnt
].next
= &pRect
[cnt
+ 1];
142 pRect
[aEntries
- 1].next
= aTailDest
;
147 void FreeChunk (void* aChunk
) { delete [] (PRUint8
*) aChunk
; }
148 void* NextChunk (void* aThisChunk
) const { return *static_cast<void**>(aThisChunk
); }
150 nsRegion::RgnRect
* ChunkHead (void* aThisChunk
) const
151 { return reinterpret_cast<nsRegion::RgnRect
*>(static_cast<PRUint8
*>(aThisChunk
) + sizeof (void*)); }
154 RgnRectMemoryAllocator (PRUint32 aNumOfEntries
);
155 ~RgnRectMemoryAllocator ();
157 nsRegion::RgnRect
* Alloc ();
158 void Free (nsRegion::RgnRect
* aRect
);
162 RgnRectMemoryAllocator::RgnRectMemoryAllocator (PRUint32 aNumOfEntries
)
165 mChunkListHead
= AllocChunk (aNumOfEntries
, nsnull
, nsnull
);
166 mFreeEntries
= aNumOfEntries
;
167 mFreeListHead
= ChunkHead (mChunkListHead
);
170 RgnRectMemoryAllocator::~RgnRectMemoryAllocator ()
172 while (mChunkListHead
)
174 void* tmp
= mChunkListHead
;
175 mChunkListHead
= NextChunk (mChunkListHead
);
181 * As a static object this class outlives any library which would implement
182 * locking. So we intentionally leak the 'lock'.
184 * Currently RgnRectMemoryAllocator is only used from the primary thread,
185 * so we aren't using a lock which means that there is no lock to leak.
186 * If we ever switch to multiple GUI threads (e.g. one per window),
187 * we'd probably use one allocator per window-thread to avoid the
188 * locking overhead and just require consumers not to pass regions
189 * across threads/windows, which would be a reasonable restriction
190 * because they wouldn't be useful outside their window.
196 nsRegion::RgnRect
* RgnRectMemoryAllocator::Alloc ()
200 if (mFreeEntries
== 0)
202 mChunkListHead
= AllocChunk (INCR_MEM_CHUNK_ENTRIES
, mChunkListHead
, mFreeListHead
);
203 mFreeEntries
= INCR_MEM_CHUNK_ENTRIES
;
204 mFreeListHead
= ChunkHead (mChunkListHead
);
207 nsRegion::RgnRect
* tmp
= mFreeListHead
;
208 mFreeListHead
= mFreeListHead
->next
;
215 void RgnRectMemoryAllocator::Free (nsRegion::RgnRect
* aRect
)
219 aRect
->next
= mFreeListHead
;
220 mFreeListHead
= aRect
;
225 // Global pool for nsRegion::RgnRect allocation
226 static RgnRectMemoryAllocator
* gRectPool
;
228 nsresult
nsRegion::InitStatic()
230 gRectPool
= new RgnRectMemoryAllocator(INIT_MEM_CHUNK_ENTRIES
);
231 return !gRectPool
? NS_ERROR_OUT_OF_MEMORY
: NS_OK
;
234 void nsRegion::ShutdownStatic()
239 void* nsRegion::RgnRect::operator new (size_t) CPP_THROW_NEW
241 return gRectPool
->Alloc ();
244 void nsRegion::RgnRect::operator delete (void* aRect
, size_t)
246 gRectPool
->Free (static_cast<RgnRect
*>(aRect
));
251 void nsRegion::Init()
253 mRectListHead
.prev
= mRectListHead
.next
= &mRectListHead
;
254 mCurRect
= &mRectListHead
;
256 mBoundRect
.SetRect (0, 0, 0, 0);
259 inline void nsRegion::InsertBefore (RgnRect
* aNewRect
, RgnRect
* aRelativeRect
)
261 aNewRect
->prev
= aRelativeRect
->prev
;
262 aNewRect
->next
= aRelativeRect
;
263 aRelativeRect
->prev
->next
= aNewRect
;
264 aRelativeRect
->prev
= aNewRect
;
269 inline void nsRegion::InsertAfter (RgnRect
* aNewRect
, RgnRect
* aRelativeRect
)
271 aNewRect
->prev
= aRelativeRect
;
272 aNewRect
->next
= aRelativeRect
->next
;
273 aRelativeRect
->next
->prev
= aNewRect
;
274 aRelativeRect
->next
= aNewRect
;
280 // Adjust the number of rectangles in region.
281 // Content of rectangles should be changed by caller.
283 void nsRegion::SetToElements (PRUint32 aCount
)
285 if (mRectCount
< aCount
) // Add missing rectangles
287 PRUint32 InsertCount
= aCount
- mRectCount
;
289 RgnRect
* pPrev
= &mRectListHead
;
290 RgnRect
* pNext
= mRectListHead
.next
;
292 while (InsertCount
--)
294 mCurRect
= new RgnRect
;
295 mCurRect
->prev
= pPrev
;
296 pPrev
->next
= mCurRect
;
303 if (mRectCount
> aCount
) // Remove unnecessary rectangles
305 PRUint32 RemoveCount
= mRectCount
- aCount
;
307 mCurRect
= mRectListHead
.next
;
309 while (RemoveCount
--)
311 RgnRect
* tmp
= mCurRect
;
312 mCurRect
= mCurRect
->next
;
316 mRectListHead
.next
= mCurRect
;
317 mCurRect
->prev
= &mRectListHead
;
322 // Save the entire chain of linked elements in 'prev' field of the RgnRect structure.
323 // After that forward-only iterations using 'next' field could still be used.
324 // Some elements from forward-only chain could be temporarily removed to optimize inner loops.
325 // The original double linked state could be restored by call to RestoreLinkChain ().
326 // Both functions despite size can be inline because they are called only from one function.
328 inline void nsRegion::SaveLinkChain ()
330 RgnRect
* pRect
= &mRectListHead
;
334 pRect
->prev
= pRect
->next
;
336 } while (pRect
!= &mRectListHead
);
340 inline void nsRegion::RestoreLinkChain ()
342 RgnRect
* pPrev
= &mRectListHead
;
343 RgnRect
* pRect
= mRectListHead
.next
= mRectListHead
.prev
;
345 while (pRect
!= &mRectListHead
)
347 pRect
->next
= pRect
->prev
;
353 mRectListHead
.prev
= pPrev
;
357 // Insert node in right place of sorted list
358 // If necessary then bounding rectangle could be updated and rectangle combined
359 // with neighbour rectangles. This is usually done in Optimize ()
361 void nsRegion::InsertInPlace (RgnRect
* aRect
, PRBool aOptimizeOnFly
)
364 InsertAfter (aRect
, &mRectListHead
);
367 if (aRect
->y
> mCurRect
->y
)
369 mRectListHead
.y
= NS_COORD_GREATER_SENTINEL
;
370 while (aRect
->y
> mCurRect
->next
->y
)
371 mCurRect
= mCurRect
->next
;
373 mRectListHead
.x
= NS_COORD_GREATER_SENTINEL
;
374 while (aRect
->y
== mCurRect
->next
->y
&& aRect
->x
> mCurRect
->next
->x
)
375 mCurRect
= mCurRect
->next
;
377 InsertAfter (aRect
, mCurRect
);
379 if (aRect
->y
< mCurRect
->y
)
381 mRectListHead
.y
= NS_COORD_LESS_SENTINEL
;
382 while (aRect
->y
< mCurRect
->prev
->y
)
383 mCurRect
= mCurRect
->prev
;
385 mRectListHead
.x
= NS_COORD_LESS_SENTINEL
;
386 while (aRect
->y
== mCurRect
->prev
->y
&& aRect
->x
< mCurRect
->prev
->x
)
387 mCurRect
= mCurRect
->prev
;
389 InsertBefore (aRect
, mCurRect
);
392 if (aRect
->x
> mCurRect
->x
)
394 mRectListHead
.x
= NS_COORD_GREATER_SENTINEL
;
395 while (aRect
->y
== mCurRect
->next
->y
&& aRect
->x
> mCurRect
->next
->x
)
396 mCurRect
= mCurRect
->next
;
398 InsertAfter (aRect
, mCurRect
);
401 mRectListHead
.x
= NS_COORD_LESS_SENTINEL
;
402 while (aRect
->y
== mCurRect
->prev
->y
&& aRect
->x
< mCurRect
->prev
->x
)
403 mCurRect
= mCurRect
->prev
;
405 InsertBefore (aRect
, mCurRect
);
414 mBoundRect
= *mCurRect
;
417 mBoundRect
.UnionRect (mBoundRect
, *mCurRect
);
419 // Check if we can go left or up before starting to combine rectangles
420 if ((mCurRect
->y
== mCurRect
->prev
->y
&& mCurRect
->height
== mCurRect
->prev
->height
&&
421 mCurRect
->x
== mCurRect
->prev
->XMost ()) ||
422 (mCurRect
->x
== mCurRect
->prev
->x
&& mCurRect
->width
== mCurRect
->prev
->width
&&
423 mCurRect
->y
== mCurRect
->prev
->YMost ()) )
424 mCurRect
= mCurRect
->prev
;
426 // Try to combine with rectangle on right side
427 while (mCurRect
->y
== mCurRect
->next
->y
&& mCurRect
->height
== mCurRect
->next
->height
&&
428 mCurRect
->XMost () == mCurRect
->next
->x
)
430 mCurRect
->width
+= mCurRect
->next
->width
;
431 delete Remove (mCurRect
->next
);
434 // Try to combine with rectangle under this one
435 while (mCurRect
->x
== mCurRect
->next
->x
&& mCurRect
->width
== mCurRect
->next
->width
&&
436 mCurRect
->YMost () == mCurRect
->next
->y
)
438 mCurRect
->height
+= mCurRect
->next
->height
;
439 delete Remove (mCurRect
->next
);
446 nsRegion::RgnRect
* nsRegion::Remove (RgnRect
* aRect
)
448 aRect
->prev
->next
= aRect
->next
;
449 aRect
->next
->prev
= aRect
->prev
;
452 if (mCurRect
== aRect
)
453 mCurRect
= (aRect
->next
!= &mRectListHead
) ? aRect
->next
: aRect
->prev
;
459 // Try to reduce the number of rectangles in complex region by combining with
460 // surrounding ones on right and bottom sides of each rectangle in list.
461 // Update bounding rectangle
463 void nsRegion::Optimize ()
466 mBoundRect
.SetRect (0, 0, 0, 0);
469 RgnRect
* pRect
= mRectListHead
.next
;
470 PRInt32 xmost
= mRectListHead
.prev
->XMost ();
471 PRInt32 ymost
= mRectListHead
.prev
->YMost ();
472 mBoundRect
.x
= mRectListHead
.next
->x
;
473 mBoundRect
.y
= mRectListHead
.next
->y
;
475 while (pRect
!= &mRectListHead
)
477 // Try to combine with rectangle on right side
478 while (pRect
->y
== pRect
->next
->y
&& pRect
->height
== pRect
->next
->height
&&
479 pRect
->XMost () == pRect
->next
->x
)
481 pRect
->width
+= pRect
->next
->width
;
482 delete Remove (pRect
->next
);
485 // Try to combine with rectangle under this one
486 while (pRect
->x
== pRect
->next
->x
&& pRect
->width
== pRect
->next
->width
&&
487 pRect
->YMost () == pRect
->next
->y
)
489 pRect
->height
+= pRect
->next
->height
;
490 delete Remove (pRect
->next
);
493 // Determine bound rectangle. Use fact that rectangles are sorted.
494 if (pRect
->x
< mBoundRect
.x
) mBoundRect
.x
= pRect
->x
;
495 if (pRect
->XMost () > xmost
) xmost
= pRect
->XMost ();
496 if (pRect
->YMost () > ymost
) ymost
= pRect
->YMost ();
501 mBoundRect
.width
= xmost
- mBoundRect
.x
;
502 mBoundRect
.height
= ymost
- mBoundRect
.y
;
507 // Move rectangles starting from 'aStartRect' till end of the list to the destionation region.
508 // Important for temporary objects - instead of copying rectangles with Merge () and then
509 // emptying region in destructor they could be moved to destination region in one step.
511 void nsRegion::MoveInto (nsRegion
& aDestRegion
, const RgnRect
* aStartRect
)
513 RgnRect
* pRect
= const_cast<RgnRect
*>(aStartRect
);
514 RgnRect
* pPrev
= pRect
->prev
;
516 while (pRect
!= &mRectListHead
)
518 RgnRect
* next
= pRect
->next
;
519 aDestRegion
.InsertInPlace (pRect
);
525 pPrev
->next
= &mRectListHead
;
526 mRectListHead
.prev
= pPrev
;
527 mCurRect
= mRectListHead
.next
;
531 // Merge two non-overlapping regions into one.
532 // Automatically optimize region by calling Optimize ()
534 void nsRegion::Merge (const nsRegion
& aRgn1
, const nsRegion
& aRgn2
)
536 if (aRgn1
.mRectCount
== 0) // Region empty. Result is equal to other region
539 if (aRgn2
.mRectCount
== 0) // Region empty. Result is equal to other region
541 if (aRgn1
.mRectCount
== 1) // Region is single rectangle. Optimize on fly
543 RgnRect
* TmpRect
= new RgnRect (*aRgn1
.mRectListHead
.next
);
545 InsertInPlace (TmpRect
, PR_TRUE
);
547 if (aRgn2
.mRectCount
== 1) // Region is single rectangle. Optimize on fly
549 RgnRect
* TmpRect
= new RgnRect (*aRgn2
.mRectListHead
.next
);
551 InsertInPlace (TmpRect
, PR_TRUE
);
554 const nsRegion
* pCopyRegion
, *pInsertRegion
;
556 // Determine which region contains more rectangles. Copy the larger one
557 if (aRgn1
.mRectCount
>= aRgn2
.mRectCount
)
559 pCopyRegion
= &aRgn1
;
560 pInsertRegion
= &aRgn2
;
563 pCopyRegion
= &aRgn2
;
564 pInsertRegion
= &aRgn1
;
567 if (pInsertRegion
== this) // Do merge in-place
568 pInsertRegion
= pCopyRegion
;
572 const RgnRect
* pSrcRect
= pInsertRegion
->mRectListHead
.next
;
574 while (pSrcRect
!= &pInsertRegion
->mRectListHead
)
576 InsertInPlace (new RgnRect (*pSrcRect
));
578 pSrcRect
= pSrcRect
->next
;
586 nsRegion
& nsRegion::Copy (const nsRegion
& aRegion
)
588 if (&aRegion
== this)
591 if (aRegion
.mRectCount
== 0)
595 SetToElements (aRegion
.mRectCount
);
597 const RgnRect
* pSrc
= aRegion
.mRectListHead
.next
;
598 RgnRect
* pDest
= mRectListHead
.next
;
600 while (pSrc
!= &aRegion
.mRectListHead
)
608 mCurRect
= mRectListHead
.next
;
609 mBoundRect
= aRegion
.mBoundRect
;
616 nsRegion
& nsRegion::Copy (const nsRect
& aRect
)
618 if (aRect
.IsEmpty ())
623 *mRectListHead
.next
= static_cast<const RgnRect
&>(aRect
);
624 mBoundRect
= static_cast<const nsRectFast
&>(aRect
);
631 nsRegion
& nsRegion::And (const nsRegion
& aRgn1
, const nsRegion
& aRgn2
)
633 if (&aRgn1
== &aRgn2
) // And with self
636 if (aRgn1
.mRectCount
== 0 || aRgn2
.mRectCount
== 0) // If either region is empty then result is empty
642 if (aRgn1
.mRectCount
== 1 && aRgn2
.mRectCount
== 1) // Intersect rectangle with rectangle
644 TmpRect
.IntersectRect (*aRgn1
.mRectListHead
.next
, *aRgn2
.mRectListHead
.next
);
648 if (!aRgn1
.mBoundRect
.Intersects (aRgn2
.mBoundRect
)) // Regions do not intersect
652 // Region is simple rectangle and it fully overlays other region
653 if (aRgn1
.mRectCount
== 1 && aRgn1
.mBoundRect
.Contains (aRgn2
.mBoundRect
))
656 // Region is simple rectangle and it fully overlays other region
657 if (aRgn2
.mRectCount
== 1 && aRgn2
.mBoundRect
.Contains (aRgn1
.mBoundRect
))
662 nsRegion
* pSrcRgn1
= const_cast<nsRegion
*>(&aRgn1
);
663 nsRegion
* pSrcRgn2
= const_cast<nsRegion
*>(&aRgn2
);
665 if (&aRgn1
== this) // Copy region if it is both source and result
667 TmpRegion
.Copy (aRgn1
);
668 pSrcRgn1
= &TmpRegion
;
671 if (&aRgn2
== this) // Copy region if it is both source and result
673 TmpRegion
.Copy (aRgn2
);
674 pSrcRgn2
= &TmpRegion
;
677 // For outer loop prefer region for which at least one rectangle is below other's bound rectangle
678 if (pSrcRgn2
->mRectListHead
.prev
->y
>= pSrcRgn1
->mBoundRect
.YMost ())
680 nsRegion
* Tmp
= pSrcRgn1
;
687 pSrcRgn2
->SaveLinkChain ();
689 pSrcRgn1
->mRectListHead
.y
= NS_COORD_GREATER_SENTINEL
;
690 pSrcRgn2
->mRectListHead
.y
= NS_COORD_GREATER_SENTINEL
;
692 for (RgnRect
* pSrcRect1
= pSrcRgn1
->mRectListHead
.next
;
693 pSrcRect1
->y
< pSrcRgn2
->mBoundRect
.YMost () ; pSrcRect1
= pSrcRect1
->next
)
695 if (pSrcRect1
->Intersects (pSrcRgn2
->mBoundRect
)) // Rectangle intersects region. Process each rectangle
697 RgnRect
* pPrev2
= &pSrcRgn2
->mRectListHead
;
699 for (RgnRect
* pSrcRect2
= pSrcRgn2
->mRectListHead
.next
;
700 pSrcRect2
->y
< pSrcRect1
->YMost () ; pSrcRect2
= pSrcRect2
->next
)
702 if (pSrcRect2
->YMost () <= pSrcRect1
->y
) // Rect2's bottom is above the top of Rect1.
703 { // No successive rectangles in Rgn1 can intersect it.
704 pPrev2
->next
= pSrcRect2
->next
; // Remove Rect2 from Rgn2's checklist
708 if (pSrcRect1
->Contains (*pSrcRect2
)) // Rect1 fully overlays Rect2.
709 { // No any other rectangle in Rgn1 can intersect it.
710 pPrev2
->next
= pSrcRect2
->next
; // Remove Rect2 from Rgn2's checklist
711 InsertInPlace (new RgnRect (*pSrcRect2
));
716 if (TmpRect
.IntersectRect (*pSrcRect1
, *pSrcRect2
))
717 InsertInPlace (new RgnRect (TmpRect
));
724 pSrcRgn2
->RestoreLinkChain ();
735 nsRegion
& nsRegion::And (const nsRegion
& aRegion
, const nsRect
& aRect
)
737 // If either region or rectangle is empty then result is empty
738 if (aRegion
.mRectCount
== 0 || aRect
.IsEmpty ())
740 else // Intersect region with rectangle
742 const nsRectFast
& aRectFast
= static_cast<const nsRectFast
&>(aRect
);
745 if (aRegion
.mRectCount
== 1) // Intersect rectangle with rectangle
747 TmpRect
.IntersectRect (*aRegion
.mRectListHead
.next
, aRectFast
);
749 } else // Intersect complex region with rectangle
751 if (!aRectFast
.Intersects (aRegion
.mBoundRect
)) // Rectangle does not intersect region
755 if (aRectFast
.Contains (aRegion
.mBoundRect
)) // Rectangle fully overlays region
760 nsRegion
* pSrcRegion
= const_cast<nsRegion
*>(&aRegion
);
762 if (&aRegion
== this) // Copy region if it is both source and result
764 TmpRegion
.Copy (aRegion
);
765 pSrcRegion
= &TmpRegion
;
769 pSrcRegion
->mRectListHead
.y
= NS_COORD_GREATER_SENTINEL
;
771 for (const RgnRect
* pSrcRect
= pSrcRegion
->mRectListHead
.next
;
772 pSrcRect
->y
< aRectFast
.YMost () ; pSrcRect
= pSrcRect
->next
)
774 if (TmpRect
.IntersectRect (*pSrcRect
, aRectFast
))
775 InsertInPlace (new RgnRect (TmpRect
));
788 nsRegion
& nsRegion::Or (const nsRegion
& aRgn1
, const nsRegion
& aRgn2
)
790 if (&aRgn1
== &aRgn2
) // Or with self
793 if (aRgn1
.mRectCount
== 0) // Region empty. Result is equal to other region
796 if (aRgn2
.mRectCount
== 0) // Region empty. Result is equal to other region
800 if (!aRgn1
.mBoundRect
.Intersects (aRgn2
.mBoundRect
)) // Regions do not intersect
801 Merge (aRgn1
, aRgn2
);
804 // Region is simple rectangle and it fully overlays other region
805 if (aRgn1
.mRectCount
== 1 && aRgn1
.mBoundRect
.Contains (aRgn2
.mBoundRect
))
808 // Region is simple rectangle and it fully overlays other region
809 if (aRgn2
.mRectCount
== 1 && aRgn2
.mBoundRect
.Contains (aRgn1
.mBoundRect
))
814 aRgn1
.SubRegion (aRgn2
, TmpRegion
); // Get only parts of region which not overlap the other region
816 TmpRegion
.MoveInto (*this);
826 nsRegion
& nsRegion::Or (const nsRegion
& aRegion
, const nsRect
& aRect
)
828 if (aRegion
.mRectCount
== 0) // Region empty. Result is equal to rectangle
831 if (aRect
.IsEmpty ()) // Rectangle is empty. Result is equal to region
835 const nsRectFast
& aRectFast
= static_cast<const nsRectFast
&>(aRect
);
837 if (!aRectFast
.Intersects (aRegion
.mBoundRect
)) // Rectangle does not intersect region
840 InsertInPlace (new RgnRect (aRectFast
), PR_TRUE
);
843 // Region is simple rectangle and it fully overlays rectangle
844 if (aRegion
.mRectCount
== 1 && aRegion
.mBoundRect
.Contains (aRectFast
))
847 if (aRectFast
.Contains (aRegion
.mBoundRect
)) // Rectangle fully overlays region
851 aRegion
.SubRect (aRectFast
, *this); // Exclude from region parts that overlap the rectangle
852 InsertInPlace (new RgnRect (aRectFast
));
862 nsRegion
& nsRegion::Xor (const nsRegion
& aRgn1
, const nsRegion
& aRgn2
)
864 if (&aRgn1
== &aRgn2
) // Xor with self
867 if (aRgn1
.mRectCount
== 0) // Region empty. Result is equal to other region
870 if (aRgn2
.mRectCount
== 0) // Region empty. Result is equal to other region
874 if (!aRgn1
.mBoundRect
.Intersects (aRgn2
.mBoundRect
)) // Regions do not intersect
875 Merge (aRgn1
, aRgn2
);
878 // Region is simple rectangle and it fully overlays other region
879 if (aRgn1
.mRectCount
== 1 && aRgn1
.mBoundRect
.Contains (aRgn2
.mBoundRect
))
881 aRgn1
.SubRegion (aRgn2
, *this);
884 // Region is simple rectangle and it fully overlays other region
885 if (aRgn2
.mRectCount
== 1 && aRgn2
.mBoundRect
.Contains (aRgn1
.mBoundRect
))
887 aRgn2
.SubRegion (aRgn1
, *this);
892 aRgn1
.SubRegion (aRgn2
, TmpRegion
);
893 aRgn2
.SubRegion (aRgn1
, *this);
894 TmpRegion
.MoveInto (*this);
904 nsRegion
& nsRegion::Xor (const nsRegion
& aRegion
, const nsRect
& aRect
)
906 if (aRegion
.mRectCount
== 0) // Region empty. Result is equal to rectangle
909 if (aRect
.IsEmpty ()) // Rectangle is empty. Result is equal to region
913 const nsRectFast
& aRectFast
= static_cast<const nsRectFast
&>(aRect
);
915 if (!aRectFast
.Intersects (aRegion
.mBoundRect
)) // Rectangle does not intersect region
918 InsertInPlace (new RgnRect (aRectFast
), PR_TRUE
);
921 // Region is simple rectangle and it fully overlays rectangle
922 if (aRegion
.mRectCount
== 1 && aRegion
.mBoundRect
.Contains (aRectFast
))
924 aRegion
.SubRect (aRectFast
, *this);
927 if (aRectFast
.Contains (aRegion
.mBoundRect
)) // Rectangle fully overlays region
930 TmpRegion
.Copy (aRectFast
);
931 TmpRegion
.SubRegion (aRegion
, *this);
936 TmpRegion
.Copy (aRectFast
);
937 TmpRegion
.SubRegion (aRegion
, TmpRegion
);
938 aRegion
.SubRect (aRectFast
, *this);
939 TmpRegion
.MoveInto (*this);
949 nsRegion
& nsRegion::Sub (const nsRegion
& aRgn1
, const nsRegion
& aRgn2
)
951 if (&aRgn1
== &aRgn2
) // Sub from self
954 if (aRgn1
.mRectCount
== 0) // If source is empty then result is empty, too
957 if (aRgn2
.mRectCount
== 0) // Nothing to subtract
961 if (!aRgn1
.mBoundRect
.Intersects (aRgn2
.mBoundRect
)) // Regions do not intersect
965 aRgn1
.SubRegion (aRgn2
, *this);
974 nsRegion
& nsRegion::Sub (const nsRegion
& aRegion
, const nsRect
& aRect
)
976 if (aRegion
.mRectCount
== 0) // If source is empty then result is empty, too
979 if (aRect
.IsEmpty ()) // Nothing to subtract
983 const nsRectFast
& aRectFast
= static_cast<const nsRectFast
&>(aRect
);
985 if (!aRectFast
.Intersects (aRegion
.mBoundRect
)) // Rectangle does not intersect region
989 if (aRectFast
.Contains (aRegion
.mBoundRect
)) // Rectangle fully overlays region
993 aRegion
.SubRect (aRectFast
, *this);
1002 PRBool
nsRegion::Contains (const nsRect
& aRect
) const
1004 if (aRect
.IsEmpty())
1009 return mBoundRect
.Contains (aRect
);
1012 tmpRgn
.Sub(aRect
, *this);
1013 return tmpRgn
.IsEmpty();
1016 PRBool
nsRegion::Intersects (const nsRect
& aRect
) const
1018 if (aRect
.IsEmpty() || IsEmpty())
1021 const RgnRect
* r
= mRectListHead
.next
;
1022 while (r
!= &mRectListHead
)
1024 if (r
->Intersects(aRect
))
1031 // Subtract region from current region.
1032 // Both regions are non-empty and they intersect each other.
1033 // Result could be empty region if aRgn2 is rectangle that fully overlays aRgn1.
1034 // Optimize () is not called on exit (bound rectangle is not updated).
1036 void nsRegion::SubRegion (const nsRegion
& aRegion
, nsRegion
& aResult
) const
1038 if (aRegion
.mRectCount
== 1) // Subtract simple rectangle
1040 if (aRegion
.mBoundRect
.Contains (mBoundRect
))
1041 aResult
.SetEmpty ();
1043 SubRect (*aRegion
.mRectListHead
.next
, aResult
);
1046 nsRegion TmpRegion
, CompletedRegion
;
1047 const nsRegion
* pSubRgn
= &aRegion
;
1049 if (&aResult
== &aRegion
) // Copy region if it is both source and result
1051 TmpRegion
.Copy (aRegion
);
1052 pSubRgn
= &TmpRegion
;
1055 const RgnRect
* pSubRect
= pSubRgn
->mRectListHead
.next
;
1057 SubRect (*pSubRect
, aResult
, CompletedRegion
);
1058 pSubRect
= pSubRect
->next
;
1060 while (pSubRect
!= &pSubRgn
->mRectListHead
)
1062 aResult
.SubRect (*pSubRect
, aResult
, CompletedRegion
);
1063 pSubRect
= pSubRect
->next
;
1066 CompletedRegion
.MoveInto (aResult
);
1071 // Subtract rectangle from current region.
1072 // Both region and rectangle are non-empty and they intersect each other.
1073 // Result could be empty region if aRect fully overlays aRegion.
1074 // Could be called repeatedly with 'this' as input and result - bound rectangle is not known.
1075 // Optimize () is not called on exit (bound rectangle is not updated).
1077 // aCompleted is filled with rectangles which are already checked and could be safely
1078 // removed from further examination in case aRect rectangles come from ordered list.
1079 // aCompleted is not automatically emptied. aCompleted and aResult could be the same region.
1081 void nsRegion::SubRect (const nsRectFast
& aRect
, nsRegion
& aResult
, nsRegion
& aCompleted
) const
1084 const nsRegion
* pSrcRegion
= this;
1086 if (&aResult
== this) // Copy region if it is both source and result
1088 TmpRegion
.Copy (*this);
1089 pSrcRegion
= &TmpRegion
;
1092 aResult
.SetToElements (0);
1094 const_cast<nsRegion
*>(pSrcRegion
)->mRectListHead
.y
= NS_COORD_GREATER_SENTINEL
;
1095 const RgnRect
* pSrcRect
= pSrcRegion
->mRectListHead
.next
;
1097 for ( ; pSrcRect
->y
< aRect
.YMost () ; pSrcRect
= pSrcRect
->next
)
1101 // If bottom of current rectangle is above the top of aRect then this rectangle
1102 // could be moved to aCompleted region. Successive aRect rectangles from ordered
1103 // list do not have to check this rectangle again.
1104 if (pSrcRect
->YMost () <= aRect
.y
)
1106 aCompleted
.InsertInPlace (new RgnRect (*pSrcRect
));
1110 if (!TmpRect
.IntersectRect (*pSrcRect
, aRect
))
1111 aResult
.InsertInPlace (new RgnRect (*pSrcRect
));
1114 // Rectangle A. Subtract from this rectangle B
1115 const nscoord ax
= pSrcRect
->x
;
1116 const nscoord axm
= pSrcRect
->XMost ();
1117 const nscoord aw
= pSrcRect
->width
;
1118 const nscoord ay
= pSrcRect
->y
;
1119 const nscoord aym
= pSrcRect
->YMost ();
1120 const nscoord ah
= pSrcRect
->height
;
1121 // Rectangle B. Subtract this from rectangle A
1122 const nscoord bx
= aRect
.x
;
1123 const nscoord bxm
= aRect
.XMost ();
1124 const nscoord by
= aRect
.y
;
1125 const nscoord bym
= aRect
.YMost ();
1126 // Rectangle I. Area where rectangles A and B intersect
1127 const nscoord ix
= TmpRect
.x
;
1128 const nscoord ixm
= TmpRect
.XMost ();
1129 const nscoord iy
= TmpRect
.y
;
1130 const nscoord iym
= TmpRect
.YMost ();
1131 const nscoord ih
= TmpRect
.height
;
1133 // There are 16 combinations how rectangles could intersect
1135 if (bx
<= ax
&& by
<= ay
)
1137 if (bxm
< axm
&& bym
< aym
) // 1.
1139 aResult
.InsertInPlace (new RgnRect (ixm
, ay
, axm
- ixm
, ih
));
1140 aResult
.InsertInPlace (new RgnRect (ax
, iym
, aw
, aym
- iym
));
1142 if (bxm
>= axm
&& bym
< aym
) // 2.
1144 aResult
.InsertInPlace (new RgnRect (ax
, iym
, aw
, aym
- iym
));
1146 if (bxm
< axm
&& bym
>= aym
) // 3.
1148 aResult
.InsertInPlace (new RgnRect (ixm
, ay
, axm
- ixm
, ah
));
1150 if (*pSrcRect
== aRect
) // 4. subset
1151 { // Current rectangle is equal to aRect
1152 pSrcRect
= pSrcRect
->next
; // don't add this one to the result, it's removed
1153 break; // No any other rectangle in region can intersect it
1156 if (bx
> ax
&& by
<= ay
)
1158 if (bxm
< axm
&& bym
< aym
) // 5.
1160 aResult
.InsertInPlace (new RgnRect (ax
, ay
, ix
- ax
, ih
));
1161 aResult
.InsertInPlace (new RgnRect (ixm
, ay
, axm
- ixm
, ih
));
1162 aResult
.InsertInPlace (new RgnRect (ax
, iym
, aw
, aym
- iym
));
1164 if (bxm
>= axm
&& bym
< aym
) // 6.
1166 aResult
.InsertInPlace (new RgnRect (ax
, ay
, ix
- ax
, ih
));
1167 aResult
.InsertInPlace (new RgnRect (ax
, iym
, aw
, aym
- iym
));
1169 if (bxm
< axm
&& bym
>= aym
) // 7.
1171 aResult
.InsertInPlace (new RgnRect (ax
, ay
, ix
- ax
, ah
));
1172 aResult
.InsertInPlace (new RgnRect (ixm
, ay
, axm
- ixm
, ah
));
1174 if (bxm
>= axm
&& bym
>= aym
) // 8.
1176 aResult
.InsertInPlace (new RgnRect (ax
, ay
, ix
- ax
, ah
));
1179 if (bx
<= ax
&& by
> ay
)
1181 if (bxm
< axm
&& bym
< aym
) // 9.
1183 aResult
.InsertInPlace (new RgnRect (ax
, ay
, aw
, iy
- ay
));
1184 aResult
.InsertInPlace (new RgnRect (ixm
, iy
, axm
- ixm
, ih
));
1185 aResult
.InsertInPlace (new RgnRect (ax
, iym
, aw
, aym
- iym
));
1187 if (bxm
>= axm
&& bym
< aym
) // 10.
1189 aResult
.InsertInPlace (new RgnRect (ax
, ay
, aw
, iy
- ay
));
1190 aResult
.InsertInPlace (new RgnRect (ax
, iym
, aw
, aym
- iym
));
1192 if (bxm
< axm
&& bym
>= aym
) // 11.
1194 aResult
.InsertInPlace (new RgnRect (ax
, ay
, aw
, iy
- ay
));
1195 aResult
.InsertInPlace (new RgnRect (ixm
, iy
, axm
- ixm
, ih
));
1197 if (bxm
>= axm
&& bym
>= aym
) // 12.
1199 aResult
.InsertInPlace (new RgnRect (ax
, ay
, aw
, iy
- ay
));
1202 if (bx
> ax
&& by
> ay
)
1204 if (bxm
< axm
&& bym
< aym
) // 13.
1206 aResult
.InsertInPlace (new RgnRect (ax
, ay
, aw
, iy
- ay
));
1207 aResult
.InsertInPlace (new RgnRect (ax
, iy
, ix
- ax
, ih
));
1208 aResult
.InsertInPlace (new RgnRect (ixm
, iy
, axm
- ixm
, ih
));
1209 aResult
.InsertInPlace (new RgnRect (ax
, iym
, aw
, aym
- iym
));
1211 // Current rectangle fully overlays aRect. No any other rectangle can intersect it.
1212 pSrcRect
= pSrcRect
->next
; // don't add this one to the result, it's removed
1215 if (bxm
>= axm
&& bym
< aym
) // 14.
1217 aResult
.InsertInPlace (new RgnRect (ax
, ay
, aw
, iy
- ay
));
1218 aResult
.InsertInPlace (new RgnRect (ax
, iy
, ix
- ax
, ih
));
1219 aResult
.InsertInPlace (new RgnRect (ax
, iym
, aw
, aym
- iym
));
1221 if (bxm
< axm
&& bym
>= aym
) // 15.
1223 aResult
.InsertInPlace (new RgnRect (ax
, ay
, aw
, iy
- ay
));
1224 aResult
.InsertInPlace (new RgnRect (ax
, iy
, ix
- ax
, ih
));
1225 aResult
.InsertInPlace (new RgnRect (ixm
, iy
, axm
- ixm
, ih
));
1227 if (bxm
>= axm
&& bym
>= aym
) // 16.
1229 aResult
.InsertInPlace (new RgnRect (ax
, ay
, aw
, iy
- ay
));
1230 aResult
.InsertInPlace (new RgnRect (ax
, iy
, ix
- ax
, ih
));
1236 // Just copy remaining rectangles in region which are below aRect and can't intersect it.
1237 // If rectangles are in temporary region then they could be moved.
1238 if (pSrcRegion
== &TmpRegion
)
1239 TmpRegion
.MoveInto (aResult
, pSrcRect
);
1242 while (pSrcRect
!= &pSrcRegion
->mRectListHead
)
1244 aResult
.InsertInPlace (new RgnRect (*pSrcRect
));
1245 pSrcRect
= pSrcRect
->next
;
1251 PRBool
nsRegion::IsEqual (const nsRegion
& aRegion
) const
1253 if (mRectCount
== 0)
1254 return (aRegion
.mRectCount
== 0) ? PR_TRUE
: PR_FALSE
;
1256 if (aRegion
.mRectCount
== 0)
1257 return (mRectCount
== 0) ? PR_TRUE
: PR_FALSE
;
1259 if (mRectCount
== 1 && aRegion
.mRectCount
== 1) // Both regions are simple rectangles
1260 return (*mRectListHead
.next
== *aRegion
.mRectListHead
.next
);
1261 else // At least one is complex region.
1263 if (mBoundRect
!= aRegion
.mBoundRect
) // If regions are equal then bounding rectangles should match
1268 TmpRegion
.Xor (*this, aRegion
); // Get difference between two regions
1270 return (TmpRegion
.mRectCount
== 0);
1276 void nsRegion::MoveBy (nsPoint aPt
)
1280 RgnRect
* pRect
= mRectListHead
.next
;
1282 while (pRect
!= &mRectListHead
)
1284 pRect
->MoveBy (aPt
.x
, aPt
.y
);
1285 pRect
= pRect
->next
;
1288 mBoundRect
.MoveBy (aPt
.x
, aPt
.y
);
1292 nsRegion
nsRegion::ConvertAppUnitsRoundOut (PRInt32 aFromAPP
, PRInt32 aToAPP
) const
1294 if (aFromAPP
== aToAPP
) {
1297 // Do it in a simplistic and slow way to avoid any weird behaviour with
1298 // rounding causing rects to overlap. Should be fast enough for what we need.
1300 nsRegionRectIterator
iter(*this);
1302 const nsRect
* r
= iter
.Next();
1305 nsRect rect
= r
->ConvertAppUnitsRoundOut(aFromAPP
, aToAPP
);
1306 region
.Or(region
, rect
);
1311 nsRegion
nsRegion::ConvertAppUnitsRoundIn (PRInt32 aFromAPP
, PRInt32 aToAPP
) const
1313 if (aFromAPP
== aToAPP
) {
1316 // Do it in a simplistic and slow way to avoid any weird behaviour with
1317 // rounding causing rects to overlap. Should be fast enough for what we need.
1319 nsRegionRectIterator
iter(*this);
1321 const nsRect
* r
= iter
.Next();
1324 nsRect rect
= r
->ConvertAppUnitsRoundIn(aFromAPP
, aToAPP
);
1325 region
.Or(region
, rect
);
1330 nsIntRegion
nsRegion::ToOutsidePixels (nscoord aAppUnitsPerPixel
) const
1333 nsRegionRectIterator
rgnIter(*this);
1334 const nsRect
* currentRect
;
1335 while ((currentRect
= rgnIter
.Next())) {
1336 nsIntRect deviceRect
= currentRect
->ToOutsidePixels(aAppUnitsPerPixel
);
1337 result
.Or(result
, deviceRect
);
1342 // This algorithm works in three phases:
1343 // 1) Convert the region into a grid by adding vertical/horizontal lines for
1344 // each edge of each rectangle in the region.
1345 // 2) For each rectangle in the region, for each cell it contains, set that
1346 // cells's value to the area of the subrectangle it corresponds to. Cells
1347 // that are not contained by any rectangle have the value 0.
1348 // 3) Calculate the submatrix with the largest sum such that none of its cells
1349 // contain any 0s (empty regions). The rectangle represented by the
1350 // submatrix is the largest rectangle in the region.
1352 // Let k be the number of rectangles in the region.
1353 // Let m be the height of the grid generated in step 1.
1354 // Let n be the width of the grid generated in step 1.
1356 // Step 1 is O(k) in time and O(m+n) in space for the sparse grid.
1357 // Step 2 is O(mn) in time and O(mn) in additional space for the full grid.
1358 // Step 3 is O(m^2 n) in time and O(mn) in additional space
1360 // The implementation of steps 1 and 2 are rather straightforward. However our
1361 // implementation of step 3 uses dynamic programming to achieve its efficiency.
1363 // Psuedo code for step 3 is as follows where G is the grid from step 1 and A
1364 // is the array from step 2:
1365 // Phase3 = function (G, A, m, n) {
1366 // let (t,b,l,r,_) = MaxSum2D(A,m,n)
1367 // return rect(G[t],G[l],G[r],G[b]);
1369 // MaxSum2D = function (A, m, n) {
1370 // S = array(m+1,n+1)
1371 // S[0][i] = 0 for i in [0,n]
1372 // S[j][0] = 0 for j in [0,m]
1373 // S[j][i] = (if A[j-1][i-1] = 0 then some large negative number else A[j-1][i-1])
1374 // + S[j-1][n] + S[j][i-1] - S[j-1][i-1]
1376 // // top, bottom, left, right, area
1377 // var maxRect = (-1, -1, -1, -1, 0);
1379 // for all (m',m'') in [0, m]^2 {
1380 // let B = { S[m'][i] - S[m''][i] | 0 <= i <= n }
1381 // let ((l,r),area) = MaxSum1D(B,n+1)
1382 // if (area > maxRect.area) {
1383 // maxRect := (m', m'', l, r, area)
1390 // Originally taken from Improved algorithms for the k-maximum subarray problem
1391 // for small k - SE Bae, T Takaoka but modified to show the explicit tracking
1392 // of indices and we already have the prefix sums from our one call site so
1393 // there's no need to construct them.
1394 // MaxSum1D = function (A,n) {
1397 // var maxIndices = (0,0);
1399 // for i in range(n) {
1400 // let cand = A[i] - min;
1401 // if (cand > max) {
1403 // maxIndices := (minIdx, i)
1405 // if (min > A[i]) {
1410 // return (minIdx, maxIdx, max);
1414 // This class represents a partitioning of an axis delineated by coordinates.
1415 // It internally maintains a sorted array of coordinates.
1416 class AxisPartition
{
1418 // Adds a new partition at the given coordinate to this partitioning. If
1419 // the coordinate is already present in the partitioning, this does nothing.
1420 void InsertCoord(nscoord c
) {
1422 if (!mStops
.GreatestIndexLtEq(c
, i
)) {
1423 mStops
.InsertElementAt(i
, c
);
1427 // Returns the array index of the given partition point. The partition
1428 // point must already be present in the partitioning.
1429 PRInt32
IndexOf(nscoord p
) const {
1430 return mStops
.BinaryIndexOf(p
);
1433 // Returns the partition at the given index which must be non-zero and
1434 // less than the number of partitions in this partitioning.
1435 nscoord
StopAt(PRInt32 index
) const {
1436 return mStops
[index
];
1439 // Returns the size of the gap between the partition at the given index and
1440 // the next partition in this partitioning. If the index is the last index
1441 // in the partitioning, the result is undefined.
1442 nscoord
StopSize(PRInt32 index
) const {
1443 return mStops
[index
+1] - mStops
[index
];
1446 // Returns the number of partitions in this partitioning.
1447 PRInt32
GetNumStops() const { return mStops
.Length(); }
1450 nsTArray
<nscoord
> mStops
;
1453 const PRInt64 kVeryLargeNegativeNumber
= 0xffff000000000000ll
;
1455 // Returns the sum and indices of the subarray with the maximum sum of the
1456 // given array (A,n), assuming the array is already in prefix sum form.
1457 PRInt64
MaxSum1D(const nsTArray
<PRInt64
> &A
, PRInt32 n
,
1458 PRInt32
*minIdx
, PRInt32
*maxIdx
) {
1459 // The min/max indicies of the largest subarray found so far
1462 PRInt32 currentMinIdx
= 0;
1467 // Because we're given the array in prefix sum form, we know the first
1469 for(PRInt32 i
= 1; i
< n
; i
++) {
1470 PRInt64 cand
= A
[i
] - min
;
1473 *minIdx
= currentMinIdx
;
1486 nsRect
nsRegion::GetLargestRectangle () const {
1492 AxisPartition xaxis
, yaxis
;
1494 // Step 1: Calculate the grid lines
1495 nsRegionRectIterator
iter(*this);
1496 const nsRect
*currentRect
;
1497 while ((currentRect
= iter
.Next())) {
1498 xaxis
.InsertCoord(currentRect
->x
);
1499 xaxis
.InsertCoord(currentRect
->XMost());
1500 yaxis
.InsertCoord(currentRect
->y
);
1501 yaxis
.InsertCoord(currentRect
->YMost());
1504 // Step 2: Fill out the grid with the areas
1505 // Note: due to the ordering of rectangles in the region, it is not always
1506 // possible to combine steps 2 and 3 so we don't try to be clever.
1507 PRInt32 matrixHeight
= yaxis
.GetNumStops() - 1;
1508 PRInt32 matrixWidth
= xaxis
.GetNumStops() - 1;
1509 PRInt32 matrixSize
= matrixHeight
* matrixWidth
;
1510 nsTArray
<PRInt64
> areas(matrixSize
);
1511 areas
.SetLength(matrixSize
);
1512 memset(areas
.Elements(), 0, matrixSize
* sizeof(PRInt64
));
1515 while ((currentRect
= iter
.Next())) {
1516 PRInt32 xstart
= xaxis
.IndexOf(currentRect
->x
);
1517 PRInt32 xend
= xaxis
.IndexOf(currentRect
->XMost());
1518 PRInt32 y
= yaxis
.IndexOf(currentRect
->y
);
1519 PRInt32 yend
= yaxis
.IndexOf(currentRect
->YMost());
1521 for (; y
< yend
; y
++) {
1522 nscoord height
= yaxis
.StopSize(y
);
1523 for (PRInt32 x
= xstart
; x
< xend
; x
++) {
1524 nscoord width
= xaxis
.StopSize(x
);
1525 areas
[y
*matrixWidth
+x
] = width
*PRInt64(height
);
1530 // Step 3: Find the maximum submatrix sum that does not contain a rectangle
1532 // First get the prefix sum array
1533 PRInt32 m
= matrixHeight
+ 1;
1534 PRInt32 n
= matrixWidth
+ 1;
1535 nsTArray
<PRInt64
> pareas(m
*n
);
1536 pareas
.SetLength(m
*n
);
1537 // Zero out the first row
1538 for (PRInt32 x
= 0; x
< n
; x
++)
1540 for (PRInt32 y
= 1; y
< m
; y
++) {
1541 // Zero out the left column
1543 for (PRInt32 x
= 1; x
< n
; x
++) {
1544 PRInt64 area
= areas
[(y
-1)*matrixWidth
+x
-1];
1546 area
= kVeryLargeNegativeNumber
;
1547 area
+= pareas
[ y
*n
+x
-1]
1548 + pareas
[(y
-1)*n
+x
]
1549 - pareas
[(y
-1)*n
+x
-1];
1550 pareas
[y
*n
+x
] = area
;
1554 // No longer need the grid
1557 PRInt64 bestArea
= 0;
1559 PRInt32 left
, top
, right
, bottom
;
1560 } bestRectIndices
= { 0, 0, 0, 0 };
1561 for (PRInt32 m1
= 0; m1
< m
; m1
++) {
1562 for (PRInt32 m2
= m1
+1; m2
< m
; m2
++) {
1563 nsTArray
<PRInt64
> B
;
1565 for (PRInt32 i
= 0; i
< n
; i
++)
1566 B
[i
] = pareas
[m2
*n
+i
] - pareas
[m1
*n
+i
];
1567 PRInt32 minIdx
, maxIdx
;
1568 PRInt64 area
= MaxSum1D(B
, n
, &minIdx
, &maxIdx
);
1569 if (area
> bestArea
) {
1570 bestRectIndices
.left
= minIdx
;
1571 bestRectIndices
.top
= m1
;
1572 bestRectIndices
.right
= maxIdx
;
1573 bestRectIndices
.bottom
= m2
;
1579 bestRect
.MoveTo(xaxis
.StopAt(bestRectIndices
.left
),
1580 yaxis
.StopAt(bestRectIndices
.top
));
1581 bestRect
.SizeTo(xaxis
.StopAt(bestRectIndices
.right
) - bestRect
.x
,
1582 yaxis
.StopAt(bestRectIndices
.bottom
) - bestRect
.y
);
1588 void nsRegion::SimplifyOutward (PRUint32 aMaxRects
)
1590 NS_ASSERTION(aMaxRects
>= 1, "Invalid max rect count");
1592 if (mRectCount
<= aMaxRects
)
1595 *this = GetBounds();
1598 void nsRegion::SimplifyInward (PRUint32 aMaxRects
)
1600 NS_ASSERTION(aMaxRects
>= 1, "Invalid max rect count");
1602 if (mRectCount
<= aMaxRects
)
1608 void nsRegion::SimpleSubtract (const nsRect
& aRect
)
1610 if (aRect
.IsEmpty())
1613 // protect against aRect being one of our own rectangles
1614 nsRect param
= aRect
;
1615 RgnRect
* r
= mRectListHead
.next
;
1616 while (r
!= &mRectListHead
)
1618 RgnRect
* next
= r
->next
;
1619 if (param
.Contains(*r
)) {
1628 void nsRegion::SimpleSubtract (const nsRegion
& aRegion
)
1630 if (aRegion
.IsEmpty())
1633 if (&aRegion
== this) {
1638 const RgnRect
* r
= aRegion
.mRectListHead
.next
;
1639 while (r
!= &aRegion
.mRectListHead
)
1648 nsRegion
nsIntRegion::ToAppUnits (nscoord aAppUnitsPerPixel
) const
1651 nsIntRegionRectIterator
rgnIter(*this);
1652 const nsIntRect
* currentRect
;
1653 while ((currentRect
= rgnIter
.Next())) {
1654 nsRect appRect
= currentRect
->ToAppUnits(aAppUnitsPerPixel
);
1655 result
.Or(result
, appRect
);