Elm  2
ELM is a library providing generic data structures, OS-independent interface, plugins and XML.
VectorQueue.h
1 /*
2  * VectorQueue class interface
3  *
4  * This file is part of OTAWA
5  * Copyright (c) 2006-08, IRIT UPS.
6  *
7  * OTAWA is free software; you can redistribute it and/or modify
8  * it under the terms of the GNU General Public License as published by
9  * the Free Software Foundation; either version 2 of the License, or
10  * (at your option) any later version.
11  *
12  * OTAWA is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with OTAWA; if not, write to the Free Software
19  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20  */
21 #ifndef ELM_DATA_VECTORQUEUE_H
22 #define ELM_DATA_VECTORQUEUE_H
23 
24 #include <elm/assert.h>
25 #include "../equiv.h"
26 
27 namespace elm {
28 
29 // VectorQueue class
30 template <class T, class E = Equiv<T> >
31 class VectorQueue {
32  int hd, tl, cap;
33  T *buffer;
34  void enlarge(void);
35 public:
36  inline VectorQueue(int capacity = 4);
37  inline ~VectorQueue(void);
38 
39  inline int capacity(void) const;
40  inline int size(void) const;
41  inline bool isEmpty(void) const;
42 
43  inline bool contains(const T& val) const {
44  for(int i = hd; i != tl; i = (i + 1) & (cap - 1))
45  if(E::equals(buffer[i], val))
46  return true;
47  return false;
48  }
49 
50  inline void put(const T& value);
51  inline const T& get(void);
52  inline T& head(void) const;
53  inline void reset(void);
54 
55  // Operators
56  inline operator bool(void) const;
57  inline T *operator->(void) const;
58  inline T& operator*(void) const;
59 };
60 
61 // VectorQueue implementation
62 
63 template <class T, class E> void VectorQueue<T, E>::enlarge(void) {
64  int new_cap = cap * 2, off = 0;
65  T *new_buffer = new T[new_cap];
66  if( hd > tl) {
67  off = cap - hd;
68  for(int i = 0; i < off; i++)
69  new_buffer[i] = buffer[hd + i];
70  hd = 0;
71  }
72  for(int i = hd; i < tl; i++)
73  new_buffer[off + i - hd] = buffer[i];
74  delete [] buffer;
75  tl = off + tl - hd;
76  cap = new_cap;
77  buffer = new_buffer;
78 }
79 
80 template <class T, class E> inline VectorQueue<T, E>::VectorQueue(int capacity)
81 : hd(0), tl(0), cap(1 << capacity), buffer(new T[cap]) {
82  ASSERTP(cap >= 0, "capacity must be positive");
83 }
84 
85 template <class T, class E> inline VectorQueue<T, E>::~VectorQueue(void) {
86  delete [] buffer;
87 }
88 
89 template <class T, class E> inline int VectorQueue<T, E>::capacity(void) const {
90  return cap;
91 }
92 
93 template <class T, class E> inline int VectorQueue<T, E>::size(void) const {
94  if(hd < tl)
95  return tl - hd;
96  else
97  return (cap - hd) + tl;
98 }
99 
100 template <class T, class E> inline bool VectorQueue<T, E>::isEmpty(void) const {
101  return hd == tl;
102 }
103 
104 template <class T, class E> inline void VectorQueue<T, E>::put(const T& value) {
105  int new_tl = (tl + 1) & (cap - 1);
106  if(new_tl == hd) {
107  enlarge();
108  new_tl = tl + 1;
109  }
110  buffer[tl] = value;
111  tl = new_tl;
112 }
113 
114 template <class T, class E> inline const T& VectorQueue<T, E>::get(void) {
115  ASSERTP(hd != tl, "queue empty");
116  int res = hd;
117  hd = (hd + 1) & (cap - 1);
118  return buffer[res];
119 }
120 
121 template <class T, class E> inline T& VectorQueue<T, E>::head(void) const {
122  ASSERTP(hd != tl, "queue empty");
123  return buffer[hd];
124 }
125 
126 template <class T, class E> inline void VectorQueue<T, E>::reset(void) {
127  hd = 0;
128  tl = 0;
129 }
130 
131 template <class T, class E> inline VectorQueue<T, E>::operator bool(void) const {
132  return !isEmpty();
133 }
134 
135 template <class T, class E> inline T *VectorQueue<T, E>::operator->(void) const {
136  return &head();
137 }
138 
139 template <class T, class E> inline T& VectorQueue<T, E>::operator*(void) const {
140  return head();
141 }
142 
143 } // elm
144 
145 #endif // ELM_DATA_VECTORQUEUE_H
146 
elm::VectorQueue::head
T & head(void) const
Definition: VectorQueue.h:121
elm::VectorQueue::get
const T & get(void)
Definition: VectorQueue.h:114
elm::VectorQueue::isEmpty
bool isEmpty(void) const
Definition: VectorQueue.h:100
elm::equals
bool equals(const C1 &c1, const C2 &c2)
Definition: util.h:107
elm::VectorQueue::reset
void reset(void)
Definition: VectorQueue.h:126
elm::VectorQueue::put
void put(const T &value)
Definition: VectorQueue.h:104
elm::VectorQueue::operator->
T * operator->(void) const
Definition: VectorQueue.h:135
elm::VectorQueue
Definition: VectorQueue.h:31
value
elm::dtd::operator*
Content & operator*(Content &c)
Definition: xom_dtd.cpp:1185
bool
elm::VectorQueue::size
int size(void) const
Definition: VectorQueue.h:93
elm
Definition: adapter.h:26
elm::t::size
uint64 size
Definition: arch.h:35
elm::VectorQueue::contains
bool contains(const T &val) const
Definition: VectorQueue.h:43
elm::t::put
void put(var< T > &x, in< T > v)
Definition: type_info.h:287
elm::VectorQueue::operator*
T & operator*(void) const
Definition: VectorQueue.h:139
elm::VectorQueue::VectorQueue
VectorQueue(int capacity=4)
Definition: VectorQueue.h:80
elm::VectorQueue::capacity
int capacity(void) const
Definition: VectorQueue.h:89
elm::t::get
ret< T > get(const var< T > &v)
Definition: type_info.h:288
elm::VectorQueue::~VectorQueue
~VectorQueue(void)
Definition: VectorQueue.h:85