Switched to using Boost.Graph for commodity pricing

10 files changed, 474 insertions, 604 deletions

diff --git a/src/commodity.cc b/src/commodity.cc
index 643d0d1e..c0ccae11 100644
--- a/src/commodity.cc
+++ b/src/commodity.cc
@@ -40,410 +40,68 @@ namespace ledger {
 
 bool commodity_t::decimal_comma_by_default = false;
 
-void commodity_t::history_t::add_price(commodity_t&      source,
-                                       const datetime_t& date,
-                                       const amount_t&   price,
-                                       const bool        reflexive)
+void commodity_t::add_price(const datetime_t& date, const amount_t& price,
+                            const bool reflexive)
 {
-  DEBUG("commodity.prices.add", "add_price to " << source
-        << (reflexive ? " (secondary)" : " (primary)")
-        << " : " << date << ", " << price);
+  if (! reflexive)
+    add_flags(COMMODITY_PRIMARY);
+  pool().commodity_price_history.add_price(*this, date, price);
 
-  history_map::iterator i = prices.find(date);
-  if (i != prices.end()) {
-    (*i).second = price;
-  } else {
-    std::pair<history_map::iterator, bool> result
-      = prices.insert(history_map::value_type(date, price));
-    assert(result.second);
-  }
-
-  if (reflexive) {
-    amount_t inverse = price.inverted();
-    inverse.set_commodity(const_cast<commodity_t&>(source));
-    price.commodity().add_price(date, inverse, false);
-  } else {
-    DEBUG("commodity.prices.add",
-          "marking commodity " << source.symbol() << " as primary");
-    source.add_flags(COMMODITY_PRIMARY);
-  }
-}
-
-bool commodity_t::history_t::remove_price(const datetime_t& date)
-{
-  DEBUG("commodity.prices.add", "remove_price: " << date);
-
-  history_map::size_type n = prices.erase(date);
-  if (n > 0)
-    return true;
-  return false;
-}
-
-void commodity_t::varied_history_t::
-  add_price(commodity_t&      source,
-            const datetime_t& date,
-            const amount_t&   price,
-            const bool        reflexive)
-{
-  optional<history_t&> hist = history(price.commodity());
-  if (! hist) {
-    std::pair<history_by_commodity_map::iterator, bool> result
-      = histories.insert(history_by_commodity_map::value_type
-                         (&price.commodity(), history_t()));
-    assert(result.second);
-
-    hist = (*result.first).second;
-  }
-  assert(hist);
-
-  hist->add_price(source, date, price, reflexive);
+  DEBUG("commodity.prices.find", "Price added, clearing price_map");
+  base->price_map.clear();    // a price was added, invalid the map
 }
 
-bool commodity_t::varied_history_t::remove_price(const datetime_t& date,
-                                                 commodity_t&      comm)
+void commodity_t::remove_price(const datetime_t& date, commodity_t& commodity)
 {
-  DEBUG("commodity.prices.add", "varied_remove_price: " << date << ", " << comm);
+  pool().commodity_price_history.remove_price(*this, commodity, date);
 
-  if (optional<history_t&> hist = history(comm))
-    return hist->remove_price(date);
-  return false;
+  DEBUG("commodity.prices.find", "Price removed, clearing price_map");
+  base->price_map.clear();  // a price was added, invalid the map
 }
 
 optional<price_point_t>
-commodity_t::history_t::find_price(const optional<datetime_t>& moment,
-                                   const optional<datetime_t>& oldest
-#if defined(DEBUG_ON)
-                                   , const int indent
-#endif
-                                   ) const
+commodity_t::find_price(const optional<commodity_t&>& target = none,
+                        const optional<datetime_t>&   moment = none,
+                        const optional<datetime_t>&   oldest = none) const
 {
-  price_point_t point;
-  bool          found = false;
-
-#if defined(DEBUG_ON)
-#define DEBUG_INDENT(cat, indent)               \
-  do {                                          \
-    if (SHOW_DEBUG(cat))                        \
-      for (int _i = 0; _i < indent; _i++)       \
-        ledger::_log_buffer << "  ";            \
-  } while (false)
-#else
-#define DEBUG_INDENT(cat, indent)
-#endif
-
-#if defined(DEBUG_ON)
+  pair = base_t::time_and_commodity_t
+    (base_t::optional_time_pair_t(moment, oldest),
+     commodity ? &(*commodity) : NULL);
   DEBUG_INDENT("commodity.prices.find", indent);
-  if (moment)
-    DEBUG("commodity.prices.find", "find price nearest before or on: " << *moment);
-  else
-    DEBUG("commodity.prices.find", "find any price");
+  DEBUG("commodity.prices.find", "looking for memoized args: "
+        << (moment ? format_datetime(*moment) : "NONE") << ", "
+        << (oldest ? format_datetime(*oldest) : "NONE") << ", "
+        << (commodity ? commodity->symbol() : "NONE"));
 
-  if (oldest) {
+  base_t::memoized_price_map::iterator i = base->price_map.find(*pair);
+  if (i != base->price_map.end()) {
     DEBUG_INDENT("commodity.prices.find", indent);
-    DEBUG("commodity.prices.find", "but no older than: " << *oldest);
-  }
-#endif
-
-  if (prices.size() == 0) {
-    DEBUG_INDENT("commodity.prices.find", indent);
-    DEBUG("commodity.prices.find", "there are no prices in this history");
-    return none;
+    DEBUG("commodity.prices.find", "found! returning: "
+          << ((*i).second ? (*i).second->price : amount_t(0L)));
+    return (*i).second;
   }
 
-  if (! moment) {
-    history_map::const_reverse_iterator r = prices.rbegin();
-    point.when  = (*r).first;
-    point.price = (*r).second;
-    found = true;
-
-    DEBUG_INDENT("commodity.prices.find", indent);
-    DEBUG("commodity.prices.find", "using most recent price");
-  } else {
-    history_map::const_iterator i = prices.upper_bound(*moment);
-    if (i == prices.end()) {
-      history_map::const_reverse_iterator r = prices.rbegin();
-      point.when  = (*r).first;
-      point.price = (*r).second;
-      found = true;
+  optional<price_point_t> point =
+    pool().commodity_price_history.find_price
+    (*this, commodity, moment ? *moment : epoch, oldest);
 
+  if (pair) {
+    if (base->price_map.size() > base_t::max_price_map_size) {
       DEBUG_INDENT("commodity.prices.find", indent);
-      DEBUG("commodity.prices.find", "using last price");
-    } else {
-      point.when = (*i).first;
-      if (*moment < point.when) {
-        if (i != prices.begin()) {
-          --i;
-          point.when  = (*i).first;
-          point.price = (*i).second;
-          found = true;
-        }
-      } else {
-        point.price = (*i).second;
-        found = true;
-      }
-
-      DEBUG_INDENT("commodity.prices.find", indent);
-      DEBUG("commodity.prices.find", "using found price");
-    }
-  }
-
-  if (! found) {
-    DEBUG_INDENT("commodity.prices.find", indent);
-    DEBUG("commodity.prices.find", "could not find a price");
-    return none;
-  }
-  else if (moment && point.when > *moment) {
-    DEBUG_INDENT("commodity.prices.find", indent);
-    DEBUG("commodity.prices.find", "price is too young ");
-    return none;
-  }
-  else if (oldest && point.when < *oldest) {
-    DEBUG_INDENT("commodity.prices.find", indent);
-    DEBUG("commodity.prices.find", "price is too old ");
-    return none;
-  }
-  else {
-    DEBUG_INDENT("commodity.prices.find", indent);
-    DEBUG("commodity.prices.find",
-          "returning price: " << point.when << ", " << point.price);
-    return point;
-  }
-}
-
-optional<price_point_t>
-commodity_t::varied_history_t::find_price(const commodity_t&            source,
-                                          const optional<commodity_t&>& commodity,
-                                          const optional<datetime_t>&   moment,
-                                          const optional<datetime_t>&   oldest
-#if defined(DEBUG_ON)
-                                          , const int indent
-#endif
-                                          ) const
-{
-  optional<price_point_t> point;
-  optional<datetime_t>    limit = oldest;
-
-#if defined(VERIFY_ON)
-  if (commodity) {
-    VERIFY(source != *commodity);
-    VERIFY(! commodity->has_annotation());
-    VERIFY(source.referent() != commodity->referent());
-  }
-#endif
-
-#if defined(DEBUG_ON)
-  DEBUG_INDENT("commodity.prices.find", indent);
-  DEBUG("commodity.prices.find", "varied_find_price for: " << source);
-
-  DEBUG_INDENT("commodity.prices.find", indent);
-  if (commodity)
-    DEBUG("commodity.prices.find", "looking for: commodity '" << *commodity << "'");
-  else
-    DEBUG("commodity.prices.find", "looking for: any commodity");
-
-  if (moment) {
-    DEBUG_INDENT("commodity.prices.find", indent);
-    DEBUG("commodity.prices.find", "time index: " << *moment);
-  }
-
-  if (oldest) {
-    DEBUG_INDENT("commodity.prices.find", indent);
-    DEBUG("commodity.prices.find", "only consider prices younger than: " << *oldest);
-  }
-#endif
-
-  // Either we couldn't find a history for the target commodity, or we
-  // couldn't find a price.  In either case, search all histories known
-  // to this commodity for a price which we can calculate in terms of
-  // the goal commodity.
-  price_point_t best;
-  bool          found = false;
-
-  foreach (const history_by_commodity_map::value_type& hist, histories) {
-    commodity_t& comm(*hist.first);
-    if (comm == source)
-      continue;
-
-    DEBUG_INDENT("commodity.prices.find", indent + 1);
-    DEBUG("commodity.prices.find",
-          "searching for price via commodity '" << comm << "'");
-
-    point = hist.second.find_price(moment, limit
-#if defined(DEBUG_ON)
-                                   , indent + 2
-#endif
-                                   );
-    assert(! point || point->price.commodity() == comm);
-
-    if (point) {
-      optional<price_point_t> xlat;
-
-      if (commodity && comm != *commodity) {
-        DEBUG_INDENT("commodity.prices.find", indent + 1);
-        DEBUG("commodity.prices.find", "looking for translation price");
-
-        xlat = comm.find_price(commodity, moment, limit, true
-#if defined(DEBUG_ON)
-                               , indent + 2
-#endif
-                               );
-        if (xlat) {
-          DEBUG_INDENT("commodity.prices.find", indent + 1);
-          DEBUG("commodity.prices.find", "found translated price "
-                << xlat->price << " from " << xlat->when);
-
-          point->price = xlat->price * point->price;
-          if (xlat->when < point->when) {
-            point->when = xlat->when;
-
-            DEBUG_INDENT("commodity.prices.find", indent + 1);
-            DEBUG("commodity.prices.find",
-                  "adjusting date of result back to " << point->when);
-          }
-        } else {
-          DEBUG_INDENT("commodity.prices.find", indent + 1);
-          DEBUG("commodity.prices.find", "saw no translated price there");
-          continue;
-        }
-      }
-
-      assert(! commodity || point->price.commodity() == *commodity);
-
-      DEBUG_INDENT("commodity.prices.find", indent + 1);
       DEBUG("commodity.prices.find",
-            "saw a price there: " << point->price << " from " << point->when);
-
-      if (! limit || point->when > *limit) {
-        limit = point->when;
-        best  = *point;
-        found = true;
+            "price map has grown too large, clearing it by half");
 
-        DEBUG_INDENT("commodity.prices.find", indent + 1);
-        DEBUG("commodity.prices.find",
-              "search limit adjusted to " << *limit);
-      }
-    } else {
-      DEBUG_INDENT("commodity.prices.find", indent + 1);
-      DEBUG("commodity.prices.find", "saw no price there");
+      for (std::size_t i = 0; i < base_t::max_price_map_size >> 1; i++)
+        base->price_map.erase(base->price_map.begin());
     }
-  }
 
-  if (found) {
     DEBUG_INDENT("commodity.prices.find", indent);
-    DEBUG("commodity.download",
-          "found price " << best.price << " from " << best.when);
-    return best;
-  }
-  return none;
-}
-
-optional<commodity_t::history_t&>
-commodity_t::varied_history_t::history(const optional<commodity_t&>& commodity)
-{
-  commodity_t * comm = NULL;
-  if (! commodity) {
-    if (histories.size() > 1)
-      return none;
-    comm = (*histories.begin()).first;
-  } else {
-    comm = &(*commodity);
-  }
-
-  history_by_commodity_map::iterator i = histories.find(comm);
-  if (i != histories.end())
-    return (*i).second;
-
-  return none;
-}
-
-optional<price_point_t>
-commodity_t::find_price(const optional<commodity_t&>& commodity,
-                        const optional<datetime_t>&   moment,
-                        const optional<datetime_t>&   oldest,
-                        const bool                    nested
-#if defined(DEBUG_ON)
-                        , const int indent
-#endif
-                        ) const
-{
-  if (! has_flags(COMMODITY_WALKED) && base->varied_history) {
-    optional<base_t::time_and_commodity_t> pair;
-#if defined(VERIFY_ON)
-    optional<price_point_t> checkpoint;
-    bool found = false;
-#endif
-
-    if (! nested) {
-      pair = base_t::time_and_commodity_t
-        (base_t::optional_time_pair_t(moment, oldest),
-         commodity ? &(*commodity) : NULL);
-      DEBUG_INDENT("commodity.prices.find", indent);
-      DEBUG("commodity.prices.find", "looking for memoized args: "
-            << (moment ? format_datetime(*moment) : "NONE") << ", "
-            << (oldest ? format_datetime(*oldest) : "NONE") << ", "
-            << (commodity ? commodity->symbol() : "NONE"));
-
-      base_t::memoized_price_map::iterator i = base->price_map.find(*pair);
-      if (i != base->price_map.end()) {
-        DEBUG_INDENT("commodity.prices.find", indent);
-        DEBUG("commodity.prices.find", "found! returning: "
-              << ((*i).second ? (*i).second->price : amount_t(0L)));
-#if defined(VERIFY_ON)
-        IF_VERIFY() {
-          found = true;
-          checkpoint = (*i).second;
-        } else
-#endif // defined(VERIFY_ON)
-        return (*i).second;
-      }
-    }
-
-    optional<price_point_t> point;
-
-    const_cast<commodity_t&>(*this).add_flags(COMMODITY_WALKED);
-    try {
-      DEBUG_INDENT("commodity.prices.find", indent);
-      DEBUG("commodity.prices.find", "manually finding price...");
-
-      point = base->varied_history->find_price(*this, commodity,
-                                               moment, oldest
-#if defined(DEBUG_ON)
-                                               , indent
-#endif
-                                               );
-    }
-    catch (...) {
-      const_cast<commodity_t&>(*this).drop_flags(COMMODITY_WALKED);
-      throw;
-    }
-    const_cast<commodity_t&>(*this).drop_flags(COMMODITY_WALKED);
-
-#if defined(VERIFY_ON)
-    if (DO_VERIFY() && found) {
-      VERIFY(checkpoint == point);
-      return checkpoint;
-    }
-#endif // defined(VERIFY_ON)
-
-    if (! nested && pair) {
-      if (base->price_map.size() > base_t::max_price_map_size) {
-        DEBUG_INDENT("commodity.prices.find", indent);
-        DEBUG("commodity.prices.find",
-              "price map has grown too large, clearing it by half");
-
-        for (std::size_t i = 0; i < base_t::max_price_map_size >> 1; i++)
-          base->price_map.erase(base->price_map.begin());
-      }
-
-      DEBUG_INDENT("commodity.prices.find", indent);
-      DEBUG("commodity.prices.find",
-            "remembered: " << (point ? point->price : amount_t(0L)));
-      base->price_map.insert
-        (base_t::memoized_price_map::value_type(*pair, point));
-    }
-    return point;
+    DEBUG("commodity.prices.find",
+          "remembered: " << (point ? point->price : amount_t(0L)));
+    base->price_map.insert
+      (base_t::memoized_price_map::value_type(*pair, point));
   }
-  return none;
+  return point;
 }
 
 optional<price_point_t>
@@ -767,28 +425,6 @@ void to_xml(std::ostream& out, const commodity_t& comm,
   if (commodity_details) {
     if (comm.has_annotation())
       to_xml(out, as_annotated_commodity(comm).details);
-
-    if (comm.varied_history()) {
-      push_xml y(out, "varied-history");
-
-      foreach (const commodity_t::history_by_commodity_map::value_type& pair,
-               comm.varied_history()->histories) {
-        {
-          push_xml z(out, "symbol");
-          out << y.guard(pair.first->symbol());
-        }
-        {
-          push_xml z(out, "history");
-
-          foreach (const commodity_t::history_map::value_type& inner_pair,
-                   pair.second.prices) {
-            push_xml w(out, "price-point");
-            to_xml(out, inner_pair.first);
-            to_xml(out, inner_pair.second);
-          }
-        }
-      }
-    }
   }
 }
 
diff --git a/src/commodity.h b/src/commodity.h
index 68f788e3..1505fe24 100644
--- a/src/commodity.h
+++ b/src/commodity.h
@@ -85,78 +85,6 @@ class commodity_t
   : public delegates_flags<uint_least16_t>,
     public equality_comparable1<commodity_t, noncopyable>
 {
-public:
-  typedef std::map<const datetime_t, amount_t> history_map;
-
-  struct history_t
-  {
-    history_map prices;
-
-    void add_price(commodity_t&      source,
-                   const datetime_t& date,
-                   const amount_t&   price,
-                   const bool        reflexive = true);
-    bool remove_price(const datetime_t& date);
-
-    optional<price_point_t>
-    find_price(const optional<datetime_t>&   moment = none,
-               const optional<datetime_t>&   oldest = none
-#if defined(DEBUG_ON)
-               , const int indent = 0
-#endif
-               ) const;
-
-#if defined(HAVE_BOOST_SERIALIZATION)
-  private:
-    /** Serialization. */
-
-    friend class boost::serialization::access;
-
-    template<class Archive>
-    void serialize(Archive& ar, const unsigned int /* version */) {
-      ar & prices;
-    }
-#endif // HAVE_BOOST_SERIALIZATION
-  };
-
-  typedef std::map<commodity_t *, history_t> history_by_commodity_map;
-
-  struct varied_history_t
-  {
-    history_by_commodity_map histories;
-
-    void add_price(commodity_t&      source,
-                   const datetime_t& date,
-                   const amount_t&   price,
-                   const bool        reflexive = true);
-    bool remove_price(const datetime_t& date, commodity_t& commodity);
-
-    optional<price_point_t>
-    find_price(const commodity_t&            source,
-               const optional<commodity_t&>& commodity = none,
-               const optional<datetime_t>&   moment    = none,
-               const optional<datetime_t>&   oldest    = none
-#if defined(DEBUG_ON)
-               , const int indent = 0
-#endif
-               ) const;
-
-    optional<history_t&>
-    history(const optional<commodity_t&>& commodity = none);
-
-#if defined(HAVE_BOOST_SERIALIZATION)
-  private:
-    /** Serialization. */
-
-    friend class boost::serialization::access;
-
-    template<class Archive>
-    void serialize(Archive& ar, const unsigned int /* version */) {
-      ar & histories;
-    }
-#endif // HAVE_BOOST_SERIALIZATION
-  };
-
 protected:
   friend class commodity_pool_t;
   friend class annotated_commodity_t;
@@ -182,7 +110,6 @@ protected:
     amount_t::precision_t      precision;
     optional<string>           name;
     optional<string>           note;
-    optional<varied_history_t> varied_history;
     optional<amount_t>         smaller;
     optional<amount_t>         larger;
 
@@ -228,7 +155,6 @@ protected:
       ar & precision;
       ar & name;
       ar & note;
-      ar & varied_history;
       ar & smaller;
       ar & larger;
     }
@@ -335,48 +261,14 @@ public:
     base->larger = arg;
   }
 
-  optional<varied_history_t&> varied_history() {
-    if (base->varied_history)
-      return *base->varied_history;
-    return none;
-  }
-  optional<const varied_history_t&> varied_history() const {
-    if (base->varied_history)
-      return *base->varied_history;
-    return none;
-  }
-
-  optional<history_t&> history(const optional<commodity_t&>& commodity);
-
-  // These methods provide a transparent pass-through to the underlying
-  // base->varied_history object.
-
   void add_price(const datetime_t& date, const amount_t& price,
-                 const bool reflexive = true) {
-    if (! base->varied_history)
-      base->varied_history = varied_history_t();
-    base->varied_history->add_price(*this, date, price, reflexive);
-    DEBUG("commodity.prices.find", "Price added, clearing price_map");
-    base->price_map.clear();    // a price was added, invalid the map
-  }
-  bool remove_price(const datetime_t& date, commodity_t& commodity) {
-    if (base->varied_history) {
-      base->varied_history->remove_price(date, commodity);
-      DEBUG("commodity.prices.find", "Price removed, clearing price_map");
-      base->price_map.clear();  // a price was added, invalid the map
-    }
-    return false;
-  }
+                 const bool reflexive = true);
+  void remove_price(const datetime_t& date, commodity_t& commodity);
 
   optional<price_point_t>
   find_price(const optional<commodity_t&>& commodity = none,
              const optional<datetime_t>&   moment    = none,
-             const optional<datetime_t>&   oldest    = none,
-             const bool                    nested    = false
-#if defined(DEBUG_ON)
-             , const int indent = 0
-#endif
-             ) const;
+             const optional<datetime_t>&   oldest    = none) const;
 
   optional<price_point_t>
   check_for_updated_price(const optional<price_point_t>& point,
diff --git a/src/filters.cc b/src/filters.cc
index 72ce9c32..0c6222d7 100644
--- a/src/filters.cc
+++ b/src/filters.cc
@@ -754,6 +754,8 @@ void changed_value_posts::output_intermediate_prices(post_t&       post,
     // fall through...
 
   case value_t::BALANCE: {
+#if 0
+    // jww (2012-03-04): TODO
     commodity_t::history_map all_prices;
 
     foreach (const balance_t::amounts_map::value_type& amt_comm,
@@ -797,6 +799,7 @@ void changed_value_posts::output_intermediate_prices(post_t&       post,
       output_revaluation(post, price.first);
       last_total = repriced_total;
     }
+#endif
     break;
   }
   default:
diff --git a/src/history.cc b/src/history.cc
new file mode 100644
index 00000000..44d19f5a
--- /dev/null
+++ b/src/history.cc
@@ -0,0 +1,196 @@
+/*
+ * Copyright (c) 2003-2012, John Wiegley.  All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in the
+ *   documentation and/or other materials provided with the distribution.
+ *
+ * - Neither the name of New Artisans LLC nor the names of its
+ *   contributors may be used to endorse or promote products derived from
+ *   this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <system.hh>
+
+#include "history.h"
+
+template <typename T>
+struct f_max : public std::binary_function<T, T, bool> {
+  T operator()(const T& x, const T& y) const {
+    return std::max(x, y);
+  }
+};
+
+namespace ledger {
+
+void commodity_history_t::add_commodity(const commodity_t& comm)
+{
+  const vertex_descriptor vert = add_vertex(&comm, price_graph);
+  put(indexmap, vert, reinterpret_cast<std::size_t>(&comm));
+}
+
+void commodity_history_t::add_price(const commodity_t& source,
+                                    const datetime_t&  when,
+                                    const amount_t&    price)
+{
+  vertex_descriptor sv =
+    vertex(reinterpret_cast<std::size_t>(&source), price_graph);
+  vertex_descriptor tv =
+    vertex(reinterpret_cast<std::size_t>(&price.commodity()), price_graph);
+
+  std::pair<edge_descriptor, bool> e1 = add_edge(sv, tv, 0, price_graph);
+  price_map_t& prices(get(ratiomap, e1.first));
+
+  std::pair<price_map_t::iterator, bool> result =
+    prices.insert(price_map_t::value_type(when, price));
+  if (! result.second) {
+    // There is already an entry for this moment, so update it
+    (*result.first).second = price;
+  }
+}
+
+void commodity_history_t::remove_price(const commodity_t& source,
+                                       const commodity_t& target,
+                                       const datetime_t&  date)
+{
+  vertex_descriptor sv =
+    vertex(reinterpret_cast<std::size_t>(&source), price_graph);
+  vertex_descriptor tv =
+    vertex(reinterpret_cast<std::size_t>(&target), price_graph);
+
+  std::pair<edge_descriptor, bool> e1 = add_edge(sv, tv, 0, price_graph);
+  price_map_t& prices(get(ratiomap, e1.first));
+
+  // jww (2012-03-04): If it fails, should we give a warning?
+  prices.erase(date);
+}
+
+optional<price_point_t>
+commodity_history_t::find_price(const commodity_t&            source,
+                                const datetime_t&             moment,
+                                const optional<datetime_t>&   oldest,
+                                const optional<commodity_t&>& target)
+{
+  vertex_descriptor sv =
+    vertex(reinterpret_cast<std::size_t>(&source), price_graph);
+  vertex_descriptor tv =
+    vertex(reinterpret_cast<std::size_t>(&*target), price_graph);
+
+  // Filter out edges which came into being after the reference time
+
+  FGraph fg(price_graph,
+            recent_edge_weight<EdgeWeightMap, PricePointMap, PriceRatioMap>
+            (get(edge_weight, price_graph), pricemap, ratiomap,
+             moment, oldest));
+  
+  std::vector<vertex_descriptor> predecessors(num_vertices(fg));
+  std::vector<long>              distances(num_vertices(fg));
+  
+  PredecessorMap predecessorMap(&predecessors[0]);
+  DistanceMap    distanceMap(&distances[0]);
+
+  dijkstra_shortest_paths(fg, /* start= */ sv,
+                          predecessor_map(predecessorMap)
+                          .distance_map(distanceMap)
+                          .distance_combine(f_max<long>()));
+
+  // Extract the shortest path and performance the calculations
+  datetime_t least_recent = moment;
+  amount_t price;
+
+  vertex_descriptor v = tv;
+  for (vertex_descriptor u = predecessorMap[v]; 
+       u != v;
+       v = u, u = predecessorMap[v])
+  {
+    std::pair<Graph::edge_descriptor, bool> edgePair = edge(u, v, fg);
+    Graph::edge_descriptor edge = edgePair.first;
+
+    const price_point_t& point(get(pricemap, edge));
+
+    if (price.is_null()) {
+      least_recent = point.when;
+      price        = point.price;
+    }
+    else if (point.when < least_recent)
+      least_recent = point.when;
+
+    // jww (2012-03-04): TODO
+    //price *= point.price;
+  }
+
+  return price_point_t(least_recent, price);
+}
+
+#if 0
+  print_vertices(fg, f_commmap);
+  print_edges(fg, f_commmap);
+  print_graph(fg, f_commmap);
+
+  graph_traits<FGraph>::vertex_iterator f_vi, f_vend;
+  for(tie(f_vi, f_vend) = vertices(fg); f_vi != f_vend; ++f_vi)
+    std::cerr << get(f_commmap, *f_vi) << " is in the filtered graph"
+              << std::endl;
+
+  for (tie(f_vi, f_vend) = vertices(fg); f_vi != f_vend; ++f_vi) {
+    std::cerr << "distance(" << get(f_commmap, *f_vi) << ") = "
+              << distanceMap[*f_vi] << ", ";
+    std::cerr << "parent(" << get(f_commmap, *f_vi) << ") = "
+              << get(f_commmap, predecessorMap[*f_vi])
+              << std::endl;
+  }
+
+  // Write shortest path
+  FCommMap f_commmap = get(vertex_comm, fg);
+
+  std::cerr << "Shortest path from CAD to EUR:" << std::endl;
+  for (PathType::reverse_iterator pathIterator = path.rbegin();
+       pathIterator != path.rend();
+       ++pathIterator)
+  {
+    std::cerr << get(f_commmap, source(*pathIterator, fg))
+              << " -> " << get(f_commmap, target(*pathIterator, fg))
+              << " = " << get(edge_weight, fg, *pathIterator)
+              << std::endl;
+  }
+  std::cerr << std::endl;
+
+  std::cerr << "Distance: " << distanceMap[vd4] << std::endl;
+#endif
+
+#if 0
+  #include <boost/graph/graphviz.hpp>
+
+  // Writing graph to file
+  {
+    std::ofstream f("test.dot");
+
+    dynamic_properties p;
+    p.property("label", get(edge_weight, g));
+    p.property("weight", get(edge_weight, g));
+    p.property("node_id", get(vertex_comm, g));
+    write_graphviz(f,g,p);
+    f.close();
+  }
+#endif
+
+} // namespace ledger
diff --git a/src/history.h b/src/history.h
new file mode 100644
index 00000000..486602dd
--- /dev/null
+++ b/src/history.h
@@ -0,0 +1,184 @@
+/*
+ * Copyright (c) 2003-2012, John Wiegley.  All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in the
+ *   documentation and/or other materials provided with the distribution.
+ *
+ * - Neither the name of New Artisans LLC nor the names of its
+ *   contributors may be used to endorse or promote products derived from
+ *   this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/**
+ * @addtogroup math
+ */
+
+/**
+ * @file   history.h
+ * @author John Wiegley
+ *
+ * @ingroup math
+ *
+ * @brief  Types for managing commodity historys
+ *
+ * Long.
+ */
+#ifndef _HISTORY_H
+#define _HISTORY_H
+
+#include "amount.h"
+#include "commodity.h"
+
+namespace boost {
+  enum edge_price_point_t { edge_price_point };
+  enum edge_price_ratio_t { edge_price_ratio };
+  BOOST_INSTALL_PROPERTY(edge, price_point);
+  BOOST_INSTALL_PROPERTY(edge, price_ratio);
+}
+
+namespace ledger {
+
+typedef std::map<datetime_t, amount_t> price_map_t;
+
+template <typename EdgeWeightMap,
+          typename PricePointMap,
+          typename PriceRatioMap>
+class recent_edge_weight
+{
+public:
+  EdgeWeightMap weight;
+  PricePointMap price_point;
+  PriceRatioMap ratios;
+
+  datetime_t           reftime;
+  optional<datetime_t> oldest;
+
+  recent_edge_weight() { }
+  recent_edge_weight(EdgeWeightMap _weight,
+                     PricePointMap _price_point,
+                     PriceRatioMap _ratios,
+                     datetime_t    _reftime,
+                     const optional<datetime_t>& _oldest = none)
+    : weight(_weight), price_point(_price_point), ratios(_ratios),
+      reftime(_reftime), oldest(_oldest) { }
+
+  template <typename Edge>
+  bool operator()(const Edge& e) const {
+    const price_map_t& prices(get(ratios, e));
+    price_map_t::const_iterator low = prices.upper_bound(reftime);
+    if (prices.empty() ||
+        (low != prices.end() && low == prices.begin())) {
+      return false;
+    } else {
+      if (low == prices.end())
+        --low;
+      assert(((*low).first <= reftime));
+
+      if (oldest && (*low).first <= *oldest)
+        return false;
+
+      long secs = (reftime - (*low).first).total_seconds();
+      assert(secs >= 0);
+
+      put(weight, e, secs);
+      put(price_point, e, price_point_t((*low).first, (*low).second));
+
+      return true;
+    }
+  }
+};
+
+class commodity_history_t : public noncopyable
+{
+public:
+  typedef adjacency_list
+    <setS,                      // Store all edges as a set
+     setS,                      // Store all vertices in a set
+     undirectedS,               // Relations are both ways
+
+    // All vertices are commodities
+    property<vertex_name_t, const commodity_t *,
+             property<vertex_index_t, std::size_t> >,
+
+    // All edges are weights computed as the absolute difference between
+    // the reference time of a search and a known price point.  A
+    // filtered_graph is used to select the recent price point to the
+    // reference time before performing the search.
+    property<edge_weight_t, long,
+             property<edge_price_ratio_t, price_map_t,
+                      property<edge_price_point_t, price_point_t> > >,
+
+    // Graph itself has a std::string name
+    property<graph_name_t, std::string>
+    > Graph;
+
+  Graph price_graph;
+
+  typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
+  typedef graph_traits<Graph>::edge_descriptor   edge_descriptor;
+
+  typedef property_map<Graph, vertex_index_t>::type IndexMap;
+  typedef property_map<Graph, vertex_name_t>::type  NameMap;
+
+  typedef iterator_property_map<vertex_descriptor*, IndexMap,
+                                vertex_descriptor,
+                                vertex_descriptor&> PredecessorMap;
+  typedef iterator_property_map<long*, IndexMap, long, long&> DistanceMap;
+
+  typedef property_map<Graph, edge_weight_t>::type      EdgeWeightMap;
+  typedef property_map<Graph, edge_price_point_t>::type PricePointMap;
+  typedef property_map<Graph, edge_price_ratio_t>::type PriceRatioMap;
+
+  IndexMap      indexmap;
+  PricePointMap pricemap;
+  PriceRatioMap ratiomap;
+
+  typedef filtered_graph<Graph, recent_edge_weight<EdgeWeightMap,
+                                                   PricePointMap,
+                                                   PriceRatioMap> > FGraph;
+  typedef property_map<FGraph, vertex_name_t>::type FNameMap;
+
+  commodity_history_t()
+    : indexmap(get(vertex_index, price_graph)),
+      pricemap(get(edge_price_point, price_graph)),
+      ratiomap(get(edge_price_ratio, price_graph)) {}
+
+  void add_commodity(const commodity_t& comm);
+
+  void add_price(const commodity_t& source,
+                 const datetime_t&  when,
+                 const amount_t&    price);
+  void remove_price(const commodity_t& source,
+                    const commodity_t& target,
+                    const datetime_t&  date);
+
+  optional<price_point_t>
+  find_price(const commodity_t&            source,
+             const datetime_t&             moment,
+             const optional<datetime_t>&   oldest    = none,
+             const optional<commodity_t&>& commodity = none);
+};
+
+} // namespace ledger
+
+#endif // _HISTORY_H
diff --git a/src/iterators.cc b/src/iterators.cc
index 72e0481c..b7ed011e 100644
--- a/src/iterators.cc
+++ b/src/iterators.cc
@@ -90,6 +90,8 @@ void posts_commodities_iterator::reset(journal_t& journal)
 
   std::map<string, xact_t *> xacts_by_commodity;
 
