| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file | |
| 2 // for details. All rights reserved. Use of this source code is governed by a | |
| 3 // BSD-style license that can be found in the LICENSE file. | |
| 4 | |
| 5 #ifndef BIN_SET_H_ | |
| 6 #define BIN_SET_H_ | |
| 7 | |
| 8 #include <stdlib.h> | |
| 9 | |
| 10 /* | |
| 11 * Set implements a collection of distinct objects. | |
| 12 */ | |
| 13 template <class T> | |
| 14 class Set { | |
| 15 private: | |
| 16 struct Node { | |
| 17 T object_; | |
| 18 Node* next_; | |
| 19 }; | |
| 20 | |
| 21 public: | |
| 22 class Iterator { | |
| 23 public: | |
| 24 explicit Iterator(Set<T>* list) : list_(list) { | |
| 25 if (list != NULL) { | |
| 26 next_ = list->head_; | |
| 27 } else { | |
| 28 next_ = NULL; | |
| 29 } | |
| 30 } | |
| 31 | |
| 32 bool HasNext() const { | |
| 33 return next_ != NULL; | |
| 34 } | |
| 35 | |
| 36 void GetNext(T* entry) { | |
| 37 *entry = next_->object_; | |
| 38 next_ = next_->next_; | |
| 39 } | |
| 40 | |
| 41 private: | |
| 42 const Set<T>* list_; | |
| 43 struct Node* next_; | |
| 44 }; | |
| 45 | |
| 46 Set() { | |
| 47 head_ = NULL; | |
| 48 tail_ = NULL; | |
| 49 size_ = 0; | |
| 50 } | |
| 51 | |
| 52 ~Set() {} | |
| 53 | |
| 54 bool Add(const T& element) { | |
| 55 Node* new_node = new Node; | |
| 56 new_node->object_ = element; | |
| 57 new_node->next_ = NULL; | |
| 58 | |
| 59 if (Contains(element)) { | |
| 60 return false; | |
| 61 } | |
| 62 | |
| 63 if (IsEmpty()) { | |
| 64 head_ = new_node; | |
| 65 tail_ = new_node; | |
| 66 } else { | |
| 67 tail_->next_ = new_node; | |
| 68 tail_ = new_node; | |
| 69 } | |
| 70 size_++; | |
| 71 return true; | |
| 72 } | |
| 73 | |
| 74 T* Remove(const T& element) { | |
| 75 Node* current = head_; | |
| 76 Node* previous = NULL; | |
| 77 if (IsEmpty()) { | |
| 78 return NULL; | |
| 79 } | |
| 80 | |
| 81 do { | |
| 82 if (element == current->object_) { | |
| 83 if (current == head_) { | |
| 84 head_ = head_->next_; | |
| 85 } | |
| 86 if (current == tail_) { | |
| 87 tail_ = previous; | |
| 88 } | |
| 89 if (previous != NULL) { | |
| 90 previous->next_ = current->next_; | |
| 91 } | |
| 92 size_--; | |
| 93 return ¤t->object_; | |
| 94 } | |
| 95 previous = current; | |
| 96 current = current->next_; | |
| 97 } while (current); | |
| 98 return NULL; | |
| 99 } | |
| 100 | |
| 101 bool Contains(const T& element) { | |
| 102 T value; | |
| 103 Iterator iterator(this); | |
| 104 while (iterator.HasNext()) { | |
| 105 iterator.GetNext(&value); | |
| 106 if (value == element) { | |
| 107 return true; | |
| 108 } | |
| 109 } | |
| 110 return false; | |
| 111 } | |
| 112 | |
| 113 bool IsEmpty() { | |
| 114 return head_ == NULL; | |
| 115 } | |
| 116 | |
| 117 int Size() { | |
| 118 return size_; | |
| 119 } | |
| 120 | |
| 121 private: | |
| 122 Node* head_; | |
| 123 Node* tail_; | |
| 124 int size_; | |
| 125 }; | |
| 126 | |
| 127 #endif // BIN_SET_H_ | |
| 128 | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 11365262:
Remove unused files. (Closed)
Base URL: http://dart.googlecode.com/svn/branches/bleeding_edge/dart/