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 true;
39 }
40 return false;
41 }
42
addRange(const Range & r)43 void RangeList::addRange(const Range& r) {
44 if(r.getSize())
45 list.push_back(r);
46 }
47
addRanges(const RangeList & rl)48 void RangeList::addRanges(const RangeList& rl) {
49 for(int i =0; i< rl.size();i++) {
50 addRange(rl.list[i]);
51 }
52 }
53
delRanges(const RangeList & rl,RangeList & deleted)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
empty() const60 bool RangeList::empty() const{
61 return list.empty();
62 }
63
size() const64 int RangeList::size() const{
65 return list.size();
66 }
clear()67 void RangeList::clear() {
68 return list.clear();
69 }
70
erase(unsigned int i)71 void RangeList::erase(unsigned int i) {
72 if(i > list.size()) return;
73 list.erase(list.begin() +i);
74 }
75
delRange(const Range & r,RangeList & deleted)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
merge()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