PF_API 0.52

Android/jni/Libs/PF_LIB/PFQueue.h

Go to the documentation of this file.
00001 
00002 //    Copyright (C) 2004,2005 Dylan Blair
00003 //
00004 //    email: dblair@alumni.cs.utexas.edu
00005 //
00006 //    This library is free software; you can redistribute it and/or
00007 //    modify it under the terms of the GNU Lesser General Public
00008 //    License as published by the Free Software Foundation; either
00009 //    version 2.1 of the License, or (at your option) any later version.
00010 //
00011 //    This library is distributed in the hope that it will be useful,
00012 //    but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 //    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 //    Lesser General Public License for more details.
00015 //
00016 //    You should have received a copy of the GNU Lesser General Public
00017 //    License along with this library; if not, write to the Free Software
00018 //    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00020 
00021 #ifndef PFQUEUE_H
00022 #define PFQUEUE_H
00023 
00024 #include <algorithm>
00025 
00026 #include "../CD_LIB/CDGrid.h"
00027 
00028 #include "PFConsts.h"
00029 
00030 namespace OpenSkyNet {
00031     namespace PF {
00033         class Queue {
00034             struct QueueNode {
00035                 Utils::uint64 _pathDirs;
00036                 CD::DIRECTION _initPathDir;
00037                 Math::Point<Utils::uint> _bin;
00038                 QueueNode(const Math::Point<Utils::uint>& bin_=Math::Point<Utils::uint>()) : _pathDirs(CD::NONE), _initPathDir(CD::NONE), _bin(bin_) {}
00039             };
00040 
00041             static const Utils::uint64 _maxPathDirs;
00042             std::list<QueueNode> _q;
00043             std::list<QueueNode>::iterator _front;
00044             std::list<QueueNode>::iterator _back;
00045             Utils::HashTableUIntKeys<bool> _visitedBins;
00046             bool _deletedRightPaths;
00047             bool _deletedLeftPaths;
00048             bool _deletedUpPaths;
00049             bool _deletedDownPaths;
00050             bool _deletedForwardPaths;
00051             bool _deletedBackwardPaths;
00052         public:
00053             Queue() : _visitedBins(OpenSkyNet::Utils::INITIAL_TABLE_SIZE,false) {}
00054 
00055             void init(const Math::Point<Utils::uint>& bin_);
00056 
00057             inline bool isEmpty() const { return (!(_q.size() > 1)); }
00058 
00059             inline bool enqueue(CD::DIRECTION dir_, const Math::Point<Utils::uint>& bin_) {
00060                 if ((!_visitedBins[Utils::getCompositeKey(bin_)]) && (_front->_pathDirs < _maxPathDirs)) {
00061                     _q.push_back(*_front);
00062                     _back = _q.end();
00063                     --_back;
00064                     _back->_pathDirs = _back->_pathDirs*10+dir_;
00065                     if (_back->_pathDirs < 10)
00066                         _back->_initPathDir = static_cast<CD::DIRECTION>(_back->_pathDirs);
00067                     _back->_bin = bin_;
00068                     _visitedBins.add(Utils::getCompositeKey(bin_)) = true;
00069                     return true;
00070                 }
00071                 return false;
00072             }
00073 
00074             inline CD::DIRECTION dequeue(Math::Point<Utils::uint>& bin_) {
00075                 _q.pop_front();
00076                 _front = _q.begin();
00077                 bin_ = _front->_bin;
00078                 return (static_cast<CD::DIRECTION>(_front->_pathDirs - (_front->_pathDirs/10)*10));
00079             }
00080 
00081             void deletePathDirsStartingWith(CD::DIRECTION dir_);
00082 
00083             std::vector<CD::DIRECTION> returnFrontPathDirsAsVector() const;
00084 
00085             inline bool getCurrBin(Math::Point<Utils::uint>& bin_) const {
00086                 if (!_q.size()) return false;
00087                 bin_ = _front->_bin;
00088                 return true;
00089             }
00090 
00091             inline void setVisitedBin(const Math::Point<Utils::uint>& bin_, bool isVisited_) {
00092                 _visitedBins.add(Utils::getCompositeKey(bin_)) = isVisited_;
00093             }
00094         };
00095     }
00096 }
00097 
00098 #endif //PFQUEUE_H
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines