blob: 16c78bc26f76e6903e6c1786a8d37e21154443de [file] [log] [blame]
Alexander Afanasyev92136012013-07-16 20:36:30 -07001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
2/*
3 * Copyright (c) 2013, Regents of the University of California
4 * Alexander Afanasyev
5 *
6 * BSD license, See the LICENSE file for more information
7 *
8 * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
9 */
10
11#include "exclude.h"
12
13#include "detail/error.h"
14
15NDN_NAMESPACE_BEGIN
16
17Exclude::Exclude ()
18{
19}
20
21// example: ANY /b /d ANY /f
22//
23// ordered in map as:
24//
25// /f (false); /d (true); /b (false); / (true)
26//
27// lower_bound (/) -> / (true) <-- excluded (equal)
28// lower_bound (/a) -> / (true) <-- excluded (any)
29// lower_bound (/b) -> /b (false) <--- excluded (equal)
30// lower_bound (/c) -> /b (false) <--- not excluded (not equal and no ANY)
31// lower_bound (/d) -> /d (true) <- excluded
32// lower_bound (/e) -> /d (true) <- excluded
33bool
34Exclude::isExcluded (const name::Component &comp) const
35{
36 const_iterator lowerBound = m_exclude.lower_bound (comp);
37 if (lowerBound == end ())
38 return false;
39
40 if (lowerBound->second)
41 return true;
42 else
43 return lowerBound->first == comp;
44
45 return false;
46}
47
48Exclude &
49Exclude::excludeOne (const name::Component &comp)
50{
51 if (!isExcluded (comp))
52 {
53 m_exclude.insert (std::make_pair (comp, false));
54 }
55 return *this;
56}
57
58
59// example: ANY /b0 /d0 ANY /f0
60//
61// ordered in map as:
62//
63// /f0 (false); /d0 (true); /b0 (false); / (true)
64//
65// lower_bound (/) -> / (true) <-- excluded (equal)
66// lower_bound (/a0) -> / (true) <-- excluded (any)
67// lower_bound (/b0) -> /b0 (false) <--- excluded (equal)
68// lower_bound (/c0) -> /b0 (false) <--- not excluded (not equal and no ANY)
69// lower_bound (/d0) -> /d0 (true) <- excluded
70// lower_bound (/e0) -> /d0 (true) <- excluded
71
72
73// examples with desired outcomes
74// excludeRange (/, /f0) -> ANY /f0
75// /f0 (false); / (true)
76// excludeRange (/, /f1) -> ANY /f1
77// /f1 (false); / (true)
78// excludeRange (/a0, /e0) -> ANY /f0
79// /f0 (false); / (true)
80// excludeRange (/a0, /e0) -> ANY /f0
81// /f0 (false); / (true)
82
83// excludeRange (/b1, /c0) -> ANY /b0 /b1 ANY /c0 /d0 ANY /f0
84// /f0 (false); /d0 (true); /c0 (false); /b1 (true); /b0 (false); / (true)
85
86Exclude &
87Exclude::excludeRange (const name::Component &from, const name::Component &to)
88{
89 if (from >= to)
90 {
91 BOOST_THROW_EXCEPTION (error::Exclude ()
92 << error::msg ("Invalid exclude range (for single name exclude use Exclude::excludeOne)")
93 << error::msg (from.toUri ())
94 << error::msg (to.toUri ()));
95 }
96
97 iterator newFrom = m_exclude.lower_bound (from);
98 if (newFrom == end () || !newFrom->second /*without ANY*/)
99 {
100 std::pair<iterator, bool> fromResult = m_exclude.insert (std::make_pair (from, true));
101 newFrom = fromResult.first;
102 if (!fromResult.second)
103 {
104 // this means that the lower bound is equal to the item itself. So, just update ANY flag
105 newFrom->second = true;
106 }
107 }
108 // else
109 // nothing special if start of the range already exists with ANY flag set
110
111 iterator newTo = m_exclude.lower_bound (to); // !newTo cannot be end ()
112 if (newTo == newFrom || !newTo->second)
113 {
114 std::pair<iterator, bool> toResult = m_exclude.insert (std::make_pair (to, false));
115 newTo = toResult.first;
116 ++ newTo;
117 }
118 else
119 {
120 // nothing to do really
121 }
122
123 m_exclude.erase (newTo, newFrom); // remove any intermediate node, since all of the are excluded
124
125 return *this;
126}
127
128Exclude &
129Exclude::excludeAfter (const name::Component &from)
130{
131 iterator newFrom = m_exclude.lower_bound (from);
132 if (newFrom == end () || !newFrom->second /*without ANY*/)
133 {
134 std::pair<iterator, bool> fromResult = m_exclude.insert (std::make_pair (from, true));
135 newFrom = fromResult.first;
136 if (!fromResult.second)
137 {
138 // this means that the lower bound is equal to the item itself. So, just update ANY flag
139 newFrom->second = true;
140 }
141 }
142 // else
143 // nothing special if start of the range already exists with ANY flag set
144
145 if (newFrom != m_exclude.begin ())
146 {
147 m_exclude.erase (m_exclude.begin (), newFrom); // remove any intermediate node, since all of the are excluded
148 }
149
150 return *this;
151}
152
153
154std::ostream&
155operator << (std::ostream &os, const Exclude &exclude)
156{
157 for (Exclude::const_reverse_iterator i = exclude.rbegin (); i != exclude.rend (); i++)
158 {
159 os << i->first.toUri () << " ";
160 if (i->second)
161 os << "----> ";
162 }
163 return os;
164}
165
166NDN_NAMESPACE_END