1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 // vim:cindent:ts=8:et:sw=4:
3 /* This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
7 /* a set of ranges on a number-line */
9 #include "nsIntervalSet.h"
13 nsIntervalSet::nsIntervalSet(IntervalSetAlloc aAlloc
, IntervalSetFree aFree
,
14 void* aAllocatorClosure
)
18 mAllocatorClosure(aAllocatorClosure
)
20 NS_ASSERTION(mAlloc
&& mFree
, "null callback params");
23 nsIntervalSet::~nsIntervalSet()
25 Interval
*current
= mList
;
27 Interval
*trash
= current
;
28 current
= current
->mNext
;
33 void nsIntervalSet::FreeInterval(nsIntervalSet::Interval
*aInterval
)
35 NS_ASSERTION(aInterval
, "null interval");
37 aInterval
->Interval::~Interval();
38 (*mFree
)(sizeof(Interval
), aInterval
, mAllocatorClosure
);
41 void nsIntervalSet::IncludeInterval(coord_type aBegin
, coord_type aEnd
)
43 Interval
*newInterval
= static_cast<Interval
*>
44 ((*mAlloc
)(sizeof(Interval
), mAllocatorClosure
));
46 NS_NOTREACHED("allocation failure");
49 new(newInterval
) Interval(aBegin
, aEnd
);
51 Interval
**current
= &mList
;
52 while (*current
&& (*current
)->mEnd
< aBegin
)
53 current
= &(*current
)->mNext
;
55 newInterval
->mNext
= *current
;
56 *current
= newInterval
;
58 Interval
*subsumed
= newInterval
->mNext
;
59 while (subsumed
&& subsumed
->mBegin
<= aEnd
) {
60 newInterval
->mBegin
= std::min(newInterval
->mBegin
, subsumed
->mBegin
);
61 newInterval
->mEnd
= std::max(newInterval
->mEnd
, subsumed
->mEnd
);
62 newInterval
->mNext
= subsumed
->mNext
;
63 FreeInterval(subsumed
);
64 subsumed
= newInterval
->mNext
;
68 bool nsIntervalSet::Intersects(coord_type aBegin
, coord_type aEnd
) const
70 Interval
*current
= mList
;
71 while (current
&& current
->mBegin
<= aEnd
) {
72 if (current
->mEnd
>= aBegin
)
74 current
= current
->mNext
;
79 bool nsIntervalSet::Contains(coord_type aBegin
, coord_type aEnd
) const
81 Interval
*current
= mList
;
82 while (current
&& current
->mBegin
<= aBegin
) {
83 if (current
->mEnd
>= aEnd
)
85 current
= current
->mNext
;