From fc6d6774bb3d125be622bd84edb7e2ed4f77655c Mon Sep 17 00:00:00 2001 From: Chris Dams Date: Wed, 13 Sep 2006 16:46:47 +0000 Subject: [PATCH] Made unarchiving algorithms order N instead of order N^2. --- ginac/archive.cpp | 41 ++++++++++++++++++++++++++++++++++------- ginac/archive.h | 31 +++++++++++++++++++++---------- ginac/container.h | 12 +++++++----- ginac/expairseq.cpp | 14 +++++++++----- ginac/matrix.cpp | 11 ++++++----- ginac/pseries.cpp | 15 ++++++++++----- 6 files changed, 87 insertions(+), 37 deletions(-) diff --git a/ginac/archive.cpp b/ginac/archive.cpp index 7e5e648d..79798b61 100644 --- a/ginac/archive.cpp +++ b/ginac/archive.cpp @@ -352,6 +352,27 @@ bool archive_node::has_same_ex_as(const archive_node &other) const return e.bp == other.e.bp; } +archive_node::archive_node_cit + archive_node::find_first(const std::string &name) const +{ + archive_atom name_atom = a.atomize(name); + for (archive_node_cit i=props.begin(); i!=props.end(); ++i) + if (i->name == name_atom) + return i; + return props.end();; +} + +archive_node::archive_node_cit + archive_node::find_last(const std::string &name) const +{ + archive_atom name_atom = a.atomize(name); + for (archive_node_cit i=props.end(); i!=props.begin();) { + --i; + if (i->name == name_atom) + return i; + } + return props.end(); +} void archive_node::add_bool(const std::string &name, bool value) { @@ -379,7 +400,7 @@ void archive_node::add_ex(const std::string &name, const ex &value) bool archive_node::find_bool(const std::string &name, bool &ret, unsigned index) const { archive_atom name_atom = a.atomize(name); - std::vector::const_iterator i = props.begin(), iend = props.end(); + archive_node_cit i = props.begin(), iend = props.end(); unsigned found_index = 0; while (i != iend) { if (i->type == PTYPE_BOOL && i->name == name_atom) { @@ -397,7 +418,7 @@ bool archive_node::find_bool(const std::string &name, bool &ret, unsigned index) bool archive_node::find_unsigned(const std::string &name, unsigned &ret, unsigned index) const { archive_atom name_atom = a.atomize(name); - std::vector::const_iterator i = props.begin(), iend = props.end(); + archive_node_cit i = props.begin(), iend = props.end(); unsigned found_index = 0; while (i != iend) { if (i->type == PTYPE_UNSIGNED && i->name == name_atom) { @@ -415,7 +436,7 @@ bool archive_node::find_unsigned(const std::string &name, unsigned &ret, unsigne bool archive_node::find_string(const std::string &name, std::string &ret, unsigned index) const { archive_atom name_atom = a.atomize(name); - std::vector::const_iterator i = props.begin(), iend = props.end(); + archive_node_cit i = props.begin(), iend = props.end(); unsigned found_index = 0; while (i != iend) { if (i->type == PTYPE_STRING && i->name == name_atom) { @@ -430,10 +451,16 @@ bool archive_node::find_string(const std::string &name, std::string &ret, unsign return false; } +void archive_node::find_ex_by_loc(archive_node_cit loc, ex &ret, lst &sym_lst) + const +{ + ret = a.get_node(loc->value).unarchive(sym_lst); +} + bool archive_node::find_ex(const std::string &name, ex &ret, lst &sym_lst, unsigned index) const { archive_atom name_atom = a.atomize(name); - std::vector::const_iterator i = props.begin(), iend = props.end(); + archive_node_cit i = props.begin(), iend = props.end(); unsigned found_index = 0; while (i != iend) { if (i->type == PTYPE_NODE && i->name == name_atom) { @@ -451,7 +478,7 @@ bool archive_node::find_ex(const std::string &name, ex &ret, lst &sym_lst, unsig const archive_node &archive_node::find_ex_node(const std::string &name, unsigned index) const { archive_atom name_atom = a.atomize(name); - std::vector::const_iterator i = props.begin(), iend = props.end(); + archive_node_cit i = props.begin(), iend = props.end(); unsigned found_index = 0; while (i != iend) { if (i->type == PTYPE_NODE && i->name == name_atom) { @@ -468,7 +495,7 @@ const archive_node &archive_node::find_ex_node(const std::string &name, unsigned void archive_node::get_properties(propinfovector &v) const { v.clear(); - std::vector::const_iterator i = props.begin(), iend = props.end(); + archive_node_cit i = props.begin(), iend = props.end(); while (i != iend) { property_type type = i->type; std::string name = a.unatomize(i->name); @@ -583,7 +610,7 @@ void archive_node::printraw(std::ostream &os) const os << "\n"; // Dump properties - std::vector::const_iterator i = props.begin(), iend = props.end(); + archive_node_cit i = props.begin(), iend = props.end(); while (i != iend) { os << " "; switch (i->type) { diff --git a/ginac/archive.h b/ginac/archive.h index af7bbc27..8e98c820 100644 --- a/ginac/archive.h +++ b/ginac/archive.h @@ -72,6 +72,17 @@ public: }; typedef std::vector propinfovector; + /** Archived property (data type, name and associated data) */ + struct property { + property() {} + property(archive_atom n, property_type t, unsigned v) : type(t), name(n), value(v) {} + + property_type type; /**< Data type of property. */ + archive_atom name; /**< Name of property. */ + unsigned value; /**< Stored value. */ + }; + typedef std::vector::const_iterator archive_node_cit; + archive_node() : a(*dummy_ar_creator()), has_expression(false) {} // hack for cint which always requires a default constructor archive_node(archive &ar) : a(ar), has_expression(false) {} archive_node(archive &ar, const ex &expr); @@ -102,10 +113,20 @@ public: * @return "true" if property was found, "false" otherwise */ bool find_string(const std::string &name, std::string &ret, unsigned index = 0) const; + /** Find the location in the vector of properties of the first/last + * property with a given name. */ + archive_node_cit find_first(const std::string &name) const; + archive_node_cit find_last(const std::string &name) const; + /** Retrieve property of type "ex" from node. * @return "true" if property was found, "false" otherwise */ bool find_ex(const std::string &name, ex &ret, lst &sym_lst, unsigned index = 0) const; + /** Retrieve property of type "ex" from the node if it is known + * that this node in fact contains such a property at the given + * location. This is much more efficient than the preceding function. */ + void find_ex_by_loc(archive_node_cit loc, ex &ret, lst &sym_lst) const; + /** Retrieve property of type "ex" from node, returning the node of * the sub-expression. */ const archive_node &find_ex_node(const std::string &name, unsigned index = 0) const; @@ -124,16 +145,6 @@ public: private: static archive* dummy_ar_creator(); - /** Archived property (data type, name and associated data) */ - struct property { - property() {} - property(archive_atom n, property_type t, unsigned v) : type(t), name(n), value(v) {} - - property_type type; /**< Data type of property. */ - archive_atom name; /**< Name of property. */ - unsigned value; /**< Stored value. */ - }; - /** Reference to the archive to which this node belongs. */ archive &a; diff --git a/ginac/container.h b/ginac/container.h index b173e35d..7a1bfaba 100644 --- a/ginac/container.h +++ b/ginac/container.h @@ -487,12 +487,14 @@ container::container(const archive_node &n, lst &sym_lst) : inherited(n, sym_ { setflag(get_default_flags()); - for (unsigned int i=0; true; i++) { + archive_node::archive_node_cit first = n.find_first("seq"); + archive_node::archive_node_cit last = n.find_last("seq"); + ++last; + reserve(this->seq, last - first); + for (archive_node::archive_node_cit i=first; iseq.push_back(e); - else - break; + n.find_ex_by_loc(i, e, sym_lst); + this->seq.push_back(e); } } diff --git a/ginac/expairseq.cpp b/ginac/expairseq.cpp index 2d427a92..3fb2d991 100644 --- a/ginac/expairseq.cpp +++ b/ginac/expairseq.cpp @@ -145,13 +145,17 @@ expairseq::expairseq(const archive_node &n, lst &sym_lst) : inherited(n, sym_lst , hashtabsize(0) #endif { - for (unsigned int i=0; true; i++) { + archive_node::archive_node_cit first = n.find_first("rest"); + archive_node::archive_node_cit last = n.find_last("coeff"); + ++last; + seq.reserve((last-first)/2); + + for (archive_node::archive_node_cit loc = first; loc < last;) { ex rest; ex coeff; - if (n.find_ex("rest", rest, sym_lst, i) && n.find_ex("coeff", coeff, sym_lst, i)) - seq.push_back(expair(rest, coeff)); - else - break; + n.find_ex_by_loc(loc++, rest, sym_lst); + n.find_ex_by_loc(loc++, coeff, sym_lst); + seq.push_back(expair(rest, coeff)); } n.find_ex("overall_coeff", overall_coeff, sym_lst); diff --git a/ginac/matrix.cpp b/ginac/matrix.cpp index bc58245f..20c80d15 100644 --- a/ginac/matrix.cpp +++ b/ginac/matrix.cpp @@ -113,12 +113,13 @@ matrix::matrix(const archive_node &n, lst &sym_lst) : inherited(n, sym_lst) if (!(n.find_unsigned("row", row)) || !(n.find_unsigned("col", col))) throw (std::runtime_error("unknown matrix dimensions in archive")); m.reserve(row * col); - for (unsigned int i=0; true; i++) { + archive_node::archive_node_cit first = n.find_first("m"); + archive_node::archive_node_cit last = n.find_last("m"); + ++last; + for (archive_node::archive_node_cit i=first; i