+#if 0
+  // jww (2012-03-04): TODO
   foreach (commodity_t * comm, commodities) {
     if (optional<commodity_t::varied_history_t&> history =
         comm->varied_history()) {
@@ -136,6 +138,7 @@ void posts_commodities_iterator::reset(journal_t& journal)
       }
     }
   }
+#endif
 
   xacts.reset(xact_temps.begin(), xact_temps.end());
 
diff --git a/src/pool.cc b/src/pool.cc
index ba408fc5..67cfe3d1 100644
--- a/src/pool.cc
+++ b/src/pool.cc
@@ -35,6 +35,7 @@
 #include "commodity.h"
 #include "annotate.h"
 #include "pool.h"
+#include "history.h"
 #include "quotes.h"
 
 namespace ledger {
@@ -74,15 +75,15 @@ commodity_t * commodity_pool_t::create(const string& symbol)
                                                      commodity.get()));
   assert(result.second);
 
+  commodity_price_history.add_commodity(*commodity.get());
+
   return commodity.release();
 }
 
 commodity_t * commodity_pool_t::find_or_create(const string& symbol)
 {
   DEBUG("pool.commodities", "Find-or-create commodity " << symbol);
-
-  commodity_t * commodity = find(symbol);
-  if (commodity)
+  if (commodity_t * commodity = find(symbol))
     return commodity;
   return create(symbol);
 }
