00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014 #ifndef OR_TOOLS_UTIL_CONST_INT_PTR_ARRAY_H_
00015 #define OR_TOOLS_UTIL_CONST_INT_PTR_ARRAY_H_
00016
00017 #include <stddef.h>
00018 #include <algorithm>
00019 #include <functional>
00020 #include "base/hash.h"
00021 #include <string>
00022 #include <vector>
00023
00024 #include "base/basictypes.h"
00025 #include "base/integral_types.h"
00026 #include "base/logging.h"
00027 #include "base/scoped_ptr.h"
00028 #include "base/stringprintf.h"
00029 #include "base/concise_iterator.h"
00030 #include "base/map-util.h"
00031 #include "base/hash.h"
00032
00033 using std::string;
00034
00035 namespace operations_research {
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047 template <class T> class ConstIntPtrArray {
00048 public:
00049
00050 struct Cell {
00051 Cell(T* p, int64 c) : ptr(p), value(c) {}
00052 Cell() : ptr(NULL), value(0) {}
00053 string DebugString() const {
00054 return StringPrintf("(%lld|%s)", value, ptr->DebugString().c_str());
00055 }
00056 T* ptr;
00057 int64 value;
00058 };
00059
00060
00061 struct CompareValuesLT {
00062 bool operator()(const Cell& first, const Cell& second) {
00063 return first.value < second.value;
00064 }
00065 };
00066
00067 struct CompareValuesGT {
00068 bool operator()(const Cell& first, const Cell& second) {
00069 return first.value > second.value;
00070 }
00071 };
00072
00073
00074 template<typename Integer>
00075 ConstIntPtrArray(const std::vector<T*>& ptrs, const std::vector<Integer>& values)
00076 : data_(new std::vector<Cell>()) {
00077 data_->reserve(ptrs.size());
00078 CHECK_EQ(ptrs.size(), values.size());
00079 for (int i = 0; i < ptrs.size(); ++i) {
00080 data_->push_back(Cell(ptrs[i], values[i]));
00081 }
00082 }
00083
00084
00085 template<typename Integer>
00086 ConstIntPtrArray(T* const* ptrs,
00087 const Integer* const values,
00088 int size) : data_(new std::vector<Cell>()) {
00089 data_->reserve(size);
00090 for (int i = 0; i < size; ++i) {
00091 data_->push_back(Cell(ptrs[i], values[i]));
00092 }
00093 }
00094
00095
00096 explicit ConstIntPtrArray(std::vector<Cell>* const data) : data_(data) {}
00097
00098
00099
00100 std::vector<Cell>* Release() {
00101 return data_.release();
00102 }
00103
00104
00105 int size() const {
00106 CHECK_NOTNULL(data_.get());
00107 return data_->size();
00108 }
00109
00110
00111 int64 value(int64 index) const {
00112 CHECK_NOTNULL(data_.get());
00113 return (*data_)[index].value;
00114 }
00115
00116
00117
00118 T* ptr(int64 index) const {
00119 CHECK_NOTNULL(data_.get());
00120 return (*data_)[index].ptr;
00121 }
00122
00123
00124 std::vector<Cell>* Copy() const {
00125 CHECK_NOTNULL(data_.get());
00126 return new std::vector<Cell>(*data_);
00127 }
00128
00129
00130 std::vector<Cell>* SortedCopy(bool increasing) const {
00131 std::vector<Cell>* new_data = new std::vector<Cell>(*data_);
00132 Sort(new_data, increasing);
00133 return new_data;
00134 }
00135
00136
00137
00138
00139
00140 std::vector<Cell>* SortedCopyAggregateValues(bool increasing,
00141 bool remove_zeros) const {
00142
00143 hash_map<T*, int64> ptr_value_map;
00144 for (ConstIter<std::vector<Cell> > iter(*data_.get()); !iter.at_end(); ++iter) {
00145 T* const ptr = iter->ptr;
00146 const int64 current_value = FindWithDefault(ptr_value_map, ptr, 0);
00147 ptr_value_map[ptr] = current_value + iter->value;
00148 }
00149
00150 std::vector<Cell>* const new_data = new std::vector<Cell>();
00151 for (ConstIter<hash_map<T*, int64> > iter(ptr_value_map);
00152 !iter.at_end();
00153 ++iter) {
00154 if (!remove_zeros || iter->second != 0) {
00155 new_data->push_back(Cell(iter->first, iter->second));
00156 }
00157 }
00158
00159 Sort(new_data, increasing);
00160 return new_data;
00161 }
00162
00163
00164 string DebugString() const {
00165 if (data_.get() == NULL) {
00166 return "Released ConstIntPtrArray";
00167 }
00168 string result = "[";
00169 bool first = true;
00170 for (ConstIter<std::vector<Cell> > iter(*data_.get()); !iter.at_end(); ++iter) {
00171 if (first) {
00172 first = false;
00173 } else {
00174 result.append(", ");
00175 }
00176 result.append(iter->DebugString());
00177 }
00178 result.append("]");
00179 return result;
00180 }
00181 private:
00182 void Sort(std::vector<Cell>* const data, bool increasing) const {
00183 if (increasing) {
00184 std::stable_sort(data->begin(), data->end(), CompareValuesLT());
00185 } else {
00186 std::stable_sort(data->begin(), data->end(), CompareValuesGT());
00187 }
00188 }
00189 scoped_ptr<std::vector<Cell> > data_;
00190 };
00191 }
00192 #endif // OR_TOOLS_UTIL_CONST_INT_PTR_ARRAY_H_