138c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka/* 238c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka * Copyright (C) 2012 The Android Open Source Project 338c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka * 438c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka * Licensed under the Apache License, Version 2.0 (the "License"); 538c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka * you may not use this file except in compliance with the License. 638c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka * You may obtain a copy of the License at 738c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka * 838c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka * http://www.apache.org/licenses/LICENSE-2.0 938c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka * 1038c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka * Unless required by applicable law or agreed to in writing, software 1138c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka * distributed under the License is distributed on an "AS IS" BASIS, 1238c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1338c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka * See the License for the specific language governing permissions and 1438c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka * limitations under the License. 1538c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka */ 1638c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka 1738c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka#ifndef LATINIME_DIC_NODE_PRIORITY_QUEUE_H 1838c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka#define LATINIME_DIC_NODE_PRIORITY_QUEUE_H 1938c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka 20865e6cf49764f3a411ee32861d927b15653ee398Keisuke Kuroyanagi#include <algorithm> 2138c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka#include <queue> 2238c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka#include <vector> 2338c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka 2438c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka#include "defines.h" 25a65c267b1f1207e54c6f821148c600e3899b7f9cKen Wakasa#include "suggest/core/dicnode/dic_node.h" 2667ff21f3217c9f2ff81beac6f29f5c35a83da228Keisuke Kuroyanagi#include "suggest/core/dicnode/dic_node_pool.h" 2738c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka 2838c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataokanamespace latinime { 2938c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka 3067ff21f3217c9f2ff81beac6f29f5c35a83da228Keisuke Kuroyanagiclass DicNodePriorityQueue { 3138c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka public: 3280ca7abea32a97acefcd8a8cb6145f0cdc8f0503Keisuke Kuroyanagi AK_FORCE_INLINE explicit DicNodePriorityQueue(const int capacity) 3367ff21f3217c9f2ff81beac6f29f5c35a83da228Keisuke Kuroyanagi : mMaxSize(capacity), mDicNodesQueue(), mDicNodePool(capacity) { 3467ff21f3217c9f2ff81beac6f29f5c35a83da228Keisuke Kuroyanagi clear(); 3538c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka } 3638c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka 3738c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka // Non virtual inline destructor -- never inherit this class 3838c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka AK_FORCE_INLINE ~DicNodePriorityQueue() {} 3938c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka 4067ff21f3217c9f2ff81beac6f29f5c35a83da228Keisuke Kuroyanagi AK_FORCE_INLINE int getSize() const { 4138c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka return static_cast<int>(mDicNodesQueue.size()); 4238c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka } 4338c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka 4467ff21f3217c9f2ff81beac6f29f5c35a83da228Keisuke Kuroyanagi AK_FORCE_INLINE int getMaxSize() const { 4538c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka return mMaxSize; 4638c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka } 4738c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka 4838c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka AK_FORCE_INLINE void setMaxSize(const int maxSize) { 4967ff21f3217c9f2ff81beac6f29f5c35a83da228Keisuke Kuroyanagi mMaxSize = maxSize; 5038c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka } 5138c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka 5238c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka AK_FORCE_INLINE void clear() { 5338c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka clearAndResize(mMaxSize); 5438c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka } 5538c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka 5638c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka AK_FORCE_INLINE void clearAndResize(const int maxSize) { 5767ff21f3217c9f2ff81beac6f29f5c35a83da228Keisuke Kuroyanagi mMaxSize = maxSize; 5838c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka while (!mDicNodesQueue.empty()) { 5938c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka mDicNodesQueue.pop(); 6038c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka } 6167ff21f3217c9f2ff81beac6f29f5c35a83da228Keisuke Kuroyanagi mDicNodePool.reset(mMaxSize + 1); 6238c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka } 6338c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka 6467ff21f3217c9f2ff81beac6f29f5c35a83da228Keisuke Kuroyanagi AK_FORCE_INLINE void copyPush(const DicNode *const dicNode) { 6567ff21f3217c9f2ff81beac6f29f5c35a83da228Keisuke Kuroyanagi DicNode *const pooledDicNode = newDicNode(dicNode); 6667ff21f3217c9f2ff81beac6f29f5c35a83da228Keisuke Kuroyanagi if (!pooledDicNode) { 6767ff21f3217c9f2ff81beac6f29f5c35a83da228Keisuke Kuroyanagi return; 6867ff21f3217c9f2ff81beac6f29f5c35a83da228Keisuke Kuroyanagi } 6967ff21f3217c9f2ff81beac6f29f5c35a83da228Keisuke Kuroyanagi if (getSize() < mMaxSize) { 7067ff21f3217c9f2ff81beac6f29f5c35a83da228Keisuke Kuroyanagi mDicNodesQueue.push(pooledDicNode); 7167ff21f3217c9f2ff81beac6f29f5c35a83da228Keisuke Kuroyanagi return; 7267ff21f3217c9f2ff81beac6f29f5c35a83da228Keisuke Kuroyanagi } 7367ff21f3217c9f2ff81beac6f29f5c35a83da228Keisuke Kuroyanagi if (betterThanWorstDicNode(pooledDicNode)) { 7467ff21f3217c9f2ff81beac6f29f5c35a83da228Keisuke Kuroyanagi mDicNodePool.placeBackInstance(mDicNodesQueue.top()); 7567ff21f3217c9f2ff81beac6f29f5c35a83da228Keisuke Kuroyanagi mDicNodesQueue.pop(); 7667ff21f3217c9f2ff81beac6f29f5c35a83da228Keisuke Kuroyanagi mDicNodesQueue.push(pooledDicNode); 7767ff21f3217c9f2ff81beac6f29f5c35a83da228Keisuke Kuroyanagi return; 7867ff21f3217c9f2ff81beac6f29f5c35a83da228Keisuke Kuroyanagi } 7967ff21f3217c9f2ff81beac6f29f5c35a83da228Keisuke Kuroyanagi mDicNodePool.placeBackInstance(pooledDicNode); 8038c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka } 8138c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka 8267ff21f3217c9f2ff81beac6f29f5c35a83da228Keisuke Kuroyanagi AK_FORCE_INLINE void copyPop(DicNode *const dest) { 8338c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka if (mDicNodesQueue.empty()) { 8438c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka ASSERT(false); 8538c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka return; 8638c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka } 8738c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka DicNode *node = mDicNodesQueue.top(); 8838c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka if (dest) { 8938c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka DicNodeUtils::initByCopy(node, dest); 9038c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka } 9167ff21f3217c9f2ff81beac6f29f5c35a83da228Keisuke Kuroyanagi mDicNodePool.placeBackInstance(node); 9238c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka mDicNodesQueue.pop(); 9338c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka } 9438c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka 9567ff21f3217c9f2ff81beac6f29f5c35a83da228Keisuke Kuroyanagi AK_FORCE_INLINE void dump() { 9667ff21f3217c9f2ff81beac6f29f5c35a83da228Keisuke Kuroyanagi mDicNodePool.dump(); 9738c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka } 9838c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka 9938c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka private: 10080ca7abea32a97acefcd8a8cb6145f0cdc8f0503Keisuke Kuroyanagi DISALLOW_IMPLICIT_CONSTRUCTORS(DicNodePriorityQueue); 10138c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka 102655b65cb0ba8d803c9f57b5e06dc242f77769883Keisuke Kuroyanagi AK_FORCE_INLINE static bool compareDicNode(const DicNode *const left, 103655b65cb0ba8d803c9f57b5e06dc242f77769883Keisuke Kuroyanagi const DicNode *const right) { 10438c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka return left->compare(right); 10538c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka } 10638c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka 10738c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka struct DicNodeComparator { 10867ff21f3217c9f2ff81beac6f29f5c35a83da228Keisuke Kuroyanagi bool operator ()(const DicNode *left, const DicNode *right) const { 10938c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka return compareDicNode(left, right); 11038c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka } 11138c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka }; 11238c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka 11338c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka typedef std::priority_queue<DicNode *, std::vector<DicNode *>, DicNodeComparator> DicNodesQueue; 11438c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka int mMaxSize; 11538c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka DicNodesQueue mDicNodesQueue; 11667ff21f3217c9f2ff81beac6f29f5c35a83da228Keisuke Kuroyanagi DicNodePool mDicNodePool; 11738c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka 118655b65cb0ba8d803c9f57b5e06dc242f77769883Keisuke Kuroyanagi AK_FORCE_INLINE bool betterThanWorstDicNode(const DicNode *const dicNode) const { 11938c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka DicNode *worstNode = mDicNodesQueue.top(); 12038c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka if (!worstNode) { 12138c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka return true; 12238c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka } 12338c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka return compareDicNode(dicNode, worstNode); 12438c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka } 12538c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka 126655b65cb0ba8d803c9f57b5e06dc242f77769883Keisuke Kuroyanagi AK_FORCE_INLINE DicNode *newDicNode(const DicNode *const dicNode) { 12767ff21f3217c9f2ff81beac6f29f5c35a83da228Keisuke Kuroyanagi DicNode *newNode = mDicNodePool.getInstance(); 12880ca7abea32a97acefcd8a8cb6145f0cdc8f0503Keisuke Kuroyanagi if (newNode) { 12980ca7abea32a97acefcd8a8cb6145f0cdc8f0503Keisuke Kuroyanagi DicNodeUtils::initByCopy(dicNode, newNode); 13080ca7abea32a97acefcd8a8cb6145f0cdc8f0503Keisuke Kuroyanagi } 13180ca7abea32a97acefcd8a8cb6145f0cdc8f0503Keisuke Kuroyanagi return newNode; 13280ca7abea32a97acefcd8a8cb6145f0cdc8f0503Keisuke Kuroyanagi } 13338c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka}; 13438c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka} // namespace latinime 13538c26dd0bf8cd5c4511e4a02d5eeae4b3553f03aSatoshi Kataoka#endif // LATINIME_DIC_NODE_PRIORITY_QUEUE_H 136