00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033 #include <vector>
00034 #include "Serializable.h"
00035 #include "RandomUtil.h"
00036 #include "StrUtil.h"
00037
00038 #ifndef _MACE_SPARSE_ARRAY_H
00039 #define _MACE_SPARSE_ARRAY_H
00040
00046 namespace mace {
00047
00053
00054 template<class T, int size>
00055 class sparse_array : public Serializable, public PrintPrintable {
00056
00057 public:
00058 typedef int size_type;
00059 T* data[size];
00060
00061 sparse_array() : data() {
00062 }
00063
00064 sparse_array(const sparse_array<T, size>& v) {
00065 for(int i=0; i < size; i++) {
00066 if(v.data[i] != NULL) {
00067 data[i] = new T(*v.data[i]);
00068 } else {
00069 data[i] = NULL;
00070 }
00071 }
00072 }
00073
00074 sparse_array<T, size>& operator=(const sparse_array<T, size>& v) {
00075 if(this == &v) { return *this; }
00076 for(int i=0; i < size; i++) {
00077 delete data[i];
00078 if(v.data[i] != NULL) {
00079 data[i] = new T(*v.data[i]);
00080 } else {
00081 data[i] = NULL;
00082 }
00083 }
00084 return *this;
00085 }
00086
00087 virtual ~sparse_array() {
00088 for(int i=0; i < size; i++) {
00089 if(data[i] != NULL) { delete data[i]; data[i] = NULL; }
00090 }
00091 }
00092
00093 int deserialize(std::istream& in) throw(SerializationException) {
00094 int bytes = 0;
00095
00096 int count = 0;
00097 bytes += mace::deserialize(in, &count);
00098
00099 ASSERT(count <= size);
00100 for(int i=0; i < size; i++) {
00101 if(data[i] != NULL) { delete data[i]; data[i] = NULL; }
00102 }
00103
00104 for(size_type i=0; i<count; i++) {
00105 int place = 0;
00106 bytes += mace::deserialize(in, &place);
00107 bytes += mace::deserialize(in, &this->operator[](place));
00108 }
00109
00110 return bytes;
00111 }
00112
00113 void serialize(std::string &str) const {
00114 int count = 0;
00115 for(int i = 0; i < size; i++) { if(data[i] != NULL) { count++; } }
00116 mace::serialize(str, &count);
00117
00118 for(int i = 0; i < size; i++) {
00119 if(data[i] != NULL) {
00120 mace::serialize(str, &i);
00121 mace::serialize(str, data[i]);
00122 }
00123 }
00124 }
00125
00127 const std::string& getTypeName() const {
00128 const char* types[] = { "T", "int size", 0 };
00129 static const StrUtilNamespace::StdStringList myTypes = StrUtilNamespace::getTypeFromTemplate(__PRETTY_FUNCTION__, types);
00130 return myTypes[0];
00131 }
00132
00133 void print(std::ostream& out) const {
00134 if(mace::PRINT_TYPE_NAMES) {
00135 out << "mace::sparse_array<" << getTypeName() << ">";
00136 }
00137 out << "[";
00138 for(int i = 0; i < size; i++) {
00139 if(data[i] != NULL) {
00140 out << "(" << i << " => ";
00141 mace::printItem(out, data[i]);
00142 out << ")";
00143 }
00144 }
00145 out << "]";
00146 }
00147 void printState(std::ostream& out) const {
00148 if(mace::PRINT_TYPE_NAMES) {
00149 out << "mace::sparse_array<" << getTypeName() << ">[";
00150 }
00151 for(int i = 0; i < size; i++) {
00152 if(data[i] != NULL) {
00153 out << "(" << i << " => ";
00154 mace::printState(out, data[i], *data[i]);
00155 out << ")";
00156 }
00157 }
00158 out << "]";
00159 }
00160
00162 bool contains(size_type i) const { return data[i] != NULL; }
00164 T& operator[] (size_type place) {
00165 check(place);
00166 return *data[place];
00167 }
00169 const T& operator[] (size_type place) const {
00170 if(!this->contains(place)) { throw(new Exception("place is empty in sparse array when indexing data!")); }
00171 return *data[place];
00172 }
00174 void erase(size_type i) {
00175 delete data[i];
00176 data[i] = NULL;
00177 }
00178
00180 size_type count() const {
00181 size_type count = 0;
00182 for(size_type i = 0; i < size; i++) {
00183 if(this->contains(i)) {
00184 count++;
00185 }
00186 }
00187 return count;
00188 }
00189
00191 T& random(int *p = NULL) {
00192 return (*this)[(p?*p=RandomUtil::randInt(this->count()):RandomUtil::randInt(this->count()))];
00193 }
00195 const T& random(int *p = NULL) const {
00196 return (*this)[(p?*p=RandomUtil::randInt(this->count()):RandomUtil::randInt(this->count()))];
00197 }
00198
00199
00200 private:
00202 inline void check(int i) {
00203 if(data[i] == NULL) { data[i] = new T(); }
00204 }
00205
00206 };
00207
00210 }
00211 #endif // _MACE_SPARSE_ARRAY_H