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
28namespace latinime {
29
30class DicNodePriorityQueue {
31 public:
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
38    AK_FORCE_INLINE ~DicNodePriorityQueue() {}
39
40    AK_FORCE_INLINE int getSize() const {
41        return static_cast<int>(mDicNodesQueue.size());
42    }
43
44    AK_FORCE_INLINE int getMaxSize() const {
45        return mMaxSize;
46    }
47
48    AK_FORCE_INLINE void setMaxSize(const int maxSize) {
49        mMaxSize = maxSize;
50    }
51
52    AK_FORCE_INLINE void clear() {
53        clearAndResize(mMaxSize);
54    }
55
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
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
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
95    AK_FORCE_INLINE void dump() {
96        mDicNodePool.dump();
97    }
98
99 private:
100    DISALLOW_IMPLICIT_CONSTRUCTORS(DicNodePriorityQueue);
101
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 {
108        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
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
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