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 
35 namespace 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:
48  class iterator
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>
169  typename CompactLookup<T>::iterator CompactLookup<T>::find(const int64_t& index)
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>
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__
namespace for all CiftiLib functionality
Definition: CiftiBrainModelsMap.h:41
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
T & operator[](const int64_t &index)
creates the element if it didn&#39;t exist, and returns a reference to it
Definition: CompactLookup.h:117
Definition: CompactLookup.h:39
Definition: CompactLookup.h:76
void clear()
empties the lookup
Definition: CompactLookup.h:231
Definition: CompactLookup.h:48