alpar@209: /* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@119:  *
alpar@209:  * This file is a part of LEMON, a generic C++ optimization library.
alpar@119:  *
alpar@119:  * Copyright (C) 2003-2008
alpar@119:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@119:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@119:  *
alpar@119:  * Permission to use, modify and distribute this software is granted
alpar@119:  * provided that this copyright notice appears in all copies. For
alpar@119:  * precise terms see the accompanying LICENSE file.
alpar@119:  *
alpar@119:  * This software is provided "AS IS" with no warranty of any kind,
alpar@119:  * express or implied, and with no claim as to its suitability for any
alpar@119:  * purpose.
alpar@119:  *
alpar@119:  */
alpar@119: 
alpar@119: #include <lemon/counter.h>
kpeter@171: #include <vector>
alpar@119: 
kpeter@171: using namespace lemon;
alpar@119: 
kpeter@171: template <typename T>
kpeter@171: void bubbleSort(std::vector<T>& v) {
kpeter@171:   Counter op("Bubble Sort - Operations: ");
kpeter@171:   Counter::NoSubCounter as(op, "Assignments: ");
kpeter@171:   Counter::NoSubCounter co(op, "Comparisons: ");
kpeter@171:   for (int i = v.size()-1; i > 0; --i) {
kpeter@171:     for (int j = 0; j < i; ++j) {
kpeter@171:       if (v[j] > v[j+1]) {
kpeter@171:         T tmp = v[j];
kpeter@171:         v[j] = v[j+1];
kpeter@171:         v[j+1] = tmp;
kpeter@171:         as += 3;
kpeter@171:       }
kpeter@171:       ++co;
kpeter@171:     }
kpeter@171:   }
kpeter@171: }
alpar@119: 
kpeter@171: template <typename T>
kpeter@171: void insertionSort(std::vector<T>& v) {
kpeter@171:   Counter op("Insertion Sort - Operations: ");
kpeter@171:   Counter::NoSubCounter as(op, "Assignments: ");
kpeter@171:   Counter::NoSubCounter co(op, "Comparisons: ");
kpeter@171:   for (int i = 1; i < int(v.size()); ++i) {
kpeter@171:     T value = v[i];
kpeter@171:     ++as;
kpeter@171:     int j = i;
kpeter@171:     while (j > 0 && v[j-1] > value) {
kpeter@171:       v[j] = v[j-1];
kpeter@171:       --j;
kpeter@171:       ++co; ++as;
kpeter@171:     }
kpeter@171:     v[j] = value;
kpeter@171:     ++as;
kpeter@171:   }
kpeter@171: }
kpeter@171: 
kpeter@171: template <typename MyCounter>
kpeter@171: void counterTest() {
kpeter@171:   MyCounter c("Main Counter: ");
kpeter@171:   c++;
kpeter@171:   typename MyCounter::SubCounter d(c, "SubCounter: ");
kpeter@171:   d++;
kpeter@171:   typename MyCounter::SubCounter::NoSubCounter e(d, "SubSubCounter: ");
kpeter@171:   e++;
kpeter@171:   d+=3;
kpeter@171:   c-=4;
kpeter@171:   e-=2;
kpeter@171:   c.reset(2);
kpeter@171:   c.reset();
kpeter@171: }
kpeter@171: 
kpeter@171: void init(std::vector<int>& v) {
kpeter@171:   v[0] = 10; v[1] = 60; v[2] = 20; v[3] = 90; v[4] = 100;
alpar@209:   v[5] = 80; v[6] = 40; v[7] = 30; v[8] = 50; v[9] = 70;
alpar@119: }
alpar@119: 
alpar@119: int main()
alpar@119: {
kpeter@171:   counterTest<Counter>();
kpeter@171:   counterTest<NoCounter>();
alpar@209: 
kpeter@171:   std::vector<int> x(10);
kpeter@171:   init(x); bubbleSort(x);
kpeter@171:   init(x); insertionSort(x);
alpar@119: 
alpar@119:   return 0;
alpar@119: }