src/session/internal/candidate_list.cc - mozc - Git at Google

 // Copyright 2010-2015, Google Inc.
 // All rights reserved.
 //
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 // notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 // copyright notice, this list of conditions and the following disclaimer
 // in the documentation and/or other materials provided with the
 // distribution.
 //     * Neither the name of Google Inc. nor the names of its
 // contributors may be used to endorse or promote products derived from
 // this software without specific prior written permission.
 //
 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

 // CandidateList and Candidate classes to be used with Session class.

 #include "session/internal/candidate_list.h"

 #include <algorithm>
 #include <map>
 #include <string>
 #include <vector>

 #include "base/freelist.h"
 #include "base/logging.h"
 #include "base/port.h"
 #include "base/util.h"

 namespace mozc {
 namespace session {

 Candidate::Candidate()
     : id_(0),
       attributes_(NO_ATTRIBUTES),
       subcandidate_list_(NULL),
       subcandidate_list_owner_(false) {}

 Candidate::~Candidate() {}

 void Candidate::Clear() {
   id_ = 0;
   attributes_ = NO_ATTRIBUTES;
   if (subcandidate_list_owner_ && subcandidate_list_ != NULL) {
     delete subcandidate_list_;
   }
   subcandidate_list_ = NULL;
   subcandidate_list_owner_ = false;
 }

 int Candidate::id() const {
   return id_;
 }

 void Candidate::set_id(const int id) {
   id_ = id;
 }

 Attributes Candidate::attributes() const {
   return attributes_;
 }

 void Candidate::add_attributes(const Attributes attributes) {
   attributes_ |= attributes;
 }

 void Candidate::set_attributes(const Attributes attributes) {
   attributes_ = attributes;
 }

 bool Candidate::has_attributes(const Attributes attributes) const {
   return (attributes_ & attributes) == attributes;
 }

 bool Candidate::IsSubcandidateList() const {
   return (subcandidate_list_ != NULL);
 }

 const CandidateList &Candidate::subcandidate_list() const {
   return *subcandidate_list_;
 }

 CandidateList *Candidate::mutable_subcandidate_list() {
   return subcandidate_list_;
 }

 CandidateList *Candidate::allocate_subcandidate_list(const bool rotate) {
   subcandidate_list_ = new CandidateList(rotate);
   subcandidate_list_owner_ = true;
   return subcandidate_list_;
 }

 void Candidate::set_subcandidate_list(CandidateList *subcandidate_list) {
   subcandidate_list_ = subcandidate_list;
 }


 static const size_t kDefaultPageSize = 9;

 CandidateList::CandidateList(const bool rotate)
     : rotate_(rotate),
       page_size_(kDefaultPageSize),
       focused_index_(0),
       focused_(false),
       candidate_pool_(new ObjectPool<Candidate>(kDefaultPageSize)),
       candidates_(new vector<Candidate *>),
       next_available_id_(0),
       added_candidates_(new map<uint64, int>),
       alternative_ids_(new map<int, int>) {
 }

 CandidateList::~CandidateList() {
   Clear();
 }

 void CandidateList::Clear() {
   vector<Candidate *>::iterator it;
   for (it = candidates_->begin(); it != candidates_->end(); ++it) {
     (*it)->Clear();
     candidate_pool_->Release(*it);
   }
   focused_index_ = 0;
   focused_ = false;
   candidates_->clear();
   next_available_id_ = 0;
   added_candidates_->clear();
   alternative_ids_->clear();
 }

 const Candidate &CandidateList::GetDeepestFocusedCandidate() const {
   if (focused_candidate().IsSubcandidateList()) {
     return focused_candidate().subcandidate_list().GetDeepestFocusedCandidate();
   }
   return focused_candidate();
 }

 void CandidateList::AddCandidate(const int id, const string &value) {
   AddCandidateWithAttributes(id, value, NO_ATTRIBUTES);
 }

 void CandidateList::AddCandidateWithAttributes(const int id,
                                                const string &value,
                                                const Attributes attributes) {
   if (id >= 0) {
     DCHECK(id >= next_available_id_);
     // If id is not for T13N candidate, update |last_added_id_|.
     next_available_id_ = id + 1;
   }

   // If the value has already been stored in the candidate list, reuse it and
   // update the alternative_ids_.
   const uint64 fp = Util::Fingerprint(value);

   const pair<map<uint64, int>::iterator, bool> result =
     added_candidates_->insert(make_pair(fp, id));
   if (!result.second) {  // insertion was failed.
     const int alt_id = result.first->second;
     (*alternative_ids_)[id] = alt_id;

     // Add attributes to the existing candidate.
     for (size_t i = 0; i < size(); ++i) {
       if (candidate(i).id() == alt_id) {
         (*candidates_)[i]->add_attributes(attributes);
       }
     }
     return;
   }

   Candidate *new_candidate = candidate_pool_->Alloc();
   candidates_->push_back(new_candidate);

   new_candidate->set_id(id);
   new_candidate->set_attributes(attributes);
 }

 void CandidateList::AddSubCandidateList(CandidateList *subcandidate_list) {
   Candidate *new_candidate = candidate_pool_->Alloc();
   candidates_->push_back(new_candidate);

   new_candidate->set_subcandidate_list(subcandidate_list);
 }

 CandidateList *CandidateList::AllocateSubCandidateList(const bool rotate) {
   Candidate *new_candidate = candidate_pool_->Alloc();
   candidates_->push_back(new_candidate);

   return new_candidate->allocate_subcandidate_list(rotate);
 }

 void CandidateList::set_name(const string &name) {
   name_ = name;
 }

 const string &CandidateList::name() const {
   return name_;
 }

 void CandidateList::set_page_size(const size_t page_size) {
   page_size_ = page_size;
 }

 size_t CandidateList::page_size() const {
   return page_size_;
 }

 size_t CandidateList::size() const {
   return candidates_->size();
 }

 size_t CandidateList::last_index() const {
   return size() - 1;
 }

 const Candidate &CandidateList::focused_candidate() const {
   return candidate(focused_index_);
 }

 const Candidate &CandidateList::candidate(const size_t index) const {
   return *(*candidates_)[index];
 }

 bool CandidateList::focused() const {
   return focused_;
 }

 void CandidateList::set_focused(const bool focused) {
   focused_ = focused;
 }

 int CandidateList::focused_id() const {
   // If the list does not have any candidate, 0 will be returned.
   if (size() == 0) {
     return 0;
   }
   if (focused_candidate().IsSubcandidateList()) {
     return focused_candidate().subcandidate_list().focused_id();
   }
   return focused_candidate().id();
 }

 size_t CandidateList::focused_index() const {
   return focused_index_;
 }

 int CandidateList::next_available_id() const {
   int result = next_available_id_;
   for (size_t i = 0; i < candidates_->size(); ++i) {
     if (candidate(i).IsSubcandidateList()) {
       const int sub_available_id =
           candidate(i).subcandidate_list().next_available_id();
       if (result < sub_available_id) {
         result = sub_available_id;
       }
     }
   }
   return result;
 }

 void CandidateList::GetPageRange(const size_t index,
                                  size_t *page_begin,
                                  size_t *page_end) const {
   *page_begin = index - (index % page_size_);
   *page_end = min(last_index(), *page_begin + page_size_ - 1);
 }

 void CandidateList::MoveFirst() {
   focused_index_ = 0;
 }

 void CandidateList::MoveLast() {
   focused_index_ = last_index();
 }

 bool CandidateList::MoveNext() {
   // If the current candidate points to subcandidate list, the focused
   // candidate in the subcandidate list will be operated.
   if (focused_candidate().IsSubcandidateList() &&
       mutable_focused_subcandidate_list()->MoveNext()) {
     return true;
   }

   if (IsLast(focused_index_)) {
     MoveFirst();
     if (!rotate_) {
       // If this candidate list does not rotate, the focused candidate
       // is moved to the parent candidate list.
       return false;
     }
   } else {
     ++focused_index_;
   }

   // If the new current candidate points to subcandidate list, the
   // focused candidate in the subcandidate list should be the first
   // candidate.
   if (focused_candidate().IsSubcandidateList()) {
     mutable_focused_subcandidate_list()->MoveFirst();
   }
   return true;
 }

 bool CandidateList::MovePrev() {
   // If the current candidate points to subcandidate list, the focused
   // candidate in the subcandidate list will be operated.
   if (focused_candidate().IsSubcandidateList() &&
       mutable_focused_subcandidate_list()->MovePrev()) {
     return true;
   }

   if (IsFirst(focused_index_)) {
     MoveLast();
     if (!rotate_) {
       // If this candidate list does not rotate, the focused candidate
       // is moved to the parent candidate list.
       return false;
     }
   } else {
     --focused_index_;
   }

   // If the new current candidate points to subcandidate list, the
   // focused candidate in the subcandidate list should be the first
   // candidate.
   if (focused_candidate().IsSubcandidateList()) {
     mutable_focused_subcandidate_list()->MoveLast();
   }
   return true;
 }

 bool CandidateList::MoveNextPage() {
   if (focused_candidate().IsSubcandidateList() &&
       mutable_focused_subcandidate_list()->MoveNextPage()) {
     return true;
   }

   if (IsLastPage(focused_index_)) {
     if (!rotate_) {
       // If the current candidate is the last candidate and rotation
       // should not be performed, this function does nothing and
       // returns false.
       return false;
     }
     MoveFirst();
   } else {
     focused_index_ += page_size_;
   }
   // Move the forcused index to the beginning of the page.
   focused_index_ -= (focused_index_ % page_size_);

   // If the new current candidate points to subcandidate list, the
   // focused candidate in the subcandidate list should be the first
   // candidate.
   if (focused_candidate().IsSubcandidateList()) {
     mutable_focused_subcandidate_list()->MoveFirst();
   }
   return true;
 }

 bool CandidateList::MovePrevPage() {
   if (focused_candidate().IsSubcandidateList() &&
       mutable_focused_subcandidate_list()->MovePrevPage()) {
     return true;
   }

   if (IsFirstPage(focused_index_)) {
     if (!rotate_) {
       // If the current candidate is on the first page and rotation
       // should not be performed, this function does nothing and
       // returns false.
       return false;
     }
     MoveLast();
   } else {
     // The focused index in not on the first page, so the value of
     // (focused_index_ - page_size_) must be a positive value.
     focused_index_ -= page_size_;
   }
   // Move the forcused index to the beginning of the page.
   focused_index_ -= (focused_index_ % page_size_);

   // If the new current candidate points to subcandidate list, the
   // focused candidate in the subcandidate list should be the first
   // candidate.  Note the forcused index will be moved to the
   // beginning of the page on page moves.
   if (focused_candidate().IsSubcandidateList()) {
     mutable_focused_subcandidate_list()->MoveFirst();
   }
   return true;
 }

 bool CandidateList::MoveNextAttributes(const Attributes attributes) {
   // Move one candidate.
   MoveNext();
   return MoveToAttributes(attributes);
 }

 bool CandidateList::MoveToAttributes(const Attributes attributes) {
   const size_t cand_size = size();
   for (size_t i = 0; i < cand_size; ++i) {
     // Shift the index to make the first index focused_index_.
     const size_t index = (focused_index_ + i) % cand_size;

     Candidate *cand =  (*candidates_)[index];

     // If the candidate is a subcandidate list, the subcandidate list is
     // traversed recursively.
     if (cand->IsSubcandidateList() &&
         cand->mutable_subcandidate_list()->MoveToAttributes(attributes)) {
       focused_index_ = index;
       return true;
     } else if (cand->has_attributes(attributes)) {
       focused_index_ = index;
       return true;
     }
   }

   return false;
 }

 bool CandidateList::MoveToId(const int base_id) {
   int id = base_id;

   // If an alternative id for the base_id found, use it to avoid
   // duplicated candidates.
   if (alternative_ids_->find(id) != alternative_ids_->end()) {
     id = (*alternative_ids_)[id];
   }

   // NOTE(komatsu): Although this function's order is O(N), The size
   // of N is less than kMaxCandidateSize (= 200).  So it would not be
   // a problem.
   for (size_t i = 0; i < size(); ++i) {
     Candidate *cand =  (*candidates_)[i];
     // If the candidate is a subcandidate list, the subcandidate list is
     // traversed recursively.
     if (cand->IsSubcandidateList() &&
         cand->mutable_subcandidate_list()->MoveToId(id)) {
       focused_index_ = i;
       return true;
     } else if (cand->id() == id) {
       focused_index_ = i;
       return true;
     }
   }
   return false;
 }

 bool CandidateList::MoveToPageIndex(const size_t page_index) {
   size_t begin = 0;
   size_t end = 0;
   GetPageRange(focused_index_, &begin, &end);
   if (begin + page_index > end) {
     return false;
   }
   focused_index_ = begin + page_index;
   if (focused_candidate().IsSubcandidateList()) {
     mutable_focused_subcandidate_list()->MoveFirst();
   }
   return true;
 }

 CandidateList *CandidateList::mutable_focused_subcandidate_list() {
   CHECK(focused_candidate().IsSubcandidateList());
   return (*candidates_)[focused_index_]->mutable_subcandidate_list();
 }

 bool CandidateList::IsFirst(const size_t index) const {
   return (index == 0);
 }

 bool CandidateList::IsLast(const size_t index) const {
   return (index == size() - 1);
 }

 bool CandidateList::IsFirstPage(const size_t index) const {
   return (index < page_size_);
 }

 bool CandidateList::IsLastPage(const size_t index) const {
   size_t begin = 0;
   size_t end = 0;
   GetPageRange(index, &begin, &end);
   return end == last_index();
 }

 }  // namespace session
 }  // namespace mozc
	// Copyright 2010-2015, Google Inc.
	// All rights reserved.
	//
	// Redistribution and use in source and binary forms, with or without
	// modification, are permitted provided that the following conditions are
	// met:
	//
	// * Redistributions of source code must retain the above copyright
	// notice, this list of conditions and the following disclaimer.
	// * Redistributions in binary form must reproduce the above
	// copyright notice, this list of conditions and the following disclaimer
	// in the documentation and/or other materials provided with the
	// distribution.
	// * Neither the name of Google Inc. nor the names of its
	// contributors may be used to endorse or promote products derived from
	// this software without specific prior written permission.
	//
	// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
	// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
	// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
	// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
	// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
	// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
	// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
	// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
	// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
	// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
	// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

	// CandidateList and Candidate classes to be used with Session class.

	#include "session/internal/candidate_list.h"

	#include <algorithm>
	#include <map>
	#include <string>
	#include <vector>

	#include "base/freelist.h"
	#include "base/logging.h"
	#include "base/port.h"
	#include "base/util.h"

	namespace mozc {
	namespace session {

	Candidate::Candidate()
	: id_(0),
	attributes_(NO_ATTRIBUTES),
	subcandidate_list_(NULL),
	subcandidate_list_owner_(false) {}

	Candidate::~Candidate() {}

	void Candidate::Clear() {
	id_ = 0;
	attributes_ = NO_ATTRIBUTES;
	if (subcandidate_list_owner_ && subcandidate_list_ != NULL) {
	delete subcandidate_list_;
	}
	subcandidate_list_ = NULL;
	subcandidate_list_owner_ = false;
	}

	int Candidate::id() const {
	return id_;
	}

	void Candidate::set_id(const int id) {
	id_ = id;
	}

	Attributes Candidate::attributes() const {
	return attributes_;
	}

	void Candidate::add_attributes(const Attributes attributes) {
	attributes_ \|= attributes;
	}

	void Candidate::set_attributes(const Attributes attributes) {
	attributes_ = attributes;
	}

	bool Candidate::has_attributes(const Attributes attributes) const {
	return (attributes_ & attributes) == attributes;
	}

	bool Candidate::IsSubcandidateList() const {
	return (subcandidate_list_ != NULL);
	}

	const CandidateList &Candidate::subcandidate_list() const {
	return *subcandidate_list_;
	}

	CandidateList *Candidate::mutable_subcandidate_list() {
	return subcandidate_list_;
	}

	CandidateList *Candidate::allocate_subcandidate_list(const bool rotate) {
	subcandidate_list_ = new CandidateList(rotate);
	subcandidate_list_owner_ = true;
	return subcandidate_list_;
	}

	void Candidate::set_subcandidate_list(CandidateList *subcandidate_list) {
	subcandidate_list_ = subcandidate_list;
	}


	static const size_t kDefaultPageSize = 9;

	CandidateList::CandidateList(const bool rotate)
	: rotate_(rotate),
	page_size_(kDefaultPageSize),
	focused_index_(0),
	focused_(false),
	candidate_pool_(new ObjectPool<Candidate>(kDefaultPageSize)),
	candidates_(new vector<Candidate *>),
	next_available_id_(0),
	added_candidates_(new map<uint64, int>),
	alternative_ids_(new map<int, int>) {
	}

	CandidateList::~CandidateList() {
	Clear();
	}

	void CandidateList::Clear() {
	vector<Candidate *>::iterator it;
	for (it = candidates_->begin(); it != candidates_->end(); ++it) {
	(*it)->Clear();
	candidate_pool_->Release(*it);
	}
	focused_index_ = 0;
	focused_ = false;
	candidates_->clear();
	next_available_id_ = 0;
	added_candidates_->clear();
	alternative_ids_->clear();
	}

	const Candidate &CandidateList::GetDeepestFocusedCandidate() const {
	if (focused_candidate().IsSubcandidateList()) {
	return focused_candidate().subcandidate_list().GetDeepestFocusedCandidate();
	}
	return focused_candidate();
	}

	void CandidateList::AddCandidate(const int id, const string &value) {
	AddCandidateWithAttributes(id, value, NO_ATTRIBUTES);
	}

	void CandidateList::AddCandidateWithAttributes(const int id,
	const string &value,
	const Attributes attributes) {
	if (id >= 0) {
	DCHECK(id >= next_available_id_);
	// If id is not for T13N candidate, update \|last_added_id_\|.
	next_available_id_ = id + 1;
	}

	// If the value has already been stored in the candidate list, reuse it and
	// update the alternative_ids_.
	const uint64 fp = Util::Fingerprint(value);

	const pair<map<uint64, int>::iterator, bool> result =
	added_candidates_->insert(make_pair(fp, id));
	if (!result.second) { // insertion was failed.
	const int alt_id = result.first->second;
	(*alternative_ids_)[id] = alt_id;

	// Add attributes to the existing candidate.
	for (size_t i = 0; i < size(); ++i) {
	if (candidate(i).id() == alt_id) {
	(*candidates_)[i]->add_attributes(attributes);
	}
	}
	return;
	}

	Candidate *new_candidate = candidate_pool_->Alloc();
	candidates_->push_back(new_candidate);

	new_candidate->set_id(id);
	new_candidate->set_attributes(attributes);
	}

	void CandidateList::AddSubCandidateList(CandidateList *subcandidate_list) {
	Candidate *new_candidate = candidate_pool_->Alloc();
	candidates_->push_back(new_candidate);

	new_candidate->set_subcandidate_list(subcandidate_list);
	}

	CandidateList *CandidateList::AllocateSubCandidateList(const bool rotate) {
	Candidate *new_candidate = candidate_pool_->Alloc();
	candidates_->push_back(new_candidate);

	return new_candidate->allocate_subcandidate_list(rotate);
	}

	void CandidateList::set_name(const string &name) {
	name_ = name;
	}

	const string &CandidateList::name() const {
	return name_;
	}

	void CandidateList::set_page_size(const size_t page_size) {
	page_size_ = page_size;
	}

	size_t CandidateList::page_size() const {
	return page_size_;
	}

	size_t CandidateList::size() const {
	return candidates_->size();
	}

	size_t CandidateList::last_index() const {
	return size() - 1;
	}

	const Candidate &CandidateList::focused_candidate() const {
	return candidate(focused_index_);
	}

	const Candidate &CandidateList::candidate(const size_t index) const {
	return (candidates_)[index];
	}

	bool CandidateList::focused() const {
	return focused_;
	}

	void CandidateList::set_focused(const bool focused) {
	focused_ = focused;
	}

	int CandidateList::focused_id() const {
	// If the list does not have any candidate, 0 will be returned.
	if (size() == 0) {
	return 0;
	}
	if (focused_candidate().IsSubcandidateList()) {
	return focused_candidate().subcandidate_list().focused_id();
	}
	return focused_candidate().id();
	}

	size_t CandidateList::focused_index() const {
	return focused_index_;
	}

	int CandidateList::next_available_id() const {
	int result = next_available_id_;
	for (size_t i = 0; i < candidates_->size(); ++i) {
	if (candidate(i).IsSubcandidateList()) {
	const int sub_available_id =
	candidate(i).subcandidate_list().next_available_id();
	if (result < sub_available_id) {
	result = sub_available_id;
	}
	}
	}
	return result;
	}

	void CandidateList::GetPageRange(const size_t index,
	size_t *page_begin,
	size_t *page_end) const {
	*page_begin = index - (index % page_size_);
	page_end = min(last_index(), page_begin + page_size_ - 1);
	}

	void CandidateList::MoveFirst() {
	focused_index_ = 0;
	}

	void CandidateList::MoveLast() {
	focused_index_ = last_index();
	}

	bool CandidateList::MoveNext() {
	// If the current candidate points to subcandidate list, the focused
	// candidate in the subcandidate list will be operated.
	if (focused_candidate().IsSubcandidateList() &&
	mutable_focused_subcandidate_list()->MoveNext()) {
	return true;
	}

	if (IsLast(focused_index_)) {
	MoveFirst();
	if (!rotate_) {
	// If this candidate list does not rotate, the focused candidate
	// is moved to the parent candidate list.
	return false;
	}
	} else {
	++focused_index_;
	}

	// If the new current candidate points to subcandidate list, the
	// focused candidate in the subcandidate list should be the first
	// candidate.
	if (focused_candidate().IsSubcandidateList()) {
	mutable_focused_subcandidate_list()->MoveFirst();
	}
	return true;
	}

	bool CandidateList::MovePrev() {
	// If the current candidate points to subcandidate list, the focused
	// candidate in the subcandidate list will be operated.
	if (focused_candidate().IsSubcandidateList() &&
	mutable_focused_subcandidate_list()->MovePrev()) {
	return true;
	}

	if (IsFirst(focused_index_)) {
	MoveLast();
	if (!rotate_) {
	// If this candidate list does not rotate, the focused candidate
	// is moved to the parent candidate list.
	return false;
	}
	} else {
	--focused_index_;
	}

	// If the new current candidate points to subcandidate list, the
	// focused candidate in the subcandidate list should be the first
	// candidate.
	if (focused_candidate().IsSubcandidateList()) {
	mutable_focused_subcandidate_list()->MoveLast();
	}
	return true;
	}

	bool CandidateList::MoveNextPage() {
	if (focused_candidate().IsSubcandidateList() &&
	mutable_focused_subcandidate_list()->MoveNextPage()) {
	return true;
	}

	if (IsLastPage(focused_index_)) {
	if (!rotate_) {
	// If the current candidate is the last candidate and rotation
	// should not be performed, this function does nothing and
	// returns false.
	return false;
	}
	MoveFirst();
	} else {
	focused_index_ += page_size_;
	}
	// Move the forcused index to the beginning of the page.
	focused_index_ -= (focused_index_ % page_size_);

	// If the new current candidate points to subcandidate list, the
	// focused candidate in the subcandidate list should be the first
	// candidate.
	if (focused_candidate().IsSubcandidateList()) {
	mutable_focused_subcandidate_list()->MoveFirst();
	}
	return true;
	}

	bool CandidateList::MovePrevPage() {
	if (focused_candidate().IsSubcandidateList() &&
	mutable_focused_subcandidate_list()->MovePrevPage()) {
	return true;
	}

	if (IsFirstPage(focused_index_)) {
	if (!rotate_) {
	// If the current candidate is on the first page and rotation
	// should not be performed, this function does nothing and
	// returns false.
	return false;
	}
	MoveLast();
	} else {
	// The focused index in not on the first page, so the value of
	// (focused_index_ - page_size_) must be a positive value.
	focused_index_ -= page_size_;
	}
	// Move the forcused index to the beginning of the page.
	focused_index_ -= (focused_index_ % page_size_);

	// If the new current candidate points to subcandidate list, the
	// focused candidate in the subcandidate list should be the first
	// candidate. Note the forcused index will be moved to the
	// beginning of the page on page moves.
	if (focused_candidate().IsSubcandidateList()) {
	mutable_focused_subcandidate_list()->MoveFirst();
	}
	return true;
	}

	bool CandidateList::MoveNextAttributes(const Attributes attributes) {
	// Move one candidate.
	MoveNext();
	return MoveToAttributes(attributes);
	}

	bool CandidateList::MoveToAttributes(const Attributes attributes) {
	const size_t cand_size = size();
	for (size_t i = 0; i < cand_size; ++i) {
	// Shift the index to make the first index focused_index_.
	const size_t index = (focused_index_ + i) % cand_size;

	Candidate cand = (candidates_)[index];

	// If the candidate is a subcandidate list, the subcandidate list is
	// traversed recursively.
	if (cand->IsSubcandidateList() &&
	cand->mutable_subcandidate_list()->MoveToAttributes(attributes)) {
	focused_index_ = index;
	return true;
	} else if (cand->has_attributes(attributes)) {
	focused_index_ = index;
	return true;
	}
	}

	return false;
	}

	bool CandidateList::MoveToId(const int base_id) {
	int id = base_id;

	// If an alternative id for the base_id found, use it to avoid
	// duplicated candidates.
	if (alternative_ids_->find(id) != alternative_ids_->end()) {
	id = (*alternative_ids_)[id];
	}

	// NOTE(komatsu): Although this function's order is O(N), The size
	// of N is less than kMaxCandidateSize (= 200). So it would not be
	// a problem.
	for (size_t i = 0; i < size(); ++i) {
	Candidate cand = (candidates_)[i];
	// If the candidate is a subcandidate list, the subcandidate list is
	// traversed recursively.
	if (cand->IsSubcandidateList() &&
	cand->mutable_subcandidate_list()->MoveToId(id)) {
	focused_index_ = i;
	return true;
	} else if (cand->id() == id) {
	focused_index_ = i;
	return true;
	}
	}
	return false;
	}

	bool CandidateList::MoveToPageIndex(const size_t page_index) {
	size_t begin = 0;
	size_t end = 0;
	GetPageRange(focused_index_, &begin, &end);
	if (begin + page_index > end) {
	return false;
	}
	focused_index_ = begin + page_index;
	if (focused_candidate().IsSubcandidateList()) {
	mutable_focused_subcandidate_list()->MoveFirst();
	}
	return true;
	}

	CandidateList *CandidateList::mutable_focused_subcandidate_list() {
	CHECK(focused_candidate().IsSubcandidateList());
	return (*candidates_)[focused_index_]->mutable_subcandidate_list();
	}

	bool CandidateList::IsFirst(const size_t index) const {
	return (index == 0);
	}

	bool CandidateList::IsLast(const size_t index) const {
	return (index == size() - 1);
	}

	bool CandidateList::IsFirstPage(const size_t index) const {
	return (index < page_size_);
	}

	bool CandidateList::IsLastPage(const size_t index) const {
	size_t begin = 0;
	size_t end = 0;
	GetPageRange(index, &begin, &end);
	return end == last_index();
	}

	} // namespace session
	} // namespace mozc