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 "nsAlgorithm.h"
  43 #include NEW_H
  44
  45 nsIntervalSet::nsIntervalSet(IntervalSetAlloc aAlloc, IntervalSetFree aFree,
  46                              void* aAllocatorClosure)
  47     : mList(nsnull),
  48       mAlloc(aAlloc),
  49       mFree(aFree),
  50       mAllocatorClosure(aAllocatorClosure)
  51 {
  52     NS_ASSERTION(mAlloc && mFree, "null callback params");
  53 }
  54
  55 nsIntervalSet::~nsIntervalSet()
  56 {
  57     Interval *current = mList;
  58     while (current) {
  59         Interval *trash = current;
  60         current = current->mNext;
  61         FreeInterval(trash);
  62     }
  63 }
  64
  65 void nsIntervalSet::FreeInterval(nsIntervalSet::Interval *aInterval)
  66 {
  67     NS_ASSERTION(aInterval, "null interval");
  68
  69     aInterval->Interval::~Interval();
  70     (*mFree)(sizeof(Interval), aInterval, mAllocatorClosure);
  71 }
  72
  73 void nsIntervalSet::IncludeInterval(coord_type aBegin, coord_type aEnd)
  74 {
  75     Interval *newInterval = static_cast<Interval*>
  76                                        ((*mAlloc)(sizeof(Interval), mAllocatorClosure));
  77     if (!newInterval) {
  78         NS_NOTREACHED("allocation failure");
  79         return;
  80     }
  81     new(newInterval) Interval(aBegin, aEnd);
  82
  83     Interval **current = &mList;
  84     while (*current && (*current)->mEnd < aBegin)
  85         current = &(*current)->mNext;
  86
  87     newInterval->mNext = *current;
  88     *current = newInterval;
  89
  90     Interval *subsumed = newInterval->mNext;
  91     while (subsumed && subsumed->mBegin <= aEnd) {
  92         newInterval->mBegin = NS_MIN(newInterval->mBegin, subsumed->mBegin);
  93         newInterval->mEnd = NS_MAX(newInterval->mEnd, subsumed->mEnd);
  94         newInterval->mNext = subsumed->mNext;
  95         FreeInterval(subsumed);
  96         subsumed = newInterval->mNext;
  97     }
  98 }
  99
 100 PRBool nsIntervalSet::Intersects(coord_type aBegin, coord_type aEnd) const
 101 {
 102     Interval *current = mList;
 103     while (current && current->mBegin <= aEnd) {
 104         if (current->mEnd >= aBegin)
 105             return PR_TRUE;
 106         current = current->mNext;
 107     }
 108     return PR_FALSE;
 109 }
 110
 111 PRBool nsIntervalSet::Contains(coord_type aBegin, coord_type aEnd) const
 112 {
 113     Interval *current = mList;
 114     while (current && current->mBegin <= aBegin) {
 115         if (current->mEnd >= aEnd)
 116             return PR_TRUE;
 117         current = current->mNext;
 118     }
 119     return PR_FALSE;
 120 }