CXXR (C++ R)
HeterogeneousList.hpp
Go to the documentation of this file.
1 /*CXXR $Id: HeterogeneousList.hpp 1348 2013-02-25 17:49:03Z arr $
2  *CXXR
3  *CXXR This file is part of CXXR, a project to refactor the R interpreter
4  *CXXR into C++. It may consist in whole or in part of program code and
5  *CXXR documentation taken from the R project itself, incorporated into
6  *CXXR CXXR (and possibly MODIFIED) under the terms of the GNU General Public
7  *CXXR Licence.
8  *CXXR
9  *CXXR CXXR is Copyright (C) 2008-13 Andrew R. Runnalls, subject to such other
10  *CXXR copyrights and copyright restrictions as may be stated below.
11  *CXXR
12  *CXXR CXXR is not part of the R project, and bugs and other issues should
13  *CXXR not be reported via r-bugs or other R project channels; instead refer
14  *CXXR to the CXXR website.
15  *CXXR */
16 
17 /*
18  * R : A Computer Language for Statistical Data Analysis
19  * Copyright (C) 1995, 1996 Robert Gentleman and Ross Ihaka
20  * Copyright (C) 1999-2006 The R Development Core Team.
21  *
22  * This program is free software; you can redistribute it and/or modify
23  * it under the terms of the GNU General Public License as published by
24  * the Free Software Foundation; either version 2.1 of the License, or
25  * (at your option) any later version.
26  *
27  * This program is distributed in the hope that it will be useful,
28  * but WITHOUT ANY WARRANTY; without even the implied warranty of
29  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30  * GNU Lesser General Public License for more details.
31  *
32  * You should have received a copy of the GNU General Public License
33  * along with this program; if not, a copy is available at
34  * http://www.r-project.org/Licenses/
35  */
36 
43 #ifndef HETEROGENEOUSLIST_HPP
44 #define HETEROGENEOUSLIST_HPP
45 
46 #include <iterator>
47 
48 namespace CXXR {
49  template <class Node> class HeterogeneousList;
50 
54  public:
57  class Link {
58  public:
63  Link()
64  : m_prev(this), m_next(this)
65  {}
66 
74  : m_prev(list->m_peg->m_prev), m_next(m_prev->m_next)
75  {
76  m_prev->m_next = this;
77  m_next->m_prev = this;
78  }
79 
85  void freeLink()
86  {
87  m_prev->m_next = m_next;
88  m_next->m_prev = m_prev;
89  m_prev = this;
90  m_next = this;
91  }
92  protected:
93  friend class HeterogeneousListBase;
94 
100  virtual ~Link()
101  {
102  m_prev->m_next = m_next;
103  m_next->m_prev = m_prev;
104  }
105  private:
106  Link* m_prev;
107  Link* m_next;
108  };
109 
113  : m_peg(new Link)
114  {}
115 
121  {
122  clear();
123  delete m_peg;
124  }
125 
129  void clear();
130 
135  bool empty() const
136  {
137  return m_peg->m_next == m_peg;
138  }
139 
144  void freeLinks();
145  protected:
152  static Link* predecessor(Link* link)
153  {
154  return link->m_prev;
155  }
156 
163  static Link* successor(Link* link)
164  {
165  return link->m_next;
166  }
167  private:
168  template <class Node> friend class HeterogeneousList;
169 
170  Link* m_peg; // dummy link representing end(); its successor
171  // is begin().
172 
173  // Establish a bidirectional link with 'aft' as the successor
174  // of 'fore':
175  static void link(Link* fore, Link* aft)
176  {
177  fore->m_next = aft;
178  aft->m_prev = fore;
179  }
180 
181  // Move 'mover' from its current list location to just before 'pos':
182  static void splice_link(Link* pos, Link* mover)
183  {
184  link(mover->m_prev, mover->m_next);
185  link(pos->m_prev, mover);
186  link(mover, pos);
187  }
188 
189  // Move all the nodes starting at 'from' up to but not
190  // including 'to' so that they appear in order just before
191  // 'pos'. A no-op if from==to or pos==to.
192  static void splice_links(Link* pos, Link* from, Link* to);
193 
194  // Move all the nodes on 'other' so that they appear in order
195  // at the end of this list, leaving 'other' as an empty list.
196  // A no-op if other == this.
197  void splice_list(HeterogeneousListBase* other)
198  {
199  splice_links(m_peg, other->m_peg->m_next, other->m_peg);
200  }
201  };
202 
209  template <class Node>
211  public:
215  : public std::iterator<std::bidirectional_iterator_tag,
216  const Node*>
217  {
218  public:
219  const Node* operator*() const
220  {
221  return static_cast<const Node*>(m_link);
222  }
223 
224  bool operator!=(const_iterator other) const
225  {
226  return m_link != other.m_link;
227  }
228 
229  const_iterator operator++()
230  {
231  m_link = successor(m_link);
232  return *this;
233  }
234  private:
235  friend class HeterogeneousList<Node>;
236 
237  Link* m_link;
238 
239  explicit const_iterator(Link* link)
240  : m_link(link)
241  {}
242  };
243 
249  Node* back()
250  {
251  return static_cast<Node*>(predecessor(m_peg));
252  }
253 
259  const Node* back() const
260  {
261  return static_cast<const Node*>(predecessor(m_peg));
262  }
263 
264  const_iterator begin() const
265  {
266  return const_iterator(successor(m_peg));
267  }
268 
269  const_iterator end() const
270  {
271  return const_iterator(m_peg);
272  }
273 
279  Node* front()
280  {
281  return static_cast<Node*>(successor(m_peg));
282  }
283 
289  const Node* front() const
290  {
291  return static_cast<const Node*>(successor(m_peg));
292  }
293 
300  void splice_back(const Node* node)
301  {
302  splice_link(m_peg, asLink(node));
303  }
304 
316  {
317  splice_list(other);
318  }
319  private:
320  // If C++ had mutable inheritance, we'd have Node mutably
321  // inherit from Link. But it doesn't, so instead we cast away
322  // const as we upcast:
323  Link* asLink(const Node* node)
324  {
325  return const_cast<Node*>(node);
326  }
327  };
328 } // namespace CXXR
329 
330 #endif // HETEROGENEOUSLIST_HPP