Made unarchiving algorithms order N instead of order N^2.

diff --git a/ginac/archive.cpp b/ginac/archive.cpp
index 7e5e648dc677dc07d73a1ba6a4fa71455467eadd..79798b617ffb795c1e094341f9fd53f3c63027a6 100644 (file)
--- 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;
 }
 
        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)
 {
 
 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);
 bool archive_node::find_bool(const std::string &name, bool &ret, unsigned index) const
 {
        archive_atom name_atom = a.atomize(name);

-       std::vector<property>::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) {
        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);
 bool archive_node::find_unsigned(const std::string &name, unsigned &ret, unsigned index) const
 {
        archive_atom name_atom = a.atomize(name);

-       std::vector<property>::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) {
        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);
 bool archive_node::find_string(const std::string &name, std::string &ret, unsigned index) const
 {
        archive_atom name_atom = a.atomize(name);

-       std::vector<property>::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) {
        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;
 }
 
        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);
 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<property>::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) {
        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);
 const archive_node &archive_node::find_ex_node(const std::string &name, unsigned index) const
 {
        archive_atom name_atom = a.atomize(name);

-       std::vector<property>::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) {
        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();
 void archive_node::get_properties(propinfovector &v) const
 {
        v.clear();

-       std::vector<property>::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);
        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
                os << "\n";
 
        // Dump properties

-       std::vector<property>::const_iterator i = props.begin(), iend = props.end();
+       archive_node_cit i = props.begin(), iend = props.end();

        while (i != iend) {
                os << "  ";
                switch (i->type) {
        while (i != iend) {
                os << "  ";
                switch (i->type) {

diff --git a/ginac/archive.h b/ginac/archive.h
index af7bbc27721666d1811566b4731c236025354da7..8e98c82070ec799d9011fb08b301bfaef7dff14e 100644 (file)
--- a/ginac/archive.h
+++ b/ginac/archive.h
@@ -72,6 +72,17 @@ public:
        };
        typedef std::vector<property_info> propinfovector;
 
        };
        typedef std::vector<property_info> 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<property>::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);
        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;
 
         *  @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 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;
        /** 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();
 
 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;
 
        /** Reference to the archive to which this node belongs. */
        archive &a;
 

diff --git a/ginac/container.h b/ginac/container.h
index b173e35d476ca1fa3f4f9c01f8801e6f8a3bd654..7a1bfaba176466e53f351a5872bb8f3d19946324 100644 (file)
--- a/ginac/container.h
+++ b/ginac/container.h
@@ -487,12 +487,14 @@ container<C>::container(const archive_node &n, lst &sym_lst) : inherited(n, sym_
 {
        setflag(get_default_flags());
 
 {
        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; i<last; ++i) {

                ex e;
                ex e;

-               if (n.find_ex("seq", e, sym_lst, i))
-                       this->seq.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 2d427a92dc1628a767af0b8a2179a546a5fd2285..3fb2d991286a97ecbdb454ef4eaacbe85befffb8 100644 (file)
--- 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
 {
        , 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;
                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);
        }
 
        n.find_ex("overall_coeff", overall_coeff, sym_lst);

diff --git a/ginac/matrix.cpp b/ginac/matrix.cpp
index bc58245f8f0e7cc8cf33134ce30b80e2cddd8590..20c80d15a1f198e140bdc99819fe6fa2f7babc37 100644 (file)
--- 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);
        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<last; ++i) {

                ex e;
                ex e;

-               if (n.find_ex("m", e, sym_lst, i))
-                       m.push_back(e);
-               else
-                       break;
+               n.find_ex_by_loc(i, e, sym_lst);
+               m.push_back(e);

        }
 }
 
        }
 }
 

diff --git a/ginac/pseries.cpp b/ginac/pseries.cpp
index 14488ba71c222b81e033379d51f61be66e94b062..bd8e4803a0feb57e9778ceda4cfe4d8e3cd3c56a 100644 (file)
--- a/ginac/pseries.cpp
+++ b/ginac/pseries.cpp
@@ -82,14 +82,19 @@ pseries::pseries(const ex &rel_, const epvector &ops_) : basic(&pseries::tinfo_s
 
 pseries::pseries(const archive_node &n, lst &sym_lst) : inherited(n, sym_lst)
 {
 
 pseries::pseries(const archive_node &n, lst &sym_lst) : inherited(n, sym_lst)
 {

-       for (unsigned int i=0; true; ++i) {
+       archive_node::archive_node_cit first = n.find_first("coeff");
+       archive_node::archive_node_cit last = n.find_last("power");
+       ++last;
+       seq.reserve((last-first)/2);
+
+       for (archive_node::archive_node_cit loc = first; loc < last;) {

                ex rest;
                ex coeff;
                ex rest;
                ex coeff;

-               if (n.find_ex("coeff", rest, sym_lst, i) && n.find_ex("power", 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("var", var, sym_lst);
        n.find_ex("point", point, sym_lst);
 }
        n.find_ex("var", var, sym_lst);
        n.find_ex("point", point, sym_lst);
 }