← Back to branch summary

~ubuntu-branches/ubuntu/wily/qgis/wily

« back to all changes in this revision

Viewing changes to src/core/pal/linkedlist.hpp

  • Committer: Bazaar Package Importer
  • Author(s): Johan Van de Wauw
  • Date: 2010-07-11 20:23:24 UTC
  • mfrom: (3.1.4 squeeze)
  • Revision ID: james.westby@ubuntu.com-20100711202324-5ktghxa7hracohmr
Tags: 1.4.0+12730-3ubuntu1
https://launchpad.net/bugs/540941
* Merge from Debian unstable (LP: #540941).
* Fix compilation issues with QT 4.7
* Add build-depends on libqt4-webkit-dev 

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/core/pal/linkedlist.hpp
 
1
/*
 
2
 *   libpal - Automated Placement of Labels Library
 
3
 *
 
4
 *   Copyright (C) 2008 Maxence Laurent, MIS-TIC, HEIG-VD
 
5
 *                      University of Applied Sciences, Western Switzerland
 
6
 *                      http://www.hes-so.ch
 
7
 *
 
8
 *   Contact:
 
9
 *      maxence.laurent <at> heig-vd <dot> ch
 
10
 *    or
 
11
 *      eric.taillard <at> heig-vd <dot> ch
 
12
 *
 
13
 * This file is part of libpal.
 
14
 *
 
15
 * libpal is free software: you can redistribute it and/or modify
 
16
 * it under the terms of the GNU General Public License as published by
 
17
 * the Free Software Foundation, either version 3 of the License, or
 
18
 * (at your option) any later version.
 
19
 *
 
20
 * libpal is distributed in the hope that it will be useful,
 
21
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
22
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
23
 * GNU General Public License for more details.
 
24
 *
 
25
 * You should have received a copy of the GNU General Public License
 
26
 * along with libpal.  If not, see <http://www.gnu.org/licenses/>.
 
27
 *
 
28
 */
 
29
 
 
30
#ifdef HAVE_CONFIG_H
 
31
#include <config.h>
 
32
#endif
 
33
 
 
34
#ifndef _LINKED_LIST_H
 
35
#define _LINKED_LIST_H
 
36
 
 
37
#include <iostream>
 
38
 
 
39
namespace pal
 
40
{
 
41
 
 
42
  class Layer;
 
43
 
 
44
  /**
 
45
   * \brief Generic cell for LinkedList
 
46
   * \param Type Generic class
 
47
   */
 
48
  template <class Type>
 
49
  class Cell
 
50
  {
 
51
    public:
 
52
      /** \brief Create a new Cell
 
53
       * \param item The object to store
 
54
       */
 
55
      Cell( Type item ) : item( item ), next( NULL ) {};
 
56
      Type item;
 
57
      Cell *next;
 
58
  };
 
59
 
 
60
  /**
 
61
   * \brief Generic queue
 
62
   * \param Type generic class
 
63
   * \todo thread safe
 
64
   */
 
65
  template <class Type>
 
66
  class LinkedList
 
67
  {
 
68
 
 
69
      friend class Layer;
 
70
 
 
71
    private:
 
72
      Cell<Type> *first;
 
73
      Cell<Type> *last;
 
74
      int s;
 
75
 
 
76
      bool ( *compare )( Type a, Type b );
 
77
 
 
78
    public:
 
79
 
 
80
      /**
 
81
       * \brief Create a new empty list
 
82
       */
 
83
      LinkedList( bool ( *compare )( Type a, Type b ) ) : first( NULL ), last( NULL ), s( 0 ), compare( compare ) {};
 
84
      /**
 
85
       * \brief delete the list
 
86
       */
 
87
      ~LinkedList();
 
88
 
 
89
      //void setCompareMethod (bool (*compare)(Type a, Type b));
 
90
 
 
91
      /**
 
92
       * \brief is item into list ?
 
93
       * \return true or false
 
94
       */
 
95
      bool isIn( Type item );
 
96
 
 
97
      /**
 
98
       * \brief Insert an item at the end
 
99
       * \param item The item to insert
 
100
       */
 
101
      void push_back( Type item );
 
102
 
 
103
      /**
 
104
       * \brief Insert an item in first position
 
105
       * \param item The item to insert
 
106
       */
 
107
      void push_front( Type item );
 
108
 
 
109
      /**
 
110
       * \brief extract and return the last item
 
111
       * \return Extracted item
 
112
       */
 
113
      Type pop_front();
 
114
 
 
115
      /**
 
116
       * \brief get the list size
 
117
       * \return the number of item into the queue
 
118
       */
 
119
      int size();
 
120
 
 
121
      /**
 
122
       * \brief get the first cell
 
123
       * \return the first elem, as iterator
 
124
       */
 
125
      Cell<Type> *getFirst();
 
126
 
 
127
      Cell<Type> *search( Type item );
 
128
 
 
129
      void remove( Type item );
 
130
 
 
131
      void clean();
 
132
  };
 
133
 
 
134
 
 
135
 
 
136
  template <class Type>
 
137
  LinkedList<Type>::~LinkedList()
 
138
  {
 
139
    Cell<Type> *cur;
 
140
    Cell<Type> *it;
 
141
 
 
142
    cur = first;
 
143
 
 
144
    while ( cur )
 
145
    {
 
146
      it = cur;
 
147
      cur = cur->next;
 
148
      delete it;
 
149
    }
 
150
  }
 
151
 
 
152
  template <class Type>void LinkedList<Type>::push_back( Type item )
 
153
  {
 
154
    if ( s == 0 )
 
155
    {
 
156
      first = new Cell<Type> ( item );
 
157
      last = first;
 
158
    }
 
159
    else
 
160
    {
 
161
      last->next = new Cell<Type> ( item );
 
162
      last = last->next;
 
163
    }
 
164
    s++;
 
165
  }
 
166
 
 
167
  template <class Type>void LinkedList<Type>::push_front( Type item )
 
168
  {
 
169
    Cell<Type> *n = new Cell<Type> ( item );
 
170
    n->next = first;
 
171
    first = n;
 
172
    s++;
 
173
  }
 
174
 
 
175
 
 
176
  template<class Type>Type  LinkedList<Type>::pop_front()
 
177
  {
 
178
    Type item;
 
179
    Cell<Type> *it;
 
180
 
 
181
    if ( first )
 
182
    {
 
183
      it = first;
 
184
      item = it->item;
 
185
      first = first->next;
 
186
      delete it;
 
187
      s--;
 
188
    }
 
189
    else
 
190
      item = Type( 0 );
 
191
 
 
192
    return item;
 
193
  }
 
194
 
 
195
  template <class Type>bool LinkedList<Type>::isIn( Type item )
 
196
  {
 
197
    Cell<Type> *cur = first;
 
198
 
 
199
    while ( cur )
 
200
    {
 
201
      if ( item == cur->item )
 
202
        return true;
 
203
      cur = cur->next;
 
204
    }
 
205
 
 
206
    return false;
 
207
  }
 
208
 
 
209
  template <class Type>int LinkedList<Type>::size()
 
210
  {
 
211
    return s;
 
212
  }
 
213
 
 
214
 
 
215
  template <class Type>Cell<Type> *LinkedList<Type>::getFirst()
 
216
  {
 
217
    return first;
 
218
  }
 
219
 
 
220
 
 
221
  template <class Type> void LinkedList<Type>::remove( Type item )
 
222
  {
 
223
    Cell<Type> *p = first;
 
224
    Cell<Type> *q;
 
225
 
 
226
    if ( first )
 
227
    {
 
228
      if ( compare( item, p->item ) )
 
229
      {
 
230
        first = p->next;
 
231
        s--;
 
232
        delete p;
 
233
        return;
 
234
      }
 
235
      while ( p->next && !compare( p->next->item, item ) ) {p = p->next;}
 
236
 
 
237
      if ( p->next )
 
238
      {
 
239
        q = p->next;
 
240
        p->next = q->next;
 
241
        s--;
 
242
        delete q;
 
243
        if ( !p->next )
 
244
          last = p;
 
245
      }
 
246
    }
 
247
  }
 
248
 
 
249
  template <class Type> Cell<Type> * LinkedList<Type>::search( Type item )
 
250
  {
 
251
    Cell<Type> *p = first;
 
252
 
 
253
    while ( p && !compare( p->item, item ) )
 
254
    {
 
255
      p = p->next;
 
256
    }
 
257
 
 
258
    return p;
 
259
  }
 
260
 
 
261
 
 
262
  /*template <class Type> void LinkedList<Type>::setCompareMethod (bool (*compare)(Type a, Type b)){
 
263
     this->compare = compare;
 
264
  }*/
 
265
 
 
266
  template <class Type> void LinkedList<Type>::clean()
 
267
  {
 
268
    Cell<Type> *it = first;
 
269
    Cell<Type> *cur;
 
270
 
 
271
    while ( it )
 
272
    {
 
273
      cur = it;
 
274
      it = it->next;
 
275
      delete cur;
 
276
    }
 
277
    first = last = NULL;
 
278
    s = 0;
 
279
  }
 
280
} // end namespace
 
281
#endif