@@ -222,6 +223,15 @@ commodity_t * commodity_pool_t::find_or_create(commodity_t&        comm,
   return create(comm, details, name);
 }
 
+optional<price_point_t>
+commodity_pool_t::find_price(const commodity_t&            source,
+                             const optional<commodity_t&>& commodity,
+                             const optional<datetime_t>&   moment,
+                             const optional<datetime_t>&   oldest) const
+{
+  return commodity_price_history.find_price(source, commodity, moment, oldest);
+}
+
 void commodity_pool_t::exchange(commodity_t&      commodity,
                                 const amount_t&   per_unit_cost,
                                 const datetime_t& moment)
@@ -382,76 +392,4 @@ commodity_pool_t::parse_price_expression(const std::string&          str,
   return NULL;
 }
 
-void commodity_pool_t::print_pricemap(std::ostream&               out,
-                                      const keep_details_t&       keep,
-                                      const optional<datetime_t>& moment)
-{
-  typedef std::map<commodity_t *, commodity_t *> comm_map_t;
-
-  comm_map_t comm_map;
-
-  foreach (const commodities_map::value_type& comm_pair, commodities) {
-    commodity_t * comm(&comm_pair.second->strip_annotations(keep));
-    comm_map.insert(comm_map_t::value_type(comm, NULL));
-  }
-
-  out << "digraph commodities {\n";
-
-  foreach (const comm_map_t::value_type& comm_pair, comm_map) {
-    commodity_t * comm(comm_pair.first);
-    if (comm->has_flags(COMMODITY_BUILTIN))
-      continue;
-
-    out << "    ";
-    if (commodity_t::symbol_needs_quotes(comm->symbol()))
-      out << comm->symbol() << ";\n";
-    else
-      out << "\"" << comm->symbol() << "\";\n";
-
-    if (! comm->has_flags(COMMODITY_NOMARKET) &&
-        (! commodity_pool_t::current_pool->default_commodity ||
-         comm != commodity_pool_t::current_pool->default_commodity)) {
-      if (optional<commodity_t::varied_history_t&> vhist =
-          comm->varied_history()) {
-        foreach (const commodity_t::history_by_commodity_map::value_type& pair,
-                 vhist->histories) {
-          datetime_t most_recent;
-          amount_t   most_recent_amt;
-          foreach (const commodity_t::history_map::value_type& inner_pair,
-                   pair.second.prices) {
-            if ((most_recent.is_not_a_date_time() ||
-                 inner_pair.first > most_recent) &&
-                (! moment || inner_pair.first <= moment)) {
-              most_recent     = inner_pair.first;
-              most_recent_amt = inner_pair.second;
-            }
-          }
-
-          if (! most_recent.is_not_a_date_time()) {
-            out << "    ";
-            if (commodity_t::symbol_needs_quotes(comm->symbol()))
-              out << comm->symbol();
-            else
-              out << "\"" << comm->symbol() << "\"";
-
-            out << " -> ";
-
-            if (commodity_t::symbol_needs_quotes(pair.first->symbol()))
-              out << pair.first->symbol();
-            else
-              out << "\"" << pair.first->symbol() << "\"";
-
-            out << " [label=\""
-                << most_recent_amt.number() << "\\n"
-                << format_date(most_recent.date(), FMT_WRITTEN)
-                << "\" fontcolor=\"#008e28\"];\n";
-          }
-        }
-      }
-    }
-  }
-
-  out << "}\n";
-}
-
 } // namespace ledger
