absl/strings/internal/cord_rep_btree_navigator_test.cc - external/github.com/abseil/abseil-cpp - Git at Google

 // Copyright 2021 The Abseil Authors
 //
 // Licensed under the Apache License, Version 2.0 (the "License");
 // you may not use this file except in compliance with the License.
 // You may obtain a copy of the License at
 //
 //     https://www.apache.org/licenses/LICENSE-2.0
 //
 // Unless required by applicable law or agreed to in writing, software
 // distributed under the License is distributed on an "AS IS" BASIS,
 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 // See the License for the specific language governing permissions and
 // limitations under the License.

 #include "absl/strings/internal/cord_rep_btree_navigator.h"

 #include <string>
 #include <vector>

 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include "absl/base/config.h"
 #include "absl/base/internal/raw_logging.h"
 #include "absl/strings/internal/cord_internal.h"
 #include "absl/strings/internal/cord_rep_btree.h"
 #include "absl/strings/internal/cord_rep_test_util.h"
 #include "absl/strings/str_cat.h"
 #include "absl/strings/string_view.h"

 namespace absl {
 ABSL_NAMESPACE_BEGIN
 namespace cord_internal {
 namespace {

 using ::testing::Eq;
 using ::testing::Ne;

 using ::absl::cordrep_testing::CordRepBtreeFromFlats;
 using ::absl::cordrep_testing::CordToString;
 using ::absl::cordrep_testing::CreateFlatsFromString;
 using ::absl::cordrep_testing::CreateRandomString;
 using ::absl::cordrep_testing::MakeFlat;
 using ::absl::cordrep_testing::MakeSubstring;

 using ReadResult = CordRepBtreeNavigator::ReadResult;
 using Position = CordRepBtreeNavigator::Position;

 // CordRepBtreeNavigatorTest is a test fixture which automatically creates a
 // tree to test navigation logic on. The parameter `count' defines the number of
 // data edges in the test tree.
 class CordRepBtreeNavigatorTest : public testing::TestWithParam<size_t> {
  public:
   using Flats = std::vector<CordRep*>;
   static constexpr size_t kCharsPerFlat = 3;

   CordRepBtreeNavigatorTest() {
     data_ = CreateRandomString(count() * kCharsPerFlat);
     flats_ = CreateFlatsFromString(data_, kCharsPerFlat);

     // Turn flat 0 or 1 into a substring to cover partial reads on substrings.
     if (count() > 1) {
       CordRep::Unref(flats_[1]);
       flats_[1] = MakeSubstring(kCharsPerFlat, kCharsPerFlat, MakeFlat(data_));
     } else {
       CordRep::Unref(flats_[0]);
       flats_[0] = MakeSubstring(0, kCharsPerFlat, MakeFlat(data_));
     }

     tree_ = CordRepBtreeFromFlats(flats_);
   }

   ~CordRepBtreeNavigatorTest() override { CordRep::Unref(tree_); }

   size_t count() const { return GetParam(); }
   CordRepBtree* tree() { return tree_; }
   const std::string& data() const { return data_; }
   const std::vector<CordRep*>& flats() const { return flats_; }

   static std::string ToString(testing::TestParamInfo<size_t> param) {
     return absl::StrCat(param.param, "_Flats");
   }

  private:
   std::string data_;
   Flats flats_;
   CordRepBtree* tree_;
 };

 INSTANTIATE_TEST_SUITE_P(
     WithParam, CordRepBtreeNavigatorTest,
     testing::Values(1, CordRepBtree::kMaxCapacity - 1,
                     CordRepBtree::kMaxCapacity,
                     CordRepBtree::kMaxCapacity* CordRepBtree::kMaxCapacity - 1,
                     CordRepBtree::kMaxCapacity* CordRepBtree::kMaxCapacity,
                     CordRepBtree::kMaxCapacity* CordRepBtree::kMaxCapacity + 1,
                     CordRepBtree::kMaxCapacity* CordRepBtree::kMaxCapacity * 2 +
                         17),
     CordRepBtreeNavigatorTest::ToString);

 TEST(CordRepBtreeNavigatorTest, Uninitialized) {
   CordRepBtreeNavigator nav;
   EXPECT_FALSE(nav);
   EXPECT_THAT(nav.btree(), Eq(nullptr));
 #if defined(GTEST_HAS_DEATH_TEST) && !defined(NDEBUG)
   EXPECT_DEATH(nav.Current(), ".*");
 #endif
 }

 TEST_P(CordRepBtreeNavigatorTest, InitFirst) {
   CordRepBtreeNavigator nav;
   CordRep* edge = nav.InitFirst(tree());
   EXPECT_TRUE(nav);
   EXPECT_THAT(nav.btree(), Eq(tree()));
   EXPECT_THAT(nav.Current(), Eq(flats().front()));
   EXPECT_THAT(edge, Eq(flats().front()));
 }

 TEST_P(CordRepBtreeNavigatorTest, InitLast) {
   CordRepBtreeNavigator nav;
   CordRep* edge = nav.InitLast(tree());
   EXPECT_TRUE(nav);
   EXPECT_THAT(nav.btree(), Eq(tree()));
   EXPECT_THAT(nav.Current(), Eq(flats().back()));
   EXPECT_THAT(edge, Eq(flats().back()));
 }

 TEST_P(CordRepBtreeNavigatorTest, NextPrev) {
   CordRepBtreeNavigator nav;
   nav.InitFirst(tree());
   const Flats& flats = this->flats();

   EXPECT_THAT(nav.Previous(), Eq(nullptr));
   EXPECT_THAT(nav.Current(), Eq(flats.front()));
   for (size_t i = 1; i < flats.size(); ++i) {
     ASSERT_THAT(nav.Next(), Eq(flats[i]));
     EXPECT_THAT(nav.Current(), Eq(flats[i]));
   }
   EXPECT_THAT(nav.Next(), Eq(nullptr));
   EXPECT_THAT(nav.Current(), Eq(flats.back()));
   for (size_t i = flats.size() - 1; i > 0; --i) {
     ASSERT_THAT(nav.Previous(), Eq(flats[i - 1]));
     EXPECT_THAT(nav.Current(), Eq(flats[i - 1]));
   }
   EXPECT_THAT(nav.Previous(), Eq(nullptr));
   EXPECT_THAT(nav.Current(), Eq(flats.front()));
 }

 TEST_P(CordRepBtreeNavigatorTest, PrevNext) {
   CordRepBtreeNavigator nav;
   nav.InitLast(tree());
   const Flats& flats = this->flats();

   EXPECT_THAT(nav.Next(), Eq(nullptr));
   EXPECT_THAT(nav.Current(), Eq(flats.back()));
   for (size_t i = flats.size() - 1; i > 0; --i) {
     ASSERT_THAT(nav.Previous(), Eq(flats[i - 1]));
     EXPECT_THAT(nav.Current(), Eq(flats[i - 1]));
   }
   EXPECT_THAT(nav.Previous(), Eq(nullptr));
   EXPECT_THAT(nav.Current(), Eq(flats.front()));
   for (size_t i = 1; i < flats.size(); ++i) {
     ASSERT_THAT(nav.Next(), Eq(flats[i]));
     EXPECT_THAT(nav.Current(), Eq(flats[i]));
   }
   EXPECT_THAT(nav.Next(), Eq(nullptr));
   EXPECT_THAT(nav.Current(), Eq(flats.back()));
 }

 TEST(CordRepBtreeNavigatorTest, Reset) {
   CordRepBtree* tree = CordRepBtree::Create(MakeFlat("abc"));
   CordRepBtreeNavigator nav;
   nav.InitFirst(tree);
   nav.Reset();
   EXPECT_FALSE(nav);
   EXPECT_THAT(nav.btree(), Eq(nullptr));
 #if defined(GTEST_HAS_DEATH_TEST) && !defined(NDEBUG)
   EXPECT_DEATH(nav.Current(), ".*");
 #endif
   CordRep::Unref(tree);
 }

 TEST_P(CordRepBtreeNavigatorTest, Skip) {
   size_t count = this->count();
   const Flats& flats = this->flats();
   CordRepBtreeNavigator nav;
   nav.InitFirst(tree());

   for (size_t char_offset = 0; char_offset < kCharsPerFlat; ++char_offset) {
     Position pos = nav.Skip(char_offset);
     EXPECT_THAT(pos.edge, Eq(nav.Current()));
     EXPECT_THAT(pos.edge, Eq(flats[0]));
     EXPECT_THAT(pos.offset, Eq(char_offset));
   }

   for (size_t index1 = 0; index1 < count; ++index1) {
     for (size_t index2 = index1; index2 < count; ++index2) {
       for (size_t char_offset = 0; char_offset < kCharsPerFlat; ++char_offset) {
         CordRepBtreeNavigator nav;
         nav.InitFirst(tree());

         size_t length1 = index1 * kCharsPerFlat;
         Position pos1 = nav.Skip(length1 + char_offset);
         ASSERT_THAT(pos1.edge, Eq(flats[index1]));
         ASSERT_THAT(pos1.edge, Eq(nav.Current()));
         ASSERT_THAT(pos1.offset, Eq(char_offset));

         size_t length2 = index2 * kCharsPerFlat;
         Position pos2 = nav.Skip(length2 - length1 + char_offset);
         ASSERT_THAT(pos2.edge, Eq(flats[index2]));
         ASSERT_THAT(pos2.edge, Eq(nav.Current()));
         ASSERT_THAT(pos2.offset, Eq(char_offset));
       }
     }
   }
 }

 TEST_P(CordRepBtreeNavigatorTest, Seek) {
   size_t count = this->count();
   const Flats& flats = this->flats();
   CordRepBtreeNavigator nav;
   nav.InitFirst(tree());

   for (size_t char_offset = 0; char_offset < kCharsPerFlat; ++char_offset) {
     Position pos = nav.Seek(char_offset);
     EXPECT_THAT(pos.edge, Eq(nav.Current()));
     EXPECT_THAT(pos.edge, Eq(flats[0]));
     EXPECT_THAT(pos.offset, Eq(char_offset));
   }

   for (size_t index = 0; index < count; ++index) {
     for (size_t char_offset = 0; char_offset < kCharsPerFlat; ++char_offset) {
       size_t offset = index * kCharsPerFlat + char_offset;
       Position pos1 = nav.Seek(offset);
       ASSERT_THAT(pos1.edge, Eq(flats[index]));
       ASSERT_THAT(pos1.edge, Eq(nav.Current()));
       ASSERT_THAT(pos1.offset, Eq(char_offset));
     }
   }
 }

 TEST(CordRepBtreeNavigatorTest, InitOffset) {
   // Whitebox: InitOffset() is implemented in terms of Seek() which is
   // exhaustively tested. Only test it initializes / forwards properly..
   CordRepBtree* tree = CordRepBtree::Create(MakeFlat("abc"));
   tree = CordRepBtree::Append(tree, MakeFlat("def"));
   CordRepBtreeNavigator nav;
   Position pos = nav.InitOffset(tree, 5);
   EXPECT_TRUE(nav);
   EXPECT_THAT(nav.btree(), Eq(tree));
   EXPECT_THAT(pos.edge, Eq(tree->Edges()[1]));
   EXPECT_THAT(pos.edge, Eq(nav.Current()));
   EXPECT_THAT(pos.offset, Eq(2u));
   CordRep::Unref(tree);
 }

 TEST(CordRepBtreeNavigatorTest, InitOffsetAndSeekBeyondLength) {
   CordRepBtree* tree1 = CordRepBtree::Create(MakeFlat("abc"));
   CordRepBtree* tree2 = CordRepBtree::Create(MakeFlat("def"));

   CordRepBtreeNavigator nav;
   nav.InitFirst(tree1);
   EXPECT_THAT(nav.Seek(3).edge, Eq(nullptr));
   EXPECT_THAT(nav.Seek(100).edge, Eq(nullptr));
   EXPECT_THAT(nav.btree(), Eq(tree1));
   EXPECT_THAT(nav.Current(), Eq(tree1->Edges().front()));

   EXPECT_THAT(nav.InitOffset(tree2, 3).edge, Eq(nullptr));
   EXPECT_THAT(nav.InitOffset(tree2, 100).edge, Eq(nullptr));
   EXPECT_THAT(nav.btree(), Eq(tree1));
   EXPECT_THAT(nav.Current(), Eq(tree1->Edges().front()));

   CordRep::Unref(tree1);
   CordRep::Unref(tree2);
 }

 TEST_P(CordRepBtreeNavigatorTest, Read) {
   const Flats& flats = this->flats();
   const std::string& data = this->data();

   for (size_t offset = 0; offset < data.size(); ++offset) {
     for (size_t length = 1; length <= data.size() - offset; ++length) {
       CordRepBtreeNavigator nav;
       nav.InitFirst(tree());

       // Skip towards edge holding offset
       size_t edge_offset = nav.Skip(offset).offset;

       // Read node
       ReadResult result = nav.Read(edge_offset, length);
       ASSERT_THAT(result.tree, Ne(nullptr));
       EXPECT_THAT(result.tree->length, Eq(length));
       if (result.tree->tag == BTREE) {
         ASSERT_TRUE(CordRepBtree::IsValid(result.tree->btree()));
       }

       // Verify contents
       std::string value = CordToString(result.tree);
       EXPECT_THAT(value, Eq(data.substr(offset, length)));

       // Verify 'partial last edge' reads.
       size_t partial = (offset + length) % kCharsPerFlat;
       ASSERT_THAT(result.n, Eq(partial));

       // Verify ending position if not EOF
       if (offset + length < data.size()) {
         size_t index = (offset + length) / kCharsPerFlat;
         EXPECT_THAT(nav.Current(), Eq(flats[index]));
       }

       CordRep::Unref(result.tree);
     }
   }
 }

 TEST_P(CordRepBtreeNavigatorTest, ReadBeyondLengthOfTree) {
   CordRepBtreeNavigator nav;
   nav.InitFirst(tree());
   ReadResult result = nav.Read(2, tree()->length);
   ASSERT_THAT(result.tree, Eq(nullptr));
 }

 TEST(CordRepBtreeNavigatorTest, NavigateMaximumTreeDepth) {
   CordRepFlat* flat1 = MakeFlat("Hello world");
   CordRepFlat* flat2 = MakeFlat("World Hello");

   CordRepBtree* node = CordRepBtree::Create(flat1);
   node = CordRepBtree::Append(node, flat2);
   while (node->height() < CordRepBtree::kMaxHeight) {
     node = CordRepBtree::New(node);
   }

   CordRepBtreeNavigator nav;
   CordRep* edge = nav.InitFirst(node);
   EXPECT_THAT(edge, Eq(flat1));
   EXPECT_THAT(nav.Next(), Eq(flat2));
   EXPECT_THAT(nav.Next(), Eq(nullptr));
   EXPECT_THAT(nav.Previous(), Eq(flat1));
   EXPECT_THAT(nav.Previous(), Eq(nullptr));

   CordRep::Unref(node);
 }

 }  // namespace
 }  // namespace cord_internal
 ABSL_NAMESPACE_END
 }  // namespace absl
	// Copyright 2021 The Abseil Authors
	//
	// Licensed under the Apache License, Version 2.0 (the "License");
	// you may not use this file except in compliance with the License.
	// You may obtain a copy of the License at
	//
	// https://www.apache.org/licenses/LICENSE-2.0
	//
	// Unless required by applicable law or agreed to in writing, software
	// distributed under the License is distributed on an "AS IS" BASIS,
	// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	// See the License for the specific language governing permissions and
	// limitations under the License.

	#include "absl/strings/internal/cord_rep_btree_navigator.h"

	#include <string>
	#include <vector>

	#include "gmock/gmock.h"
	#include "gtest/gtest.h"
	#include "absl/base/config.h"
	#include "absl/base/internal/raw_logging.h"
	#include "absl/strings/internal/cord_internal.h"
	#include "absl/strings/internal/cord_rep_btree.h"
	#include "absl/strings/internal/cord_rep_test_util.h"
	#include "absl/strings/str_cat.h"
	#include "absl/strings/string_view.h"

	namespace absl {
	ABSL_NAMESPACE_BEGIN
	namespace cord_internal {
	namespace {

	using ::testing::Eq;
	using ::testing::Ne;

	using ::absl::cordrep_testing::CordRepBtreeFromFlats;
	using ::absl::cordrep_testing::CordToString;
	using ::absl::cordrep_testing::CreateFlatsFromString;
	using ::absl::cordrep_testing::CreateRandomString;
	using ::absl::cordrep_testing::MakeFlat;
	using ::absl::cordrep_testing::MakeSubstring;

	using ReadResult = CordRepBtreeNavigator::ReadResult;
	using Position = CordRepBtreeNavigator::Position;

	// CordRepBtreeNavigatorTest is a test fixture which automatically creates a
	// tree to test navigation logic on. The parameter `count' defines the number of
	// data edges in the test tree.
	class CordRepBtreeNavigatorTest : public testing::TestWithParam<size_t> {
	public:
	using Flats = std::vector<CordRep*>;
	static constexpr size_t kCharsPerFlat = 3;

	CordRepBtreeNavigatorTest() {
	data_ = CreateRandomString(count() * kCharsPerFlat);
	flats_ = CreateFlatsFromString(data_, kCharsPerFlat);

	// Turn flat 0 or 1 into a substring to cover partial reads on substrings.
	if (count() > 1) {
	CordRep::Unref(flats_[1]);
	flats_[1] = MakeSubstring(kCharsPerFlat, kCharsPerFlat, MakeFlat(data_));
	} else {
	CordRep::Unref(flats_[0]);
	flats_[0] = MakeSubstring(0, kCharsPerFlat, MakeFlat(data_));
	}

	tree_ = CordRepBtreeFromFlats(flats_);
	}

	~CordRepBtreeNavigatorTest() override { CordRep::Unref(tree_); }

	size_t count() const { return GetParam(); }
	CordRepBtree* tree() { return tree_; }
	const std::string& data() const { return data_; }
	const std::vector<CordRep*>& flats() const { return flats_; }

	static std::string ToString(testing::TestParamInfo<size_t> param) {
	return absl::StrCat(param.param, "_Flats");
	}

	private:
	std::string data_;
	Flats flats_;
	CordRepBtree* tree_;
	};

	INSTANTIATE_TEST_SUITE_P(
	WithParam, CordRepBtreeNavigatorTest,
	testing::Values(1, CordRepBtree::kMaxCapacity - 1,
	CordRepBtree::kMaxCapacity,
	CordRepBtree::kMaxCapacity* CordRepBtree::kMaxCapacity - 1,
	CordRepBtree::kMaxCapacity* CordRepBtree::kMaxCapacity,
	CordRepBtree::kMaxCapacity* CordRepBtree::kMaxCapacity + 1,
	CordRepBtree::kMaxCapacity* CordRepBtree::kMaxCapacity * 2 +
	17),
	CordRepBtreeNavigatorTest::ToString);

	TEST(CordRepBtreeNavigatorTest, Uninitialized) {
	CordRepBtreeNavigator nav;
	EXPECT_FALSE(nav);
	EXPECT_THAT(nav.btree(), Eq(nullptr));
	#if defined(GTEST_HAS_DEATH_TEST) && !defined(NDEBUG)
	EXPECT_DEATH(nav.Current(), ".*");
	#endif
	}

	TEST_P(CordRepBtreeNavigatorTest, InitFirst) {
	CordRepBtreeNavigator nav;
	CordRep* edge = nav.InitFirst(tree());
	EXPECT_TRUE(nav);
	EXPECT_THAT(nav.btree(), Eq(tree()));
	EXPECT_THAT(nav.Current(), Eq(flats().front()));
	EXPECT_THAT(edge, Eq(flats().front()));
	}

	TEST_P(CordRepBtreeNavigatorTest, InitLast) {
	CordRepBtreeNavigator nav;
	CordRep* edge = nav.InitLast(tree());
	EXPECT_TRUE(nav);
	EXPECT_THAT(nav.btree(), Eq(tree()));
	EXPECT_THAT(nav.Current(), Eq(flats().back()));
	EXPECT_THAT(edge, Eq(flats().back()));
	}

	TEST_P(CordRepBtreeNavigatorTest, NextPrev) {
	CordRepBtreeNavigator nav;
	nav.InitFirst(tree());
	const Flats& flats = this->flats();

	EXPECT_THAT(nav.Previous(), Eq(nullptr));
	EXPECT_THAT(nav.Current(), Eq(flats.front()));
	for (size_t i = 1; i < flats.size(); ++i) {
	ASSERT_THAT(nav.Next(), Eq(flats[i]));
	EXPECT_THAT(nav.Current(), Eq(flats[i]));
	}
	EXPECT_THAT(nav.Next(), Eq(nullptr));
	EXPECT_THAT(nav.Current(), Eq(flats.back()));
	for (size_t i = flats.size() - 1; i > 0; --i) {
	ASSERT_THAT(nav.Previous(), Eq(flats[i - 1]));
	EXPECT_THAT(nav.Current(), Eq(flats[i - 1]));
	}
	EXPECT_THAT(nav.Previous(), Eq(nullptr));
	EXPECT_THAT(nav.Current(), Eq(flats.front()));
	}

	TEST_P(CordRepBtreeNavigatorTest, PrevNext) {
	CordRepBtreeNavigator nav;
	nav.InitLast(tree());
	const Flats& flats = this->flats();

	EXPECT_THAT(nav.Next(), Eq(nullptr));
	EXPECT_THAT(nav.Current(), Eq(flats.back()));
	for (size_t i = flats.size() - 1; i > 0; --i) {
	ASSERT_THAT(nav.Previous(), Eq(flats[i - 1]));
	EXPECT_THAT(nav.Current(), Eq(flats[i - 1]));
	}
	EXPECT_THAT(nav.Previous(), Eq(nullptr));
	EXPECT_THAT(nav.Current(), Eq(flats.front()));
	for (size_t i = 1; i < flats.size(); ++i) {
	ASSERT_THAT(nav.Next(), Eq(flats[i]));
	EXPECT_THAT(nav.Current(), Eq(flats[i]));
	}
	EXPECT_THAT(nav.Next(), Eq(nullptr));
	EXPECT_THAT(nav.Current(), Eq(flats.back()));
	}

	TEST(CordRepBtreeNavigatorTest, Reset) {
	CordRepBtree* tree = CordRepBtree::Create(MakeFlat("abc"));
	CordRepBtreeNavigator nav;
	nav.InitFirst(tree);
	nav.Reset();
	EXPECT_FALSE(nav);
	EXPECT_THAT(nav.btree(), Eq(nullptr));
	#if defined(GTEST_HAS_DEATH_TEST) && !defined(NDEBUG)
	EXPECT_DEATH(nav.Current(), ".*");
	#endif
	CordRep::Unref(tree);
	}

	TEST_P(CordRepBtreeNavigatorTest, Skip) {
	size_t count = this->count();
	const Flats& flats = this->flats();
	CordRepBtreeNavigator nav;
	nav.InitFirst(tree());

	for (size_t char_offset = 0; char_offset < kCharsPerFlat; ++char_offset) {
	Position pos = nav.Skip(char_offset);
	EXPECT_THAT(pos.edge, Eq(nav.Current()));
	EXPECT_THAT(pos.edge, Eq(flats[0]));
	EXPECT_THAT(pos.offset, Eq(char_offset));
	}

	for (size_t index1 = 0; index1 < count; ++index1) {
	for (size_t index2 = index1; index2 < count; ++index2) {
	for (size_t char_offset = 0; char_offset < kCharsPerFlat; ++char_offset) {
	CordRepBtreeNavigator nav;
	nav.InitFirst(tree());

	size_t length1 = index1 * kCharsPerFlat;
	Position pos1 = nav.Skip(length1 + char_offset);
	ASSERT_THAT(pos1.edge, Eq(flats[index1]));
	ASSERT_THAT(pos1.edge, Eq(nav.Current()));
	ASSERT_THAT(pos1.offset, Eq(char_offset));

	size_t length2 = index2 * kCharsPerFlat;
	Position pos2 = nav.Skip(length2 - length1 + char_offset);
	ASSERT_THAT(pos2.edge, Eq(flats[index2]));
	ASSERT_THAT(pos2.edge, Eq(nav.Current()));
	ASSERT_THAT(pos2.offset, Eq(char_offset));
	}
	}
	}
	}

	TEST_P(CordRepBtreeNavigatorTest, Seek) {
	size_t count = this->count();
	const Flats& flats = this->flats();
	CordRepBtreeNavigator nav;
	nav.InitFirst(tree());

	for (size_t char_offset = 0; char_offset < kCharsPerFlat; ++char_offset) {
	Position pos = nav.Seek(char_offset);
	EXPECT_THAT(pos.edge, Eq(nav.Current()));
	EXPECT_THAT(pos.edge, Eq(flats[0]));
	EXPECT_THAT(pos.offset, Eq(char_offset));
	}

	for (size_t index = 0; index < count; ++index) {
	for (size_t char_offset = 0; char_offset < kCharsPerFlat; ++char_offset) {
	size_t offset = index * kCharsPerFlat + char_offset;
	Position pos1 = nav.Seek(offset);
	ASSERT_THAT(pos1.edge, Eq(flats[index]));
	ASSERT_THAT(pos1.edge, Eq(nav.Current()));
	ASSERT_THAT(pos1.offset, Eq(char_offset));
	}
	}
	}

	TEST(CordRepBtreeNavigatorTest, InitOffset) {
	// Whitebox: InitOffset() is implemented in terms of Seek() which is
	// exhaustively tested. Only test it initializes / forwards properly..
	CordRepBtree* tree = CordRepBtree::Create(MakeFlat("abc"));
	tree = CordRepBtree::Append(tree, MakeFlat("def"));
	CordRepBtreeNavigator nav;
	Position pos = nav.InitOffset(tree, 5);
	EXPECT_TRUE(nav);
	EXPECT_THAT(nav.btree(), Eq(tree));
	EXPECT_THAT(pos.edge, Eq(tree->Edges()[1]));
	EXPECT_THAT(pos.edge, Eq(nav.Current()));
	EXPECT_THAT(pos.offset, Eq(2u));
	CordRep::Unref(tree);
	}

	TEST(CordRepBtreeNavigatorTest, InitOffsetAndSeekBeyondLength) {
	CordRepBtree* tree1 = CordRepBtree::Create(MakeFlat("abc"));
	CordRepBtree* tree2 = CordRepBtree::Create(MakeFlat("def"));

	CordRepBtreeNavigator nav;
	nav.InitFirst(tree1);
	EXPECT_THAT(nav.Seek(3).edge, Eq(nullptr));
	EXPECT_THAT(nav.Seek(100).edge, Eq(nullptr));
	EXPECT_THAT(nav.btree(), Eq(tree1));
	EXPECT_THAT(nav.Current(), Eq(tree1->Edges().front()));

	EXPECT_THAT(nav.InitOffset(tree2, 3).edge, Eq(nullptr));
	EXPECT_THAT(nav.InitOffset(tree2, 100).edge, Eq(nullptr));
	EXPECT_THAT(nav.btree(), Eq(tree1));
	EXPECT_THAT(nav.Current(), Eq(tree1->Edges().front()));

	CordRep::Unref(tree1);
	CordRep::Unref(tree2);
	}

	TEST_P(CordRepBtreeNavigatorTest, Read) {
	const Flats& flats = this->flats();
	const std::string& data = this->data();

	for (size_t offset = 0; offset < data.size(); ++offset) {
	for (size_t length = 1; length <= data.size() - offset; ++length) {
	CordRepBtreeNavigator nav;
	nav.InitFirst(tree());

	// Skip towards edge holding offset
	size_t edge_offset = nav.Skip(offset).offset;

	// Read node
	ReadResult result = nav.Read(edge_offset, length);
	ASSERT_THAT(result.tree, Ne(nullptr));
	EXPECT_THAT(result.tree->length, Eq(length));
	if (result.tree->tag == BTREE) {
	ASSERT_TRUE(CordRepBtree::IsValid(result.tree->btree()));
	}

	// Verify contents
	std::string value = CordToString(result.tree);
	EXPECT_THAT(value, Eq(data.substr(offset, length)));

	// Verify 'partial last edge' reads.
	size_t partial = (offset + length) % kCharsPerFlat;
	ASSERT_THAT(result.n, Eq(partial));

	// Verify ending position if not EOF
	if (offset + length < data.size()) {
	size_t index = (offset + length) / kCharsPerFlat;
	EXPECT_THAT(nav.Current(), Eq(flats[index]));
	}

	CordRep::Unref(result.tree);
	}
	}
	}

	TEST_P(CordRepBtreeNavigatorTest, ReadBeyondLengthOfTree) {
	CordRepBtreeNavigator nav;
	nav.InitFirst(tree());
	ReadResult result = nav.Read(2, tree()->length);
	ASSERT_THAT(result.tree, Eq(nullptr));
	}

	TEST(CordRepBtreeNavigatorTest, NavigateMaximumTreeDepth) {
	CordRepFlat* flat1 = MakeFlat("Hello world");
	CordRepFlat* flat2 = MakeFlat("World Hello");

	CordRepBtree* node = CordRepBtree::Create(flat1);
	node = CordRepBtree::Append(node, flat2);
	while (node->height() < CordRepBtree::kMaxHeight) {
	node = CordRepBtree::New(node);
	}

	CordRepBtreeNavigator nav;
	CordRep* edge = nav.InitFirst(node);
	EXPECT_THAT(edge, Eq(flat1));
	EXPECT_THAT(nav.Next(), Eq(flat2));
	EXPECT_THAT(nav.Next(), Eq(nullptr));
	EXPECT_THAT(nav.Previous(), Eq(flat1));
	EXPECT_THAT(nav.Previous(), Eq(nullptr));

	CordRep::Unref(node);
	}

	} // namespace
	} // namespace cord_internal
	ABSL_NAMESPACE_END
	} // namespace absl