С.И.Хашин
В этом модуле собраны несколько несложных функций, постоянно требующихся
при программировании на C++.
Функции практически независимы друг от друга, кроме нескольких очевидных случаев.
Поэтому, если нужны только одна-две фунции, можно взять только их.
ОГЛАВЛЕНИЕ
//typedef long double ldouble; typedef double ldouble;Visual C++ игнорирует тип long double. Однако стоит сохранить возможность работать с 10-байтовыми числам (long double), пусть и с другими компиляторами. Для этого вместо double будем использовать ldouble. Под Visual C++ это просто double, под другими компиляторами это может быть long double.
Кроме того, для краткости вводятся 8-ми байтовые числа i64, u64 и BYTE.
void vError(const char *format, ...); // show error functionВывод указанного сообщения и завершение работы. Аргументы функции те же самые, что и у функции printf, например:
vError("res=%llu\n", tm);
или:
matr a;
char *fname = "lena.bmp";
int code;
if(code=a.loadBMP(fname)) vError("File %s not open, error code=%d", fname, code);
Функция вывода сообщения на экран:
void vShow (const char *format, ...); // show function
void hWrite(const char *fname, const char *format, ... ); // Открыть файл fname, записать в него строку msg и закрыть его
Пример работы:
hWrite("res.txt", "f(%8.4f)=%10.5f\n", x, f(x));
char * toString( const char* format, ... ); char * toString2(const char* format, ... );
toString(…) – возвращает строку с заданным значением, аргументы функции те же самые, что и у функции printf, например:
toString(“%s\\file_%04d.jpg”, path, k);
На самом деле функция всегда возвращает указатель на одну и ту же область памяти, в которой при вызове строится (с помощью sprintf) требуемая строка. Следовательно, функция не выделяет новую память и её не требуется освобождать.
С другой стороны, в результате этого функцию toString нельзя использовать дважды одновремено, например вызов
printf("%s_%s", toString(x), toString(y) )
неверен, так как оба раза функция возвратит один и тот же указатель.
Такая проблема нечасто, но появляется. Здесь можно предложить два выхода:
printf("%s_%s_%s", toString(x), toString2(y), toString2(z) )
но они требуются так редко, что о них не стоит заботиться.
char * copyString( const char *s ); // копия строки в куче char * nextToken( char *s ); // разбивка строки по символам табуляции
В строке s находит перый символ табуляции и заменяет его на '\0'. Возвращает указатель на символ, следующий за вставленным '\0'. Если табуляция не найдена, ничего не делаем и возвращаем NULL.
const char *FirstWord(const char *src, const char *brk, char *dst);
// dst:=1-е слово, ограниченное символами из brk, возвращает указатель на
// первый символ после слова
inline bool isRus ( char ch); // ? Русская буква
inline bool isLat (char ch); // ? Латинская буква
inline bool isDig (char ch); // ? Цифра
inline bool isLRus (char ch); // ? Большая русская буква
inline bool islRus (char ch); // ? маленькая русская буква
inline bool isBlank(char ch)'); // ? ' ', '\t', '\n', '\r'
inline bool isPnt (char ch); // ? '.!?'
#define chrKind_REST 1
#define chrKind_DIGIT 2
#define chrKind_RUS 3
#define chrKind_LAT 4
#define chrKind_PNT 5
int chrKind(char ch); // тип символа
bool isOnlylRus( char *s); // в строке только малые русские буквы?
Конвертация символов:
unsigned char char_866_1251 (unsigned char ch); // dos -> win
unsigned char char_Koi8_1251(unsigned char ch); // koi8-r -> win
unsigned char char_utf8_1251(unsigned char *&s); // uft8 -> win,
очередной символ строки, s0 переустанавливается на следующий символ
Конвертация строк производится "на месте":
unsigned char* cnv1251_866(unsigned char *s); // win -> dos (in place) unsigned char* cnv866_1251(unsigned char *s); // dos -> win (in place) unsigned char* cnvKoi8_1251(unsigned char *s); // koi8-r -> win (in place)
Обратите внимание, что в тексте этой функции задана длинная строка из 257 символов. Её ни в коем случае нельзя изменять, ни один пробел не должен пропасть!
unsigned char* cnv_utf8_1251(unsigned char *s); // uft8 -> win (in place)
В этой функции все символы, которые нельзя закодировать в кодовой странице cp-1251 будут
заменены на пробелы.
Строка может стать короче!
#define rCP_unknown 0 #define rCP_1251 1 #define rCP_866 2 #define rCP_koi8r 3 #define rCP_utf8 4 int rCodePage(unsigned char *s); inline int rCodePage(char *s);
Кодировка определяется с помощью имеющейся таблицы частот русских букв. Проверяем в какой из четырех кодировок частоты будут ближе к стандартным, ту кодировку и выбираем.
Внимание! Результат не абсолютный, а лишь "вероятный"!
void ltrim(char *s); // удалить начальные пробелы из строки void rtrim(char *s); // удалить конечные пробелы из строки void trim (char *s); // удалить начальные и конечные пробелы из строки char* toLatLow(char *txt); // Большие латинские сделать маленькими char* toRusLow(char *txt); // Оставить в строке только малые русские буквы и пробелы
В этой функции все знаки, кроме русских букв заменяются на пробелы.
char* toRusLowP(char *txt); // Оставить в строке только малые русские буквы, точки и пробелы
В этой функции все знаки, кроме русских букв и точки заменяются на пробелы.
char* txtPress(char *txt); // trim + сжатие пробелов и точек в один
Например, после выполнения вот такого кода
char s[] = "char* toRusLow(char *txt); // Оставить в строке только малые русские буквы и пробелы\n\
Продолжение строки. end\t.\n";
char *s1 = toRusLow(s);
s1 = txtPress(s1);
в s1 оказывается строка:
"оставить в строке только малые русские буквы и пробелы продолжение строки"
В последней функции из строки удаляются начальные и конечные пробелы, несколько пробелов подряд заменяются на один пробел.
Полезнейшие константы:
const int million = 1000000; const int billion = 1000000000;
int iDivide( int a, int b ); // round(a/b) int mod ( int a, int b ); // math: a mod b int iround ( int x, int k ); // округлить целое до кратного k int iSquare( int x ); // возведение в квадрат BYTE clip256( int x ); // меньшие 0 заменяем на 0, большие 255 на 255. int ilog2 ( unsigned x ); // максимальная степень 2, <= x, ilog2(0)=ilog2(1)=0, ilog2(2)=ilog2(3)=1, ... void swapInt( int &a, int &b); // перестановка чисел u64 binomial( int n, int k ); // n!/(k!*(n-k)!, binomial(3,2)=3
Будьте внимательны!
binomial(62,31) = 465 428 353 255 261 088 (correct)
binomial(63,31) = 148 894 686 314 746 622 (wrong, correct value 916 312 070 471 295 267 too large!)
bool odd(int x); // нечетное?
Отображаем целые числа в натуральные и обратно:
0, 1, 2, ... -> 0, 2, 4, ...,
-1,-2, ... -> 1, 3, ....
int toNatural(int x); // map signed x to positive integer int fromNatural(int x); // remap positive x to signed integer
// max/min
int imax2( int a, int b );
int imax3(int a, int b, int c);
int imax4(int a, int b, int c, int d);
int imin2( int a, int b );
int imin3( int a, int b, int c );
int imin4(int a, int b, int c, int d);
int imax(int N, int *a, int &k); // максимум в массиве a[0..N-1], k - его индекс в массиве
int imin(int N, int *a, int &k); // минимум в массиве a[0..N-1], k - его индекс в массиве
void corrMinMax(int x, int &min, int &max); // коррекция минимума и максимума
void iShiftR(int N, int *a); // циклический сдвиг вправо: a[0]->a[1]->...->a[N-1]->a[0]
void iShiftL(int N, int *a); // циклический сдвиг влево : a[0]<-a[1]<-...<-a[N-1]<-a[0]
int byteAdd(int a, int b); // побайтовое сложение целых чисел
int quantil ( int k, unsigned *hist, int p ); // в гистограмме hist размера k найти квантиль p
int quantilr( int k, unsigned *hist, int p ); // в гистограмме hist размера k найти правый квантиль p
Поясним две последние функции. Допустим, дан массив h[10] целых чисел:
h[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
При вызове функции
quantil(10, h, 9);
в массиве неотрицательных чисел hist[0..9] будем искать наименьшее s
такое, что сумма первых s чисел ≥ p.
Если же сумма всех чисел оказалась меньше p, то возвращаем -1.
В данном случае
h[0] + h[1] + h[2] = 1+2+3 = 6 < 9,Сумма первых трех чисел меньше 9.
h[0] + h[1] + h[2] + h[3] = 1+2+3+4 = 10 ≥ 9,
Сумма первых четырех чисел ≥ 9. Таким образом, функция вернет результат 4.
Аналогичным образом, при вызове функции
quantilr(10, h, 19);
получаем:
h[9] = 10 < 19,Последнее число меньше 19.
h[9] + h[8] = 10+9 = 19 ≥ 19,
Сумма последних двух чисел ≥ 19. Таким образом, функция вернет результат 2.
#define dPi 3.14159265358979324 #define TwoPi 6.28318530717958648 #define macheps (2.2e-16) // машинная точность double #define dbl_MAX (9e+307) // 2*dbl_MAX = #inf #define round(x) ((int)floor((x)+0.5 )) // округлить до целого
В прежних версиях С++ не было функции lround(). Что бы не путаться с версиями, ввёл функцию (макрос) round().
ldouble dSquare(ldouble x); // возвести аргумент в квадрат ldouble noise2psnr( ldouble x ); // 20*log10(255/x) ldouble psnr2dfd ( ldouble x ); // 255/exp(0.1151*x) void swapDbl( ldouble &a, ldouble &b); ldouble angle( ldouble x, ldouble y); // угол (0..2Pi) вектора (x,y) с осью X. ldouble hypot2( ldouble x1, ldouble x2 );// sqrt(x1*x1+x2*x2); ldouble hypot3( ldouble x1, ldouble x2, ldouble x3);// sqrt(x1*x1+x2*x2+x3*x3); // max/min ldouble dmax2( ldouble a, ldouble b ); ldouble dmax3(ldouble a, ldouble b, ldouble c); ldouble dmax4(ldouble a, ldouble b, ldouble c, ldouble d); ldouble dmin2( ldouble a, ldouble b ); ldouble dmin3( ldouble a, ldouble b, ldouble c ); ldouble dmin4(ldouble a, ldouble b, ldouble c, ldouble d);
Следующая функция сортирует три числа по возрастанию:
void dblSort3( ldouble &a, ldouble &b, ldouble &c); // make: a <= b <= c
bool isMultiple(ldouble a, ldouble b, ldouble eps); // a - кратно b с точностью до eps
Работа с векторами из действительных чисел
// vectors of ldouble void vdbl_set (int N, ldouble *a, ldouble k); // a[i] = k void vdbl_add (int N, ldouble *a, ldouble *b); // A += B void vdbl_cop (int N, ldouble *a, ldouble *b); // A := B void vdbl_mul (int N, ldouble *a, ldouble k); // A *= k void vdbl_div (int N, ldouble *a, ldouble k); // A /= k void vdbl_addmul(int N,ldouble *a, ldouble *b,ldouble k);// A += k*B ldouble vdbl_len2 (int N, ldouble *a); // |A|^2 ldouble vdbl_len (int N, ldouble *a); // |A| void vdbl_norm (int N, ldouble *a); // |A| := 1 ldouble vdbl_dist2(int N, ldouble *a, ldouble *b); // |A-B|^2 ldouble vdbl_dist (int N, ldouble *a, ldouble *b); // |A-B| ldouble vdbl_sprod(int N, ldouble *a, ldouble *b); // scalar product(A,B) ldouble vdbl_max (int N, ldouble *a, int &ind); // maximal value and its index ldouble vdbl_min (int N, ldouble *a, int &ind); // minimal value and its index
Непрерывные (цепные) дроби. Для данного x находим его наилучшее рациональное приближение со знаменателем <= maxQ
// Continued fraction ldouble chainFract(ldouble x, i64 &p, i64 &q, i64 maxQ); // optimal rat.approx p/q of x, q<=maxQ, return tolerance
bool fileExist( const char *fileName ); // существует ли указанный файл void fileClear( const char *fileName ); // опустошить файл int fileSize ( const char *fileName ); // размер файла const char*fileExt(const char *fileName ); // расширение void chExt(char *fileName, const char *ext);// изменить расширение файла на ext int NLines(const char *fileName); // количество строк в текстовом файле int NLines1(const char *fileName); // количество непустых строк в текстовом файле
Для открытия существующего файла на "добавление", обычно пишут так:
FILE *f = fopen("ttt.txt", "a");
Но если файла с таким именем не существует, возникает ошибка.
Если вам надо открыть текстовый файл на добавление, если он существует,
а в противном случае создать новый, это можно сделать одним оператором:
FILE *aopen(const char *fname); // открыть (или создать) текстовый файл для добавления
Далее,
bool writeFile(char *fname, const BYTE *buf, unsigned bsize);
// сохранить буфер в файл
BYTE *fileRead(const char *fname, unsigned &fsize);
// Прочитать файл в двоичный буфер (в конце добавлен ещё один нулевой байт).
int iCadr( char *s ); // извлечь номер кадра из имени файла
void nextFname(char *s); // следующее имя файла
Функция iCadr. После вызова
char fname[64] = "c:\\a\\frame\f_0234.bmp"; int k = iCadr(fname);переменная k будет равна 234.
После вызова
next(fname);строка fname окажется равна
"c:\\a\\frame\f_0235.bmp";Отметим, что если написать
char *fname = "c:\\a\\frame\f_0234.bmp";то строка fname будет лежать в статической памяти, которую запрещено изменять во время выполнения и функция nextFrame даст ошибку.
long long getMillisec(); // время в миллисекундах ldouble getSec(); // время в секундах
Точное время в тактах таймера (только под Windows)
Отметим, что измеряются не такты процессора, а такты некоторого
высокоточного таймера, получается примерно 3.5 миллиона тактов в секунду.
i64 TimerCounter(); // счётчик циклов i64 TimerFrequency(); // тактовая частота таймера
Рассмотрим пример.
double dtm = -getSec(); // секунды
u64 ms = -getMillisec(); // миллисекунды
i64 tm = -TimerCounter(); // начальное время со знаком минус
unsigned sum = 0;
for (unsigned i = MAX32; i>0; i--) // это цикл - просто задержка вычислений
sum += i;
tm += TimerCounter(); // прибавили текущее время, получили разность в тактах таймера
ms += getMillisec();
dtm += getSec();
double tm2=(double)tm;
tm2 /= TimerFrequency(); // теперь dtm - время выполнения блока в секундах
printf("sec = %10.5f, ms = %10llu\n", dtm, ms);
printf("tm=%11llu tacts (%10.6f sec)\n", tm, tm2);
Получим результат:
sec = 0.83200, ms = 832
tm = 2847755 tacts (0.832221 sec)
Число p = 264 - 59 является простым, причем 2 будет первообразным корнем по модулю p. Поэтому последовательность {1,2,4,8, ...} mod p будет иметь период p-1.
Если мы будет вызывать наш датчик по 1 млрд. раз в секунду, то для обхода всего цикла потребуется около 500 лет. Таким образом, с практической точки зрения эта последовательность никогда не будет повторяться.
Алгоритм умножения на 2 по модулю p = 264 - 59 можно предложить следующий:
Пусть x — 8-байтовое число без знака (unsigned long long).
Если x ≤ 263-30 то для вычисления 2x переменную x надо просто умножить на 2.
Если x > 263-30 то для вычисления 2x надо взять 2*x+59.
Чтобы закономерности в начале последовательности были не видны, в качестве случайного числа выдаем
(hRandom_value + 0x12345678abcdefL) ^ 0x4937837937219836L;
void hRandomize(unsigned init=0);// it init=0 then initialization by time
u64 hRandom_next(); // очередное случайное число
int hRandom(unsigned k); // int random 0..k-1
ldouble hRand(); // random 0..1
ldouble hRand_Std();
// нормальная случайная величина с мат.ожиданием 0 и дисперсией 1
ldouble hRand_Normal(ldouble m, ldouble s);
// нормальная случайная величина с мат.ожиданием m и дисперсией s^2
Нормальная случайная величина hRand_Std() получается у нас как сумма 12 величин
равномерно распределённых на отрезке [-0.5…0.5]. Этого достаточно для практических
приложений. Если вам нужна большая точноcть, придётся реализовывать более сложные
алгоритмы.
Для того, чтобы обойти все точки из множества [0,1,...,N-1] в некотором псевдослучайном порядке поступим следующим образом. Выберем простое число p, больше или равное N и первообразный корень a по модулю N. Тогда в последовательности
[1, a, a2 mod p,..., ap-2 mod p]
все числа от 1 до p-1 встречаются ровно по одному разу. Если из них оставить только
числа ≤ N получим все числа
от 1 до N ровно по одному разу. А если из них вычесть единицу, то получим решение
исходной задачи.
Для эффектиной работы требуется для данного N найти простое p, которое не слишком превосходит N и соответствующие первообразные корни. Они были выбраны следующие:
p (prime) a mod p
0, 0, // 0
3, 1, // 1
5, 2, // 2
11, 6, // 3
17, 5, // 4
37, 13, // 5
67, 18, // 6
131, 37, // 7
257, 65, // 8
521, 134, // 9
1031, 257, // 10
2053, 516, // 11
4099, 1032, // 12
8209, 2049, // 13
16411, 4098, // 14
32771, 8196, // 15
65537, 16385, // 16
131101, 32777, // 17
262147, 65538, // 18
524309, 131073, // 19
1048583, 262145, // 20
2097169, 524304, // 21
4194319, 1048577, // 22
8388617, 2097153, // 23
16777259, 4194308, // 24
33554467, 8388611, // 25
67108879, 16777217, // 26
134217757, 33554435, // 27
268435459, 67108870, // 28
536870923, 134217732, // 29
1073741827, 268435458, // 30
2147483659, 536870920, // 31
Здесь выбрано, что p[k] - это первое простое число, большее 2k, a[k] - первый первообразный корень, больший p/4.
Для данного N находим первое простое число из этого списка, превосходящее N.
Начинать обход можно с любой точки, но последовательность точек будет всегда одна и та же. Для получения другой последовательности можно взять натуральное b взаимно простое с N и некоторое целое d. Тогда последовательность b*x[i]+d, где x[i] - последовательность, описанная выше, опять будет обходить все точки от 0 до N-1 по одному разу.
void copyBuf( int *dst, int stepDst, int *src, int stepSrc, int size );
Следующая фукнция предназначена для обхода целочисленные точки плоскости по спирали
void nextPoint( int &x, int &y );
| |
| 182
-----+----> x ----705---> x
| 463
| y | y
v v
0) 0 0
1) 1 -1
2) 1 1
3) -1 1
4) -1 -1
5) 1 0
6) 0 1
7) -1 0
8) 0 -1
9) 2 -2
10) 2 2
В компьютерной графике иногда требуется для произвольного вектора (x,y) найти среди восьми векторов
(-1,-1) ( 0,-1) ( 1,-1)
(-1, 0) ( 1, 0)
(-1, 1) ( 0, 1) ( 1, 1)
наиболее близкий к (x,y) по направлению. Это выполняет функция
void length1( int &x, int &y); // довести вектор (x,y) до координат [-1,0,1]Если исходный вектор равен 0, то он и остается нулевым.
Для преобразования между форматами представления цвета RGB ↔YUV используются следующие функции:
void rgb_yuv( int r, int g, int b, int &y, int &u, int &v ); void yuv_rgb( int &r, int &g, int &b, int y, int u, int v ); int rgb_int( int r, int g, int b ); // (r,g,b) -> x void int_rgb( int x, int &r, int &g, int &b); // x -> (r,g,b)Прямоугольник на плоскости задается четырьмя числами: верхним левым углом и его размерами:
int x0, y0, dx, dy;
Для работы с точками на границе прямоугольника предназначены следующие три функции:
bool boxBord(int x0, int y0, int dx, int dy, int x1, int y1);
// лежит ли точка (x1,y1) на границе прямоугольника
void boxNext(int x0, int y0, int dx, int dy, int &x1, int &y1);
// (x1,y1) - следующая на границе по часовой стрелке
void boxPrev(int x0, int y0, int dx, int dy, int &x1, int &y1);
// (x1,y1) - следующая на границе против часовой стрелки