activemq-cpp/src/main/decaf/internal/util/TimerTaskHeap.cpp

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include "TimerTaskHeap.h"

using namespace decaf;
using namespace decaf::internal;
using namespace decaf::internal::util;

////////////////////////////////////////////////////////////////////////////////
TimerTaskHeap::TimerTaskHeap() : heap() {
}

////////////////////////////////////////////////////////////////////////////////
TimerTaskHeap::~TimerTaskHeap() {
}

////////////////////////////////////////////////////////////////////////////////
Pointer<TimerTask> TimerTaskHeap::peek() {

    if (heap.empty()) {
        return Pointer<TimerTask>();
    }

    return heap[0];
}

////////////////////////////////////////////////////////////////////////////////
bool TimerTaskHeap::isEmpty() const {
    return heap.empty();
}

////////////////////////////////////////////////////////////////////////////////
std::size_t TimerTaskHeap::size() const {
    return this->heap.size();
}

////////////////////////////////////////////////////////////////////////////////
void TimerTaskHeap::insert(const Pointer<TimerTask>& task) {

    heap.push_back(task);
    upHeap();
}

////////////////////////////////////////////////////////////////////////////////
void TimerTaskHeap::remove(std::size_t pos) {

    // possible to delete any position of the heap
    if (pos < heap.size()) {
        heap[pos] = heap.back();
        heap.pop_back();
        downHeap(pos);
    }
}

////////////////////////////////////////////////////////////////////////////////
void TimerTaskHeap::upHeap() {

    std::size_t current = heap.size() - 1;
    std::size_t parent = (current - 1) / 2;

    while (current != 0 && heap[current]->when < heap[parent]->when) {

        // swap the two
        Pointer<TimerTask> tmp = heap[current];
        heap[current] = heap[parent];
        heap[parent] = tmp;

        // update parent and current positions.
        current = parent;
        parent = (current - 1) / 2;
    }
}

////////////////////////////////////////////////////////////////////////////////
void TimerTaskHeap::downHeap(std::size_t pos) {

    std::size_t current = pos;
    std::size_t child = 2 * current + 1;

    while (child < heap.size() && !heap.empty()) {

        // compare the children if they exist
        if (child + 1 < heap.size() && heap[child + 1]->when < heap[child]->when) {
            child++;
        }

        // compare selected child with parent
        if (heap[current]->when < heap[child]->when) {
            break;
        }

        // swap the two
        Pointer<TimerTask> tmp = heap[current];
        heap[current] = heap[child];
        heap[child] = tmp;

        // update child and current positions
        current = child;
        child = 2 * current + 1;
    }
}

////////////////////////////////////////////////////////////////////////////////
void TimerTaskHeap::reset() {
    heap.clear();
}

////////////////////////////////////////////////////////////////////////////////
void TimerTaskHeap::adjustMinimum() {
    downHeap(0);
}

////////////////////////////////////////////////////////////////////////////////
std::size_t TimerTaskHeap::deleteIfCancelled() {

    std::size_t result = 0;

    for (std::size_t i = 0; i < heap.size(); ++i) {
        if (heap[i]->cancelled) {
            result++;
            remove(i);
            // re-try this point
            i--;
        }
    }

    return result;
}

////////////////////////////////////////////////////////////////////////////////
std::size_t TimerTaskHeap::find(const Pointer<TimerTask>& task) const {

    for (std::size_t i = 0; i < heap.size(); ++i) {
        if (heap[i] == task) {
            return i;
        }
    }

    return -1;
}