diff --git a/src/pool.h b/src/pool.h
index 87b315f9..709f5c71 100644
--- a/src/pool.h
+++ b/src/pool.h
@@ -46,6 +46,8 @@
 #ifndef _POOL_H
 #define _POOL_H
 
+#include "history.h"
+
 namespace ledger {
 
 struct cost_breakdown_t
@@ -66,15 +68,16 @@ public:
    */
   typedef std::map<string, commodity_t *> commodities_map;
 
-  commodities_map commodities;
-  commodity_t *   null_commodity;
-  commodity_t *   default_commodity;
+  commodities_map     commodities;
+  commodity_history_t commodity_price_history;
+  commodity_t *       null_commodity;
+  commodity_t *       default_commodity;
 
-  bool            keep_base;        // --base
+  bool                keep_base;        // --base
 
-  optional<path>  price_db;         // --price-db=
-  long            quote_leeway;     // --leeway=
-  bool            get_quotes;       // --download
+  optional<path>      price_db;         // --price-db=
+  long                quote_leeway;     // --leeway=
+  bool                get_quotes;       // --download
 
   static shared_ptr<commodity_pool_t> current_pool;
 
@@ -131,12 +134,6 @@ public:
                          const bool                  add_prices = true,
                          const optional<datetime_t>& moment     = none);
 
