test/counter_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 24 Mar 2009 00:18:25 +0100
changeset 596 8c3112a66878
parent 209 765619b7cbb2
child 549 f53d641aa967
permissions -rw-r--r--
Use XTI implementation instead of ATI in NetworkSimplex (#234)

XTI (eXtended Threaded Index) is an imporved version of the widely
known ATI (Augmented Threaded Index) method for storing and updating
the spanning tree structure in Network Simplex algorithms.

In the ATI data structure three indices are stored for each node:
predecessor, thread and depth. In the XTI data structure depth is
replaced by the number of successors and the last successor
(according to the thread index).
alpar@209
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@119
     2
 *
alpar@209
     3
 * This file is a part of LEMON, a generic C++ optimization library.
alpar@119
     4
 *
alpar@440
     5
 * Copyright (C) 2003-2009
alpar@119
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@119
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@119
     8
 *
alpar@119
     9
 * Permission to use, modify and distribute this software is granted
alpar@119
    10
 * provided that this copyright notice appears in all copies. For
alpar@119
    11
 * precise terms see the accompanying LICENSE file.
alpar@119
    12
 *
alpar@119
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@119
    14
 * express or implied, and with no claim as to its suitability for any
alpar@119
    15
 * purpose.
alpar@119
    16
 *
alpar@119
    17
 */
alpar@119
    18
alpar@119
    19
#include <lemon/counter.h>
kpeter@171
    20
#include <vector>
alpar@119
    21
kpeter@171
    22
using namespace lemon;
alpar@119
    23
kpeter@171
    24
template <typename T>
kpeter@171
    25
void bubbleSort(std::vector<T>& v) {
kpeter@171
    26
  Counter op("Bubble Sort - Operations: ");
kpeter@171
    27
  Counter::NoSubCounter as(op, "Assignments: ");
kpeter@171
    28
  Counter::NoSubCounter co(op, "Comparisons: ");
kpeter@171
    29
  for (int i = v.size()-1; i > 0; --i) {
kpeter@171
    30
    for (int j = 0; j < i; ++j) {
kpeter@171
    31
      if (v[j] > v[j+1]) {
kpeter@171
    32
        T tmp = v[j];
kpeter@171
    33
        v[j] = v[j+1];
kpeter@171
    34
        v[j+1] = tmp;
kpeter@171
    35
        as += 3;
kpeter@171
    36
      }
kpeter@171
    37
      ++co;
kpeter@171
    38
    }
kpeter@171
    39
  }
kpeter@171
    40
}
alpar@119
    41
kpeter@171
    42
template <typename T>
kpeter@171
    43
void insertionSort(std::vector<T>& v) {
kpeter@171
    44
  Counter op("Insertion Sort - Operations: ");
kpeter@171
    45
  Counter::NoSubCounter as(op, "Assignments: ");
kpeter@171
    46
  Counter::NoSubCounter co(op, "Comparisons: ");
kpeter@171
    47
  for (int i = 1; i < int(v.size()); ++i) {
kpeter@171
    48
    T value = v[i];
kpeter@171
    49
    ++as;
kpeter@171
    50
    int j = i;
kpeter@171
    51
    while (j > 0 && v[j-1] > value) {
kpeter@171
    52
      v[j] = v[j-1];
kpeter@171
    53
      --j;
kpeter@171
    54
      ++co; ++as;
kpeter@171
    55
    }
kpeter@171
    56
    v[j] = value;
kpeter@171
    57
    ++as;
kpeter@171
    58
  }
kpeter@171
    59
}
kpeter@171
    60
kpeter@171
    61
template <typename MyCounter>
kpeter@171
    62
void counterTest() {
kpeter@171
    63
  MyCounter c("Main Counter: ");
kpeter@171
    64
  c++;
kpeter@171
    65
  typename MyCounter::SubCounter d(c, "SubCounter: ");
kpeter@171
    66
  d++;
kpeter@171
    67
  typename MyCounter::SubCounter::NoSubCounter e(d, "SubSubCounter: ");
kpeter@171
    68
  e++;
kpeter@171
    69
  d+=3;
kpeter@171
    70
  c-=4;
kpeter@171
    71
  e-=2;
kpeter@171
    72
  c.reset(2);
kpeter@171
    73
  c.reset();
kpeter@171
    74
}
kpeter@171
    75
kpeter@171
    76
void init(std::vector<int>& v) {
kpeter@171
    77
  v[0] = 10; v[1] = 60; v[2] = 20; v[3] = 90; v[4] = 100;
alpar@209
    78
  v[5] = 80; v[6] = 40; v[7] = 30; v[8] = 50; v[9] = 70;
alpar@119
    79
}
alpar@119
    80
alpar@119
    81
int main()
alpar@119
    82
{
kpeter@171
    83
  counterTest<Counter>();
kpeter@171
    84
  counterTest<NoCounter>();
alpar@209
    85
kpeter@171
    86
  std::vector<int> x(10);
kpeter@171
    87
  init(x); bubbleSort(x);
kpeter@171
    88
  init(x); insertionSort(x);
alpar@119
    89
alpar@119
    90
  return 0;
alpar@119
    91
}