1 /* 2 * Copyright (C) 2011, 2013 Nicolas Bonnefon and other contributors 3 * 4 * This file is part of glogg. 5 * 6 * glogg is free software: you can redistribute it and/or modify 7 * it under the terms of the GNU General Public License as published by 8 * the Free Software Foundation, either version 3 of the License, or 9 * (at your option) any later version. 10 * 11 * glogg is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * GNU General Public License for more details. 15 * 16 * You should have received a copy of the GNU General Public License 17 * along with glogg. If not, see <http://www.gnu.org/licenses/>. 18 */ 19 20 #ifndef UTILS_H 21 #define UTILS_H 22 23 #include <QtGlobal> 24 25 #include "config.h" 26 27 // Use a bisection method to find the given line number 28 // in a sorted list. 29 // The T type must be a container containing elements that 30 // implement the lineNumber() member. 31 // Returns true if the lineNumber is found, false if not 32 // foundIndex is the index of the found number or the index 33 // of the closest greater element. 34 template <typename T> bool lookupLineNumber( 35 const T& list, qint64 lineNumber, int* foundIndex ) 36 { 37 int minIndex = 0; 38 int maxIndex = list.size() - 1; 39 // If the list is not empty 40 if ( maxIndex - minIndex >= 0 ) { 41 // First we test the ends 42 if ( list[minIndex].lineNumber() == lineNumber ) { 43 *foundIndex = minIndex; 44 return true; 45 } 46 else if ( list[maxIndex].lineNumber() == lineNumber ) { 47 *foundIndex = maxIndex; 48 return true; 49 } 50 51 // Then we test the rest 52 while ( (maxIndex - minIndex) > 1 ) { 53 const int tryIndex = (minIndex + maxIndex) / 2; 54 const qint64 currentMatchingNumber = 55 list[tryIndex].lineNumber(); 56 if ( currentMatchingNumber > lineNumber ) 57 maxIndex = tryIndex; 58 else if ( currentMatchingNumber < lineNumber ) 59 minIndex = tryIndex; 60 else if ( currentMatchingNumber == lineNumber ) { 61 *foundIndex = tryIndex; 62 return true; 63 } 64 } 65 66 // If we haven't found anything... 67 // ... end of the list or before the next 68 if ( lineNumber > list[maxIndex].lineNumber() ) 69 *foundIndex = maxIndex + 1; 70 else if ( lineNumber > list[minIndex].lineNumber() ) 71 *foundIndex = minIndex + 1; 72 else 73 *foundIndex = minIndex; 74 } 75 else { 76 *foundIndex = 0; 77 } 78 79 return false; 80 } 81 82 // Represents a position in a file (line, column) 83 class FilePosition 84 { 85 public: 86 FilePosition() 87 { line_ = -1; column_ = -1; } 88 FilePosition( qint64 line, int column ) 89 { line_ = line; column_ = column; } 90 91 qint64 line() const { return line_; } 92 int column() const { return column_; } 93 94 private: 95 qint64 line_; 96 int column_; 97 }; 98 99 #ifndef HAVE_MAKE_UNIQUE 100 #include <memory> 101 102 namespace std { 103 template<typename T, typename... Args> 104 std::unique_ptr<T> make_unique(Args&&... args) { 105 return std::unique_ptr<T>(new T(std::forward<Args>(args)...)); 106 } 107 } 108 #endif 109 110 #endif 111