OLD | NEW |
1 /* | 1 /* |
2 * Copyright (C) 2010 Google Inc. All rights reserved. | 2 * Copyright (C) 2010 Google Inc. All rights reserved. |
3 * | 3 * |
4 * Redistribution and use in source and binary forms, with or without | 4 * Redistribution and use in source and binary forms, with or without |
5 * modification, are permitted provided that the following conditions | 5 * modification, are permitted provided that the following conditions |
6 * are met: | 6 * are met: |
7 * | 7 * |
8 * 1. Redistributions of source code must retain the above copyright | 8 * 1. Redistributions of source code must retain the above copyright |
9 * notice, this list of conditions and the following disclaimer. | 9 * notice, this list of conditions and the following disclaimer. |
10 * 2. Redistributions in binary form must reproduce the above copyright | 10 * 2. Redistributions in binary form must reproduce the above copyright |
(...skipping 153 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
164 if (!arena_) | 164 if (!arena_) |
165 arena_ = PODFreeListArena<Node>::Create(); | 165 arena_ = PODFreeListArena<Node>::Create(); |
166 } | 166 } |
167 | 167 |
168 void InitIfNeeded(PODFreeListArena<Node>* arena) { | 168 void InitIfNeeded(PODFreeListArena<Node>* arena) { |
169 if (!arena_) | 169 if (!arena_) |
170 arena_ = arena; | 170 arena_ = arena; |
171 } | 171 } |
172 | 172 |
173 void Add(const T& data) { | 173 void Add(const T& data) { |
174 ASSERT(IsInitialized()); | 174 DCHECK(IsInitialized()); |
175 Node* node = arena_->template AllocateObject<T>(data); | 175 Node* node = arena_->template AllocateObject<T>(data); |
176 InsertNode(node); | 176 InsertNode(node); |
177 } | 177 } |
178 | 178 |
179 // Returns true if the datum was found in the tree. | 179 // Returns true if the datum was found in the tree. |
180 bool Remove(const T& data) { | 180 bool Remove(const T& data) { |
181 ASSERT(IsInitialized()); | 181 DCHECK(IsInitialized()); |
182 Node* node = TreeSearch(data); | 182 Node* node = TreeSearch(data); |
183 if (node) { | 183 if (node) { |
184 DeleteNode(node); | 184 DeleteNode(node); |
185 return true; | 185 return true; |
186 } | 186 } |
187 return false; | 187 return false; |
188 } | 188 } |
189 | 189 |
190 bool Contains(const T& data) const { | 190 bool Contains(const T& data) const { |
191 ASSERT(IsInitialized()); | 191 DCHECK(IsInitialized()); |
192 return TreeSearch(data); | 192 return TreeSearch(data); |
193 } | 193 } |
194 | 194 |
195 void VisitInorder(Visitor* visitor) const { | 195 void VisitInorder(Visitor* visitor) const { |
196 ASSERT(IsInitialized()); | 196 DCHECK(IsInitialized()); |
197 if (!root_) | 197 if (!root_) |
198 return; | 198 return; |
199 VisitInorderImpl(root_, visitor); | 199 VisitInorderImpl(root_, visitor); |
200 } | 200 } |
201 | 201 |
202 int size() const { | 202 int size() const { |
203 ASSERT(IsInitialized()); | 203 DCHECK(IsInitialized()); |
204 Counter counter; | 204 Counter counter; |
205 VisitInorder(&counter); | 205 VisitInorder(&counter); |
206 return counter.Count(); | 206 return counter.Count(); |
207 } | 207 } |
208 | 208 |
209 // See the class documentation for an explanation of this property. | 209 // See the class documentation for an explanation of this property. |
210 void SetNeedsFullOrderingComparisons(bool needs_full_ordering_comparisons) { | 210 void SetNeedsFullOrderingComparisons(bool needs_full_ordering_comparisons) { |
211 needs_full_ordering_comparisons_ = needs_full_ordering_comparisons; | 211 needs_full_ordering_comparisons_ = needs_full_ordering_comparisons; |
212 } | 212 } |
213 | 213 |
214 virtual bool CheckInvariants() const { | 214 virtual bool CheckInvariants() const { |
215 ASSERT(IsInitialized()); | 215 DCHECK(IsInitialized()); |
216 int black_count; | 216 int black_count; |
217 return CheckInvariantsFromNode(root_, &black_count); | 217 return CheckInvariantsFromNode(root_, &black_count); |
218 } | 218 } |
219 | 219 |
220 #ifndef NDEBUG | 220 #ifndef NDEBUG |
221 // Dumps the tree's contents to the logging info stream for | 221 // Dumps the tree's contents to the logging info stream for |
222 // debugging purposes. | 222 // debugging purposes. |
223 void Dump() const { | 223 void Dump() const { |
224 if (arena_) | 224 if (arena_) |
225 DumpFromNode(root_, 0); | 225 DumpFromNode(root_, 0); |
(...skipping 311 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
537 // a node. Note that x may be null, which is why xParent must be | 537 // a node. Note that x may be null, which is why xParent must be |
538 // supplied. | 538 // supplied. |
539 void DeleteFixup(Node* x, Node* x_parent) { | 539 void DeleteFixup(Node* x, Node* x_parent) { |
540 while (x != root_ && (!x || x->GetColor() == kBlack)) { | 540 while (x != root_ && (!x || x->GetColor() == kBlack)) { |
541 if (x == x_parent->Left()) { | 541 if (x == x_parent->Left()) { |
542 // Note: the text points out that w can not be null. | 542 // Note: the text points out that w can not be null. |
543 // The reason is not obvious from simply looking at | 543 // The reason is not obvious from simply looking at |
544 // the code; it comes about from the properties of the | 544 // the code; it comes about from the properties of the |
545 // red-black tree. | 545 // red-black tree. |
546 Node* w = x_parent->Right(); | 546 Node* w = x_parent->Right(); |
547 ASSERT(w); // x's sibling should not be null. | 547 DCHECK(w); // x's sibling should not be null. |
548 if (w->GetColor() == kRed) { | 548 if (w->GetColor() == kRed) { |
549 // Case 1 | 549 // Case 1 |
550 w->SetColor(kBlack); | 550 w->SetColor(kBlack); |
551 x_parent->SetColor(kRed); | 551 x_parent->SetColor(kRed); |
552 LeftRotate(x_parent); | 552 LeftRotate(x_parent); |
553 w = x_parent->Right(); | 553 w = x_parent->Right(); |
554 } | 554 } |
555 if ((!w->Left() || w->Left()->GetColor() == kBlack) && | 555 if ((!w->Left() || w->Left()->GetColor() == kBlack) && |
556 (!w->Right() || w->Right()->GetColor() == kBlack)) { | 556 (!w->Right() || w->Right()->GetColor() == kBlack)) { |
557 // Case 2 | 557 // Case 2 |
(...skipping 19 matching lines...) Expand all Loading... |
577 } | 577 } |
578 } else { | 578 } else { |
579 // Same as "then" clause with "right" and "left" | 579 // Same as "then" clause with "right" and "left" |
580 // exchanged. | 580 // exchanged. |
581 | 581 |
582 // Note: the text points out that w can not be null. | 582 // Note: the text points out that w can not be null. |
583 // The reason is not obvious from simply looking at | 583 // The reason is not obvious from simply looking at |
584 // the code; it comes about from the properties of the | 584 // the code; it comes about from the properties of the |
585 // red-black tree. | 585 // red-black tree. |
586 Node* w = x_parent->Left(); | 586 Node* w = x_parent->Left(); |
587 ASSERT(w); // x's sibling should not be null. | 587 DCHECK(w); // x's sibling should not be null. |
588 if (w->GetColor() == kRed) { | 588 if (w->GetColor() == kRed) { |
589 // Case 1 | 589 // Case 1 |
590 w->SetColor(kBlack); | 590 w->SetColor(kBlack); |
591 x_parent->SetColor(kRed); | 591 x_parent->SetColor(kRed); |
592 RightRotate(x_parent); | 592 RightRotate(x_parent); |
593 w = x_parent->Left(); | 593 w = x_parent->Left(); |
594 } | 594 } |
595 if ((!w->Right() || w->Right()->GetColor() == kBlack) && | 595 if ((!w->Right() || w->Right()->GetColor() == kBlack) && |
596 (!w->Left() || w->Left()->GetColor() == kBlack)) { | 596 (!w->Left() || w->Left()->GetColor() == kBlack)) { |
597 // Case 2 | 597 // Case 2 |
(...skipping 188 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
786 Node* root_; | 786 Node* root_; |
787 bool needs_full_ordering_comparisons_; | 787 bool needs_full_ordering_comparisons_; |
788 #ifndef NDEBUG | 788 #ifndef NDEBUG |
789 bool verbose_debugging_; | 789 bool verbose_debugging_; |
790 #endif | 790 #endif |
791 }; | 791 }; |
792 | 792 |
793 } // namespace blink | 793 } // namespace blink |
794 | 794 |
795 #endif // PODRedBlackTree_h | 795 #endif // PODRedBlackTree_h |
OLD | NEW |