00001
#ifndef SORTEDVECTOR_H
00002
#define SORTEDVECTOR_H
00003
00004
#include <exception>
00005
#include <vector>
00006
#include <map>
00007
#include <algorithm>
00008
#include <assert.h>
00009
#include <Exceptions.h>
00010
00011
using namespace std;
00012
00013
template<
typename TValue>
00014 class SortedIndex
00015 {
00016
public:
00017
SortedIndex();
00018
virtual ~SortedIndex();
00019
00020
00021
00022
00023
void set(size_t i,
const TValue & v)
00024
throw (std::exception);
00025
00026
00027
void unset(size_t i)
00028
throw (std::exception);
00029
00030
00031
00032
00033
00034
00035
bool findByIndex(size_t k, TValue & v)
const
00036
throw (std::exception);
00037
00038
00039
00040
const map<size_t, TValue> &
getIndex()
const
00041
throw (std::exception);
00042
00043
00044
00045
00046
const multimap<TValue, size_t> &
getSortedMultimap()
const
00047
throw (std::exception);
00048
00049
00050
00051 size_t
getMaxIndex()
const
00052
throw (std::exception);
00053
00054
00055 size_t
size()
const
00056
throw (std::exception);
00057
00058
private:
00059
00060
void ensureUnset(size_t i)
00061
throw (std::exception);
00062
00063 map<size_t, TValue> _index;
00064 multimap<TValue, size_t> _sorted;
00065 };
00066
00067
00068
00069
template<
typename TValue>
00070 void SortedIndex<TValue>::set(size_t i,
const TValue & v)
00071
throw (std::exception)
00072 {
00073 ensureUnset(i);
00074 _index.insert(make_pair(i, v));
00075 _sorted.insert(make_pair(v, i));
00076 }
00077
00078
00079
00080
template<
typename TValue>
00081 void SortedIndex<TValue>::unset(size_t i)
00082
throw (std::exception)
00083 {
00084 ensureUnset(i);
00085 }
00086
00087
00088
00089
template<
typename TValue>
00090 bool SortedIndex<TValue>::findByIndex(size_t k, TValue & v)
const
00091
throw (std::exception)
00092 {
00093
typename map<size_t, TValue>::const_iterator indexPos = _index.find(i);
00094
00095
if (indexPos != _index.end())
00096 {
00097 v = indexPos->second;
00098
return true;
00099 }
00100
else
00101 {
00102
return false;
00103 }
00104 }
00105
00106
00107
00108
template<
typename TValue>
00109 const map<size_t, TValue> &
SortedIndex<TValue>::getIndex() const
00110 throw (std::exception)
00111 {
00112
return _index;
00113 }
00114
00115
00116
00117
template<
typename TValue>
00118 const multimap<TValue, size_t> &
SortedIndex<TValue>::getSortedMultimap() const
00119 throw (std::exception)
00120 {
00121
return _sorted;
00122 }
00123
00124
00125
00126
template<
typename TValue>
00127 size_t
SortedIndex<TValue>::getMaxIndex() const
00128 throw (std::exception)
00129 {
00130
typename map<size_t, TValue>::reverse_iterator rPos = _index.rbegin();
00131
if (rPos == _index.rend())
00132 {
00133
Throw(
AuroraException,
"The container is empty");
00134 }
00135
00136
return rPos->first;
00137 }
00138
00139
00140
00141
template<
typename TValue>
00142 size_t
SortedIndex<TValue>::size() const
00143 throw (std::exception)
00144 {
00145
return _index.size();
00146 }
00147
00148
00149
00150
template<
typename TValue>
00151
void SortedIndex<TValue>::ensureUnset(size_t i)
00152
throw (std::exception)
00153 {
00154
typename map<size_t, TValue>::iterator indexPos = _index.find(i);
00155
const TValue & oldValue = indexPos->second;
00156
00157
if (indexPos != _index.end())
00158 {
00159 multimapEraseExact<TValue, size_t>(_sorted, make_pair(oldValue, i));
00160 _index.erase(indexPos);
00161 }
00162 }
00163
00164
#endif