1 /*
2  * Copyright (C) 2012 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #ifndef LATINIME_DIC_NODE_PRIORITY_QUEUE_H
18 #define LATINIME_DIC_NODE_PRIORITY_QUEUE_H
19 
20 #include <algorithm>
21 #include <queue>
22 #include <vector>
23 
24 #include "defines.h"
25 #include "suggest/core/dicnode/dic_node.h"
26 #include "suggest/core/dicnode/dic_node_pool.h"
27 
28 namespace latinime {
29 
30 class DicNodePriorityQueue {
31  public:
DicNodePriorityQueue(const int capacity)32     AK_FORCE_INLINE explicit DicNodePriorityQueue(const int capacity)
33             : mMaxSize(capacity), mDicNodesQueue(), mDicNodePool(capacity) {
34         clear();
35     }
36 
37     // Non virtual inline destructor -- never inherit this class
~DicNodePriorityQueue()38     AK_FORCE_INLINE ~DicNodePriorityQueue() {}
39 
getSize()40     AK_FORCE_INLINE int getSize() const {
41         return static_cast<int>(mDicNodesQueue.size());
42     }
43 
getMaxSize()44     AK_FORCE_INLINE int getMaxSize() const {
45         return mMaxSize;
46     }
47 
setMaxSize(const int maxSize)48     AK_FORCE_INLINE void setMaxSize(const int maxSize) {
49         mMaxSize = maxSize;
50     }
51 
clear()52     AK_FORCE_INLINE void clear() {
53         clearAndResize(mMaxSize);
54     }
55 
clearAndResize(const int maxSize)56     AK_FORCE_INLINE void clearAndResize(const int maxSize) {
57         mMaxSize = maxSize;
58         while (!mDicNodesQueue.empty()) {
59             mDicNodesQueue.pop();
60         }
61         mDicNodePool.reset(mMaxSize + 1);
62     }
63 
copyPush(const DicNode * const dicNode)64     AK_FORCE_INLINE void copyPush(const DicNode *const dicNode) {
65         DicNode *const pooledDicNode = newDicNode(dicNode);
66         if (!pooledDicNode) {
67             return;
68         }
69         if (getSize() < mMaxSize) {
70             mDicNodesQueue.push(pooledDicNode);
71             return;
72         }
73         if (betterThanWorstDicNode(pooledDicNode)) {
74             mDicNodePool.placeBackInstance(mDicNodesQueue.top());
75             mDicNodesQueue.pop();
76             mDicNodesQueue.push(pooledDicNode);
77             return;
78         }
79         mDicNodePool.placeBackInstance(pooledDicNode);
80     }
81 
copyPop(DicNode * const dest)82     AK_FORCE_INLINE void copyPop(DicNode *const dest) {
83         if (mDicNodesQueue.empty()) {
84             ASSERT(false);
85             return;
86         }
87         DicNode *node = mDicNodesQueue.top();
88         if (dest) {
89             DicNodeUtils::initByCopy(node, dest);
90         }
91         mDicNodePool.placeBackInstance(node);
92         mDicNodesQueue.pop();
93     }
94 
dump()95     AK_FORCE_INLINE void dump() {
96         mDicNodePool.dump();
97     }
98 
99  private:
100     DISALLOW_IMPLICIT_CONSTRUCTORS(DicNodePriorityQueue);
101 
compareDicNode(const DicNode * const left,const DicNode * const right)102     AK_FORCE_INLINE static bool compareDicNode(const DicNode *const left,
103             const DicNode *const right) {
104         return left->compare(right);
105     }
106 
107     struct DicNodeComparator {
operatorDicNodeComparator108         bool operator ()(const DicNode *left, const DicNode *right) const {
109             return compareDicNode(left, right);
110         }
111     };
112 
113     typedef std::priority_queue<DicNode *, std::vector<DicNode *>, DicNodeComparator> DicNodesQueue;
114     int mMaxSize;
115     DicNodesQueue mDicNodesQueue;
116     DicNodePool mDicNodePool;
117 
betterThanWorstDicNode(const DicNode * const dicNode)118     AK_FORCE_INLINE bool betterThanWorstDicNode(const DicNode *const dicNode) const {
119         DicNode *worstNode = mDicNodesQueue.top();
120         if (!worstNode) {
121             return true;
122         }
123         return compareDicNode(dicNode, worstNode);
124     }
125 
newDicNode(const DicNode * const dicNode)126     AK_FORCE_INLINE DicNode *newDicNode(const DicNode *const dicNode) {
127         DicNode *newNode = mDicNodePool.getInstance();
128         if (newNode) {
129             DicNodeUtils::initByCopy(dicNode, newNode);
130         }
131         return newNode;
132     }
133 };
134 } // namespace latinime
135 #endif // LATINIME_DIC_NODE_PRIORITY_QUEUE_H
136