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 false;
     39     }
     40     return false;
     41 }
     42 
     43 void RangeList::addRange(const Range& r) {
     44     list.push_back(r);
     45 }
     46 
     47 void RangeList::addRanges(const RangeList& rl) {
     48     for(int i =0; i< rl.size();i++) {
     49        addRange(rl.list[i]);
     50     }
     51 }
     52 
     53 void RangeList::delRanges(const RangeList& rl,RangeList& deleted) {
     54     for(int i =0; i< rl.size();i++) {
     55        delRange(rl.list[i],deleted);
     56     }
     57 }
     58 
     59 bool RangeList::empty() const{
     60     return list.empty();
     61 }
     62 
     63 int  RangeList::size() const{
     64     return list.size();
     65 }
     66 void RangeList::clear() {
     67     return list.clear();
     68 }
     69 
     70 void RangeList::erase(unsigned int i) {
     71     if(i > list.size()) return;
     72     list.erase(list.begin() +i);
     73 }
     74 
     75 void RangeList::delRange(const Range& r,RangeList& deleted) {
     76     if(r.getSize() == 0) return;
     77 
     78     Range intersection;
     79     Range temp;
     80     // compare new rect to each and any of the rects on the list
     81     for (int i=0;i<(int)list.size();i++) { // i must be signed for i-- below
     82      // if there is intersection
     83      if (r.rangeIntersection(list[i],intersection)) {
     84              Range old=list[i];
     85          // remove old as it is about to be split
     86          erase(i);
     87          i--;
     88          if (intersection!=old) { // otherwise split:
     89              //intersection on right side
     90              if(old.getStart() != intersection.getStart()) {
     91                  list.insert(list.begin(),Range(old.getStart(),intersection.getStart() - old.getStart()));
     92              }
     93 
     94              //intersection on left side
     95              if(old.getEnd() != intersection.getEnd()) {
     96                  list.insert(list.begin(),Range(intersection.getEnd(),old.getEnd() - intersection.getEnd()));
     97              }
     98          }
     99          deleted.addRange(intersection);
    100      }
    101  }
    102 }
    103 
    104 void RangeList::merge() {
    105     if(list.empty()) return;
    106 
    107     Range temp;
    108     bool changed;
    109 
    110     do { // re-run if changed in last run
    111         changed=0;
    112         // run for each combinations of two rects in the list
    113         for (int i=0;i<(((int)list.size())-1) && !changed ;i++)
    114         {
    115             for (int j=i+1;j<(int)list.size() && !changed ;j++)
    116             {
    117                if (list[i].rangeUnion(list[j],temp)) {
    118                     // are them exactly one on left of the other
    119                     list[i] = temp;
    120                     erase(j);
    121                     changed=1;
    122                }
    123             }
    124         }
    125     } while (changed);
    126 }
    127