ARB
RangeList.cxx
Go to the documentation of this file.
1 // ============================================================= //
2 // //
3 // File : RangeList.cxx //
4 // Purpose : //
5 // //
6 // Coded by Ralf Westram (coder@reallysoft.de) in April 2012 //
7 // Institute of Microbiology (Technical University Munich) //
8 // http://www.arb-home.de/ //
9 // //
10 // ============================================================= //
11 
12 #include "RangeList.h"
13 
14 void RangeList::add_combined(const PosRange& range, iterator found) {
15  PosRange combined(std::min(range.start(), found->start()), std::max(range.end(), found->end()));
16  ranges.erase(found);
17  add(combined);
18 }
19 
21  RangeList inv;
22 
23  for (RangeList::iterator r = begin(); r != end(); ++r) {
24  rl_assert(versus.contains(*r));
25  inv.add(intersection(r->prior(), versus));
26  versus = intersection(r->after(), versus);
27  }
28  inv.add(versus);
29  return inv;
30 }
31 
32 RangeList build_RangeList_from_string(const char *SAI_data, const char *set_bytes, bool invert) {
33  RangeList rlist;
34  int pos = 0;
35  bool isSet = strchr(set_bytes, SAI_data[pos]);
36 
37  while (SAI_data[pos]) {
38  if (isSet) {
39  size_t setCount = strspn(SAI_data+pos, set_bytes);
40  rl_assert(setCount>0);
41  rlist.add(PosRange(pos, pos+setCount-1));
42  pos += setCount;
43  }
44  else {
45  size_t clrCount = strcspn(SAI_data+pos, set_bytes);
46  pos += clrCount;
47  }
48  isSet = !isSet;
49  }
50 
51  return invert
52  ? rlist.inverse(ExplicitRange(0, pos-1))
53  : rlist;
54 }
55 
56 // --------------------------------------------------------------------------------
57 
58 #ifdef UNIT_TESTS
59 #ifndef TEST_UNIT_H
60 #include <test_unit.h>
61 #endif
62 #include <arb_strbuf.h>
63 
64 static const char *dump(const RangeList& rlist) {
65  static GBS_strstruct buf;
66  buf.erase();
67  for (RangeList::iterator i = rlist.begin(); i != rlist.end(); ++i) {
68  buf.nprintf(40, "%i-%i,", i->start(), i->end());
69  }
70  buf.cut_tail(1);
71  return buf.get_data();
72 }
73 static const char *dump_reverse(const RangeList& rlist) {
74  static GBS_strstruct buf;
75  buf.erase();
76  for (RangeList::reverse_iterator i = rlist.rbegin(); i != rlist.rend(); ++i) {
77  buf.nprintf(40, "%i-%i,", i->start(), i->end());
78  }
79  buf.cut_tail(1);
80  return buf.get_data();
81 }
82 
83 void TEST_RangeList() {
84  RangeList ranges;
85 
86  TEST_EXPECT_EQUAL(ranges.size(), 0);
87 
88  ranges.add(PosRange(10, 20));
89  TEST_EXPECT_EQUAL(ranges.size(), 1);
90  TEST_EXPECT_EQUAL(dump(ranges), "10-20");
91 
92  ranges.add(PosRange(30, 40));
93  TEST_EXPECT_EQUAL(ranges.size(), 2);
94  TEST_EXPECT_EQUAL(dump(ranges), "10-20,30-40");
95 
96  ranges.add(PosRange(5, 6));
97  TEST_EXPECT_EQUAL(ranges.size(), 3);
98  TEST_EXPECT_EQUAL(dump(ranges), "5-6,10-20,30-40");
99 
100  // add range inbetween
101  ranges.add(PosRange(25, 27));
102  TEST_EXPECT_EQUAL(ranges.size(), 4);
103  TEST_EXPECT_EQUAL(dump(ranges), "5-6,10-20,25-27,30-40");
104 
105  // add already-set range
106  ranges.add(PosRange(12, 17));
107  TEST_EXPECT_EQUAL(ranges.size(), 4);
108  TEST_EXPECT_EQUAL(dump(ranges), "5-6,10-20,25-27,30-40");
109 
110  TEST_EXPECT_EQUAL(dump_reverse(ranges), "30-40,25-27,10-20,5-6"); // test reverse iterator
111 
112  // expand an already-set range (upwards; overlapping)
113  ranges.add(PosRange(38, 42));
114  TEST_EXPECT_EQUAL(ranges.size(), 4);
115  TEST_EXPECT_EQUAL(dump(ranges), "5-6,10-20,25-27,30-42");
116 
117  // expand an already-set range (upwards; adjacent)
118  ranges.add(PosRange(43, 45));
119  TEST_EXPECT_EQUAL(ranges.size(), 4);
120  TEST_EXPECT_EQUAL(dump(ranges), "5-6,10-20,25-27,30-45");
121 
122  // expand an already-set range (downwards; overlapping)
123  ranges.add(PosRange(8, 12));
124  TEST_EXPECT_EQUAL(ranges.size(), 4);
125  TEST_EXPECT_EQUAL(dump(ranges), "5-6,8-20,25-27,30-45");
126 
127  // expand an already-set range (downwards; adjacent)
128  ranges.add(PosRange(24, 24));
129  TEST_EXPECT_EQUAL(ranges.size(), 4);
130  TEST_EXPECT_EQUAL(dump(ranges), "5-6,8-20,24-27,30-45");
131 
132  // aggregate ranges (overlapping)
133  ranges.add(PosRange(19, 25));
134  TEST_EXPECT_EQUAL(ranges.size(), 3);
135  TEST_EXPECT_EQUAL(dump(ranges), "5-6,8-27,30-45");
136 
137  // aggregate ranges (adjacent)
138  ranges.add(PosRange(28, 29));
139  TEST_EXPECT_EQUAL(ranges.size(), 2);
140  TEST_EXPECT_EQUAL(dump(ranges), "5-6,8-45");
141 }
142 
143 static const char *convert(const char *saistring, const char *set_bytes, bool invert) {
144  RangeList rlist = build_RangeList_from_string(saistring, set_bytes, invert);
145  return dump(rlist);
146 }
147 
148 void TEST_string2RangeList() {
149  TEST_EXPECT_EQUAL(convert("---", "x", false), "");
150  TEST_EXPECT_EQUAL(convert("---", "x", true), "0-2");
151 
152  TEST_EXPECT_EQUAL(convert("xxxxx-----xxxxx-----xxxxx-----", "x", false), "0-4,10-14,20-24");
153  TEST_EXPECT_EQUAL(convert("-----xxxxx-----xxxxx-----xxxxx", "-", false), "0-4,10-14,20-24");
154  TEST_EXPECT_EQUAL(convert("-----xxxxx-----xxxxx-----xxxxx", "x", true), "0-4,10-14,20-24");
155  TEST_EXPECT_EQUAL(convert("xxxxx-----yyyyy-----xxzzx-----", "xyz", false), "0-4,10-14,20-24");
156 
157  TEST_EXPECT_EQUAL(convert("-----xxxxx-----xxxxx-----xxxxx", "x", false), "5-9,15-19,25-29");
158  TEST_EXPECT_EQUAL(convert("xxxxx-----xxxxx-----xxxxx-----", "-", false), "5-9,15-19,25-29");
159  TEST_EXPECT_EQUAL(convert("xxxxx-----xxxxx-----xxxxx-----", "x", true), "5-9,15-19,25-29");
160 
161  TEST_EXPECT_EQUAL(convert("x-x-x", "x", false), "0-0,2-2,4-4");
162  TEST_EXPECT_EQUAL(convert("x-x-x", "-", false), "1-1,3-3");
163  TEST_EXPECT_EQUAL(convert("x-x-x", "x", true), "1-1,3-3");
164 
165 }
166 TEST_PUBLISH(TEST_string2RangeList);
167 
168 #endif // UNIT_TESTS
169 
170 // --------------------------------------------------------------------------------
171 
172 
void cut_tail(size_t byte_count)
Definition: arb_strbuf.h:134
PosRange intersection(PosRange r1, PosRange r2)
Definition: pos_range.h:98
int start() const
Definition: pos_range.h:57
range_set::const_iterator iterator
Definition: RangeList.h:46
size_t size() const
Definition: RangeList.h:49
void convert(const FormattedFile &in, const FormattedFile &out)
Definition: convert.cxx:156
void erase()
Definition: arb_strbuf.h:82
void add(const PosRange &range)
Definition: RangeList.h:61
#define TEST_PUBLISH(testfunction)
Definition: test_unit.h:1485
bool contains(int pos) const
Definition: pos_range.h:83
reverse_iterator rend() const
Definition: RangeList.h:55
iterator begin() const
Definition: RangeList.h:51
iterator end() const
Definition: RangeList.h:52
#define rl_assert(cond)
Definition: RangeList.h:22
reverse_iterator rbegin() const
Definition: RangeList.h:54
RangeList inverse(ExplicitRange versus)
Definition: RangeList.cxx:20
void nprintf(size_t maxlen, const char *templat,...) __ATTR__FORMAT_MEMBER(2)
Definition: arb_strbuf.cxx:29
RangeList build_RangeList_from_string(const char *SAI_data, const char *set_bytes, bool invert)
Definition: RangeList.cxx:32
int end() const
Definition: pos_range.h:61
const char * get_data() const
Definition: arb_strbuf.h:70
range_set::const_reverse_iterator reverse_iterator
Definition: RangeList.h:47
#define min(a, b)
Definition: f2c.h:153
#define TEST_EXPECT_EQUAL(expr, want)
Definition: test_unit.h:1283
#define max(a, b)
Definition: f2c.h:154