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 // Use a bisection method to find the given line number 24 // in a sorted list. 25 // The T type must be a container containing elements that 26 // implement the lineNumber() member. 27 // Returns true if the lineNumber is found, false if not 28 // foundIndex is the index of the found number or the index 29 // of the closest greater element. 30 template <typename T> bool lookupLineNumber( 31 const T& list, qint64 lineNumber, int* foundIndex ) 32 { 33 int minIndex = 0; 34 int maxIndex = list.size() - 1; 35 // If the list is not empty 36 if ( maxIndex - minIndex >= 0 ) { 37 // First we test the ends 38 if ( list[minIndex].lineNumber() == lineNumber ) { 39 *foundIndex = minIndex; 40 return true; 41 } 42 else if ( list[maxIndex].lineNumber() == lineNumber ) { 43 *foundIndex = maxIndex; 44 return true; 45 } 46 47 // Then we test the rest 48 while ( (maxIndex - minIndex) > 1 ) { 49 const int tryIndex = (minIndex + maxIndex) / 2; 50 const qint64 currentMatchingNumber = 51 list[tryIndex].lineNumber(); 52 if ( currentMatchingNumber > lineNumber ) 53 maxIndex = tryIndex; 54 else if ( currentMatchingNumber < lineNumber ) 55 minIndex = tryIndex; 56 else if ( currentMatchingNumber == lineNumber ) { 57 *foundIndex = tryIndex; 58 return true; 59 } 60 } 61 62 // If we haven't found anything... 63 // ... end of the list or before the next 64 if ( lineNumber > list[maxIndex].lineNumber() ) 65 *foundIndex = maxIndex + 1; 66 else if ( lineNumber > list[minIndex].lineNumber() ) 67 *foundIndex = minIndex + 1; 68 else 69 *foundIndex = minIndex; 70 } 71 else { 72 *foundIndex = 0; 73 } 74 75 return false; 76 } 77 78 // Represents a position in a file (line, column) 79 class FilePosition 80 { 81 public: 82 FilePosition() 83 { line_ = -1; column_ = -1; } 84 FilePosition( qint64 line, int column ) 85 { line_ = line; column_ = column; } 86 87 qint64 line() const { return line_; } 88 int column() const { return column_; } 89 90 private: 91 qint64 line_; 92 int column_; 93 }; 94 95 #endif 96