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 <queue>
21#include <vector>
22
23#include "defines.h"
24#include "suggest/core/dicnode/dic_node.h"
25#include "suggest/core/dicnode/dic_node_release_listener.h"
26
27namespace latinime {
28
29class DicNodePriorityQueue : public DicNodeReleaseListener {
30 public:
31    AK_FORCE_INLINE explicit DicNodePriorityQueue(const int capacity)
32            : mCapacity(capacity), mMaxSize(capacity), mDicNodesBuf(),
33              mUnusedNodeIndices(), mNextUnusedNodeId(0), mDicNodesQueue() {
34        mDicNodesBuf.resize(mCapacity + 1);
35        mUnusedNodeIndices.resize(mCapacity + 1);
36        clearAndResizeToCapacity();
37    }
38
39    // Non virtual inline destructor -- never inherit this class
40    AK_FORCE_INLINE ~DicNodePriorityQueue() {}
41
42    int getSize() const {
43        return static_cast<int>(mDicNodesQueue.size());
44    }
45
46    int getMaxSize() const {
47        return mMaxSize;
48    }
49
50    AK_FORCE_INLINE void setMaxSize(const int maxSize) {
51        ASSERT(maxSize <= mCapacity);
52        mMaxSize = min(maxSize, mCapacity);
53    }
54
55    AK_FORCE_INLINE void clearAndResizeToCapacity() {
56        clearAndResize(mCapacity);
57    }
58
59    AK_FORCE_INLINE void clear() {
60        clearAndResize(mMaxSize);
61    }
62
63    AK_FORCE_INLINE void clearAndResize(const int maxSize) {
64        ASSERT(maxSize <= mCapacity);
65        while (!mDicNodesQueue.empty()) {
66            mDicNodesQueue.pop();
67        }
68        setMaxSize(maxSize);
69        for (int i = 0; i < mCapacity + 1; ++i) {
70            mDicNodesBuf[i].remove();
71            mDicNodesBuf[i].setReleaseListener(this);
72            mUnusedNodeIndices[i] = i == mCapacity ? NOT_A_NODE_ID : static_cast<int>(i) + 1;
73        }
74        mNextUnusedNodeId = 0;
75    }
76
77    // Copy
78    AK_FORCE_INLINE DicNode *copyPush(DicNode *dicNode) {
79        return copyPush(dicNode, mMaxSize);
80    }
81
82    AK_FORCE_INLINE void copyPop(DicNode *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        node->remove();
92        mDicNodesQueue.pop();
93    }
94
95    void onReleased(DicNode *dicNode) {
96        const int index = static_cast<int>(dicNode - &mDicNodesBuf[0]);
97        if (mUnusedNodeIndices[index] != NOT_A_NODE_ID) {
98            // it's already released
99            return;
100        }
101        mUnusedNodeIndices[index] = mNextUnusedNodeId;
102        mNextUnusedNodeId = index;
103        ASSERT(index >= 0 && index < (mCapacity + 1));
104    }
105
106    AK_FORCE_INLINE void dump() const {
107        AKLOGI("\n\n\n\n\n===========================");
108        for (int i = 0; i < mCapacity + 1; ++i) {
109            if (mDicNodesBuf[i].isUsed()) {
110                mDicNodesBuf[i].dump("QUEUE: ");
111            }
112        }
113        AKLOGI("===========================\n\n\n\n\n");
114    }
115
116 private:
117    DISALLOW_IMPLICIT_CONSTRUCTORS(DicNodePriorityQueue);
118    static const int NOT_A_NODE_ID = -1;
119
120    AK_FORCE_INLINE static bool compareDicNode(DicNode *left, DicNode *right) {
121        return left->compare(right);
122    }
123
124    struct DicNodeComparator {
125        bool operator ()(DicNode *left, DicNode *right) {
126            return compareDicNode(left, right);
127        }
128    };
129
130    typedef std::priority_queue<DicNode *, std::vector<DicNode *>, DicNodeComparator> DicNodesQueue;
131    const int mCapacity;
132    int mMaxSize;
133    std::vector<DicNode> mDicNodesBuf; // of each element of mDicNodesBuf respectively
134    std::vector<int> mUnusedNodeIndices;
135    int mNextUnusedNodeId;
136    DicNodesQueue mDicNodesQueue;
137
138    inline bool isFull(const int maxSize) const {
139        return getSize() >= maxSize;
140    }
141
142    AK_FORCE_INLINE void pop() {
143        copyPop(0);
144    }
145
146    AK_FORCE_INLINE bool betterThanWorstDicNode(DicNode *dicNode) const {
147        DicNode *worstNode = mDicNodesQueue.top();
148        if (!worstNode) {
149            return true;
150        }
151        return compareDicNode(dicNode, worstNode);
152    }
153
154    AK_FORCE_INLINE DicNode *searchEmptyDicNode() {
155        if (mCapacity == 0) {
156            return 0;
157        }
158        if (mNextUnusedNodeId == NOT_A_NODE_ID) {
159            AKLOGI("No unused node found.");
160            for (int i = 0; i < mCapacity + 1; ++i) {
161                AKLOGI("Dump node availability, %d, %d, %d",
162                        i, mDicNodesBuf[i].isUsed(), mUnusedNodeIndices[i]);
163            }
164            ASSERT(false);
165            return 0;
166        }
167        DicNode *dicNode = &mDicNodesBuf[mNextUnusedNodeId];
168        markNodeAsUsed(dicNode);
169        return dicNode;
170    }
171
172    AK_FORCE_INLINE void markNodeAsUsed(DicNode *dicNode) {
173        const int index = static_cast<int>(dicNode - &mDicNodesBuf[0]);
174        mNextUnusedNodeId = mUnusedNodeIndices[index];
175        mUnusedNodeIndices[index] = NOT_A_NODE_ID;
176        ASSERT(index >= 0 && index < (mCapacity + 1));
177    }
178
179    AK_FORCE_INLINE DicNode *pushPoolNodeWithMaxSize(DicNode *dicNode, const int maxSize) {
180        if (!dicNode) {
181            return 0;
182        }
183        if (!isFull(maxSize)) {
184            mDicNodesQueue.push(dicNode);
185            return dicNode;
186        }
187        if (betterThanWorstDicNode(dicNode)) {
188            pop();
189            mDicNodesQueue.push(dicNode);
190            return dicNode;
191        }
192        dicNode->remove();
193        return 0;
194    }
195
196    // Copy
197    AK_FORCE_INLINE DicNode *copyPush(DicNode *dicNode, const int maxSize) {
198        return pushPoolNodeWithMaxSize(newDicNode(dicNode), maxSize);
199    }
200
201    AK_FORCE_INLINE DicNode *newDicNode(DicNode *dicNode) {
202        DicNode *newNode = searchEmptyDicNode();
203        if (newNode) {
204            DicNodeUtils::initByCopy(dicNode, newNode);
205        }
206        return newNode;
207    }
208
209};
210} // namespace latinime
211#endif // LATINIME_DIC_NODE_PRIORITY_QUEUE_H
212