First-time sync: asymptotic running time improvement

chrome/browser/sync/syncable/syncable_id_unittest.cc

 // Copyright (c) 2009 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "chrome/browser/sync/syncable/syncable_id.h"
 
 #include <vector>
 
 #include "chrome/test/sync/engine/test_id_factory.h"
 #include "testing/gtest/include/gtest/gtest.h"
@@ skipping 23 matching lines @@
     for (vector<Id>::iterator j = v.begin(); j != i; ++j) {
       ASSERT_NE(*i, *j) << "mis equated two distinct ids";
     }
     ASSERT_EQ(*i, *i) << "self-equality failed";
     Id copy1 = *i;
     Id copy2 = *i;
     ASSERT_EQ(copy1, copy2) << "equality after copy failed";
   }
 }
 
+TEST(SyncableIdTest, GetLeastIdForLexicographicComparison) {
+  vector<Id> v;
+  v.push_back(Id::CreateFromServerId("z5"));
+  v.push_back(Id::CreateFromServerId("z55"));
+  v.push_back(Id::CreateFromServerId("z6"));
+  v.push_back(Id::CreateFromClientString("zA-"));
+  v.push_back(Id::CreateFromClientString("zA--"));
+  v.push_back(Id::CreateFromServerId("zA--"));
+
+  for (int i = 0; i <= 255; ++i) {
+    std::string one_character_id;
+    one_character_id.push_back(i);
+    v.push_back(Id::CreateFromClientString(one_character_id));
+  }
+
+  for (vector<Id>::iterator i = v.begin(); i != v.end(); ++i) {
+    // The following looks redundant, but we're testing a custom operator<.
+    ASSERT_LT(Id::GetLeastIdForLexicographicComparison(), *i);
+    ASSERT_NE(*i, i->GetLexicographicSuccessor());
+    ASSERT_NE(i->GetLexicographicSuccessor(), *i);
+    ASSERT_LT(*i, i->GetLexicographicSuccessor());
+    ASSERT_GT(i->GetLexicographicSuccessor(), *i);
+    for (vector<Id>::iterator j = v.begin(); j != v.end(); ++j) {
+      if (j == i)
+        continue;
+      if (*j < *i) {
+        ASSERT_LT(j->GetLexicographicSuccessor(), *i);
+        ASSERT_LT(j->GetLexicographicSuccessor(),
+            i->GetLexicographicSuccessor());
+        ASSERT_LT(*j, i->GetLexicographicSuccessor());
+      } else {
+        ASSERT_GT(j->GetLexicographicSuccessor(), *i);
+        ASSERT_GT(j->GetLexicographicSuccessor(),
+            i->GetLexicographicSuccessor());
+        ASSERT_GT(*j, i->GetLexicographicSuccessor());
+      }
+    }
+  }
+}
+
 }  // namespace syncable