layout/generic/nsIntervalSet.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 // vim:cindent:ts=8:et:sw=4:
   3 /* ***** BEGIN LICENSE BLOCK *****
   4  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   5  *
   6  * The contents of this file are subject to the Mozilla Public License Version
   7  * 1.1 (the "License"); you may not use this file except in compliance with
   8  * the License. You may obtain a copy of the License at
   9  * http://www.mozilla.org/MPL/
  10  *
  11  * Software distributed under the License is distributed on an "AS IS" basis,
  12  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  13  * for the specific language governing rights and limitations under the
  14  * License.
  15  *
  16  * The Original Code is nsIntervalSet.
  17  *
  18  * The Initial Developer of the Original Code is Netscape Communications
  19  * Corporation.  Portions created by the Initial Developer are Copyright
  20  * (C) 2001 the Initial Developer. All Rights Reserved.
  21  *
  22  * Contributor(s):
  23  *   L. David Baron <dbaron@dbaron.org> (original author)
  24  *
  25  * Alternatively, the contents of this file may be used under the terms of
  26  * either the GNU General Public License Version 2 or later (the "GPL"), or
  27  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  28  * in which case the provisions of the GPL or the LGPL are applicable instead
  29  * of those above. If you wish to allow use of your version of this file only
  30  * under the terms of either the GPL or the LGPL, and not to allow others to
  31  * use your version of this file under the terms of the MPL, indicate your
  32  * decision by deleting the provisions above and replace them with the notice
  33  * and other provisions required by the GPL or the LGPL. If you do not delete
  34  * the provisions above, a recipient may use your version of this file under
  35  * the terms of any one of the MPL, the GPL or the LGPL.
  36  *
  37  * ***** END LICENSE BLOCK ***** */
  38
  39 /* a set of ranges on a number-line */
  40
  41 #include "nsIntervalSet.h"
  42 #include NEW_H
  43
  44 nsIntervalSet::nsIntervalSet(IntervalSetAlloc aAlloc, IntervalSetFree aFree,
  45                              void* aAllocatorClosure)
  46     : mList(nsnull),
  47       mAlloc(aAlloc),
  48       mFree(aFree),
  49       mAllocatorClosure(aAllocatorClosure)
  50 {
  51     NS_ASSERTION(mAlloc && mFree, "null callback params");
  52 }
  53
  54 nsIntervalSet::~nsIntervalSet()
  55 {
  56     Interval *current = mList;
  57     while (current) {
  58         Interval *trash = current;
  59         current = current->mNext;
  60         FreeInterval(trash);
  61     }
  62 }
  63
  64 void nsIntervalSet::FreeInterval(nsIntervalSet::Interval *aInterval)
  65 {
  66     NS_ASSERTION(aInterval, "null interval");
  67
  68     aInterval->Interval::~Interval();
  69     (*mFree)(sizeof(Interval), aInterval, mAllocatorClosure);
  70 }
  71
  72 void nsIntervalSet::IncludeInterval(coord_type aBegin, coord_type aEnd)
  73 {
  74     Interval *newInterval = static_cast<Interval*>
  75                                        ((*mAlloc)(sizeof(Interval), mAllocatorClosure));
  76     if (!newInterval) {
  77         NS_NOTREACHED("allocation failure");
  78         return;
  79     }
  80     new(newInterval) Interval(aBegin, aEnd);
  81
  82     Interval **current = &mList;
  83     while (*current && (*current)->mEnd < aBegin)
  84         current = &(*current)->mNext;
  85
  86     newInterval->mNext = *current;
  87     *current = newInterval;
  88
  89     Interval *subsumed = newInterval->mNext;
  90     while (subsumed && subsumed->mBegin <= aEnd) {
  91         newInterval->mBegin = PR_MIN(newInterval->mBegin, subsumed->mBegin);
  92         newInterval->mEnd = PR_MAX(newInterval->mEnd, subsumed->mEnd);
  93         newInterval->mNext = subsumed->mNext;
  94         FreeInterval(subsumed);
  95         subsumed = newInterval->mNext;
  96     }
  97 }
  98
  99 PRBool nsIntervalSet::HasPoint(coord_type aPoint) const
 100 {
 101     Interval *current = mList;
 102     while (current && current->mBegin <= aPoint) {
 103         if (current->mEnd >= aPoint)
 104             return PR_TRUE;
 105         current = current->mNext;
 106     }
 107     return PR_FALSE;
 108 }
 109
 110 PRBool nsIntervalSet::Intersects(coord_type aBegin, coord_type aEnd) const
 111 {
 112     Interval *current = mList;
 113     while (current && current->mBegin <= aEnd) {
 114         if (current->mEnd >= aBegin)
 115             return PR_TRUE;
 116         current = current->mNext;
 117     }
 118     return PR_FALSE;
 119 }
 120
 121 PRBool nsIntervalSet::Contains(coord_type aBegin, coord_type aEnd) const
 122 {
 123     Interval *current = mList;
 124     while (current && current->mBegin <= aBegin) {
 125         if (current->mEnd >= aEnd)
 126             return PR_TRUE;
 127         current = current->mNext;
 128     }
 129     return PR_FALSE;
 130 }