| 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 227 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 238 | 238 |
| 239 // Turns on or off verbose debugging of the tree, causing many | 239 // Turns on or off verbose debugging of the tree, causing many |
| 240 // messages to be logged during insertion and other operations in | 240 // messages to be logged during insertion and other operations in |
| 241 // debug mode. | 241 // debug mode. |
| 242 void setVerboseDebugging(bool verboseDebugging) | 242 void setVerboseDebugging(bool verboseDebugging) |
| 243 { | 243 { |
| 244 m_verboseDebugging = verboseDebugging; | 244 m_verboseDebugging = verboseDebugging; |
| 245 } | 245 } |
| 246 #endif | 246 #endif |
| 247 | 247 |
| 248 enum Color { | 248 enum NodeColor { |
| 249 Red = 1, | 249 Red = 1, |
| 250 Black | 250 Black |
| 251 }; | 251 }; |
| 252 | 252 |
| 253 // The base Node class which is stored in the tree. Nodes are only | 253 // The base Node class which is stored in the tree. Nodes are only |
| 254 // an internal concept; users of the tree deal only with the data | 254 // an internal concept; users of the tree deal only with the data |
| 255 // they store in it. | 255 // they store in it. |
| 256 class Node { | 256 class Node { |
| 257 DISALLOW_NEW_EXCEPT_PLACEMENT_NEW(); | 257 DISALLOW_NEW_EXCEPT_PLACEMENT_NEW(); |
| 258 WTF_MAKE_NONCOPYABLE(Node); | 258 WTF_MAKE_NONCOPYABLE(Node); |
| 259 public: | 259 public: |
| 260 // Constructor. Newly-created nodes are colored red. | 260 // Constructor. Newly-created nodes are colored red. |
| 261 explicit Node(const T& data) | 261 explicit Node(const T& data) |
| 262 : m_left(0) | 262 : m_left(0) |
| 263 , m_right(0) | 263 , m_right(0) |
| 264 , m_parent(0) | 264 , m_parent(0) |
| 265 , m_color(Red) | 265 , m_color(Red) |
| 266 , m_data(data) | 266 , m_data(data) |
| 267 { | 267 { |
| 268 } | 268 } |
| 269 | 269 |
| 270 virtual ~Node() { } | 270 virtual ~Node() { } |
| 271 | 271 |
| 272 Color color() const { return m_color; } | 272 NodeColor color() const { return m_color; } |
| 273 void setColor(Color color) { m_color = color; } | 273 void setColor(NodeColor color) { m_color = color; } |
| 274 | 274 |
| 275 // Fetches the user data. | 275 // Fetches the user data. |
| 276 T& data() { return m_data; } | 276 T& data() { return m_data; } |
| 277 | 277 |
| 278 // Copies all user-level fields from the source node, but not | 278 // Copies all user-level fields from the source node, but not |
| 279 // internal fields. For example, the base implementation of this | 279 // internal fields. For example, the base implementation of this |
| 280 // method copies the "m_data" field, but not the child or parent | 280 // method copies the "m_data" field, but not the child or parent |
| 281 // fields. Any augmentation information also does not need to be | 281 // fields. Any augmentation information also does not need to be |
| 282 // copied, as it will be recomputed. Subclasses must call the | 282 // copied, as it will be recomputed. Subclasses must call the |
| 283 // superclass implementation. | 283 // superclass implementation. |
| 284 virtual void copyFrom(Node* src) { m_data = src->data(); } | 284 virtual void copyFrom(Node* src) { m_data = src->data(); } |
| 285 | 285 |
| 286 Node* left() const { return m_left; } | 286 Node* left() const { return m_left; } |
| 287 void setLeft(Node* node) { m_left = node; } | 287 void setLeft(Node* node) { m_left = node; } |
| 288 | 288 |
| 289 Node* right() const { return m_right; } | 289 Node* right() const { return m_right; } |
| 290 void setRight(Node* node) { m_right = node; } | 290 void setRight(Node* node) { m_right = node; } |
| 291 | 291 |
| 292 Node* parent() const { return m_parent; } | 292 Node* parent() const { return m_parent; } |
| 293 void setParent(Node* node) { m_parent = node; } | 293 void setParent(Node* node) { m_parent = node; } |
| 294 | 294 |
| 295 private: | 295 private: |
| 296 Node* m_left; | 296 Node* m_left; |
| 297 Node* m_right; | 297 Node* m_right; |
| 298 Node* m_parent; | 298 Node* m_parent; |
| 299 Color m_color; | 299 NodeColor m_color; |
| 300 T m_data; | 300 T m_data; |
| 301 }; | 301 }; |
| 302 | 302 |
| 303 protected: | 303 protected: |
| 304 // Returns the root of the tree, which is needed by some subclasses. | 304 // Returns the root of the tree, which is needed by some subclasses. |
| 305 Node* root() const { return m_root; } | 305 Node* root() const { return m_root; } |
| 306 | 306 |
| 307 private: | 307 private: |
| 308 // This virtual method is the hook that subclasses should use when | 308 // This virtual method is the hook that subclasses should use when |
| 309 // augmenting the red-black tree with additional per-node summary | 309 // augmenting the red-black tree with additional per-node summary |
| (...skipping 513 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 823 Node* m_root; | 823 Node* m_root; |
| 824 bool m_needsFullOrderingComparisons; | 824 bool m_needsFullOrderingComparisons; |
| 825 #ifndef NDEBUG | 825 #ifndef NDEBUG |
| 826 bool m_verboseDebugging; | 826 bool m_verboseDebugging; |
| 827 #endif | 827 #endif |
| 828 }; | 828 }; |
| 829 | 829 |
| 830 } // namespace blink | 830 } // namespace blink |
| 831 | 831 |
| 832 #endif // PODRedBlackTree_h | 832 #endif // PODRedBlackTree_h |
| OLD | NEW |