OpenCores
URL https://opencores.org/ocsvn/scarts/scarts/trunk

Subversion Repositories scarts

[/] [scarts/] [trunk/] [toolchain/] [scarts-gcc/] [gcc-4.1.1/] [libstdc++-v3/] [testsuite/] [ext/] [pb_assoc/] [example/] [tree_intervals.cc] - Blame information for rev 19

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 19 jlechner
// -*- C++ -*-
2
 
3
// Copyright (C) 2005 Free Software Foundation, Inc.
4
//
5
// This file is part of the GNU ISO C++ Library.  This library is free
6
// software; you can redistribute it and/or modify it under the
7
// terms of the GNU General Public License as published by the
8
// Free Software Foundation; either version 2, or (at your option)
9
// any later version.
10
 
11
// This library is distributed in the hope that it will be useful,
12
// but WITHOUT ANY WARRANTY; without even the implied warranty of
13
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14
// GNU General Public License for more details.
15
 
16
// You should have received a copy of the GNU General Public License along
17
// with this library; see the file COPYING.  If not, write to the Free
18
// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
19
// USA.
20
 
21
// As a special exception, you may use this file as part of a free software
22
// library without restriction.  Specifically, if other files instantiate
23
// templates or use macros or inline functions from this file, or you compile
24
// this file and link it with other files to produce an executable, this
25
// file does not by itself cause the resulting executable to be covered by
26
// the GNU General Public License.  This exception does not however
27
// invalidate any other reasons why the executable file might be covered by
28
// the GNU General Public License.
29
 
30
// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
31
 
32
// Permission to use, copy, modify, sell, and distribute this software
33
// is hereby granted without fee, provided that the above copyright
34
// notice appears in all copies, and that both that copyright notice and
35
// this permission notice appear in supporting documentation. None of
36
// the above authors, nor IBM Haifa Research Laboratories, make any
37
// representation about the suitability of this software for any
38
// purpose. It is provided "as is" without express or implied warranty.
39
 
40
/*
41
 * @file tree_set_intervals_example.cpp
42
 * An example showing how to augment a trees to support operations involving
43
 *      line intervals.
44
 */
45
 
46
// For ov_tree_set
47
#include <ext/pb_assoc/assoc_cntnr.hpp>
48
// For assert
49
#include <cassert>
50
// For NULL
51
#include <cstdlib>
52
 
53
/*
54
 * Following are definitions of line intervals and functors operating on them.
55
 *      As the purpose of this example is node invariants, and not
56
 *      computational-geometry algorithms per-se, some simplifications are made
57
 *(e.g., intervals are defined by unsigned integers, and not by*a parameterized type, data members are public, etc.).
58
 */
59
 
60
/*
61
 * An interval of unsigned integers.
62
 **/
63
struct interval
64
{
65
  /*
66
   * Constructor.
67
   * @param start [i] - Start point.
68
   * @param end [i] - End point.
69
   */
70
  interval(unsigned int start, unsigned int end) : m_start(start),
71
                                                   m_end(end)
72
  {
73
    assert(start <= end);
74
  }
75
 
76
  /*
77
   * Comparison predicate.
78
   * @param r_rhs [i] - Right-hand object with which to compare.
79
   **/
80
  bool
81
  operator<(const interval& r_rhs) const
82
  {
83
    if (m_start != r_rhs.m_start)
84
      return (m_start < r_rhs.m_start);
85
 
86
    return (m_end < r_rhs.m_end);
87
  }
88
 
89
  /*
90
   * Start point.
91
   */
92
  unsigned int m_start;
93
 
94
  /*
95
   * End point.
96
   **/
97
  unsigned int m_end;
98
};
99
 
100
struct intervals_node_updator;
101
 
102
template<class Cntnr>
103
bool
104
overlaps(const Cntnr& r_c, const interval& r_interval);
105
 
106
/*
107
 * The entry of the set. It includes an interval and the
108
 *      maximal endpoint of the intervals in its subtree.
109
 */
110
struct entry
111
{
112
  // Constructor. The maximal endpoint is set to the endpoint
113
  explicit entry(unsigned int start, unsigned int end) : m_interval(start, end),
114
                                                         m_max_endpoint(end)
115
  { }
116
 
117
  // Compares two entries by their intervals.
118
  inline bool
119
  operator<(const entry& r_rhs) const
120
  {
121
    return (m_interval < r_rhs.m_interval);
122
  }
123
 
124
  // An interval
125
  interval m_interval;
126
 
127
private:
128
  // The maximal endpoint of the intervals in its subtree.
129
  mutable unsigned int m_max_endpoint;
130
 
131
  friend struct intervals_node_updator;
132
 
133
  template<class Cntnr>
134
  friend bool
135
  overlaps(const Cntnr& r_c, const interval& r_interval);
136
 
137
};
138
 
