From 48ab6ad1dbab100bb8abd87029a0ca5bc501a3db Mon Sep 17 00:00:00 2001 From: John Wiegley Date: Sun, 4 Mar 2012 03:35:06 -0600 Subject: Switched to using Boost.Graph for commodity pricing --- src/commodity.cc | 442 +++++-------------------------------------------------- src/commodity.h | 114 +------------- src/filters.cc | 3 + src/history.cc | 196 ++++++++++++++++++++++++ src/history.h | 184 +++++++++++++++++++++++ src/iterators.cc | 3 + src/pool.cc | 88 ++--------- src/pool.h | 23 ++- src/report.cc | 10 +- src/system.hh.in | 15 ++ 10 files changed, 474 insertions(+), 604 deletions(-) create mode 100644 src/history.cc create mode 100644 src/history.h (limited to 'src') 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 result - = prices.insert(history_map::value_type(date, price)); - assert(result.second); - } - - if (reflexive) { - amount_t inverse = price.inverted(); - inverse.set_commodity(const_cast(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 hist = history(price.commodity()); - if (! hist) { - std::pair 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 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 -commodity_t::history_t::find_price(const optional& moment, - const optional& oldest -#if defined(DEBUG_ON) - , const int indent -#endif - ) const +commodity_t::find_price(const optional& target = none, + const optional& moment = none, + const optional& 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 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 -commodity_t::varied_history_t::find_price(const commodity_t& source, - const optional& commodity, - const optional& moment, - const optional& oldest -#if defined(DEBUG_ON) - , const int indent -#endif - ) const -{ - optional point; - optional 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 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::varied_history_t::history(const optional& 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 -commodity_t::find_price(const optional& commodity, - const optional& moment, - const optional& oldest, - const bool nested -#if defined(DEBUG_ON) - , const int indent -#endif - ) const -{ - if (! has_flags(COMMODITY_WALKED) && base->varied_history) { - optional pair; -#if defined(VERIFY_ON) - optional 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 point; - - const_cast(*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(*this).drop_flags(COMMODITY_WALKED); - throw; - } - const_cast(*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 @@ -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, public equality_comparable1 { -public: - typedef std::map 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 - find_price(const optional& moment = none, - const optional& 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 - void serialize(Archive& ar, const unsigned int /* version */) { - ar & prices; - } -#endif // HAVE_BOOST_SERIALIZATION - }; - - typedef std::map 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 - find_price(const commodity_t& source, - const optional& commodity = none, - const optional& moment = none, - const optional& oldest = none -#if defined(DEBUG_ON) - , const int indent = 0 -#endif - ) const; - - optional - history(const optional& commodity = none); - -#if defined(HAVE_BOOST_SERIALIZATION) - private: - /** Serialization. */ - - friend class boost::serialization::access; - - template - 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 name; optional note; - optional varied_history; optional smaller; optional 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() { - if (base->varied_history) - return *base->varied_history; - return none; - } - optional varied_history() const { - if (base->varied_history) - return *base->varied_history; - return none; - } - - optional history(const optional& 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 find_price(const optional& commodity = none, const optional& moment = none, - const optional& oldest = none, - const bool nested = false -#if defined(DEBUG_ON) - , const int indent = 0 -#endif - ) const; + const optional& oldest = none) const; optional check_for_updated_price(const optional& 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 + +#include "history.h" + +template +struct f_max : public std::binary_function { + 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(&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(&source), price_graph); + vertex_descriptor tv = + vertex(reinterpret_cast(&price.commodity()), price_graph); + + std::pair e1 = add_edge(sv, tv, 0, price_graph); + price_map_t& prices(get(ratiomap, e1.first)); + + std::pair 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(&source), price_graph); + vertex_descriptor tv = + vertex(reinterpret_cast(&target), price_graph); + + std::pair 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 +commodity_history_t::find_price(const commodity_t& source, + const datetime_t& moment, + const optional& oldest, + const optional& target) +{ + vertex_descriptor sv = + vertex(reinterpret_cast(&source), price_graph); + vertex_descriptor tv = + vertex(reinterpret_cast(&*target), price_graph); + + // Filter out edges which came into being after the reference time + + FGraph fg(price_graph, + recent_edge_weight + (get(edge_weight, price_graph), pricemap, ratiomap, + moment, oldest)); + + std::vector predecessors(num_vertices(fg)); + std::vector 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())); + + // 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 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::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 + + // 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 price_map_t; + +template +class recent_edge_weight +{ +public: + EdgeWeightMap weight; + PricePointMap price_point; + PriceRatioMap ratios; + + datetime_t reftime; + optional oldest; + + recent_edge_weight() { } + recent_edge_weight(EdgeWeightMap _weight, + PricePointMap _price_point, + PriceRatioMap _ratios, + datetime_t _reftime, + const optional& _oldest = none) + : weight(_weight), price_point(_price_point), ratios(_ratios), + reftime(_reftime), oldest(_oldest) { } + + template + 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 + >, + + // 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 > >, + + // Graph itself has a std::string name + property + > Graph; + + Graph price_graph; + + typedef graph_traits::vertex_descriptor vertex_descriptor; + typedef graph_traits::edge_descriptor edge_descriptor; + + typedef property_map::type IndexMap; + typedef property_map::type NameMap; + + typedef iterator_property_map PredecessorMap; + typedef iterator_property_map DistanceMap; + + typedef property_map::type EdgeWeightMap; + typedef property_map::type PricePointMap; + typedef property_map::type PriceRatioMap; + + IndexMap indexmap; + PricePointMap pricemap; + PriceRatioMap ratiomap; + + typedef filtered_graph > FGraph; + typedef property_map::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 + find_price(const commodity_t& source, + const datetime_t& moment, + const optional& oldest = none, + const optional& 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 xacts_by_commodity; +#if 0 + // jww (2012-03-04): TODO foreach (commodity_t * comm, commodities) { if (optional 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 +commodity_pool_t::find_price(const commodity_t& source, + const optional& commodity, + const optional& moment, + const optional& 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& moment) -{ - typedef std::map 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 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 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 price_db; // --price-db= - long quote_leeway; // --leeway= - bool get_quotes; // --download + optional price_db; // --price-db= + long quote_leeway; // --leeway= + bool get_quotes; // --download static shared_ptr current_pool; @@ -131,12 +134,6 @@ public: const bool add_prices = true, const optional& 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& 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(0) ? optional(datetime_t(parse_date(args.get(0)))) : none); - +#endif return true; } @@ -913,6 +914,11 @@ option_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 #include #include + #include #include #include + #include #include #include #include #include + #if !(defined(__GXX_EXPERIMENTAL_CXX0X__) && __GXX_EXPERIMENTAL_CXX0X__) #include #endif #include + +#include +#include +#include +#include + #include + #include #include #define BOOST_IOSTREAMS_USE_DEPRECATED 1 #include + #include #include + #include #include #include #include + #include #include #include #include + #if defined(HAVE_BOOST_REGEX_UNICODE) #include #else #include + #endif // HAVE_BOOST_REGEX_UNICODE #include #include -- cgit v1.2.3