adevs
adevs_bag.h
1 
31 #ifndef _adevs_bag_h
32 #define _adevs_bag_h
33 #include <cstdlib>
34 
35 namespace adevs
36 {
37 
45 template <class T> class Bag
46 {
47  public:
49  class iterator
50  {
51  public:
52  iterator(unsigned int start = 0, T* b = NULL):
53  i(start),b(b){}
54  iterator(const iterator& src):
55  i(src.i),b(src.b){}
56  const iterator& operator=(const iterator& src)
57  {
58  i = src.i;
59  b = src.b;
60  return *this;
61  }
62  bool operator==(const iterator& src) const { return i==src.i; }
63  bool operator!=(const iterator& src) const { return i!=src.i; }
64  T& operator*() { return b[i]; }
65  const T& operator*() const { return b[i]; }
66  iterator& operator++() { i++; return *this; }
67  iterator& operator--() { i--; return *this; }
68  iterator& operator++(int) { ++i; return *this; }
69  iterator& operator--(int) { --i; return *this; }
70  private:
71  friend class Bag<T>;
72  unsigned int i;
73  T* b;
74  };
75  typedef iterator const_iterator;
77  Bag(unsigned int cap = 8):
78  cap_(cap),size_(0),b(new T[cap]){}
80  Bag(const Bag<T>& src):
81  cap_(src.cap_),
82  size_(src.size_)
83  {
84  b = new T[src.cap_];
85  for (unsigned int i = 0; i < size_; i++)
86  b[i] = src.b[i];
87  }
89  const Bag<T>& operator=(const Bag<T>& src)
90  {
91  cap_ = src.cap_;
92  size_ = src.size_;
93  delete [] b;
94  b = new T[src.cap_];
95  for (unsigned int i = 0; i < size_; i++)
96  b[i] = src.b[i];
97  return *this;
98  }
101  {
102  unsigned tmp_cap_, tmp_size_;
103  T* tmp_b;
104  tmp_cap_ = src.cap_;
105  tmp_size_ = src.size_;
106  tmp_b = src.b;
107  src.cap_ = cap_;
108  src.size_ = size_;
109  src.b = b;
110  cap_ = tmp_cap_;
111  size_ = tmp_size_;
112  b = tmp_b;
113  return *this;
114  }
116  unsigned count(const T& a) const
117  {
118  unsigned result = 0;
119  for (unsigned i = 0; i < size_; i++)
120  if (b[i] == a) result++;
121  return result;
122  }
124  unsigned size() const { return size_; }
126  bool empty() const { return size_ == 0; }
128  iterator begin() const { return iterator(0,b); }
130  iterator end() const { return iterator(size_,b); }
132  void erase(const T& k)
133  {
134  iterator p = find(k);
135  if (p != end()) erase(p);
136  }
138  void erase(iterator p)
139  {
140  size_--;
141  b[p.i] = b[size_];
142  }
144  void clear() { size_ = 0; }
146  iterator find(const T& k) const
147  {
148  for (unsigned i = 0; i < size_; i++)
149  if (b[i] == k) return iterator(i,b);
150  return end();
151  }
153  void insert(const T& t)
154  {
155  if (cap_ == size_) enlarge(2*cap_);
156  b[size_] = t;
157  size_++;
158  }
159  ~Bag() { delete [] b; }
160  private:
161  unsigned cap_, size_;
162  T* b;
164  void enlarge(unsigned adjustment)
165  {
166  cap_ = cap_ + adjustment;
167  T* rb = new T[cap_];
168  for (unsigned i = 0; i < size_; i++)
169  rb[i] = b[i];
170  delete [] b;
171  b = rb;
172  }
173  };
174 
175 } // end of namespace
176 
177 #endif
bool empty() const
Same as size()==0.
Definition: adevs_bag.h:126
void erase(const T &k)
Erase the first instance of k.
Definition: adevs_bag.h:132
iterator find(const T &k) const
Find the first instance of k, or end() if no instance is found. Uses == for comparing T...
Definition: adevs_bag.h:146
void clear()
Remove all of the elements from the bag.
Definition: adevs_bag.h:144
iterator begin() const
Get an iterator pointing to the first element in the bag.
Definition: adevs_bag.h:128
unsigned count(const T &a) const
Count the instances of a stored in the bag.
Definition: adevs_bag.h:116
iterator end() const
Get an iterator to the end of the bag (i.e., just after the last element)
Definition: adevs_bag.h:130
void erase(iterator p)
Erase the element pointed to by p.
Definition: adevs_bag.h:138
Bag(unsigned int cap=8)
Create an empty bag with an initial capacity.
Definition: adevs_bag.h:77
Bag(const Bag< T > &src)
Copy constructor uses the = operator of T.
Definition: adevs_bag.h:80
Bag< T > & swap(Bag< T > &src)
Swaps contents of this bag with the contents of the supplied bag. Returns this bag.
Definition: adevs_bag.h:100
A bidirectional iterator for the Bag.
Definition: adevs_bag.h:49
unsigned size() const
Get the number of elements in the bag.
Definition: adevs_bag.h:124
void insert(const T &t)
Put t into the bag.
Definition: adevs_bag.h:153
const Bag< T > & operator=(const Bag< T > &src)
Assignment operator uses the = operator of T.
Definition: adevs_bag.h:89
Definition: adevs_bag.h:45