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
rangeIntersection(const Range & r,Range & rOut) const19 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
rangeUnion(const Range & r,Range & rOut) const31 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
addRange(const Range & r)43 void RangeList::addRange(const Range& r) {
44 list.push_back(r);
45 }
46
addRanges(const RangeList & rl)47 void RangeList::addRanges(const RangeList& rl) {
48 for(int i =0; i< rl.size();i++) {
49 addRange(rl.list[i]);
50 }
51 }
52
delRanges(const RangeList & rl,RangeList & deleted)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
empty() const59 bool RangeList::empty() const{
60 return list.empty();
61 }
62
size() const63 int RangeList::size() const{
64 return list.size();
65 }
clear()66 void RangeList::clear() {
67 return list.clear();
68 }
69
erase(unsigned int i)70 void RangeList::erase(unsigned int i) {
71 if(i > list.size()) return;
72 list.erase(list.begin() +i);
73 }
74
delRange(const Range & r,RangeList & deleted)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
merge()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