COIN-OR::LEMON - Graph Library

Changeset 361:ab0899df30d2 in lemon-0.x for src


Ignore:
Timestamp:
04/21/04 17:46:40 (16 years ago)
Author:
Mihaly Barasz
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@489
Message:

IterableMap? with template ValueType?. IterableBoolMap? as a specialization.
Range checking warnings...

Location:
src/work/klao
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/work/klao/iter_map.h

    r347 r361  
    1717  /// \todo Decide whether we need all the range checkings!!!
    1818
    19   template<typename KeyIntMap, uint8_t N>
     19  template<typename KeyIntMap, uint8_t N, typename Val = uint8_t>
    2020  class IterableMap {
    2121  public:
    2222
    2323    typedef typename KeyIntMap::KeyType KeyType;
    24     typedef uint8_t ValueType;
     24    typedef Val ValueType;
    2525
    2626    typedef typename std::vector<KeyType>::const_iterator iterator;
     
    3030    std::vector<KeyType> data;
    3131    size_t bounds[N];
     32    Val def_val;
    3233
    33     uint8_t find(size_t a) const {
    34       uint8_t n=0;
    35       for(; n<N && bounds[n]<=a; ++n);
    36       return n;
     34    Val find(size_t a) const {
     35      for(uint8_t n=0; n<N; ++n) {
     36        if(bounds[n] > a)
     37          return n;
     38      }
     39      return def_val;
    3740    }
    3841
     
    6770  public:
    6871   
    69     IterableMap(KeyIntMap &_base) : base(_base) {
     72    IterableMap(KeyIntMap &_base, Val d = N+1) : base(_base), def_val(d) {
    7073      memset(bounds, 0, sizeof(bounds));
    7174      //    for(int i=0; i<N; ++i) { bounds[i]=0; }
    7275    }
    7376
    74     uint8_t operator[](const KeyType& k) const {
     77    Val operator[](const KeyType& k) const {
    7578      return find(base[k]);
    7679    }
    7780
    78     void set(const KeyType& k, uint8_t n) {
     81    void set(const KeyType& k, Val n) {
     82      // FIXME: n < N ???
    7983      size_t a = base[k];
    80       if(a < bounds[N-1]) {
     84      if(a < bounds[N-1] && n < N) {
    8185        base.set(k, move(a, find(a), n));
    8286      }
    8387    }
    8488
    85     void insert(const KeyType& k, uint8_t n) {
    86       if(n<N) {
     89    void insert(const KeyType& k, Val n) {
     90      if(n < N) {
    8791        data.push_back(k);
    8892        base.set(k, move(bounds[N-1]++, N-1, n));
     
    9094    }
    9195
    92     iterator begin(uint8_t n) const {
     96    iterator begin(Val n) const {
    9397      if(n < N)
    9498        return data.begin() + (n ? bounds[n-1] : 0);
     
    97101    }
    98102
    99     iterator end(uint8_t n) const {
     103    iterator end(Val n) const {
    100104      if(n < N)
    101105        return data.begin() + bounds[n];
     
    104108    }
    105109
    106     size_t size(uint8_t n) const {
     110    size_t size(Val n) const {
    107111      if(n < N)
    108112        return bounds[n] - (n ? bounds[n-1] : 0);
     
    118122  };
    119123
     124
     125
     126
     127  template<typename KeyIntMap>
     128  class IterableBoolMap : public IterableMap<KeyIntMap, 2, bool> {
     129    typedef IterableMap<KeyIntMap, 2, bool> Parent;
     130
     131  public:
     132    IterableBoolMap(KeyIntMap &_base, bool d = false) : Parent(_base, d) {}
     133  };
     134
    120135}
    121136#endif
  • src/work/klao/iter_map_test.cc

    r347 r361  
    1111typedef StdMap<int,int> BaseMap;
    1212typedef IterableMap<BaseMap, N> TestMap;
    13 
    14 
    15 void print(TestMap const& m) {
     13typedef IterableBoolMap<BaseMap> TestBoolMap;
     14
     15
     16template<typename TM>
     17void print(TM const& m, int N = 3) {
    1618  cout << "Size of the map: " << m.size() << endl;
    1719  for(int i=0; i<N; ++i) {
    1820    cout << "  Class " << i << ". (size=" << m.size(i) << "): " << flush;
    1921    cout << "    ";
    20     for(TestMap::iterator j = m.begin(i); j!=m.end(i); ++j) {
     22    for(typename TM::iterator j = m.begin(i); j!=m.end(i); ++j) {
    2123      cout << " " << *j;
    2224    }
     
    2931int main() {
    3032
    31   BaseMap base(344);
    32   TestMap test(base);
    33 
    34 
    35   print(test);
    36 
    37   cout << "Inserting 12 to class 2...\n";
    38   test.insert(12,2);
    39   print(test);
    40 
    41 
    42   cout << "Inserting 22 to class 2...\n";
    43   test.insert(22,2);
    44   print(test);
    45 
    46   cout << "Testing some map values:\n";
    47   cout << " 12: " << int(test[12]) << endl;
    48 
    49   cout << "Inserting 10 to class 0...\n";
    50   test.insert(10,0);
    51   print(test);
    52 
    53   cout << "Testing some map values:\n";
    54   cout << " 12: " << int(test[12]) << endl;
    55 
    56   cout << "Inserting 11 to class 1...\n";
    57   test.insert(11,1);
    58   print(test);
    59 
    60   cout << "Testing some map values:\n";
    61   cout << " 12: " << int(test[12]) << endl;
    62   cout << " 22: " << int(test[22]) << endl;
    63   cout << " 10: " << int(test[10]) << endl;
    64   cout << " 11: " << int(test[11]) << endl;
    65   cout << " 42: " << int(test[42]) << endl;
    66 
    67   cout << "Inserting 21 to class 1...\n";
    68   test.insert(21,1);
    69   print(test);
    70 
    71   cout << "Inserting 20 to class 1...\n";
    72   test.insert(20,0);
    73   print(test);
    74 
    75   cout << "Testing some map values:\n";
    76   cout << " 12: " << int(test[12]) << endl;
    77   cout << " 22: " << int(test[22]) << endl;
    78   cout << " 10: " << int(test[10]) << endl;
    79   cout << " 20: " << int(test[20]) << endl;
    80   cout << " 11: " << int(test[11]) << endl;
    81   cout << " 21: " << int(test[21]) << endl;
    82   cout << " 42: " << int(test[42]) << endl;
    83 
    84   cout << "Setting 20 to class 2...\n";
    85   test.set(20,2);
    86   print(test);
    87  
    88   cout << "Setting 10 to class 1...\n";
    89   test.set(10,1);
    90   print(test);
    91  
    92   cout << "Setting 11 to class 1...\n";
    93   test.set(11,1);
    94   print(test);
    95  
    96   cout << "Setting 12 to class 1...\n";
    97   test.set(12,1);
    98   print(test);
    99  
    100   cout << "Setting 21 to class 2...\n";
    101   test.set(21,2);
    102   print(test);
    103  
    104   cout << "Setting 22 to class 2...\n";
    105   test.set(22,2);
    106   print(test);
    107  
    108   cout << "Testing some map values:\n";
    109   cout << " 12: " << int(test[12]) << endl;
    110   cout << " 22: " << int(test[22]) << endl;
    111   cout << " 10: " << int(test[10]) << endl;
    112   cout << " 20: " << int(test[20]) << endl;
    113   cout << " 11: " << int(test[11]) << endl;
    114   cout << " 21: " << int(test[21]) << endl;
    115   cout << " 42: " << int(test[42]) << endl;
    116 
     33  {
     34    BaseMap base(344);
     35    TestMap test(base);
     36
     37
     38    print(test);
     39
     40    cout << "Inserting 12 to class 2...\n";
     41    test.insert(12,2);
     42    print(test);
     43
     44
     45    cout << "Inserting 22 to class 2...\n";
     46    test.insert(22,2);
     47    print(test);
     48
     49    cout << "Testing some map values:\n";
     50    cout << " 12: " << int(test[12]) << endl;
     51
     52    cout << "Inserting 10 to class 0...\n";
     53    test.insert(10,0);
     54    print(test);
     55
     56    cout << "Testing some map values:\n";
     57    cout << " 12: " << int(test[12]) << endl;
     58
     59    cout << "Inserting 11 to class 1...\n";
     60    test.insert(11,1);
     61    print(test);
     62
     63    cout << "Testing some map values:\n";
     64    cout << " 12: " << int(test[12]) << endl;
     65    cout << " 22: " << int(test[22]) << endl;
     66    cout << " 10: " << int(test[10]) << endl;
     67    cout << " 11: " << int(test[11]) << endl;
     68    cout << " 42: " << int(test[42]) << endl;
     69
     70    cout << "Inserting 21 to class 1...\n";
     71    test.insert(21,1);
     72    print(test);
     73
     74    cout << "Inserting 20 to class 1...\n";
     75    test.insert(20,0);
     76    print(test);
     77
     78    cout << "Testing some map values:\n";
     79    cout << " 12: " << int(test[12]) << endl;
     80    cout << " 22: " << int(test[22]) << endl;
     81    cout << " 10: " << int(test[10]) << endl;
     82    cout << " 20: " << int(test[20]) << endl;
     83    cout << " 11: " << int(test[11]) << endl;
     84    cout << " 21: " << int(test[21]) << endl;
     85    cout << " 42: " << int(test[42]) << endl;
     86
     87    cout << "Setting 20 to class 2...\n";
     88    test.set(20,2);
     89    print(test);
     90 
     91    cout << "Setting 10 to class 1...\n";
     92    test.set(10,1);
     93    print(test);
     94 
     95    cout << "Setting 11 to class 1...\n";
     96    test.set(11,1);
     97    print(test);
     98 
     99    cout << "Setting 12 to class 1...\n";
     100    test.set(12,1);
     101    print(test);
     102 
     103    cout << "Setting 21 to class 2...\n";
     104    test.set(21,2);
     105    print(test);
     106 
     107    cout << "Setting 22 to class 2...\n";
     108    test.set(22,2);
     109    print(test);
     110 
     111    cout << "Testing some map values:\n";
     112    cout << " 12: " << int(test[12]) << endl;
     113    cout << " 22: " << int(test[22]) << endl;
     114    cout << " 10: " << int(test[10]) << endl;
     115    cout << " 20: " << int(test[20]) << endl;
     116    cout << " 11: " << int(test[11]) << endl;
     117    cout << " 21: " << int(test[21]) << endl;
     118    cout << " 42: " << int(test[42]) << endl;
     119  }
     120
     121  {
     122    cout << "Testing the IterableBoolMap...\n";
     123
     124    BaseMap base(344);
     125    TestBoolMap test(base);
     126
     127
     128    print(test,2);
     129
     130    cout << "Inserting 12 to class true...\n";
     131    test.insert(12,true);
     132    print(test,2);
     133
     134
     135    cout << "Inserting 22 to class true...\n";
     136    test.insert(22,true);
     137    print(test,2);
     138
     139    cout << "Testing some map values:\n";
     140    cout << " 12: " << test[12] << endl;
     141
     142    cout << "Inserting 10 to class false...\n";
     143    test.insert(10,false);
     144    print(test,2);
     145
     146    cout << "Testing some map values:\n";
     147    cout << " 12: " << test[12] << endl;
     148
     149    cout << "Inserting 11 to class false...\n";
     150    test.insert(11,false);
     151    print(test,2);
     152
     153    cout << "Testing some map values:\n";
     154    cout << " 12: " << test[12] << endl;
     155    cout << " 22: " << test[22] << endl;
     156    cout << " 10: " << test[10] << endl;
     157    cout << " 11: " << test[11] << endl;
     158    cout << " 42: " << test[42] << endl;
     159
     160    cout << "Inserting 21 to class 1...\n";
     161    test.insert(21,1);
     162    print(test,2);
     163
     164    cout << "Inserting 20 to class 1...\n";
     165    test.insert(20,0);
     166    print(test,2);
     167
     168    cout << "Testing some map values:\n";
     169    cout << " 12: " << test[12] << endl;
     170    cout << " 22: " << test[22] << endl;
     171    cout << " 10: " << test[10] << endl;
     172    cout << " 20: " << test[20] << endl;
     173    cout << " 11: " << test[11] << endl;
     174    cout << " 21: " << test[21] << endl;
     175    cout << " 42: " << test[42] << endl;
     176
     177    cout << "Setting 20 to class 2...\n";
     178    test.set(20,2);
     179    print(test,2);
     180 
     181    cout << "Setting 10 to class 1...\n";
     182    test.set(10,1);
     183    print(test,2);
     184 
     185    cout << "Setting 11 to class 1...\n";
     186    test.set(11,1);
     187    print(test,2);
     188 
     189    cout << "Setting 12 to class 1...\n";
     190    test.set(12,1);
     191    print(test,2);
     192 
     193    cout << "Setting 21 to class 2...\n";
     194    test.set(21,2);
     195    print(test,2);
     196 
     197    cout << "Setting 22 to class 2...\n";
     198    test.set(22,2);
     199    print(test,2);
     200 
     201    cout << "Testing some map values:\n";
     202    cout << " 12: " << test[12] << endl;
     203    cout << " 22: " << test[22] << endl;
     204    cout << " 10: " << test[10] << endl;
     205    cout << " 20: " << test[20] << endl;
     206    cout << " 11: " << test[11] << endl;
     207    cout << " 21: " << test[21] << endl;
     208    cout << " 42: " << test[42] << endl;
     209
     210  }
    117211}
Note: See TracChangeset for help on using the changeset viewer.