PFQueue.h

Go to the documentation of this file.

//    Copyright (C) 2004,2005 Dylan Blair
//
//    email: dblair@alumni.cs.utexas.edu
//
//    This library is free software; you can redistribute it and/or
//    modify it under the terms of the GNU Lesser General Public
//    License as published by the Free Software Foundation; either
//    version 2.1 of the License, or (at your option) any later version.
//
//    This library is distributed in the hope that it will be useful,
//    but WITHOUT ANY WARRANTY; without even the implied warranty of
//    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
//    Lesser General Public License for more details.
//
//    You should have received a copy of the GNU Lesser General Public
//    License along with this library; if not, write to the Free Software
//    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

#ifndef PFQUEUE_H
#define PFQUEUE_H

#include <algorithm>

#include "../CD_LIB/CDGrid.h"

#include "PFConsts.h"

namespace OpenSkyNet {
    namespace PF {
        class Queue {
            struct QueueNode {
                Utils::uint64 _pathDirs;
                CD::DIRECTION _initPathDir;
                Math::Point<Utils::uint> _bin;
                QueueNode(const Math::Point<Utils::uint>& bin_=Math::Point<Utils::uint>()) : _pathDirs(CD::NONE), _initPathDir(CD::NONE), _bin(bin_) {}
            };

            static const Utils::uint64 _maxPathDirs;
            std::list<QueueNode> _q;
            std::list<QueueNode>::iterator _front;
            std::list<QueueNode>::iterator _back;
            Utils::HashTableUIntKeys<bool> _visitedBins;
            bool _deletedRightPaths;
            bool _deletedLeftPaths;
            bool _deletedUpPaths;
            bool _deletedDownPaths;
            bool _deletedForwardPaths;
            bool _deletedBackwardPaths;
        public:
            Queue() : _visitedBins(OpenSkyNet::Utils::INITIAL_TABLE_SIZE,false) {}

            void init(const Math::Point<Utils::uint>& bin_);

            inline bool isEmpty() const { return (!(_q.size() > 1)); }

            inline bool enqueue(CD::DIRECTION dir_, const Math::Point<Utils::uint>& bin_) {
                if ((!_visitedBins[Utils::getCompositeKey(bin_)]) && (_front->_pathDirs < _maxPathDirs)) {
                    _q.push_back(*_front);
                    _back = _q.end();
                    --_back;
                    _back->_pathDirs = _back->_pathDirs*10+dir_;
                    if (_back->_pathDirs < 10)
                        _back->_initPathDir = static_cast<CD::DIRECTION>(_back->_pathDirs);
                    _back->_bin = bin_;
                    _visitedBins.add(Utils::getCompositeKey(bin_)) = true;
                    return true;
                }
                return false;
            }

            inline CD::DIRECTION dequeue(Math::Point<Utils::uint>& bin_) {
                _q.pop_front();
                _front = _q.begin();
                bin_ = _front->_bin;
                return (static_cast<CD::DIRECTION>(_front->_pathDirs - (_front->_pathDirs/10)*10));
            }

            void deletePathDirsStartingWith(CD::DIRECTION dir_);

            std::vector<CD::DIRECTION> returnFrontPathDirsAsVector() const;

            inline bool getCurrBin(Math::Point<Utils::uint>& bin_) const {
                if (!_q.size()) return false;
                bin_ = _front->_bin;
                return true;
            }

            inline void setVisitedBin(const Math::Point<Utils::uint>& bin_, bool isVisited_) {
                _visitedBins.add(Utils::getCompositeKey(bin_)) = isVisited_;
            }
        };
    }
}

#endif //PFQUEUE_H