45 int count()
const {
return fArray.size(); }
48 const T&
peek()
const {
return fArray[0]; }
55 if (1 == fArray.size()) {
60 fArray[0] = fArray[fArray.size() - 1];
63 this->percolateDownIfNecessary(0);
71 int index = fArray.size();
72 *fArray.append() = entry;
73 this->setIndex(fArray.size() - 1);
74 this->percolateUpIfNecessary(index);
81 int index = *INDEX(entry);
82 SkASSERT(index >= 0 && index < fArray.size());
85 if (index == fArray.size() - 1) {
89 fArray[index] = fArray[fArray.size() - 1];
91 this->setIndex(index);
92 this->percolateUpOrDown(index);
101 int index = *INDEX(entry);
102 SkASSERT(index >= 0 && index < fArray.size());
103 this->validate(index);
104 this->percolateUpOrDown(index);
110 T at(
int i)
const {
return fArray[i]; }
116 if (fArray.size() > 1) {
117 SkTQSort<T>(fArray.begin(), fArray.end(), LESS);
118 for (
int i = 0; i < fArray.size(); i++) {
126 static int LeftOf(
int x) {
SkASSERT(
x >= 0);
return 2 *
x + 1; }
127 static int ParentOf(
int x) {
SkASSERT(
x > 0);
return (
x - 1) >> 1; }
129 void percolateUpOrDown(
int index) {
131 if (!percolateUpIfNecessary(index)) {
132 this->validate(index);
133 this->percolateDownIfNecessary(index);
137 bool percolateUpIfNecessary(
int index) {
139 bool percolated =
false;
142 this->setIndex(index);
145 int p = ParentOf(index);
146 if (
LESS(fArray[index], fArray[p])) {
148 swap(fArray[index], fArray[p]);
149 this->setIndex(index);
153 this->setIndex(index);
156 this->validate(index);
160 void percolateDownIfNecessary(
int index) {
163 int child = LeftOf(index);
165 if (child >= fArray.size()) {
167 this->setIndex(index);
171 if (child + 1 >= fArray.size()) {
173 if (
LESS(fArray[child], fArray[index])) {
175 swap(fArray[child], fArray[index]);
176 this->setIndex(child);
177 this->setIndex(index);
180 }
else if (
LESS(fArray[child + 1], fArray[child])) {
186 if (
LESS(fArray[child], fArray[index])) {
188 swap(fArray[child], fArray[index]);
189 this->setIndex(index);
193 this->setIndex(index);
196 this->validate(index);
200 void setIndex(
int index) {
203 *INDEX(fArray[index]) = index;
207 void validate(
int excludedIndex = -1)
const {
209 for (
int i = 1; i < fArray.size(); ++i) {
211 if (excludedIndex != p && excludedIndex != i) {