-
Notifications
You must be signed in to change notification settings - Fork 10
/
adevs_bag.h
177 lines (173 loc) · 5.63 KB
/
adevs_bag.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
/**
* Copyright (c) 2013, James Nutaro
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* 1. Redistributions of source code must retain the above copyright notice, this
* list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
* ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
* The views and conclusions contained in the software and documentation are those
* of the authors and should not be interpreted as representing official policies,
* either expressed or implied, of the FreeBSD Project.
*
* Bugs, comments, and questions can be sent to nutaro@gmail.com
*/
#ifndef _adevs_bag_h
#define _adevs_bag_h
#include <cstdlib>
namespace adevs
{
/**
* The Bag is (almost) a model of a STL Multiple Associative Container.
* This implementation is optimized for the simulation engine, and it
* does not satisfy the STL complexity requirements. Neither does it implement
* the full set of required methods, but those methods that are implemented
* conform to the standard (except for the time complexity requirement).
*/
template <class T> class Bag
{
public:
/// A bidirectional iterator for the Bag
class iterator
{
public:
iterator(unsigned int start = 0, T* b = NULL):
i(start),b(b){}
iterator(const iterator& src):
i(src.i),b(src.b){}
const iterator& operator=(const iterator& src)
{
i = src.i;
b = src.b;
return *this;
}
bool operator==(const iterator& src) const { return i==src.i; }
bool operator!=(const iterator& src) const { return i!=src.i; }
T& operator*() { return b[i]; }
const T& operator*() const { return b[i]; }
iterator& operator++() { i++; return *this; }
iterator& operator--() { i--; return *this; }
iterator& operator++(int) { ++i; return *this; }
iterator& operator--(int) { --i; return *this; }
private:
friend class Bag<T>;
unsigned int i;
T* b;
};
typedef iterator const_iterator;
/// Create an empty bag with an initial capacity
Bag(unsigned int cap = 8):
cap_(cap),size_(0),b(new T[cap]){}
/// Copy constructor uses the = operator of T
Bag(const Bag<T>& src):
cap_(src.cap_),
size_(src.size_)
{
b = new T[src.cap_];
for (unsigned int i = 0; i < size_; i++)
b[i] = src.b[i];
}
/// Assignment operator uses the = operator of T
const Bag<T>& operator=(const Bag<T>& src)
{
cap_ = src.cap_;
size_ = src.size_;
delete [] b;
b = new T[src.cap_];
for (unsigned int i = 0; i < size_; i++)
b[i] = src.b[i];
return *this;
}
/// Swaps contents of this bag with the contents of the supplied bag. Returns this bag.
Bag<T>& swap(Bag<T>& src)
{
unsigned tmp_cap_, tmp_size_;
T* tmp_b;
tmp_cap_ = src.cap_;
tmp_size_ = src.size_;
tmp_b = src.b;
src.cap_ = cap_;
src.size_ = size_;
src.b = b;
cap_ = tmp_cap_;
size_ = tmp_size_;
b = tmp_b;
return *this;
}
/// Count the instances of a stored in the bag
unsigned count(const T& a) const
{
unsigned result = 0;
for (unsigned i = 0; i < size_; i++)
if (b[i] == a) result++;
return result;
}
/// Get the number of elements in the bag
unsigned size() const { return size_; }
/// Same as size()==0
bool empty() const { return size_ == 0; }
/// Get an iterator pointing to the first element in the bag
iterator begin() const { return iterator(0,b); }
/// Get an iterator to the end of the bag (i.e., just after the last element)
iterator end() const { return iterator(size_,b); }
/// Erase the first instance of k
void erase(const T& k)
{
iterator p = find(k);
if (p != end()) erase(p);
}
/// Erase the element pointed to by p
void erase(iterator p)
{
size_--;
b[p.i] = b[size_];
}
/// Remove all of the elements from the bag
void clear() { size_ = 0; }
/// Find the first instance of k, or end() if no instance is found. Uses == for comparing T.
iterator find(const T& k) const
{
for (unsigned i = 0; i < size_; i++)
if (b[i] == k) return iterator(i,b);
return end();
}
/// Put t into the bag
void insert(const T& t)
{
if (cap_ == size_) enlarge(2*cap_);
b[size_] = t;
size_++;
}
~Bag() { delete [] b; }
private:
unsigned cap_, size_;
T* b;
/// Adds the specified capacity to the bag.
void enlarge(unsigned adjustment)
{
cap_ = cap_ + adjustment;
T* rb = new T[cap_];
for (unsigned i = 0; i < size_; i++)
rb[i] = b[i];
delete [] b;
b = rb;
}
};
} // end of namespace
#endif