139
/*
140
 * Functor updating maximal endpoints of entries.
141
 *      Algorithm taken from "Introduction to Algorithms" by Cormen, Leiserson,
142
 *      and Rivest.
143
 */
144
struct intervals_node_updator
145
{
146
  inline void
147
  operator()(const entry* p_entry, const entry* p_l_child_entry, const entry* p_r_child_entry)
148
  {
149
    /* The left maximal endpoint is 0 if there is no left child.
150
     */
151
    const unsigned int l_max_endpoint =(p_l_child_entry == NULL)? 0 : p_l_child_entry->m_max_endpoint;
152
 
153
    /* The right maximal endpoint is 0 if there is no right child.
154
     */
155
    const unsigned int r_max_endpoint =(p_r_child_entry == NULL)? 0 : p_r_child_entry->m_max_endpoint;
156
 
157
    p_entry->m_max_endpoint = std::max(p_entry->m_interval.m_end,
158
                                       std::max<unsigned int>(l_max_endpoint, r_max_endpoint));
159
  }
160
};
161
 
162
/*
163
 * Checks whether a set of intervals contains at least one interval
164
 *      overlapping some interval.
165
 *      Algorithm taken from "Introduction to Algorithms" by Cormen, Leiserson,
166
 *      and Rivest.
167
 **/
168
template<class Cntnr>
169
bool
170
overlaps(const Cntnr& r_c, const interval& r_interval)
171
{
172
  typedef typename Cntnr::const_iterator intr_set_const_it;
173
 
174
  typedef typename Cntnr::const_node_iterator intr_set_const_node_it;
175
 
176
  intr_set_const_node_it node_it = r_c.node_begin();
177
 
178
  while (node_it != r_c.node_end())
179
    {
180
      // Check whether r_interval overlaps the current interval.
181
 
182
      intr_set_const_it it =* node_it;
183
 
184
      if (r_interval.m_end >= it->m_interval.m_start&&
185
          r_interval.m_start <= it->m_interval.m_end)
186
        return (true);
187
 
188
      intr_set_const_node_it l_node_it = node_it.l_child();
189
 
190
      const unsigned int l_max_endpoint =(l_node_it == r_c.node_end())?
191
 
192
 
193
      if (l_max_endpoint >= r_interval.m_start)
194
        node_it = l_node_it;
195
      else
196
        node_it = node_it.r_child();
197
    }
198
 
199
  return (false);
200
}
201
 
202
template<class Cntnr>
203
void
204
some_op_sequence(Cntnr c)
205
{
206
  // Insert some entries.
207
 
208
  c.insert(entry(0, 100));
209
  c.insert(entry(150, 160));
210
  c.insert(entry(300, 1000));
211
  c.insert(entry(10000, 100000));
212
  c.insert(entry(200, 100200));
213
 
214
  // Test overlaps.
215
 
216
  // Overlaps 150 - 160
217
  assert(overlaps(c, interval(145, 165)) == true);
218
  // Overlaps 150 - 160
219
  assert(overlaps(c, interval(145, 155)) == true);
220
  assert(overlaps(c, interval(165, 175)) == false);
221
  assert(overlaps(c, interval(100201, 100203)) == false);
222
 
223
  // Erase an entry.
224
 
225
  entry e(150, 160);
226
 
227
  c.erase(e);
228
 
229
  // Test overlaps again.
230
 
231
  assert(overlaps(c, interval(145, 165)) == false);
232
  assert(overlaps(c, interval(165, 175)) == false);
233
  assert(overlaps(c, interval(0, 300000)) == true);
234
}
235
 
236
int
237
main()
238
{
239
  some_op_sequence(pb_assoc::tree_assoc_cntnr<
240
                   entry,
241
                   pb_assoc::null_data_type,
242
                   std::less<entry>,
243
                   pb_assoc::ov_tree_ds_tag,
244
                   intervals_node_updator>());
245
 
246
  some_op_sequence(pb_assoc::tree_assoc_cntnr<
247
                   entry,
248
                   pb_assoc::null_data_type,
249
                   std::less<entry>,
250
                   pb_assoc::rb_tree_ds_tag,
251
                   intervals_node_updator>());
252
 
253
  some_op_sequence(pb_assoc::tree_assoc_cntnr<
254
                   entry,
255
                   pb_assoc::null_data_type,
256
                   std::less<entry>,
257
                   pb_assoc::splay_tree_ds_tag,
258
                   intervals_node_updator>());
259
}
260
 

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.