NCBI C++ Toolkit Cross Reference

C++/src/util/itree.cpp

  1 /*  $Id: itree.cpp 103491 2007-05-04 17:18:18Z kazimird $
  2 * ===========================================================================
  3 *
  4 *                            PUBLIC DOMAIN NOTICE
  5 *               National Center for Biotechnology Information
  6 *
  7 *  This software/database is a "United States Government Work" under the
  8 *  terms of the United States Copyright Act.  It was written as part of
  9 *  the author's official duties as a United States Government employee and
 10 *  thus cannot be copyrighted.  This software/database is freely available
 11 *  to the public for use. The National Library of Medicine and the U.S.
 12 *  Government have not placed any restriction on its use or reproduction.
 13 *
 14 *  Although all reasonable efforts have been taken to ensure the accuracy
 15 *  and reliability of the software and data, the NLM and the U.S.
 16 *  Government do not and cannot warrant the performance or results that
 17 *  may be obtained by using this software or data. The NLM and the U.S.
 18 *  Government disclaim all warranties, express or implied, including
 19 *  warranties of performance, merchantability or fitness for any particular
 20 *  purpose.
 21 *
 22 *  Please cite the author in any work or product based on this material.
 23 *
 24 * ===========================================================================
 25 *
 26 * Author: Eugene Vasilchenko
 27 *
 28 * File Description:
 29 *   Implementation of interval search tree.
 30 *
 31 * ===========================================================================
 32 */
 33 
 34 #include <ncbi_pch.hpp>
 35 #include <corelib/ncbistd.hpp>
 36 #include <util/itree.hpp>
 37 
 38 BEGIN_NCBI_SCOPE
 39 
 40 inline
 41 CIntervalTree::coordinate_type CIntervalTree::GetMaxRootCoordinate(void) const
 42 {
 43     coordinate_type max = m_Root.m_Key * 2;
 44     if ( max <= 0 )
 45         max = TTraits::GetMaxCoordinate();
 46     return max;
 47 }
 48 
 49 inline
 50 CIntervalTree::coordinate_type CIntervalTree::GetNextRootKey(void) const
 51 {
 52     coordinate_type nextKey = m_Root.m_Key * 2;
 53     _ASSERT(nextKey > 0);
 54     return nextKey;
 55 }
 56 
 57 void CIntervalTree::DoInsert(const interval_type& interval, TTreeMapI value)
 58 {
 59     _ASSERT(TTraits::IsNormal(interval));
 60 
 61     // ensure our tree covers specified interval
 62     if ( interval.GetTo() > GetMaxRootCoordinate() ) {
 63         // insert one more level on top
 64         if ( m_Root.m_Left || m_Root.m_Right || m_Root.m_NodeIntervals ) {
 65             // non empty tree, insert new root node
 66             do {
 67                 TTreeNode* newLeft = AllocNode();
 68                 // copy root node contents
 69                 *newLeft = m_Root;
 70                 // fill new root
 71                 m_Root.m_Key = GetNextRootKey();
 72                 m_Root.m_Left = newLeft;
 73                 m_Root.m_Right = 0;
 74                 m_Root.m_NodeIntervals = 0;
 75             } while ( interval.GetTo() > GetMaxRootCoordinate() );
 76         }
 77         else {
 78             // empty tree, just recalculate root
 79             do {
 80                 m_Root.m_Key = GetNextRootKey();
 81             } while ( interval.GetTo() > GetMaxRootCoordinate() );
 82         }
 83     }
 84 
 85     TTreeNode* node = &m_Root;
 86     coordinate_type nodeSize = m_Root.m_Key;
 87     for ( ;; ) {
 88         coordinate_type key = node->m_Key;
 89         nodeSize = (nodeSize + 1) / 2;
 90 
 91         TTreeNode** nextPtr;
 92         coordinate_type nextKeyOffset;
 93 
 94         if ( interval.GetFrom() > key  ) {
 95             nextPtr = &node->m_Right;
 96             nextKeyOffset = nodeSize;
 97         }
 98         else if ( interval.GetTo() < key ) {
 99             nextPtr = &node->m_Left;
100             nextKeyOffset = -nodeSize;
101         }
102         else {
103             // found our tile
104             TTreeNodeInts* nodeIntervals = node->m_NodeIntervals;
105             if ( !nodeIntervals )
106                 node->m_NodeIntervals = nodeIntervals = CreateNodeIntervals();
107             nodeIntervals->Insert(interval, value);
108             return;
109         }
110 
111         TTreeNode* next = *nextPtr;
112         if ( !next ) // create new node
113             (*nextPtr) = next = InitNode(AllocNode(), key + nextKeyOffset);
114 
115         _ASSERT(next->m_Key == key + nextKeyOffset);
116         node = next;
117     }
118 }
119 
120 bool CIntervalTree::DoDelete(TTreeNode* node, const interval_type& interval,
121                              TTreeMapI value)
122 {
123     _ASSERT(node);
124     coordinate_type key = node->m_Key;
125     if ( interval.GetFrom() > key ) {
126         // left
127         return DoDelete(node->m_Right, interval, value) &&
128             !node->m_NodeIntervals && !node->m_Left;
129     }
130     else if ( interval.GetTo() < key ) {
131         // right
132         return DoDelete(node->m_Left, interval, value) &&
133             !node->m_NodeIntervals && !node->m_Right;
134     }
135     else {
136         // inside
137         TTreeNodeInts* nodeIntervals = node->m_NodeIntervals;
138         _ASSERT(nodeIntervals);
139 
140         if ( !nodeIntervals->Delete(interval, value) )
141             return false; // node intervals non empty
142 
143         // remove node intervals
144         DeleteNodeIntervals(nodeIntervals);
145         node->m_NodeIntervals = 0;
146 
147         // delete node if it doesn't have leaves
148         return !node->m_Left && !node->m_Right;
149     }
150 }
151 
152 void CIntervalTree::Destroy(void)
153 {
154     ClearNode(&m_Root);
155     m_ByX.clear();
156 }
157 
158 CIntervalTree::iterator CIntervalTree::Insert(const interval_type& interval,
159                                               const mapped_type& value)
160 {
161     TTreeMapI iter = m_ByX.insert(TTreeMapValue(interval.GetFrom(),
162                                                 interval.GetTo(),
163                                                 value));
164     DoInsert(interval, iter);
165 
166     return iterator(0, TTraits::GetMaxCoordinate(), &TTreeMap::get(iter));
167 }
168 
169 CIntervalTree::const_iterator
170 CIntervalTree::IntervalsOverlapping(const interval_type& interval) const
171 {
172     coordinate_type x = interval.GetFrom();
173     coordinate_type y = interval.GetTo();
174 
175     const_iterator it(x, TTraits::GetMaxCoordinate(), 0, &m_Root);
176 
177     TTreeMapCI iter =
178         m_ByX.lower_bound(TTreeMapValue(x + 1, 0, mapped_type()));
179     if ( iter != m_ByX.end() && iter->GetKey() <= y ) {
180         it.m_SearchLimit = y;
181         it.m_CurrentMapValue = &*iter;
182     }
183     else {
184         it.NextLevel();
185     }
186     return it;
187 }
188 
189 CIntervalTree::iterator
190 CIntervalTree::IntervalsOverlapping(const interval_type& interval)
191 {
192     coordinate_type x = interval.GetFrom();
193     coordinate_type y = interval.GetTo();
194 
195     iterator it(x, TTraits::GetMaxCoordinate(), 0, &m_Root);
196 
197     TTreeMapI iter =
198         m_ByX.lower_bound(TTreeMapValue(x + 1, 0, mapped_type()));
199     if ( iter != m_ByX.end() && iter->GetKey() <= y ) {
200         it.m_SearchLimit = y;
201         it.m_CurrentMapValue = &TTreeMap::get(iter);
202     }
203     else {
204         it.NextLevel();
205     }
206     return it;
207 }
208 
209 CIntervalTree::TTreeNode* CIntervalTree::AllocNode(void)
210 {
211     return m_NodeAllocator.allocate(1, (TTreeNode*) 0);
212 }
213 
214 void CIntervalTree::DeallocNode(TTreeNode* node)
215 {
216     m_NodeAllocator.deallocate(node, 1);
217 }
218 
219 CIntervalTree::TTreeNodeInts* CIntervalTree::AllocNodeIntervals(void)
220 {
221     return m_NodeIntervalsAllocator.allocate(1, (TTreeNodeInts*) 0);
222 }
223 
224 void CIntervalTree::DeallocNodeIntervals(TTreeNodeInts* ptr)
225 {
226     m_NodeIntervalsAllocator.deallocate(ptr, 1);
227 }
228 
229 CIntervalTree::TTreeNodeInts* CIntervalTree::CreateNodeIntervals(void)
230 {
231     TTreeNodeInts* ints = new (AllocNodeIntervals())TTreeNodeInts();
232 #if defined(_RWSTD_VER) && !defined(_RWSTD_STRICT_ANSI)
233     ints->m_ByX.allocation_size(16);
234     ints->m_ByY.allocation_size(16);
235 #endif
236     return ints;
237 }
238 
239 void CIntervalTree::DeleteNodeIntervals(TTreeNodeInts* ptr)
240 {
241     if ( ptr ) {
242         ptr->~TTreeNodeInts();
243         DeallocNodeIntervals(ptr);
244     }
245 }
246 
247 void CIntervalTree::ClearNode(TTreeNode* node)
248 {
249     DeleteNodeIntervals(node->m_NodeIntervals);
250 
251     DeleteNode(node->m_Left);
252     DeleteNode(node->m_Right);
253     node->m_Left = node->m_Right = 0;
254 }
255 
256 pair<double, CIntervalTree::size_type> CIntervalTree::Stat(void) const
257 {
258     SStat stat;
259     stat.total = stat.count = stat.max = 0;
260     Stat(&m_Root, stat);
261     return make_pair(double(stat.total) / stat.count, stat.max);
262 }
263 
264 void CIntervalTree::Stat(const TTreeNode* node, SStat& stat) const
265 {
266     if ( !node )
267         return;
268 
269     if ( node->m_NodeIntervals ) {
270         size_type len = node->m_NodeIntervals->m_ByX.size();
271         ++stat.count;
272         stat.total += len;
273         stat.max = max(stat.max, len);
274     }
275 
276     Stat(node->m_Right, stat);
277     Stat(node->m_Left, stat);
278 }
279 
280 END_NCBI_SCOPE
281
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ]
This page was automatically generated by the LXR engine.
Visit the LXR main site for more information.