summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJohn Wiegley <johnw@newartisans.com>2012-03-04 03:35:06 -0600
committerJohn Wiegley <johnw@newartisans.com>2012-03-05 05:03:52 -0600
commit48ab6ad1dbab100bb8abd87029a0ca5bc501a3db (patch)
tree294112ea9df8ecac90c98c08327ce13fe5592682
parent58d912827d2c6bd90c063537378baffff014c0f2 (diff)
downloadfork-ledger-48ab6ad1dbab100bb8abd87029a0ca5bc501a3db.tar.gz
fork-ledger-48ab6ad1dbab100bb8abd87029a0ca5bc501a3db.tar.bz2
fork-ledger-48ab6ad1dbab100bb8abd87029a0ca5bc501a3db.zip
Switched to using Boost.Graph for commodity pricing
-rw-r--r--src/commodity.cc442
-rw-r--r--src/commodity.h114
-rw-r--r--src/filters.cc3
-rw-r--r--src/history.cc196
-rw-r--r--src/history.h184
-rw-r--r--src/iterators.cc3
-rw-r--r--src/pool.cc88
-rw-r--r--src/pool.h23
-rw-r--r--src/report.cc10
-rw-r--r--src/system.hh.in15
-rw-r--r--tools/Makefile.am2
11 files changed, 476 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>
diff --git a/tools/Makefile.am b/tools/Makefile.am
index 09021b1f..671db294 100644
--- a/tools/Makefile.am
+++ b/tools/Makefile.am
@@ -30,6 +30,7 @@ libledger_util_la_LDFLAGS = -release $(LIBVERSION)
libledger_math_la_SOURCES = \
src/balance.cc \
src/quotes.cc \
+ src/history.cc \
src/pool.cc \
src/annotate.cc \
src/commodity.cc \
@@ -104,6 +105,7 @@ pkginclude_HEADERS = \
src/amount.h \
src/commodity.h \
src/annotate.h \
+ src/history.h \
src/pool.h \
src/quotes.h \
src/balance.h \