Remove CGW_ArrayTemplate and its O(n^2 log n) sort.

R=thestig@chromium.org

Review URL: https://codereview.chromium.org/1652613002 .

4 files changed, 106 insertions, 235 deletions

diff --git a/fpdfsdk/include/fsdk_baseform.h b/fpdfsdk/include/fsdk_baseform.h
index f553bd8848..0290ef021d 100644
--- a/fpdfsdk/include/fsdk_baseform.h
+++ b/fpdfsdk/include/fsdk_baseform.h
@@ -14,12 +14,13 @@
 #endif
 
 #include <map>
+#include <vector>
 
 #include "core/include/fpdfapi/fpdf_parser.h"
 #include "core/include/fpdfdoc/fpdf_doc.h"
 #include "core/include/fxcrt/fx_basic.h"
 #include "core/include/fxge/fx_dib.h"
-#include "fsdk_baseannot.h"
+#include "fpdfsdk/include/fsdk_baseannot.h"
 
 class CFFL_FormFiller;
 class CPDFSDK_Annot;
@@ -273,14 +274,10 @@ class CPDFSDK_InterForm : public CPDF_FormNotify {
   FX_BOOL m_bNeedHightlight[kNumFieldTypes];
 };
 
-#define BAI_STRUCTURE 0
-#define BAI_ROW 1
-#define BAI_COLUMN 2
-
-#define CPDFSDK_Annots CFX_ArrayTemplate<CPDFSDK_Annot*>
-#define CPDFSDK_SortAnnots CGW_ArrayTemplate<CPDFSDK_Annot*>
 class CBA_AnnotIterator {
  public:
+  enum TabOrder { STRUCTURE = 0, ROW, COLUMN };
+
   CBA_AnnotIterator(CPDFSDK_PageView* pPageView,
                     const CFX_ByteString& sType,
                     const CFX_ByteString& sSubType);
@@ -293,15 +290,19 @@ class CBA_AnnotIterator {
 
  private:
   void GenerateResults();
-  static int CompareByLeft(CPDFSDK_Annot* p1, CPDFSDK_Annot* p2);
-  static int CompareByTop(CPDFSDK_Annot* p1, CPDFSDK_Annot* p2);
-  static CPDF_Rect GetAnnotRect(CPDFSDK_Annot* pAnnot);
+  static CPDF_Rect GetAnnotRect(const CPDFSDK_Annot* pAnnot);
+
+  // Function signature compatible with std::sort().
+  static bool CompareByLeftAscending(const CPDFSDK_Annot* p1,
+                                     const CPDFSDK_Annot* p2);
+  static bool CompareByTopDescending(const CPDFSDK_Annot* p1,
+                                     const CPDFSDK_Annot* p2);
 
+  TabOrder m_eTabOrder;
   CPDFSDK_PageView* m_pPageView;
   CFX_ByteString m_sType;
   CFX_ByteString m_sSubType;
-  int m_nTabs;
-  CPDFSDK_Annots m_Annots;
+  std::vector<CPDFSDK_Annot*> m_Annots;
 };
 
 #endif  // FPDFSDK_INCLUDE_FSDK_BASEFORM_H_
diff --git a/fpdfsdk/include/fsdk_mgr.h b/fpdfsdk/include/fsdk_mgr.h
index 4b07cc3127..323b07a46d 100644
--- a/fpdfsdk/include/fsdk_mgr.h
+++ b/fpdfsdk/include/fsdk_mgr.h
@@ -292,6 +292,7 @@ class CPDFSDK_Document {
   FX_BOOL m_bChangeMask;
   FX_BOOL m_bBeingDestroyed;
 };
+
 class CPDFSDK_PageView final {
  public:
   CPDFSDK_PageView(CPDFSDK_Document* pSDKDoc, UnderlyingPageType* page);
@@ -368,77 +369,4 @@ class CPDFSDK_PageView final {
   FX_BOOL m_bTakeOverPage;
 };
 
-template <class TYPE>
-class CGW_ArrayTemplate : public CFX_ArrayTemplate<TYPE> {
- public:
-  CGW_ArrayTemplate() {}
-  ~CGW_ArrayTemplate() {}
-
-  typedef int (*LP_COMPARE)(TYPE p1, TYPE p2);
-
-  void Sort(LP_COMPARE pCompare, FX_BOOL bAscent = TRUE) {
-    int nSize = this->GetSize();
-    QuickSort(0, nSize - 1, bAscent, pCompare);
-  }
-
- private:
-  void QuickSort(FX_UINT nStartPos,
-                 FX_UINT nStopPos,
-                 FX_BOOL bAscend,
-                 LP_COMPARE pCompare) {
-    if (nStartPos >= nStopPos)
-      return;
-
-    if ((nStopPos - nStartPos) == 1) {
-      TYPE Value1 = this->GetAt(nStartPos);
-      TYPE Value2 = this->GetAt(nStopPos);
-
-      int iGreate = (*pCompare)(Value1, Value2);
-      if ((bAscend && iGreate > 0) || (!bAscend && iGreate < 0)) {
-        this->SetAt(nStartPos, Value2);
-        this->SetAt(nStopPos, Value1);
-      }
-      return;
-    }
-
-    FX_UINT m = nStartPos + (nStopPos - nStartPos) / 2;
-    FX_UINT i = nStartPos;
-
-    TYPE Value = this->GetAt(m);
-
-    while (i < m) {
-      TYPE temp = this->GetAt(i);
-
-      int iGreate = (*pCompare)(temp, Value);
-      if ((bAscend && iGreate > 0) || (!bAscend && iGreate < 0)) {
-        this->InsertAt(m + 1, temp);
-        this->RemoveAt(i);
-        m--;
-      } else {
-        i++;
-      }
-    }
-
-    FX_UINT j = nStopPos;
-
-    while (j > m) {
-      TYPE temp = this->GetAt(j);
-
-      int iGreate = (*pCompare)(temp, Value);
-      if ((bAscend && iGreate < 0) || (!bAscend && iGreate > 0)) {
-        this->RemoveAt(j);
-        this->InsertAt(m, temp);
-        m++;
-      } else {
-        j--;
-      }
-    }
-
-    if (nStartPos < m)
-      QuickSort(nStartPos, m, bAscend, pCompare);
-    if (nStopPos > m)
-      QuickSort(m, nStopPos, bAscend, pCompare);
-  }
-};
-
 #endif  // FPDFSDK_INCLUDE_FSDK_MGR_H_
diff --git a/fpdfsdk/src/fsdk_baseform.cpp b/fpdfsdk/src/fsdk_baseform.cpp
index 218ee1d83a..46aa1f3d85 100644
--- a/fpdfsdk/src/fsdk_baseform.cpp
+++ b/fpdfsdk/src/fsdk_baseform.cpp
@@ -6,6 +6,7 @@
 
 #include "fpdfsdk/include/fsdk_baseform.h"
 
+#include <algorithm>
 #include <memory>
 
 #include "fpdfsdk/include/formfiller/FFL_FormFiller.h"
@@ -2079,177 +2080,125 @@ FX_COLORREF CPDFSDK_InterForm::GetHighlightColor(int nFieldType) {
 CBA_AnnotIterator::CBA_AnnotIterator(CPDFSDK_PageView* pPageView,
                                      const CFX_ByteString& sType,
                                      const CFX_ByteString& sSubType)
-    : m_pPageView(pPageView),
+    : m_eTabOrder(STRUCTURE),
+      m_pPageView(pPageView),
       m_sType(sType),
-      m_sSubType(sSubType),
-      m_nTabs(BAI_STRUCTURE) {
+      m_sSubType(sSubType) {
   CPDF_Page* pPDFPage = m_pPageView->GetPDFPage();
   CFX_ByteString sTabs = pPDFPage->m_pFormDict->GetStringBy("Tabs");
-
-  if (sTabs == "R") {
-    m_nTabs = BAI_ROW;
-  } else if (sTabs == "C") {
-    m_nTabs = BAI_COLUMN;
-  } else {
-    m_nTabs = BAI_STRUCTURE;
-  }
+  if (sTabs == "R")
+    m_eTabOrder = ROW;
+  else if (sTabs == "C")
+    m_eTabOrder = COLUMN;
 
   GenerateResults();
 }
 
 CBA_AnnotIterator::~CBA_AnnotIterator() {
-  m_Annots.RemoveAll();
 }
 
 CPDFSDK_Annot* CBA_AnnotIterator::GetFirstAnnot() {
-  if (m_Annots.GetSize() > 0)
-    return m_Annots[0];
-
-  return NULL;
+  return m_Annots.empty() ? nullptr : m_Annots.front();
 }
 
 CPDFSDK_Annot* CBA_AnnotIterator::GetLastAnnot() {
-  if (m_Annots.GetSize() > 0)
-    return m_Annots[m_Annots.GetSize() - 1];
-
-  return NULL;
+  return m_Annots.empty() ? nullptr : m_Annots.back();
 }
 
 CPDFSDK_Annot* CBA_AnnotIterator::GetNextAnnot(CPDFSDK_Annot* pAnnot) {
-  for (int i = 0, sz = m_Annots.GetSize(); i < sz; ++i) {
-    if (m_Annots[i] == pAnnot)
-      return (i + 1 < sz) ? m_Annots[i + 1] : m_Annots[0];
-  }
-  return NULL;
+  auto iter = std::find(m_Annots.begin(), m_Annots.end(), pAnnot);
+  if (iter == m_Annots.end())
+    return nullptr;
+  ++iter;
+  if (iter == m_Annots.end())
+    iter = m_Annots.begin();
+  return *iter;
 }
 
 CPDFSDK_Annot* CBA_AnnotIterator::GetPrevAnnot(CPDFSDK_Annot* pAnnot) {
-  for (int i = 0, sz = m_Annots.GetSize(); i < sz; ++i) {
-    if (m_Annots[i] == pAnnot)
-      return (i - 1 >= 0) ? m_Annots[i - 1] : m_Annots[sz - 1];
-  }
-  return NULL;
+  auto iter = std::find(m_Annots.begin(), m_Annots.end(), pAnnot);
+  if (iter == m_Annots.end())
+    return nullptr;
+  if (iter == m_Annots.begin())
+    iter = m_Annots.end();
+  return *(--iter);
 }
 
-int CBA_AnnotIterator::CompareByLeft(CPDFSDK_Annot* p1, CPDFSDK_Annot* p2) {
-  ASSERT(p1);
-  ASSERT(p2);
-
-  CPDF_Rect rcAnnot1 = GetAnnotRect(p1);
-  CPDF_Rect rcAnnot2 = GetAnnotRect(p2);
-
-  if (rcAnnot1.left < rcAnnot2.left)
-    return -1;
-  if (rcAnnot1.left > rcAnnot2.left)
-    return 1;
-  return 0;
+// static
+bool CBA_AnnotIterator::CompareByLeftAscending(const CPDFSDK_Annot* p1,
+                                               const CPDFSDK_Annot* p2) {
+  return GetAnnotRect(p1).left < GetAnnotRect(p2).left;
 }
 
-int CBA_AnnotIterator::CompareByTop(CPDFSDK_Annot* p1, CPDFSDK_Annot* p2) {
-  ASSERT(p1);
-  ASSERT(p2);
-
-  CPDF_Rect rcAnnot1 = GetAnnotRect(p1);
-  CPDF_Rect rcAnnot2 = GetAnnotRect(p2);
-
-  if (rcAnnot1.top < rcAnnot2.top)
-    return -1;
-  if (rcAnnot1.top > rcAnnot2.top)
-    return 1;
-  return 0;
+// static
+bool CBA_AnnotIterator::CompareByTopDescending(const CPDFSDK_Annot* p1,
+                                               const CPDFSDK_Annot* p2) {
+  return GetAnnotRect(p1).top > GetAnnotRect(p2).top;
 }
 
 void CBA_AnnotIterator::GenerateResults() {
-  switch (m_nTabs) {
-    case BAI_STRUCTURE: {
+  switch (m_eTabOrder) {
+    case STRUCTURE: {
       for (size_t i = 0; i < m_pPageView->CountAnnots(); ++i) {
         CPDFSDK_Annot* pAnnot = m_pPageView->GetAnnot(i);
         if (pAnnot->GetType() == m_sType && pAnnot->GetSubType() == m_sSubType)
-          m_Annots.Add(pAnnot);
+          m_Annots.push_back(pAnnot);
       }
-      break;
-    }
-    case BAI_ROW: {
-      CPDFSDK_SortAnnots sa;
+    } break;
+    case ROW: {
+      std::vector<CPDFSDK_Annot*> sa;
       for (size_t i = 0; i < m_pPageView->CountAnnots(); ++i) {
         CPDFSDK_Annot* pAnnot = m_pPageView->GetAnnot(i);
         if (pAnnot->GetType() == m_sType && pAnnot->GetSubType() == m_sSubType)
-          sa.Add(pAnnot);
+          sa.push_back(pAnnot);
       }
 
-      if (sa.GetSize() > 0)
-        sa.Sort(CBA_AnnotIterator::CompareByLeft);
-
-      while (sa.GetSize() > 0) {
+      std::sort(sa.begin(), sa.end(), CompareByLeftAscending);
+      while (!sa.empty()) {
         int nLeftTopIndex = -1;
         FX_FLOAT fTop = 0.0f;
-
-        for (int i = sa.GetSize() - 1; i >= 0; i--) {
-          CPDFSDK_Annot* pAnnot = sa.GetAt(i);
-          ASSERT(pAnnot);
-
-          CPDF_Rect rcAnnot = GetAnnotRect(pAnnot);
-
+        for (int i = sa.size() - 1; i >= 0; i--) {
+          CPDF_Rect rcAnnot = GetAnnotRect(sa[i]);
           if (rcAnnot.top > fTop) {
             nLeftTopIndex = i;
             fTop = rcAnnot.top;
           }
         }
-
         if (nLeftTopIndex >= 0) {
-          CPDFSDK_Annot* pLeftTopAnnot = sa.GetAt(nLeftTopIndex);
-          ASSERT(pLeftTopAnnot);
-
+          CPDFSDK_Annot* pLeftTopAnnot = sa[nLeftTopIndex];
           CPDF_Rect rcLeftTop = GetAnnotRect(pLeftTopAnnot);
+          m_Annots.push_back(pLeftTopAnnot);
+          sa.erase(sa.begin() + nLeftTopIndex);
 
-          m_Annots.Add(pLeftTopAnnot);
-          sa.RemoveAt(nLeftTopIndex);
-
-          CFX_ArrayTemplate<int> aSelect;
-
-          for (int i = 0, sz = sa.GetSize(); i < sz; ++i) {
-            CPDFSDK_Annot* pAnnot = sa.GetAt(i);
-            ASSERT(pAnnot);
-
-            CPDF_Rect rcAnnot = GetAnnotRect(pAnnot);
+          std::vector<int> aSelect;
+          for (int i = 0; i < sa.size(); ++i) {
+            CPDF_Rect rcAnnot = GetAnnotRect(sa[i]);
             FX_FLOAT fCenterY = (rcAnnot.top + rcAnnot.bottom) / 2.0f;
             if (fCenterY > rcLeftTop.bottom && fCenterY < rcLeftTop.top)
-              aSelect.Add(i);
+              aSelect.push_back(i);
           }
+          for (int i = 0; i < aSelect.size(); ++i)
+            m_Annots.push_back(sa[aSelect[i]]);
 
-          for (int i = 0, sz = aSelect.GetSize(); i < sz; ++i)
-            m_Annots.Add(sa[aSelect[i]]);
-
-          for (int i = aSelect.GetSize() - 1; i >= 0; --i)
-              sa.RemoveAt(aSelect[i]);
-
-          aSelect.RemoveAll();
+          for (int i = aSelect.size() - 1; i >= 0; --i)
+            sa.erase(sa.begin() + aSelect[i]);
         }
       }
-      sa.RemoveAll();
-      break;
-    }
-    case BAI_COLUMN: {
-      CPDFSDK_SortAnnots sa;
+    } break;
+    case COLUMN: {
+      std::vector<CPDFSDK_Annot*> sa;
       for (size_t i = 0; i < m_pPageView->CountAnnots(); ++i) {
         CPDFSDK_Annot* pAnnot = m_pPageView->GetAnnot(i);
         if (pAnnot->GetType() == m_sType && pAnnot->GetSubType() == m_sSubType)
-          sa.Add(pAnnot);
+          sa.push_back(pAnnot);
       }
 
-      if (sa.GetSize() > 0)
-        sa.Sort(CBA_AnnotIterator::CompareByTop, FALSE);
-
-      while (sa.GetSize() > 0) {
+      std::sort(sa.begin(), sa.end(), CompareByTopDescending);
+      while (!sa.empty()) {
         int nLeftTopIndex = -1;
         FX_FLOAT fLeft = -1.0f;
-
-        for (int i = sa.GetSize() - 1; i >= 0; --i) {
-          CPDFSDK_Annot* pAnnot = sa.GetAt(i);
-          ASSERT(pAnnot);
-
-          CPDF_Rect rcAnnot = GetAnnotRect(pAnnot);
-
+        for (int i = sa.size() - 1; i >= 0; --i) {
+          CPDF_Rect rcAnnot = GetAnnotRect(sa[i]);
           if (fLeft < 0) {
             nLeftTopIndex = 0;
             fLeft = rcAnnot.left;
@@ -2260,41 +2209,31 @@ void CBA_AnnotIterator::GenerateResults() {
         }
 
         if (nLeftTopIndex >= 0) {
-          CPDFSDK_Annot* pLeftTopAnnot = sa.GetAt(nLeftTopIndex);
-          ASSERT(pLeftTopAnnot);
-
+          CPDFSDK_Annot* pLeftTopAnnot = sa[nLeftTopIndex];
           CPDF_Rect rcLeftTop = GetAnnotRect(pLeftTopAnnot);
+          m_Annots.push_back(pLeftTopAnnot);
+          sa.erase(sa.begin() + nLeftTopIndex);
 
-          m_Annots.Add(pLeftTopAnnot);
-          sa.RemoveAt(nLeftTopIndex);
-
-          CFX_ArrayTemplate<int> aSelect;
-          for (int i = 0, sz = sa.GetSize(); i < sz; ++i) {
-            CPDFSDK_Annot* pAnnot = sa.GetAt(i);
-            ASSERT(pAnnot);
-
-            CPDF_Rect rcAnnot = GetAnnotRect(pAnnot);
+          std::vector<int> aSelect;
+          for (int i = 0; i < sa.size(); ++i) {
+            CPDF_Rect rcAnnot = GetAnnotRect(sa[i]);
             FX_FLOAT fCenterX = (rcAnnot.left + rcAnnot.right) / 2.0f;
             if (fCenterX > rcLeftTop.left && fCenterX < rcLeftTop.right)
-              aSelect.Add(i);
+              aSelect.push_back(i);
           }
+          for (int i = 0; i < aSelect.size(); ++i)
+            m_Annots.push_back(sa[aSelect[i]]);
 
-          for (int i = 0, sz = aSelect.GetSize(); i < sz; ++i)
-            m_Annots.Add(sa[aSelect[i]]);
-
-          for (int i = aSelect.GetSize() - 1; i >= 0; --i)
-            sa.RemoveAt(aSelect[i]);
-
-          aSelect.RemoveAll();
+          for (int i = aSelect.size() - 1; i >= 0; --i)
+            sa.erase(sa.begin() + aSelect[i]);
         }
       }
-      sa.RemoveAll();
       break;
     }
   }
 }
 
-CPDF_Rect CBA_AnnotIterator::GetAnnotRect(CPDFSDK_Annot* pAnnot) {
+CPDF_Rect CBA_AnnotIterator::GetAnnotRect(const CPDFSDK_Annot* pAnnot) {
   CPDF_Rect rcAnnot;
   pAnnot->GetPDFAnnot()->GetRect(rcAnnot);
   return rcAnnot;
diff --git a/fpdfsdk/src/javascript/Field.cpp b/fpdfsdk/src/javascript/Field.cpp
index d97001aae2..0b78ba24a6 100644
--- a/fpdfsdk/src/javascript/Field.cpp
+++ b/fpdfsdk/src/javascript/Field.cpp
@@ -6,6 +6,10 @@
 
 #include "Field.h"
 
+#include <algorithm>
+#include <memory>
+#include <vector>
+
 #include "Document.h"
 #include "Icon.h"
 #include "JS_Context.h"
@@ -3083,10 +3087,6 @@ FX_BOOL Field::deleteItemAt(IJS_Context* cc,
   return TRUE;
 }
 
-int JS_COMPARESTRING(CFX_WideString* ps1, CFX_WideString* ps2) {
-  return ps1->Compare(*ps2);
-}
-
 FX_BOOL Field::getArray(IJS_Context* cc,
                         const std::vector<CJS_Value>& params,
                         CJS_Value& vRet,
@@ -3095,35 +3095,38 @@ FX_BOOL Field::getArray(IJS_Context* cc,
   if (FieldArray.empty())
     return FALSE;
 
-  CGW_ArrayTemplate<CFX_WideString*> swSort;
+  std::vector<std::unique_ptr<CFX_WideString>> swSort;
+  for (CPDF_FormField* pFormField : FieldArray) {
+    swSort.push_back(std::unique_ptr<CFX_WideString>(
+        new CFX_WideString(pFormField->GetFullName())));
+  }
 
-  for (CPDF_FormField* pFormField : FieldArray)
-    swSort.Add(new CFX_WideString(pFormField->GetFullName()));
-  swSort.Sort(JS_COMPARESTRING);
+  std::sort(
+      swSort.begin(), swSort.end(),
+      [](const std::unique_ptr<CFX_WideString>& p1,
+         const std::unique_ptr<CFX_WideString>& p2) { return *p1 < *p2; });
 
   CJS_Context* pContext = (CJS_Context*)cc;
   CJS_Runtime* pRuntime = pContext->GetJSRuntime();
-  ASSERT(pRuntime);
-
   CJS_Array FormFieldArray(pRuntime);
-  for (int j = 0, jsz = swSort.GetSize(); j < jsz; j++) {
-    std::unique_ptr<CFX_WideString> pStr(swSort.GetAt(j));
+
+  int j = 0;
+  for (const auto& pStr : swSort) {
     v8::Local<v8::Object> pObj = FXJS_NewFxDynamicObj(
         pRuntime->GetIsolate(), pRuntime, CJS_Field::g_nObjDefnID);
     ASSERT(!pObj.IsEmpty());
 
     CJS_Field* pJSField =
-        (CJS_Field*)FXJS_GetPrivate(pRuntime->GetIsolate(), pObj);
-    Field* pField = (Field*)pJSField->GetEmbedObject();
+        static_cast<CJS_Field*>(FXJS_GetPrivate(pRuntime->GetIsolate(), pObj));
+    Field* pField = static_cast<Field*>(pJSField->GetEmbedObject());
     pField->AttachField(m_pJSDoc, *pStr);
 
     CJS_Value FormFieldValue(pRuntime);
     FormFieldValue = pJSField;
-    FormFieldArray.SetElement(j, FormFieldValue);
+    FormFieldArray.SetElement(j++, FormFieldValue);
   }
 
   vRet = FormFieldArray;
-  swSort.RemoveAll();
   return TRUE;
 }