-  // Output the commodity price map for a given date as a DOT file
-
-  void print_pricemap(std::ostream&               out,
-                      const keep_details_t&       keep,
-                      const optional<datetime_t>& moment = none);
-
 #if defined(HAVE_BOOST_SERIALIZATION)
 private:
   /** Serialization. */
diff --git a/src/report.cc b/src/report.cc
index 647df3d2..689028d0 100644
--- a/src/report.cc
+++ b/src/report.cc
@@ -878,11 +878,12 @@ value_t report_t::echo_command(call_scope_t& args)
 value_t report_t::pricemap_command(call_scope_t& args)
 {
   std::ostream& out(output_stream);
-
+#if 0
+  // jww (2012-03-04): TODO
   commodity_pool_t::current_pool->print_pricemap
     (out, what_to_keep(), args.has<string>(0) ?
      optional<datetime_t>(datetime_t(parse_date(args.get<string>(0)))) : none);
-
+#endif
   return true;
 }
 
@@ -913,6 +914,11 @@ option_t<report_t> * report_t::lookup_option(const char * p)
   case 'G':
     OPT_CH(gain);
     break;
+#if 0
+  case 'H':
+    OPT_CH(historical);
+    break;
+#endif
   case 'I':
     OPT_CH(price);
     break;
diff --git a/src/system.hh.in b/src/system.hh.in
index 3aa60f71..8f684486 100644
--- a/src/system.hh.in
+++ b/src/system.hh.in
@@ -138,37 +138,52 @@ typedef std::ostream::pos_type ostream_pos_type;
 #include <boost/bind.hpp>
 #include <boost/cast.hpp>
 #include <boost/current_function.hpp>
