CiftiLib
A C++ library for CIFTI-2 and CIFTI-1 files
CompactLookup.h
1#ifndef __COMPACT_LOOKUP_H__
2#define __COMPACT_LOOKUP_H__
3
4/*LICENSE_START*/
5/*
6 * Copyright (c) 2014, Washington University School of Medicine
7 * All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without modification,
10 * are permitted provided that the following conditions are met:
11 *
12 * 1. Redistributions of source code must retain the above copyright notice,
13 * this list of conditions and the following disclaimer.
14 *
15 * 2. Redistributions in binary form must reproduce the above copyright notice,
16 * this list of conditions and the following disclaimer in the documentation
17 * and/or other materials provided with the distribution.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
21 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
24 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
25 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
26 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
28 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 */
30
31#include "CiftiAssert.h"
32#include "stdint.h"
33#include <vector>
34
35namespace cifti
36{
37
38 template <typename T>
40 {
41 struct Chunk
42 {
43 int64_t start;
44 std::vector<T> elements;
45 };
46 std::vector<Chunk> m_chunks;
47 public:
49 {
50 CompactLookup<T>& m_container;
51 std::size_t m_chunk;
52 int64_t m_elem;
53 iterator(CompactLookup<T>& container, std::size_t chunk, int64_t elem) : m_container(container), m_chunk(chunk), m_elem(elem) { }
54 public:
55 bool operator==(const iterator& rhs) const
56 {
57 if (&m_container != &(rhs.m_container)) return false;
58 if (m_chunk != rhs.m_chunk) return false;
59 if (m_elem != rhs.m_elem) return false;
60 return true;
61 }
62 T& operator*()
63 {
64 CiftiAssert(m_chunk < m_container.m_chunks.size());
65 CiftiAssert(m_elem >= 0 && m_elem < (int64_t)m_container.m_chunks[m_chunk].elements.size());
66 return m_container.m_chunks[m_chunk].elements[m_elem];
67 }
68 T* operator->()
69 {
70 CiftiAssert(m_chunk < m_container.m_chunks.size());
71 CiftiAssert(m_elem >= 0 && m_elem < (int64_t)m_container.m_chunks[m_chunk].elements.size());
72 return &(m_container.m_chunks[m_chunk].elements[m_elem]);
73 }
74 friend class CompactLookup<T>;
75 };
77 {
78 const CompactLookup<T>& m_container;
79 std::size_t m_chunk;
80 int64_t m_elem;
81 const_iterator(const CompactLookup<T>& container, std::size_t chunk, std::size_t elem) : m_container(container), m_chunk(chunk), m_elem(elem) { }
82 public:
83 bool operator==(const const_iterator& rhs) const
84 {
85 if (&m_container != &(rhs.m_container)) return false;
86 if (m_chunk != rhs.m_chunk) return false;
87 if (m_elem != rhs.m_elem) return false;
88 return true;
89 }
90 const T& operator*()
91 {
92 CiftiAssert(m_chunk < m_container.m_chunks.size());
93 CiftiAssert(m_elem >= 0 && m_elem < (int64_t)m_container.m_chunks[m_chunk].elements.size());
94 return m_container.m_chunks[m_chunk].elements[m_elem];
95 }
96 const T* operator->()
97 {
98 CiftiAssert(m_chunk < m_container.m_chunks.size());
99 CiftiAssert(m_elem >= 0 && m_elem < (int64_t)m_container.m_chunks[m_chunk].elements.size());
100 return &(m_container.m_chunks[m_chunk].elements[m_elem]);
101 }
102 friend class CompactLookup<T>;
103 };
105 T& operator[](const int64_t& index);
107 iterator find(const int64_t& index);
109 const_iterator find(const int64_t& index) const;
110 iterator end();
111 const_iterator end() const;
113 void clear();
114 };
115
116 template <typename T>
117 T& CompactLookup<T>::operator[](const int64_t& index)
118 {
119 std::size_t numChunks = m_chunks.size();
120 std::size_t low = 0, high = numChunks, guess;//NOTE: low is 0 because size_t is unsigned, really means -1
121 bool attach_low = false, attach_high = false;
122 while (low < high)//bisection search for the chunk with the largest start value not greater than
123 {
124 guess = (low + high - 1) / 2;//which is why we subtract 1 here
125 CiftiAssert(guess < m_chunks.size());
126 if (m_chunks[guess].start > index)
127 {
128 high = guess;
129 } else {
130 low = guess + 1;
131 }
132 }//NOTE: low == high after loop ends
133 if (high > 0 && m_chunks[high - 1].start + (int64_t)(m_chunks[high - 1].elements.size()) > index)//element exists, return it
134 {
135 CiftiAssertVectorIndex(m_chunks[high -1].elements, index - m_chunks[high - 1].start);
136 return m_chunks[high - 1].elements[index - m_chunks[high - 1].start];
137 }
138 if (high > 0 && m_chunks[high - 1].start + (int64_t)(m_chunks[high - 1].elements.size()) == index) attach_low = true;//index is 1 beyond the range
139 if (high < numChunks && m_chunks[high].start == index + 1) attach_high = true;//index is 1 before the next range
140 if (attach_low)
141 {
142 std::vector<T>& lowvec = m_chunks[high - 1].elements;
143 std::size_t retIndex = lowvec.size();
144 lowvec.push_back(T());
145 if (attach_high)
146 {
147 std::vector<T>& highvec = m_chunks[high].elements;
148 lowvec.insert(lowvec.end(), highvec.begin(), highvec.end());
149 m_chunks.erase(m_chunks.begin() + high);
150 }
151 return lowvec[retIndex];
152 } else {
153 if (attach_high)
154 {
155 std::vector<T>& highvec = m_chunks[high].elements;
156 highvec.insert(highvec.begin(), T());//add a new element to the start of the vector (yes, this could be slow)
157 m_chunks[high].start = index;//and change the start value of the chunk
158 return highvec[0];
159 } else {
160 m_chunks.insert(m_chunks.begin() + high, Chunk());
161 m_chunks[high].start = index;
162 m_chunks[high].elements.push_back(T());
163 return m_chunks[high].elements[0];
164 }
165 }
166 }
167
168 template <typename T>
170 {
171 std::size_t numChunks = m_chunks.size();
172 std::size_t low = 0, high = numChunks, guess;//NOTE: low is 0 because size_t is unsigned, really means -1
173 while (low < high)//bisection search for the chunk with the largest start value not greater than
174 {
175 guess = (low + high - 1) / 2;//which is why we subtract 1 here
176 CiftiAssert(guess < m_chunks.size());
177 if (m_chunks[guess].start > index)
178 {
179 high = guess;
180 } else {
181 low = guess + 1;
182 }
183 }//NOTE: low == high after loop ends
184 if (high > 0 && m_chunks[high - 1].start + (int64_t)(m_chunks[high - 1].elements.size()) > index)//element exists, return it
185 {
186 std::size_t outIndex = index - m_chunks[high - 1].start;
187 CiftiAssert(outIndex < m_chunks[high - 1].elements.size());
188 return iterator(*this, high - 1, outIndex);
189 }
190 return end();
191 }
192
193 template <typename T>
194 typename CompactLookup<T>::const_iterator CompactLookup<T>::find(const int64_t& index) const
195 {
196 std::size_t numChunks = m_chunks.size();
197 std::size_t low = 0, high = numChunks, guess;//NOTE: low is 0 because size_t is unsigned, really means -1
198 while (low < high)//bisection search for the chunk with the largest start value not greater than
199 {
200 guess = (low + high - 1) / 2;//which is why we subtract 1 here
201 CiftiAssert(guess < m_chunks.size());
202 if (m_chunks[guess].start > index)
203 {
204 high = guess;
205 } else {
206 low = guess + 1;
207 }
208 }//NOTE: low == high after loop ends
209 if (high > 0 && m_chunks[high - 1].start + (int64_t)(m_chunks[high - 1].elements.size()) > index)//element exists, return it
210 {
211 std::size_t outIndex = index - m_chunks[high - 1].start;
212 CiftiAssert(outIndex < m_chunks[high - 1].elements.size());
213 return const_iterator(*this, high - 1, outIndex);
214 }
215 return end();
216 }
217
218 template <typename T>
220 {
221 return iterator(*this, 0, -1);
222 }
223
224 template <typename T>
225 typename CompactLookup<T>::const_iterator CompactLookup<T>::end() const
226 {
227 return const_iterator(*this, 0, -1);
228 }
229
230 template <typename T>
232 {
233 m_chunks.clear();
234 }
235}
236
237#endif //__COMPACT_LOOKUP_H__
Definition: CompactLookup.h:77
Definition: CompactLookup.h:49
Definition: CompactLookup.h:40
const_iterator find(const int64_t &index) const
returns a const_iterator pointing to the desired element, or one equal to end() if no such element is...
Definition: CompactLookup.h:194
void clear()
empties the lookup
Definition: CompactLookup.h:231
T & operator[](const int64_t &index)
creates the element if it didn't exist, and returns a reference to it
Definition: CompactLookup.h:117
iterator find(const int64_t &index)
returns an iterator pointing to the desired element, or one equal to end() if no such element is foun...
Definition: CompactLookup.h:169
namespace for all CiftiLib functionality
Definition: CiftiBrainModelsMap.h:42