use binary search for starmath token

Change-Id: I187a5471f0e733007e3a56d8bb4972ee71f7cf17
Reviewed-on: https://gerrit.libreoffice.org/63882
Tested-by: Jenkins
Reviewed-by: Noel Grandin <noel.grandin@collabora.co.uk>

1 files changed, 33 insertions, 17 deletions

diff --git a/starmath/source/parse.cxx b/starmath/source/parse.cxx
index 3cd64af729db..937ef8d5b9cf 100644
--- a/starmath/source/parse.cxx
+++ b/starmath/source/parse.cxx
@@ -68,11 +68,7 @@ SmToken::SmToken(SmTokenType eTokenType,
 
 static const SmTokenTableEntry aTokenTable[] =
 {
-    { "Im" , TIM, MS_IM, TG::Standalone, 5 },
-    { "Re" , TRE, MS_RE, TG::Standalone, 5 },
     { "abs", TABS, '\0', TG::UnOper, 13 },
-    { "arcosh", TACOSH, '\0', TG::Function, 5 },
-    { "arcoth", TACOTH, '\0', TG::Function, 5 },
     { "acute", TACUTE, MS_ACUTE, TG::Attribute, 5 },
     { "aleph" , TALEPH, MS_ALEPH, TG::Standalone, 5 },
     { "alignb", TALIGNC, '\0', TG::Align, 0},
@@ -86,6 +82,8 @@ static const SmTokenTableEntry aTokenTable[] =
     { "aqua", TAQUA, '\0', TG::Color, 0},
     { "arccos", TACOS, '\0', TG::Function, 5},
     { "arccot", TACOT, '\0', TG::Function, 5},
+    { "arcosh", TACOSH, '\0', TG::Function, 5 },
+    { "arcoth", TACOTH, '\0', TG::Function, 5 },
     { "arcsin", TASIN, '\0', TG::Function, 5},
     { "arctan", TATAN, '\0', TG::Function, 5},
     { "arsinh", TASINH, '\0', TG::Function, 5},
@@ -131,7 +129,6 @@ static const SmTokenTableEntry aTokenTable[] =
     { "emptyset" , TEMPTYSET, MS_EMPTYSET, TG::Standalone, 5},
     { "equiv", TEQUIV, MS_EQUIV, TG::Relation, 0},
     { "exists", TEXISTS, MS_EXISTS, TG::Standalone, 5},
-    { "notexists", TNOTEXISTS, MS_NOTEXISTS, TG::Standalone, 5},
     { "exp", TEXP, '\0', TG::Function, 5},
     { "fact", TFACT, MS_FACT, TG::UnOper, 5},
     { "fixed", TFIXED, '\0', TG::Font, 0},
@@ -151,6 +148,7 @@ static const SmTokenTableEntry aTokenTable[] =
     { "hbar" , THBAR, MS_HBAR, TG::Standalone, 5},
     { "iiint", TIIINT, MS_IIINT, TG::Oper, 5},
     { "iint", TIINT, MS_IINT, TG::Oper, 5},
+    { "im" , TIM, MS_IM, TG::Standalone, 5 },
     { "in", TIN, MS_IN, TG::Relation, 0},
     { "infinity" , TINFINITY, MS_INFINITY, TG::Standalone, 5},
     { "infty" , TINFINITY, MS_INFINITY, TG::Standalone, 5},
@@ -200,11 +198,14 @@ static const SmTokenTableEntry aTokenTable[] =
     { "nitalic", TNITALIC, '\0', TG::FontAttr, 5},
     { "none", TNONE, '\0', TG::LBrace | TG::RBrace, 0},
     { "nospace", TNOSPACE, '\0', TG::Standalone, 5},
+    { "notexists", TNOTEXISTS, MS_NOTEXISTS, TG::Standalone, 5},
     { "notin", TNOTIN, MS_NOTIN, TG::Relation, 0},
+    { "nprec", TNOTPRECEDES, MS_NOTPRECEDES, TG::Relation, 0 },
     { "nroot", TNROOT, MS_SQRT, TG::UnOper, 5},
     { "nsubset", TNSUBSET, MS_NSUBSET, TG::Relation, 0 },
-    { "nsupset", TNSUPSET, MS_NSUPSET, TG::Relation, 0 },
     { "nsubseteq", TNSUBSETEQ, MS_NSUBSETEQ, TG::Relation, 0 },
+    { "nsucc", TNOTSUCCEEDS, MS_NOTSUCCEEDS, TG::Relation, 0 },
+    { "nsupset", TNSUPSET, MS_NSUPSET, TG::Relation, 0 },
     { "nsupseteq", TNSUPSETEQ, MS_NSUPSETEQ, TG::Relation, 0 },
     { "odivide", TODIVIDE, MS_ODIVIDE, TG::Product, 0},
     { "odot", TODOT, MS_ODOT, TG::Product, 0},
@@ -227,7 +228,6 @@ static const SmTokenTableEntry aTokenTable[] =
     { "prec", TPRECEDES, MS_PRECEDES, TG::Relation, 0 },
     { "preccurlyeq", TPRECEDESEQUAL, MS_PRECEDESEQUAL, TG::Relation, 0 },
     { "precsim", TPRECEDESEQUIV, MS_PRECEDESEQUIV, TG::Relation, 0 },
-    { "nprec", TNOTPRECEDES, MS_NOTPRECEDES, TG::Relation, 0 },
     { "prod", TPROD, MS_PROD, TG::Oper, 5},
     { "prop", TPROP, MS_PROP, TG::Relation, 0},
     { "purple", TPURPLE, '\0', TG::Color, 0},
@@ -236,6 +236,7 @@ static const SmTokenTableEntry aTokenTable[] =
     { "rceil", TRCEIL, MS_RCEIL, TG::RBrace, 0},
     { "rdbracket", TRDBRACKET, MS_RDBRACKET, TG::RBrace, 0},
     { "rdline", TRDLINE, MS_DVERTLINE, TG::RBrace, 0},
+    { "re" , TRE, MS_RE, TG::Standalone, 5 },
     { "red", TRED, '\0', TG::Color, 0},
     { "rfloor", TRFLOOR, MS_RFLOOR, TG::RBrace, 0},  //! 0 to terminate expression
     { "right", TRIGHT, '\0', TG::NONE, 0},
@@ -246,11 +247,11 @@ static const SmTokenTableEntry aTokenTable[] =
     { "sans", TSANS, '\0', TG::Font, 0},
     { "serif", TSERIF, '\0', TG::Font, 0},
     { "setC" , TSETC, MS_SETC, TG::Standalone, 5},
+    { "setminus", TBACKSLASH, MS_BACKSLASH, TG::Product, 0 },
     { "setN" , TSETN, MS_SETN, TG::Standalone, 5},
     { "setQ" , TSETQ, MS_SETQ, TG::Standalone, 5},
     { "setR" , TSETR, MS_SETR, TG::Standalone, 5},
     { "setZ" , TSETZ, MS_SETZ, TG::Standalone, 5},
-    { "setminus", TBACKSLASH, MS_BACKSLASH, TG::Product, 0 },
     { "silver", TSILVER, '\0', TG::Color, 0},
     { "sim", TSIM, MS_SIM, TG::Relation, 0},
     { "simeq", TSIMEQ, MS_SIMEQ, TG::Relation, 0},
@@ -262,11 +263,10 @@ static const SmTokenTableEntry aTokenTable[] =
     { "stack", TSTACK, '\0', TG::NONE, 5},
     { "sub", TRSUB, '\0', TG::Power, 0},
     { "subset", TSUBSET, MS_SUBSET, TG::Relation, 0},
+    { "subseteq", TSUBSETEQ, MS_SUBSETEQ, TG::Relation, 0},
     { "succ", TSUCCEEDS, MS_SUCCEEDS, TG::Relation, 0 },
     { "succcurlyeq", TSUCCEEDSEQUAL, MS_SUCCEEDSEQUAL, TG::Relation, 0 },
     { "succsim", TSUCCEEDSEQUIV, MS_SUCCEEDSEQUIV, TG::Relation, 0 },
-    { "nsucc", TNOTSUCCEEDS, MS_NOTSUCCEEDS, TG::Relation, 0 },
-    { "subseteq", TSUBSETEQ, MS_SUBSETEQ, TG::Relation, 0},
     { "sum", TSUM, MS_SUM, TG::Oper, 5},
     { "sup", TRSUP, '\0', TG::Power, 0},
     { "supset", TSUPSET, MS_SUPSET, TG::Relation, 0},
@@ -289,23 +289,39 @@ static const SmTokenTableEntry aTokenTable[] =
     { "white", TWHITE, '\0', TG::Color, 0},
     { "widebslash", TWIDEBACKSLASH, MS_BACKSLASH, TG::Product, 0 },
     { "widehat", TWIDEHAT, MS_HAT, TG::Attribute, 5},
-    { "widetilde", TWIDETILDE, MS_TILDE, TG::Attribute, 5},
     { "wideslash", TWIDESLASH, MS_SLASH, TG::Product, 0 },
+    { "widetilde", TWIDETILDE, MS_TILDE, TG::Attribute, 5},
     { "widevec", TWIDEVEC, MS_VEC, TG::Attribute, 5},
     { "wp" , TWP, MS_WP, TG::Standalone, 5},
     { "yellow", TYELLOW, '\0', TG::Color, 0}
 };
 
+#if !defined NDEBUG
+static bool sortCompare(const SmTokenTableEntry & lhs, const SmTokenTableEntry & rhs)
+{
+    return OUString::createFromAscii(lhs.pIdent).compareToIgnoreAsciiCase(OUString::createFromAscii(rhs.pIdent)) < 0;
+}
+#endif
+static bool findCompare(const SmTokenTableEntry & lhs, const OUString & s)
+{
+    return s.compareToIgnoreAsciiCaseAscii(lhs.pIdent) > 0;
+}
 const SmTokenTableEntry * SmParser::GetTokenTableEntry( const OUString &rName )
 {
-    if (!rName.isEmpty())
+    static bool bSortKeyWords = false;
+    if( !bSortKeyWords )
     {
-        for (auto const &token : aTokenTable)
-        {
-            if (rName.equalsIgnoreAsciiCaseAscii( token.pIdent ))
-                return &token;
-        }
+        assert( std::is_sorted( std::begin(aTokenTable), std::end(aTokenTable), sortCompare ) );
+        bSortKeyWords = true;
     }
+
+    if (rName.isEmpty())
+        return nullptr;
+
+    auto findIter = std::lower_bound( std::begin(aTokenTable), std::end(aTokenTable), rName, findCompare );
+    if ( findIter != std::end(aTokenTable) && rName.equalsIgnoreAsciiCaseAscii( findIter->pIdent ))
+        return &*findIter;
+
     return nullptr;
 }