+
 #include <boost/date_time/posix_time/posix_time.hpp>
 #include <boost/date_time/posix_time/posix_time_io.hpp>
 #include <boost/date_time/gregorian/gregorian_io.hpp>
+
 #include <boost/filesystem/convenience.hpp>
 #include <boost/filesystem/exception.hpp>
 #include <boost/filesystem/fstream.hpp>
 #include <boost/filesystem/operations.hpp>
 #include <boost/filesystem/path.hpp>
+
 #if !(defined(__GXX_EXPERIMENTAL_CXX0X__) && __GXX_EXPERIMENTAL_CXX0X__)
 #include <boost/foreach.hpp>
 #endif
 #include <boost/function.hpp>
+
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/filtered_graph.hpp>
+#include <boost/graph/dijkstra_shortest_paths.hpp>
+#include <boost/graph/graph_utility.hpp>
+
 #include <boost/intrusive_ptr.hpp>
+
 #include <boost/iostreams/stream.hpp>
 #include <boost/iostreams/write.hpp>
 #define BOOST_IOSTREAMS_USE_DEPRECATED 1
 #include <boost/iostreams/device/file_descriptor.hpp>
+
 #include <boost/iterator/iterator_facade.hpp>
 #include <boost/iterator/transform_iterator.hpp>
+
 #include <boost/lexical_cast.hpp>
 #include <boost/operators.hpp>
 #include <boost/optional.hpp>
 #include <boost/ptr_container/ptr_list.hpp>
+
 #include <boost/random/mersenne_twister.hpp>
 #include <boost/random/uniform_int.hpp>
 #include <boost/random/uniform_real.hpp>
 #include <boost/random/variate_generator.hpp>
+
 #if defined(HAVE_BOOST_REGEX_UNICODE)
 #include <boost/regex/icu.hpp>
 #else
 #include <boost/regex.hpp>
+
 #endif // HAVE_BOOST_REGEX_UNICODE
 #include <boost/variant.hpp>
 #include <boost/version.hpp>