← Back to branch summary

~ubuntu-branches/ubuntu/raring/babel/raring-proposed

« back to all changes in this revision

Viewing changes to regression/sort/libCxx/sort_QuickSort_Impl.cxx

  • Committer: Bazaar Package Importer
  • Author(s): Adam C. Powell, IV
  • Date: 2008-08-01 07:56:58 UTC
  • mfrom: (3.1.2 intrepid)
  • Revision ID: james.westby@ubuntu.com-20080801075658-9ezcrbh8dcs8lg70
Tags: 1.2.0.dfsg-6
http://bugs.debian.org/483324
Added libparsifal-dev as dependency to libsidl-dev (closes: #483324).

Show diffs side-by-side

added added

removed removed

Lines of Context:
regression/sort/libCxx/sort_QuickSort_Impl.cxx
 
1
// 
 
2
// File:          sort_QuickSort_Impl.cxx
 
3
// Symbol:        sort.QuickSort-v0.1
 
4
// Symbol Type:   class
 
5
// Babel Version: 1.2.0
 
6
// Description:   Server-side implementation for sort.QuickSort
 
7
// 
 
8
// WARNING: Automatically generated; only changes within splicers preserved
 
9
// 
 
10
// 
 
11
#include "sort_QuickSort_Impl.hxx"
 
12
 
 
13
// 
 
14
// Includes for all method dependencies.
 
15
// 
 
16
#ifndef included_sidl_BaseInterface_hxx
 
17
#include "sidl_BaseInterface.hxx"
 
18
#endif
 
19
#ifndef included_sidl_ClassInfo_hxx
 
20
#include "sidl_ClassInfo.hxx"
 
21
#endif
 
22
#ifndef included_sort_Comparator_hxx
 
23
#include "sort_Comparator.hxx"
 
24
#endif
 
25
#ifndef included_sort_Container_hxx
 
26
#include "sort_Container.hxx"
 
27
#endif
 
28
#ifndef included_sort_Counter_hxx
 
29
#include "sort_Counter.hxx"
 
30
#endif
 
31
#ifndef included_sidl_NotImplementedException_hxx
 
32
#include "sidl_NotImplementedException.hxx"
 
33
#endif
 
34
#line 35 "/home/epperly/current/release_1.2.0/linux_dist/../babel_branch/regression/sort/libCxx/sort_QuickSort_Impl.cxx"
 
35
// DO-NOT-DELETE splicer.begin(sort.QuickSort._includes)
 
36
/**
 
37
 * Choose the middle of the first, middle and last element of the
 
38
 * list.  For small lists, return the middle without checking.
 
39
 */
 
40
static int32_t
 
41
choosePivot(::sort::Container  &elems,
 
42
            ::sort::Comparator &comp,
 
43
            ::sort::Counter    &cmp,
 
44
            int32_t           start,
 
45
            int32_t           end)
 
46
{
 
47
  int32_t pivot = (start + end) >> 1;
 
48
  if ((end - start) > 4) {
 
49
    int32_t mid = pivot;
 
50
    cmp.inc();
 
51
    if (elems.compare(start, mid, comp) <= 0) {
 
52
      cmp.inc();
 
53
      if (elems.compare(mid, end - 1, comp) > 0) {
 
54
        cmp.inc();
 
55
        if (elems.compare( start, end - 1, comp) < 0) {
 
56
          pivot = end - 1;
 
57
        }
 
58
        else {
 
59
          pivot = start;
 
60
        }
 
61
      }
 
62
    }
 
63
    else {
 
64
      cmp.inc();
 
65
      if (elems.compare( mid, end - 1, comp) < 0) {
 
66
        cmp.inc();
 
67
        if (elems.compare( start, end - 1, comp) > 0) {
 
68
          pivot = end - 1;
 
69
        }
 
70
        else {
 
71
          pivot = start;
 
72
        }
 
73
      }
 
74
    }
 
75
  }
 
76
  return pivot;
 
77
}
 
78
 
 
79
static void 
 
80
quickSort(::sort::Container  &elems,
 
81
          ::sort::Comparator &comp,
 
82
          ::sort::Counter    &cmp,
 
83
          ::sort::Counter    &swp,
 
84
          int32_t           start,
 
85
          int32_t           end)
 
86
{
 
87
  if ((end - start) > 1) {
 
88
    int32_t pivot = choosePivot(elems, comp, cmp, start, end);
 
89
    int32_t i = start;
 
90
    int32_t j = end;
 
91
    if (pivot != start) {
 
92
      swp.inc();
 
93
      elems.swap(start, pivot);
 
94
    }
 
95
    for(;;) {
 
96
      do {
 
97
        --j;
 
98
        cmp.inc();
 
99
      } while (elems.compare( start, j, comp) < 0);
 
100
      while (++i < j) {
 
101
        cmp.inc();
 
102
        if (elems.compare( start, i, comp) < 0) break;
 
103
      }
 
104
      if (i >= j) break;
 
105
      swp.inc();
 
106
      elems.swap(i, j);
 
107
    }
 
108
    if (j != start) {
 
109
      swp.inc();
 
110
      elems.swap(start, j);
 
111
    }
 
112
    quickSort(elems, comp, cmp, swp, start, j);
 
113
    quickSort(elems, comp, cmp, swp, j + 1, end);
 
114
  }
 
115
}
 
116
// DO-NOT-DELETE splicer.end(sort.QuickSort._includes)
 
117
#line 117 "../regression/sort/libCxx/sort_QuickSort_Impl.cxx"
 
118
 
 
119
// special constructor, used for data wrapping(required).  Do not put code here unless you really know what you're doing!
 
120
sort::QuickSort_impl::QuickSort_impl() : StubBase(reinterpret_cast< void*>(
 
121
  ::sort::QuickSort::_wrapObj(reinterpret_cast< void*>(this))),false) , 
 
122
  _wrapped(true){ 
 
123
#line 124 "/home/epperly/current/release_1.2.0/linux_dist/../babel_branch/regression/sort/libCxx/sort_QuickSort_Impl.cxx"
 
124
  // DO-NOT-DELETE splicer.begin(sort.QuickSort._ctor2)
 
125
  // Insert-Code-Here {sort.QuickSort._ctor2} (ctor2)
 
126
  // DO-NOT-DELETE splicer.end(sort.QuickSort._ctor2)
 
127
#line 127 "../regression/sort/libCxx/sort_QuickSort_Impl.cxx"
 
128
}
 
129
 
 
130
// user defined constructor
 
131
void sort::QuickSort_impl::_ctor() {
 
132
#line 133 "/home/epperly/current/release_1.2.0/linux_dist/../babel_branch/regression/sort/libCxx/sort_QuickSort_Impl.cxx"
 
133
  // DO-NOT-DELETE splicer.begin(sort.QuickSort._ctor)
 
134
  // add construction details here
 
135
  // DO-NOT-DELETE splicer.end(sort.QuickSort._ctor)
 
136
#line 136 "../regression/sort/libCxx/sort_QuickSort_Impl.cxx"
 
137
}
 
138
 
 
139
// user defined destructor
 
140
void sort::QuickSort_impl::_dtor() {
 
141
#line 142 "/home/epperly/current/release_1.2.0/linux_dist/../babel_branch/regression/sort/libCxx/sort_QuickSort_Impl.cxx"
 
142
  // DO-NOT-DELETE splicer.begin(sort.QuickSort._dtor)
 
143
  // add destruction details here
 
144
  // DO-NOT-DELETE splicer.end(sort.QuickSort._dtor)
 
145
#line 145 "../regression/sort/libCxx/sort_QuickSort_Impl.cxx"
 
146
}
 
147
 
 
148
// static class initializer
 
149
void sort::QuickSort_impl::_load() {
 
150
#line 151 "/home/epperly/current/release_1.2.0/linux_dist/../babel_branch/regression/sort/libCxx/sort_QuickSort_Impl.cxx"
 
151
  // DO-NOT-DELETE splicer.begin(sort.QuickSort._load)
 
152
  // guaranteed to be called at most once before any other method in this class
 
153
  // DO-NOT-DELETE splicer.end(sort.QuickSort._load)
 
154
#line 154 "../regression/sort/libCxx/sort_QuickSort_Impl.cxx"
 
155
}
 
156
 
 
157
// user defined static methods: (none)
 
158
 
 
159
// user defined non-static methods:
 
160
/**
 
161
 * Sort elements using Quick Sort.
 
162
 */
 
163
void
 
164
sort::QuickSort_impl::sort_impl (
 
165
  /* in */::sort::Container& elems,
 
166
  /* in */::sort::Comparator& comp ) 
 
167
{
 
168
#line 169 "/home/epperly/current/release_1.2.0/linux_dist/../babel_branch/regression/sort/libCxx/sort_QuickSort_Impl.cxx"
 
169
  // DO-NOT-DELETE splicer.begin(sort.QuickSort.sort)
 
170
  const int32_t num = elems.getLength();
 
171
  ::sort::Counter cmp = getCompareCounter();
 
172
  ::sort::Counter swp = getSwapCounter();
 
173
  quickSort(elems, comp, cmp, swp, 0, num);
 
174
  // DO-NOT-DELETE splicer.end(sort.QuickSort.sort)
 
175
#line 175 "../regression/sort/libCxx/sort_QuickSort_Impl.cxx"
 
176
}
 
177
 
 
178
/**
 
179
 * Return quick sort.
 
180
 */
 
181
::std::string
 
182
sort::QuickSort_impl::getName_impl () 
 
183
 
 
184
{
 
185
#line 186 "/home/epperly/current/release_1.2.0/linux_dist/../babel_branch/regression/sort/libCxx/sort_QuickSort_Impl.cxx"
 
186
  // DO-NOT-DELETE splicer.begin(sort.QuickSort.getName)
 
187
  return "Quick sort";
 
188
  // DO-NOT-DELETE splicer.end(sort.QuickSort.getName)
 
189
#line 189 "../regression/sort/libCxx/sort_QuickSort_Impl.cxx"
 
190
}
 
191
 
 
192
 
 
193
#line 194 "/home/epperly/current/release_1.2.0/linux_dist/../babel_branch/regression/sort/libCxx/sort_QuickSort_Impl.cxx"
 
194
// DO-NOT-DELETE splicer.begin(sort.QuickSort._misc)
 
195
// Put miscellaneous code here
 
196
// DO-NOT-DELETE splicer.end(sort.QuickSort._misc)
 
197
#line 197 "../regression/sort/libCxx/sort_QuickSort_Impl.cxx"
 
198