Home | History | Annotate | Download | only in GLcommon 
      1 /*
      2 * Copyright (C) 2011 The Android Open Source Project
      3 *
      4 * Licensed under the Apache License, Version 2.0 (the "License");
      5 * you may not use this file except in compliance with the License.
      6 * You may obtain a copy of the License at
      7 *
      8 * http://www.apache.org/licenses/LICENSE-2.0
      9 *
     10 * Unless required by applicable law or agreed to in writing, software
     11 * distributed under the License is distributed on an "AS IS" BASIS,
     12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13 * See the License for the specific language governing permissions and
     14 * limitations under the License.
     15 */
     16 #include <GLcommon/RangeManip.h>
     17 
     18 
     19 bool Range::rangeIntersection(const Range& r,Range& rOut) const {
     20     if(m_start > r.getEnd() || r.getStart() > m_end) return false;
     21     int max_start = (m_start > r.getStart())? m_start:r.getStart();
     22     int min_end = (m_end < r.getEnd())?m_end:r.getEnd();
     23     int size = min_end - max_start;
     24     if(size) {
     25         rOut.setRange(max_start,min_end-max_start);
     26         return true;
     27     }
     28     return false;
     29 }
     30 
     31 bool Range::rangeUnion(const Range& r,Range& rOut) const {
     32     if(m_start > r.getEnd() || r.getStart() > m_end) return false;
     33     int min_start = (m_start < r.getStart())?m_start:r.getStart();
     34     int max_end = (m_end > r.getEnd())?m_end:r.getEnd();
     35     int size =  max_end - min_start;
     36     if(size) {
     37         rOut.setRange(min_start,max_end-min_start);
     38         return true;
     39     }
     40     return false;
     41 }
     42 
     43 void RangeList::addRange(const Range& r) {
     44     if(r.getSize())
     45         list.push_back(r);
     46 }
     47 
     48 void RangeList::addRanges(const RangeList& rl) {
     49     for(int i =0; i< rl.size();i++) {
     50        addRange(rl.list[i]);
     51     }
     52 }
     53 
     54 void RangeList::delRanges(const RangeList& rl,RangeList& deleted) {
     55     for(int i =0; i< rl.size();i++) {
     56        delRange(rl.list[i],deleted);
     57     }
     58 }
     59 
     60 bool RangeList::empty() const{
     61     return list.empty();
     62 }
     63 
     64 int  RangeList::size() const{
     65     return list.size();
     66 }
     67 void RangeList::clear() {
     68     return list.clear();
     69 }
     70 
     71 void RangeList::erase(unsigned int i) {
     72     if(i > list.size()) return;
     73     list.erase(list.begin() +i);
     74 }
     75 
     76 void RangeList::delRange(const Range& r,RangeList& deleted) {
     77     if(r.getSize() == 0) return;
     78 
     79     Range intersection;
     80     Range temp;
     81     // compare new rect to each and any of the rects on the list
     82     for (int i=0;i<(int)list.size();i++) { // i must be signed for i-- below
     83      // if there is intersection
     84      if (r.rangeIntersection(list[i],intersection)) {
     85              Range old=list[i];
     86          // remove old as it is about to be split
     87          erase(i);
     88          i--;
     89          if (intersection!=old) { // otherwise split:
     90              //intersection on right side
     91              if(old.getStart() != intersection.getStart()) {
     92                  list.insert(list.begin(),Range(old.getStart(),intersection.getStart() - old.getStart()));
     93              }
     94 
     95              //intersection on left side
     96              if(old.getEnd() != intersection.getEnd()) {
     97                  list.insert(list.begin(),Range(intersection.getEnd(),old.getEnd() - intersection.getEnd()));
     98              }
     99          }
    100          deleted.addRange(intersection);
    101      }
    102  }
    103 }
    104 
    105 void RangeList::merge() {
    106     if(list.empty()) return;
    107 
    108     Range temp;
    109     bool changed;
    110 
    111     do { // re-run if changed in last run
    112         changed=0;
    113         // run for each combinations of two rects in the list
    114         for (int i=0;i<(((int)list.size())-1) && !changed ;i++)
    115         {
    116             for (int j=i+1;j<(int)list.size() && !changed ;j++)
    117             {
    118                if (list[i].rangeUnion(list[j],temp)) {
    119                     // are them exactly one on left of the other
    120                     list[i] = temp;
    121                     erase(j);
    122                     changed=1;
    123                }
    124             }
    125         }
    126     } while (changed);
    127 }
    128