COIN-OR::LEMON - Graph Library

Changeset 82:bce6c8f93d10 in lemon-1.0


Ignore:
Timestamp:
03/15/08 23:39:41 (11 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Add basic logical maps and doc improvements

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/maps.h

    r81 r82  
    8787  /// Constant map.
    8888
    89   /// This is a \ref concepts::ReadMap "readable" map which assigns a
    90   /// specified value to each key.
     89  /// This \ref concepts::ReadMap "readable map" assigns a specified
     90  /// value to each key.
    9191  ///
    9292  /// In other aspects it is equivalent to \ref NullMap.
     
    150150  /// Constant map with inlined constant value.
    151151
    152   /// This is a \ref concepts::ReadMap "readable" map which assigns a
    153   /// specified value to each key.
     152  /// This \ref concepts::ReadMap "readable map" assigns a specified
     153  /// value to each key.
    154154  ///
    155155  /// In other aspects it is equivalent to \ref NullMap.
     
    190190
    191191
    192   /// \brief Identity map.
    193   ///
    194   /// This map gives back the given key as value without any
    195   /// modification.
     192  /// Identity map.
     193
     194  /// This \ref concepts::ReadMap "read-only map" gives back the given
     195  /// key as value without any modification.
    196196  ///
    197197  /// \sa ConstMap
     
    204204
    205205    /// Gives back the given value without any modification.
    206     const T& operator[](const T& t) const {
    207       return t;
     206    Value operator[](const Key &k) const {
     207      return k;
    208208    }
    209209  };
     
    465465  /// Composition of two maps
    466466
    467   /// This \ref concepts::ReadMap "read only map" returns the
     467  /// This \ref concepts::ReadMap "read-only map" returns the
    468468  /// composition of two given maps. That is to say, if \c m1 is of
    469469  /// type \c M1 and \c m2 is of \c M2, then for
     
    517517  /// Combination of two maps using an STL (binary) functor.
    518518
    519   /// This \ref concepts::ReadMap "read only map" takes two maps and a
     519  /// This \ref concepts::ReadMap "read-only map" takes two maps and a
    520520  /// binary functor and returns the combination of the two given maps
    521521  /// using the functor.
     
    596596  /// Converts an STL style (unary) functor to a map
    597597
    598   /// This \ref concepts::ReadMap "read only map" returns the value
     598  /// This \ref concepts::ReadMap "read-only map" returns the value
    599599  /// of a given functor. Actually, it just wraps the functor and
    600600  /// provides the \c Key and \c Value typedefs.
     
    776776  /// Sum of two maps
    777777
    778   /// This \ref concepts::ReadMap "read only map" returns the sum
     778  /// This \ref concepts::ReadMap "read-only map" returns the sum
    779779  /// of the values of the two given maps.
    780780  /// Its \c Key and \c Value types are inherited from \c M1.
     
    825825  /// Difference of two maps
    826826
    827   /// This \ref concepts::ReadMap "read only map" returns the difference
     827  /// This \ref concepts::ReadMap "read-only map" returns the difference
    828828  /// of the values of the two given maps.
    829829  /// Its \c Key and \c Value types are inherited from \c M1.
     
    873873  /// Product of two maps
    874874
    875   /// This \ref concepts::ReadMap "read only map" returns the product
     875  /// This \ref concepts::ReadMap "read-only map" returns the product
    876876  /// of the values of the two given maps.
    877877  /// Its \c Key and \c Value types are inherited from \c M1.
     
    922922  /// Quotient of two maps
    923923
    924   /// This \ref concepts::ReadMap "read only map" returns the quotient
     924  /// This \ref concepts::ReadMap "read-only map" returns the quotient
    925925  /// of the values of the two given maps.
    926926  /// Its \c Key and \c Value types are inherited from \c M1.
     
    970970  /// Shifts a map with a constant.
    971971
    972   /// This \ref concepts::ReadMap "read only map" returns the sum of
     972  /// This \ref concepts::ReadMap "read-only map" returns the sum of
    973973  /// the given map and a constant value (i.e. it shifts the map with
    974974  /// the constant). Its \c Key and \c Value are inherited from \c M.
     
    10711071  /// Scales a map with a constant.
    10721072
    1073   /// This \ref concepts::ReadMap "read only map" returns the value of
     1073  /// This \ref concepts::ReadMap "read-only map" returns the value of
    10741074  /// the given map multiplied from the left side with a constant value.
    10751075  /// Its \c Key and \c Value are inherited from \c M.
     
    11731173  /// Negative of a map
    11741174
    1175   /// This \ref concepts::ReadMap "read only map" returns the negative
     1175  /// This \ref concepts::ReadMap "read-only map" returns the negative
    11761176  /// of the values of the given map (using the unary \c - operator).
    11771177  /// Its \c Key and \c Value are inherited from \c M.
     
    12711271  /// Absolute value of a map
    12721272
    1273   /// This \ref concepts::ReadMap "read only map" returns the absolute
     1273  /// This \ref concepts::ReadMap "read-only map" returns the absolute
    12741274  /// value of the values of the given map.
    12751275  /// Its \c Key and \c Value are inherited from \c M.
     
    13121312  }
    13131313
     1314  /// @}
     1315 
     1316  // Logical maps and map adaptors:
     1317
     1318  /// \addtogroup maps
     1319  /// @{
     1320
     1321  /// Constant \c true map.
     1322
     1323  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
     1324  /// each key.
     1325  ///
     1326  /// Note that
     1327  /// \code
     1328  ///   TrueMap<K> tm;
     1329  /// \endcode
     1330  /// is equivalent to
     1331  /// \code
     1332  ///   ConstMap<K,bool> tm(true);
     1333  /// \endcode
     1334  ///
     1335  /// \sa FalseMap
     1336  /// \sa ConstMap
     1337  template <typename K>
     1338  class TrueMap : public MapBase<K, bool> {
     1339  public:
     1340    typedef MapBase<K, bool> Parent;
     1341    typedef typename Parent::Key Key;
     1342    typedef typename Parent::Value Value;
     1343
     1344    /// Gives back \c true.
     1345    Value operator[](const Key&) const { return true; }
     1346  };
     1347
     1348  /// Returns a \ref TrueMap class
     1349
     1350  /// This function just returns a \ref TrueMap class.
     1351  /// \relates TrueMap
     1352  template<typename K>
     1353  inline TrueMap<K> trueMap() {
     1354    return TrueMap<K>();
     1355  }
     1356
     1357
     1358  /// Constant \c false map.
     1359
     1360  /// This \ref concepts::ReadMap "read-only map" assigns \c false to
     1361  /// each key.
     1362  ///
     1363  /// Note that
     1364  /// \code
     1365  ///   FalseMap<K> fm;
     1366  /// \endcode
     1367  /// is equivalent to
     1368  /// \code
     1369  ///   ConstMap<K,bool> fm(false);
     1370  /// \endcode
     1371  ///
     1372  /// \sa TrueMap
     1373  /// \sa ConstMap
     1374  template <typename K>
     1375  class FalseMap : public MapBase<K, bool> {
     1376  public:
     1377    typedef MapBase<K, bool> Parent;
     1378    typedef typename Parent::Key Key;
     1379    typedef typename Parent::Value Value;
     1380
     1381    /// Gives back \c false.
     1382    Value operator[](const Key&) const { return false; }
     1383  };
     1384
     1385  /// Returns a \ref FalseMap class
     1386
     1387  /// This function just returns a \ref FalseMap class.
     1388  /// \relates FalseMap
     1389  template<typename K>
     1390  inline FalseMap<K> falseMap() {
     1391    return FalseMap<K>();
     1392  }
     1393
     1394  /// @}
     1395
     1396  /// \addtogroup map_adaptors
     1397  /// @{
     1398
     1399  /// Logical 'and' of two maps
     1400
     1401  /// This \ref concepts::ReadMap "read-only map" returns the logical
     1402  /// 'and' of the values of the two given maps.
     1403  /// Its \c Key type is inherited from \c M1 and its \c Value type is
     1404  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
     1405  ///
     1406  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
     1407  /// \code
     1408  ///   AndMap<M1,M2> am(m1,m2);
     1409  /// \endcode
     1410  /// <tt>am[x]</tt> will be equal to <tt>m1[x]&&m2[x]</tt>.
     1411  ///
     1412  /// The simplest way of using this map is through the andMap()
     1413  /// function.
     1414  ///
     1415  /// \sa OrMap
     1416  /// \sa NotMap, NotWriteMap
     1417  template<typename M1, typename M2>
     1418  class AndMap : public MapBase<typename M1::Key, bool> {
     1419    const M1 &_m1;
     1420    const M2 &_m2;
     1421  public:
     1422    typedef MapBase<typename M1::Key, bool> Parent;
     1423    typedef typename Parent::Key Key;
     1424    typedef typename Parent::Value Value;
     1425
     1426    /// Constructor
     1427    AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
     1428    /// \e
     1429    Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; }
     1430  };
     1431
     1432  /// Returns an \ref AndMap class
     1433
     1434  /// This function just returns an \ref AndMap class.
     1435  ///
     1436  /// For example, if \c m1 and \c m2 are both maps with \c bool values,
     1437  /// then <tt>andMap(m1,m2)[x]</tt> will be equal to
     1438  /// <tt>m1[x]&&m2[x]</tt>.
     1439  ///
     1440  /// \relates AndMap
     1441  template<typename M1, typename M2>
     1442  inline AndMap<M1, M2> andMap(const M1 &m1, const M2 &m2) {
     1443    return AndMap<M1, M2>(m1,m2);
     1444  }
     1445
     1446
     1447  /// Logical 'or' of two maps
     1448
     1449  /// This \ref concepts::ReadMap "read-only map" returns the logical
     1450  /// 'or' of the values of the two given maps.
     1451  /// Its \c Key type is inherited from \c M1 and its \c Value type is
     1452  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
     1453  ///
     1454  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
     1455  /// \code
     1456  ///   OrMap<M1,M2> om(m1,m2);
     1457  /// \endcode
     1458  /// <tt>om[x]</tt> will be equal to <tt>m1[x]||m2[x]</tt>.
     1459  ///
     1460  /// The simplest way of using this map is through the orMap()
     1461  /// function.
     1462  ///
     1463  /// \sa AndMap
     1464  /// \sa NotMap, NotWriteMap
     1465  template<typename M1, typename M2>
     1466  class OrMap : public MapBase<typename M1::Key, bool> {
     1467    const M1 &_m1;
     1468    const M2 &_m2;
     1469  public:
     1470    typedef MapBase<typename M1::Key, bool> Parent;
     1471    typedef typename Parent::Key Key;
     1472    typedef typename Parent::Value Value;
     1473
     1474    /// Constructor
     1475    OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
     1476    /// \e
     1477    Value operator[](const Key &k) const { return _m1[k]||_m2[k]; }
     1478  };
     1479
     1480  /// Returns an \ref OrMap class
     1481
     1482  /// This function just returns an \ref OrMap class.
     1483  ///
     1484  /// For example, if \c m1 and \c m2 are both maps with \c bool values,
     1485  /// then <tt>orMap(m1,m2)[x]</tt> will be equal to
     1486  /// <tt>m1[x]||m2[x]</tt>.
     1487  ///
     1488  /// \relates OrMap
     1489  template<typename M1, typename M2>
     1490  inline OrMap<M1, M2> orMap(const M1 &m1, const M2 &m2) {
     1491    return OrMap<M1, M2>(m1,m2);
     1492  }
     1493
    13141494
    13151495  /// Logical 'not' of a map
    13161496
    1317   /// This \ref concepts::ReadMap "read only map" returns the logical
     1497  /// This \ref concepts::ReadMap "read-only map" returns the logical
    13181498  /// negation of the values of the given map.
    13191499  /// Its \c Key is inherited from \c M and its \c Value is \c bool.
     
    13921572  }
    13931573
     1574
     1575  /// Combination of two maps using the \c == operator
     1576
     1577  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
     1578  /// the keys for which the corresponding values of the two maps are
     1579  /// equal.
     1580  /// Its \c Key type is inherited from \c M1 and its \c Value type is
     1581  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
     1582  ///
     1583  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
     1584  /// \code
     1585  ///   EqualMap<M1,M2> em(m1,m2);
     1586  /// \endcode
     1587  /// <tt>em[x]</tt> will be equal to <tt>m1[x]==m2[x]</tt>.
     1588  ///
     1589  /// The simplest way of using this map is through the equalMap()
     1590  /// function.
     1591  ///
     1592  /// \sa LessMap
     1593  template<typename M1, typename M2>
     1594  class EqualMap : public MapBase<typename M1::Key, bool> {
     1595    const M1 &_m1;
     1596    const M2 &_m2;
     1597  public:
     1598    typedef MapBase<typename M1::Key, bool> Parent;
     1599    typedef typename Parent::Key Key;
     1600    typedef typename Parent::Value Value;
     1601
     1602    /// Constructor
     1603    EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
     1604    /// \e
     1605    Value operator[](const Key &k) const { return _m1[k]==_m2[k]; }
     1606  };
     1607
     1608  /// Returns an \ref EqualMap class
     1609
     1610  /// This function just returns an \ref EqualMap class.
     1611  ///
     1612  /// For example, if \c m1 and \c m2 are maps with keys and values of
     1613  /// the same type, then <tt>equalMap(m1,m2)[x]</tt> will be equal to
     1614  /// <tt>m1[x]==m2[x]</tt>.
     1615  ///
     1616  /// \relates EqualMap
     1617  template<typename M1, typename M2>
     1618  inline EqualMap<M1, M2> equalMap(const M1 &m1, const M2 &m2) {
     1619    return EqualMap<M1, M2>(m1,m2);
     1620  }
     1621
     1622
     1623  /// Combination of two maps using the \c < operator
     1624
     1625  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
     1626  /// the keys for which the corresponding value of the first map is
     1627  /// less then the value of the second map.
     1628  /// Its \c Key type is inherited from \c M1 and its \c Value type is
     1629  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
     1630  ///
     1631  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
     1632  /// \code
     1633  ///   LessMap<M1,M2> lm(m1,m2);
     1634  /// \endcode
     1635  /// <tt>lm[x]</tt> will be equal to <tt>m1[x]<m2[x]</tt>.
     1636  ///
     1637  /// The simplest way of using this map is through the lessMap()
     1638  /// function.
     1639  ///
     1640  /// \sa EqualMap
     1641  template<typename M1, typename M2>
     1642  class LessMap : public MapBase<typename M1::Key, bool> {
     1643    const M1 &_m1;
     1644    const M2 &_m2;
     1645  public:
     1646    typedef MapBase<typename M1::Key, bool> Parent;
     1647    typedef typename Parent::Key Key;
     1648    typedef typename Parent::Value Value;
     1649
     1650    /// Constructor
     1651    LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
     1652    /// \e
     1653    Value operator[](const Key &k) const { return _m1[k]<_m2[k]; }
     1654  };
     1655
     1656  /// Returns an \ref LessMap class
     1657
     1658  /// This function just returns an \ref LessMap class.
     1659  ///
     1660  /// For example, if \c m1 and \c m2 are maps with keys and values of
     1661  /// the same type, then <tt>lessMap(m1,m2)[x]</tt> will be equal to
     1662  /// <tt>m1[x]<m2[x]</tt>.
     1663  ///
     1664  /// \relates LessMap
     1665  template<typename M1, typename M2>
     1666  inline LessMap<M1, M2> lessMap(const M1 &m1, const M2 &m2) {
     1667    return LessMap<M1, M2>(m1,m2);
     1668  }
     1669
    13941670  /// @}
    13951671}
  • test/maps_test.cc

    r80 r82  
    7979    map1 = constMap<A>(B());
    8080    map1.setAll(B());
    81    
     81
    8282    checkConcept<ReadWriteMap<A,int>, ConstMap<A,int> >();
    8383    check(constMap<A>(10)[A()] == 10, "Something is wrong with ConstMap");
     
    9696    IdentityMap<A> map2 = map1;
    9797    map1 = identityMap<A>();
    98    
     98
    9999    checkConcept<ReadMap<double,double>, IdentityMap<double> >();
    100100    check(identityMap<double>()[1.0] == 1.0 && identityMap<double>()[3.14] == 3.14,
     
    152152    CompMap map1(DoubleMap(),ReadMap<B,A>());
    153153    CompMap map2 = composeMap(DoubleMap(), ReadMap<B,A>());
    154    
     154
    155155    SparseMap<double, bool> m1(false); m1[3.14] = true;
    156156    RangeMap<double> m2(2); m2[0] = 3.0; m2[1] = 3.14;
     
    198198  {
    199199    checkConcept<DoubleWriteMap, ForkMap<DoubleWriteMap, DoubleWriteMap> >();
    200    
     200
    201201    typedef RangeMap<double> RM;
    202202    typedef SparseMap<int, double> SM;
     
    211211          "Something is wrong with ForkMap");
    212212  }
    213  
     213
    214214  // Arithmetic maps:
    215215  // - AddMap, SubMap, MulMap, DivMap
     
    221221    checkConcept<DoubleMap, MulMap<DoubleMap,DoubleMap> >();
    222222    checkConcept<DoubleMap, DivMap<DoubleMap,DoubleMap> >();
    223    
     223
    224224    ConstMap<int, double> c1(1.0), c2(3.14);
    225225    IdentityMap<int> im;
     
    229229    check(mulMap(id,c2)[0] == 0    && mulMap(id,c2)[2]  == 6.28, "Something is wrong with MulMap");
    230230    check(divMap(c2,id)[1] == 3.14 && divMap(c2,id)[2]  == 1.57, "Something is wrong with DivMap");
    231    
     231
    232232    checkConcept<DoubleMap, ShiftMap<DoubleMap> >();
    233233    checkConcept<DoubleWriteMap, ShiftWriteMap<DoubleWriteMap> >();
     
    253253          "Something is wrong with AbsMap");
    254254  }
    255  
    256   // Logical maps
    257   {
     255
     256  // Logical maps:
     257  // - TrueMap, FalseMap
     258  // - AndMap, OrMap
     259  // - NotMap, NotWriteMap
     260  // - EqualMap, LessMap
     261  {
     262    checkConcept<BoolMap, TrueMap<A> >();
     263    checkConcept<BoolMap, FalseMap<A> >();
     264    checkConcept<BoolMap, AndMap<BoolMap,BoolMap> >();
     265    checkConcept<BoolMap, OrMap<BoolMap,BoolMap> >();
    258266    checkConcept<BoolMap, NotMap<BoolMap> >();
    259267    checkConcept<BoolWriteMap, NotWriteMap<BoolWriteMap> >();
    260    
     268    checkConcept<BoolMap, EqualMap<DoubleMap,DoubleMap> >();
     269    checkConcept<BoolMap, LessMap<DoubleMap,DoubleMap> >();
     270
     271    TrueMap<int> tm;
     272    FalseMap<int> fm;
    261273    RangeMap<bool> rm(2);
    262274    rm[0] = true; rm[1] = false;
    263     check(!(notMap(rm)[0]) && notMap(rm)[1], "Something is wrong with NotMap");
    264     check(!(notWriteMap(rm)[0]) && notWriteMap(rm)[1], "Something is wrong with NotWriteMap");
     275    check(andMap(tm,rm)[0] && !andMap(tm,rm)[1] && !andMap(fm,rm)[0] && !andMap(fm,rm)[1],
     276          "Something is wrong with AndMap");
     277    check(orMap(tm,rm)[0] && orMap(tm,rm)[1] && orMap(fm,rm)[0] && !orMap(fm,rm)[1],
     278          "Something is wrong with OrMap");
     279    check(!notMap(rm)[0] && notMap(rm)[1], "Something is wrong with NotMap");
     280    check(!notWriteMap(rm)[0] && notWriteMap(rm)[1], "Something is wrong with NotWriteMap");
     281
     282    ConstMap<int, double> cm(2.0);
     283    IdentityMap<int> im;
     284    ConvertMap<IdentityMap<int>, double> id(im);
     285    check(lessMap(id,cm)[1] && !lessMap(id,cm)[2] && !lessMap(id,cm)[3],
     286          "Something is wrong with LessMap");
     287    check(!equalMap(id,cm)[1] && equalMap(id,cm)[2] && !equalMap(id,cm)[3],
     288          "Something is wrong with EqualMap");
    265289  }
    266290
Note: See TracChangeset for help on using the changeset viewer.