1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
|
<!-- This Source Code Form is subject to the terms of the Mozilla Public
- License, v. 2.0. If a copy of the MPL was not distributed with this
- file, You can obtain one at http://mozilla.org/MPL/2.0/. -->
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
<title>Detailed Design Template</title>
</head>
<body>
<h1><font color="#cc0000">Gecko Layout Detailed Design Document</font></h1>
<h1>Space Manager Detailed Design</h1>
<h2>Overview</h2>
<p>
The Space Manager and related classes and structures are an important of
the Gecko Layout system, specifically Block Layout. See the High Level
Design document for an overview of the Space Manager, and as an introduction
to the classes, structures and algorithms container in this, the Detailed
Design Document.
</p>
<hr width="100%" size="2">
<h2>nsSpaceManager</h2>
<p>
The Space Manager is the central class is a group of classes that manage
the occupied and available space that exists in horizontal bands across
a canvas. The primary goal of the Space Manager is to provide information
about those bands of space to support the CSS notion of floated elements.
</p>
<p>
There are three important parts to the Space Manager API: the parts that
deal with the coordinate space of the Space Manager, the parts that deal with
the regions managed by the Space Manager, and the parts that manage float
impact intervals.
</p>
<p>
The class nsSpaceManager is declared in the file <a href="http://lxr.mozilla.org/seamonkey/source/layout/base/src/nsSpaceManager.h">
nsSpaceManger.h</a>
. The class is only used in the layout module and cannot be exported
outside of that module (nor does it need to be). It is not a general
purpose class, and is not intended to be subclasses<font color="#cc0000">
.</font>
</p>
<p>
Here is the class declaration, taken from the source file as of 01.08.02
</p>
<pre>/**
* Class for dealing with bands of available space. The space manager
* defines a coordinate space with an origin at (0, 0) that grows down
* and to the right.
*/
class nsSpaceManager {
public:
nsSpaceManager(nsIPresShell* aPresShell, nsIFrame* aFrame);
~nsSpaceManager();
void* operator new(size_t aSize);
void operator delete(void* aPtr, size_t aSize);
static void Shutdown();
/*
* Get the frame that's associated with the space manager. This frame
* created the space manager, and the world coordinate space is
* relative to this frame.
*
* You can use QueryInterface() on this frame to get any additional
* interfaces.
*/
nsIFrame* GetFrame() const { return mFrame; }
/**
* Translate the current origin by the specified (dx, dy). This
* creates a new local coordinate space relative to the current
* coordinate space.
*/
void Translate(nscoord aDx, nscoord aDy) { mX += aDx; mY += aDy; }
/**
* Returns the current translation from local coordinate space to
* world coordinate space. This represents the accumulated calls to
* Translate().
*/
void GetTranslation(nscoord& aX, nscoord& aY) const { aX = mX; aY = mY; }
/**
* Returns the y-most of the bottommost band or 0 if there are no bands.
*
* @return PR_TRUE if there are bands and PR_FALSE if there are no bands
*/
PRBool YMost(nscoord& aYMost) const;
/**
* Returns a band starting at the specified y-offset. The band data
* indicates which parts of the band are available, and which parts
* are unavailable
*
* The band data that is returned is in the coordinate space of the
* local coordinate system.
*
* The local coordinate space origin, the y-offset, and the max size
* describe a rectangle that's used to clip the underlying band of
* available space, i.e.
* {0, aYOffset, aMaxSize.width, aMaxSize.height} in the local
* coordinate space
*
* @param aYOffset the y-offset of where the band begins. The coordinate is
* relative to the upper-left corner of the local coordinate space
* @param aMaxSize the size to use to constrain the band data
* @param aBandData [in,out] used to return the list of trapezoids that
* describe the available space and the unavailable space
* @return NS_OK if successful and NS_ERROR_FAILURE if the band data is not
* not large enough. The 'count' member of the band data struct
* indicates how large the array of trapezoids needs to be
*/
nsresult GetBandData(nscoord aYOffset,
const nsSize& aMaxSize,
nsBandData& aBandData) const;
/**
* Add a rectangular region of unavailable space. The space is
* relative to the local coordinate system.
*
* The region is tagged with a frame
*
* @param aFrame the frame used to identify the region. Must not be NULL
* @param aUnavailableSpace the bounding rect of the unavailable space
* @return NS_OK if successful
* NS_ERROR_FAILURE if there is already a region tagged with aFrame
*/
nsresult AddRectRegion(nsIFrame* aFrame,
const nsRect& aUnavailableSpace);
/**
* Resize the rectangular region associated with aFrame by the specified
* deltas. The height change always applies to the bottom edge or the existing
* rect. You specify whether the width change applies to the left or right edge
*
* Returns NS_OK if successful, NS_ERROR_INVALID_ARG if there is no region
* tagged with aFrame
*/
enum AffectedEdge {LeftEdge, RightEdge};
nsresult ResizeRectRegion(nsIFrame* aFrame,
nscoord aDeltaWidth,
nscoord aDeltaHeight,
AffectedEdge aEdge = RightEdge);
/**
* Offset the region associated with aFrame by the specified amount.
*
* Returns NS_OK if successful, NS_ERROR_INVALID_ARG if there is no region
* tagged with aFrame
*/
nsresult OffsetRegion(nsIFrame* aFrame, nscoord dx, nscoord dy);
/**
* Remove the region associated with aFrane.
*
* Returns NS_OK if successful and NS_ERROR_INVALID_ARG if there is no region
* tagged with aFrame
*/
nsresult RemoveRegion(nsIFrame* aFrame);
/**
* Clears the list of regions representing the unavailable space.
*/
void ClearRegions();
/**
* Methods for dealing with the propagation of float damage during
* reflow.
*/
PRBool HasFloatDamage()
{
return !mFloatDamage.IsEmpty();
}
void IncludeInDamage(nscoord aIntervalBegin, nscoord aIntervalEnd)
{
mFloatDamage.IncludeInterval(aIntervalBegin + mY, aIntervalEnd + mY);
}
PRBool IntersectsDamage(nscoord aIntervalBegin, nscoord aIntervalEnd)
{
return mFloatDamage.Intersects(aIntervalBegin + mY, aIntervalEnd + mY);
}
#ifdef DEBUG
/**
* Dump the state of the spacemanager out to a file
*/
nsresult List(FILE* out);
void SizeOf(nsISizeOfHandler* aHandler, uint32_t* aResult) const;
#endif
private:
// Structure that maintains information about the region associated
// with a particular frame
struct FrameInfo {
nsIFrame* const mFrame;
nsRect mRect; // rectangular region
FrameInfo* mNext;
FrameInfo(nsIFrame* aFrame, const nsRect& aRect);
#ifdef NS_BUILD_REFCNT_LOGGING
~FrameInfo();
#endif
};
// Doubly linked list of band rects
struct BandRect : PRCListStr {
nscoord mLeft, mTop;
nscoord mRight, mBottom;
int32_t mNumFrames; // number of frames occupying this rect
union {
nsIFrame* mFrame; // single frame occupying the space
nsVoidArray* mFrames; // list of frames occupying the space
};
BandRect(nscoord aLeft, nscoord aTop,
nscoord aRight, nscoord aBottom,
nsIFrame*);
BandRect(nscoord aLeft, nscoord aTop,
nscoord aRight, nscoord aBottom,
nsVoidArray*);
~BandRect();
// List operations
BandRect* Next() const {return (BandRect*)PR_NEXT_LINK(this);}
BandRect* Prev() const {return (BandRect*)PR_PREV_LINK(this);}
void InsertBefore(BandRect* aBandRect) {PR_INSERT_BEFORE(aBandRect, this);}
void InsertAfter(BandRect* aBandRect) {PR_INSERT_AFTER(aBandRect, this);}
void Remove() {PR_REMOVE_LINK(this);}
// Split the band rect into two vertically, with this band rect becoming
// the top part, and a new band rect being allocated and returned for the
// bottom part
//
// Does not insert the new band rect into the linked list
BandRect* SplitVertically(nscoord aBottom);
// Split the band rect into two horizontally, with this band rect becoming
// the left part, and a new band rect being allocated and returned for the
// right part
//
// Does not insert the new band rect into the linked list
BandRect* SplitHorizontally(nscoord aRight);
// Accessor functions
PRBool IsOccupiedBy(const nsIFrame*) const;
void AddFrame(const nsIFrame*);
void RemoveFrame(const nsIFrame*);
PRBool HasSameFrameList(const BandRect* aBandRect) const;
int32_t Length() const;
};
// Circular linked list of band rects
struct BandList : BandRect {
BandList();
// Accessors
PRBool IsEmpty() const {return PR_CLIST_IS_EMPTY((PRCListStr*)this);}
BandRect* Head() const {return (BandRect*)PR_LIST_HEAD(this);}
BandRect* Tail() const {return (BandRect*)PR_LIST_TAIL(this);}
// Operations
void Append(BandRect* aBandRect) {PR_APPEND_LINK(aBandRect, this);}
// Remove and delete all the band rects in the list
void Clear();
};
FrameInfo* GetFrameInfoFor(nsIFrame* aFrame);
FrameInfo* CreateFrameInfo(nsIFrame* aFrame, const nsRect& aRect);
void DestroyFrameInfo(FrameInfo*);
void ClearFrameInfo();
void ClearBandRects();
BandRect* GetNextBand(const BandRect* aBandRect) const;
void DivideBand(BandRect* aBand, nscoord aBottom);
PRBool CanJoinBands(BandRect* aBand, BandRect* aPrevBand);
PRBool JoinBands(BandRect* aBand, BandRect* aPrevBand);
void AddRectToBand(BandRect* aBand, BandRect* aBandRect);
void InsertBandRect(BandRect* aBandRect);
nsresult GetBandAvailableSpace(const BandRect* aBand,
nscoord aY,
const nsSize& aMaxSize,
nsBandData& aAvailableSpace) const;
nsIFrame* const mFrame; // frame associated with the space manager
nscoord mX, mY; // translation from local to global coordinate space
BandList mBandList; // header/sentinel for circular linked list of band rects
FrameInfo* mFrameInfoMap;
nsIntervalSet mFloatDamage;
static int32_t sCachedSpaceManagerCount;
static void* sCachedSpaceManagers[NS_SPACE_MANAGER_CACHE_SIZE];
nsSpaceManager(const nsSpaceManager&); // no implementation
void operator=(const nsSpaceManager&); // no implementation
};
</pre>
<h3>Public API</h3>
<h4>Life Cycle:</h4>
<p>
The Constructor requires a Presentation Shell, used for arena allocations
mostly, and a frame that this Space Manager is rooted on. The coordinate
space of this Space Manager is relative to the frame passed in to the constructor.
</p>
<pre> nsSpaceManager(nsIPresShell* aPresShell, nsIFrame* aFrame);
~nsSpaceManager();
</pre>
<p>
Operators 'new' and 'delete' are overridden to support a recycler. Space
Manager instances come and go pretty frequently, and this recycler prevents
excessive heap allocations and the performance penalties associated with
it. The #define NS_SPACE_MANAGER_CACHE_SIZE is used to control the number
of Space Manager instances that can be present in the recycler, currently
4. If more than NS_SPACE_MANAGER_CACHE_SIZE are allocated at a time,
then standard allocation is used.
</p>
<pre>
void* operator new(size_t aSize);
void operator delete(void* aPtr, size_t aSize);
</pre>
<p>
A Static method is used to shutdown the Space Manager recycling. This
method deletes all of the Space Mangers inthe recycler,and prevents further
recycling. It is meant to be called only when the layout module is being
terminated.
</p>
<pre> static void Shutdown();
</pre>
<h4>Origin / Coordinate Space Translation</h4>
<pre> /**
* Translate the current origin by the specified (dx, dy). This
* creates a new local coordinate space relative to the current
* coordinate space.
*/
void Translate(nscoord aDx, nscoord aDy) { mX += aDx; mY += aDy; }
/**
* Returns the current translation from local coordinate space to
* world coordinate space. This represents the accumulated calls to
* Translate().
*/
void GetTranslation(nscoord& aX, nscoord& aY) const { aX = mX; aY = mY; }
/**
* Returns the y-most of the bottommost band or 0 if there are no bands.
*
* @return PR_TRUE if there are bands and PR_FALSE if there are no bands
*/
PRBool YMost(nscoord& aYMost) const;
</pre>
<h4>Region Management</h4>
<pre> /**
* Returns a band starting at the specified y-offset. The band data
* indicates which parts of the band are available, and which parts
* are unavailable
*
* The band data that is returned is in the coordinate space of the
* local coordinate system.
*
* The local coordinate space origin, the y-offset, and the max size
* describe a rectangle that's used to clip the underlying band of
* available space, i.e.
* {0, aYOffset, aMaxSize.width, aMaxSize.height} in the local
* coordinate space
*
* @param aYOffset the y-offset of where the band begins. The coordinate is
* relative to the upper-left corner of the local coordinate space
* @param aMaxSize the size to use to constrain the band data
* @param aBandData [in,out] used to return the list of trapezoids that
* describe the available space and the unavailable space
* @return NS_OK if successful and NS_ERROR_FAILURE if the band data is not
* not large enough. The 'count' member of the band data struct
* indicates how large the array of trapezoids needs to be
*/
nsresult GetBandData(nscoord aYOffset,
const nsSize& aMaxSize,
nsBandData& aBandData) const;
/**
* Add a rectangular region of unavailable space. The space is
* relative to the local coordinate system.
*
* The region is tagged with a frame
*
* @param aFrame the frame used to identify the region. Must not be NULL
* @param aUnavailableSpace the bounding rect of the unavailable space
* @return NS_OK if successful
* NS_ERROR_FAILURE if there is already a region tagged with aFrame
*/
nsresult AddRectRegion(nsIFrame* aFrame,
const nsRect& aUnavailableSpace);
/**
* Resize the rectangular region associated with aFrame by the specified
* deltas. The height change always applies to the bottom edge or the existing
* rect. You specify whether the width change applies to the left or right edge
*
* Returns NS_OK if successful, NS_ERROR_INVALID_ARG if there is no region
* tagged with aFrame
*/
enum AffectedEdge {LeftEdge, RightEdge};
nsresult ResizeRectRegion(nsIFrame* aFrame,
nscoord aDeltaWidth,
nscoord aDeltaHeight,
AffectedEdge aEdge = RightEdge);
/**
* Offset the region associated with aFrame by the specified amount.
*
* Returns NS_OK if successful, NS_ERROR_INVALID_ARG if there is no region
* tagged with aFrame
*/
nsresult OffsetRegion(nsIFrame* aFrame, nscoord dx, nscoord dy);
/**
* Remove the region associated with aFrane.
*
* Returns NS_OK if successful and NS_ERROR_INVALID_ARG if there is no region
* tagged with aFrame
*/
nsresult RemoveRegion(nsIFrame* aFrame);
/**
* Clears the list of regions representing the unavailable space.
*/
void ClearRegions();
</pre>
<h4>Float Impact</h4>
<pre> /**
* Methods for dealing with the propagation of float damage during
* reflow.
*/
PRBool HasFloatDamage()
{
return !mFloatDamage.IsEmpty();
}
void IncludeInDamage(nscoord aIntervalBegin, nscoord aIntervalEnd)
{
mFloatDamage.IncludeInterval(aIntervalBegin + mY, aIntervalEnd + mY);
}
PRBool IntersectsDamage(nscoord aIntervalBegin, nscoord aIntervalEnd)
{
return mFloatDamage.Intersects(aIntervalBegin + mY, aIntervalEnd + mY);
}
</pre>
<h4>Debug Only Methods</h4>
<pre> /**
* Dump the state of the spacemanager out to a file
*/
nsresult List(FILE* out);
void SizeOf(nsISizeOfHandler* aHandler, uint32_t* aResult) const;
</pre>
<h4>Unused / Obsolete Methods</h4>
<pre> /*
* Get the frame that's associated with the space manager. This frame
* created the space manager, and the world coordinate space is
* relative to this frame.
*
* You can use QueryInterface() on this frame to get any additional
* interfaces.
*/
nsIFrame* GetFrame() const { return mFrame; }
</pre>
<h3>Implementation Notes</h3>
<h4></h4>
<h4>Algorithm 1: GetBandData</h4>
<p>
GetBandData is used to provide information to clients about what space if
available and unavailable in a band of space. The client provides a
vertical offset, the yOffset, that corresponds to the band that is of interest.
This will be the y offset of the frame that is being reflowed. The
caller also provides a collection of BandData objects (an array) and the
number of items that the collection can handle. If the collection is
too small, then an error is returned and the count is updated to indicate
the size required.
</p>
<p>
The algorithm to provide the band data is as follows:
</p>
<ul>
<li>Get a vertical offset in world coordinates (instead of frame-relative
coordinates) by adding the y-origin of the SpaceManager to the y offset passed
in</li>
<li>If the (adjusted) y value passed in is greater than the greatest band
being managed, then all space is available so a single trapezoid is returned,
marked as available and sized to the maximum size value (passed in).</li>
<li>If the (adjusted) y offset intersects a band, then gather the band
data:</li>
<ul>
<li>walk the internal bandData list from head to tail</li>
<li>for each band data entry, see if the top of the band is greater than
the (adjusted) y offset requested</li>
<li>if it is, then band is below the offset requested, so the area between
the band and the y offset is available - create a trapezoid with that region
and return it.</li>
<li>if the (adjusted) y offset is between the band top and bottom, then
get the available space for the band by calling GetBandAvailableSpace</li>
<li>otherwise, move to the next band</li>
</ul>
</ul>
<h5>GetBandAvailableSpace:</h5>
This method is called from GetBandData only. It walks all of the bands in
the space manager and determines which bands intersect with the band passed
in, and if within those bands there are regions that are available or occupied.
<ul>
<li>First, walk all of the bands until a band that is to the right of the
desired offset is located</li>
<li>Starting at that band, walk the remaining bands:</li>
<ul>
<li>if the current band is to the right of the requested band, then there
is available space. </li>
<ul>
<li>if there is more room in the bandData collection, then add a trapezoid
to the bandData collection such that it is marked as available and has a
rect that represents the space between the reference band tna dht band being
examined</li>
<li>if there is no more room in the BandData collection, estimate the
number of entries requires as the current count + twice the number of bands
below the reference band, plus two. Return an error code so the caller
can reallocate the collection and try again.</li>
</ul>
<li>check the size of the collection again, if there is no room left
then estimate the number of items requires as the current count + twice the
number of bands below the band in question plus one. </li>
<li>create a new trapezoid in the band collection that has a region corresponding
to the reference band rect, marked as occupied by either a single or multiple
frames.</li>
<li>move to the next band</li>
</ul>
<li>after walking all of the band data, se if we have reached the right
edge of the band. </li>
<ul>
<li>If not, then check for space in the band collection</li>
<ul>
<li>if there is no room left, then set the count to the current count
plus 1 and return an error.</li>
<li>otherwise, create another entry in the band collection, marked
as available, and with a rect corresponding to the area remainin in the band
(eg. from the right edge of the last band rect to the right edge of the band).</li>
</ul>
</ul>
</ul>
<h4>Algorithm 2: AddRectRegion</h4>
Clients call into this method to notify the Space Manager that a new frame
is occupying some space.
<ul>
<li>First, try to get frame info for the frame. If it is found, return
an error since the frame is already associated with a region in the Space
Manager.</li>
<li>Next, create a rect from the occupied space passed in by the caller,
transforming it first to world-coordinates by adding the Space Manager's
offset to the occupied space rect passed in.</li>
<li>Create a new Frame Info instance for the frame and rect, returning
an error if allocation fails.</li>
<li>Check if the occupied space rect (adjusted) is empty, if so, return
an error (<font color="#cc0000">NOTE: this could be done earlier, or
prevented by the caller</font>)</li>
<li>Allocate a new BandRect instance with the rect and frame as constructor
arguments, and insert it into the collection via InsertBandRect</li>
</ul>
<h5>InsertBandRect:</h5>
Internal method to insert a band rect into the BandList in the correct location.
There are several cases it has to handle, as specified in the source file
comments:
<pre>// When comparing a rect to a band there are seven cases to consider.
// 'R' is the rect and 'B' is the band.
//
// Case 1 Case 2 Case 3 Case 4
// ------ ------ ------ ------
// +-----+ +-----+ +-----+ +-----+
// | R | | R | +-----+ +-----+ | | | |
// +-----+ +-----+ | | | R | | B | | B |
// +-----+ | B | +-----+ | | +-----+ | |
// | | | | +-----+ | R | +-----+
// | B | +-----+ +-----+
// | |
// +-----+
//
//
//
// Case 5 Case 6 Case 7
// ------ ------ ------
// +-----+ +-----+ +-----+ +-----+
// | | | R | | B | | | +-----+
// | B | +-----+ +-----+ | R | | B |
// | | | | +-----+
// +-----+ +-----+
// +-----+
// | R |
// +-----+
//
</pre>
<ul>
<li>First, check for the easiest case, where there are no existing band
rects, or the band rect passed in is below the bottommost rect. In this case,
just append the band rect and return.</li>
<li>Starting at the head of the list of bandRects, check for intersection
with the rect passed in:</li>
<ul>
<li>case #1: the rect is totally above the current band rect, so insert
a new band rect before the current bandRect</li>
<li>cases #2 and #7: the rect is partially above the band rect, so it
is divided into two bandRects, one entirely above the band, and one containing
the remainder of the rect. Insert the part that is totally above the
bandRect before the current bandRect, as in case #1 above, and adjust the
other band rect to exclude the part already added.</li>
<li>case #5: the rect is totally below the current bandRect, so just
skip to the next band</li>
<li>case #3 and #4: rect is at least partially intersection with the
bandRect, so divide the current band into two parts, where the top part is
above the current rect. Move to the new band just created, which is
the next band.</li>
<li>case #6: the rect shares the bottom and height with the bandRect,
so just add the rect to the band.</li>
<li>case #4 and #7: create a new rect for the part that overlaps the
bandRect, and add it to the current bandRect (similar to case #6) and then
move on to the next band, removing that part from the rect passed in. If
no more bands, append the rect passed in to the end of the bandRect list.</li>
</ul>
</ul>
<i>This algorithm is pretty confusing - basically what needs to happen is
that rects and bands need to be divided up so that complicated cases like
#2, #4, and #7, are reduced to simpler cases where the rects is totally above,
below, or between a band rect. From the current implementation, it
might be worth verifying that the final result of the inserts is a correctly
ordered liest of bandRects (debug mode only).</i>
<h4>Algorithm 3: RemoveRegion</h4>
When a float is removed, the Space Manager is notified by a call to RemoveRegion,
passing in the frame that is being removed.
<ul>
<li>Get the FrameInfo for the frame passed in. If not found, an error is
returned.</li>
<li>If the rect for the frame is not empty, then visit each band in the
bandList:</li>
<ul>
<li>for each rect in the band:
</li>
</ul>
<ul>
<ul>
<li>if the bandRect is occupied by the frame, either remove the frame
from the bandRect (if there are other frames sharing it) and remember that
it was shared</li>
<li>otherwise simply remove the bandRect (no other frames share it).</li>
<li>if the bandRect was shared, then try to coalesce adjacent bandRects</li>
<ul>
<li>if the previous bandRect is directly next to the current bandRect,
and they have the same frame list, then make the current bandRect cover the
previous bandRect's full region (adjust the left edge to be that of the previous
bandRect) and remove the previous bandRect.</li>
</ul>
</ul>
</ul>
<ul>
<li>if the current band or prior band had a rect occupied byu the frame,
then try to join the two bands via JoinBands</li>
</ul>
<li>Finally, destroy the frameInfo for the frame.
</li>
</ul>
<br>
<hr width="100%" size="2">
<h2>Cross-Component Algorithms</h2>
<br>
<hr width="100%" size="2">
<h2>Tech Notes</h2>
<ul>
<li>
</li>
</ul>
</body>
</html>
|
