NCBI C Toolkit Cross Reference

C/corelib/binary.c

  1 /*   $Id: binary.c,v 1.6 2000/08/28 18:47:40 vakatov Exp $
  2 * ===========================================================================
  3 *
  4 *                            PUBLIC DOMAIN NOTICE
  5 *            National Center for Biotechnology Information (NCBI)
  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 do not place any restriction on its use or reproduction.
 13 *  We would, however, appreciate having the NCBI and the author cited in
 14 *  any work or product based on this material
 15 *
 16 *  Although all reasonable efforts have been taken to ensure the accuracy
 17 *  and reliability of the software and data, the NLM and the U.S.
 18 *  Government do not and cannot warrant the performance or results that
 19 *  may be obtained by using this software or data. The NLM and the U.S.
 20 *  Government disclaim all warranties, express or implied, including
 21 *  warranties of performance, merchantability or fitness for any particular
 22 *  purpose.
 23 *
 24 * ===========================================================================
 25 *
 26 * File Name:  $Id: binary.c,v 1.6 2000/08/28 18:47:40 vakatov Exp $
 27 *
 28 * Author:  Lewis Geer
 29 *
 30 * Version Creation Date:   8/24/99
 31 *
 32 * $Revision: 1.6 $
 33 *
 34 * File Description: Various binary search algorithms 
 35 *
 36 * Modifications:
 37 * --------------------------------------------------------------------------
 38 * $Log: binary.c,v $
 39 * Revision 1.6  2000/08/28 18:47:40  vakatov
 40 * Added missing type cast to pass C++ compilation
 41 *
 42 * Revision 1.5  1999/11/23 22:02:29  vakatov
 43 * Fixed for the MSVC DLL compilation
 44 *
 45 * Revision 1.4  1999/10/14 22:00:33  vakatov
 46 * More changes in the included headers
 47 *
 48 * Revision 1.3  1999/10/14 19:08:09  kans
 49 * header changes for Mac
 50 *
 51 * Revision 1.2  1999/10/05 23:18:25  lewisg
 52 * add ddv and udv to cn3d with memory management
 53 *
 54 * Revision 1.1  1999/09/21 18:09:13  lewisg
 55 * binary search added to color manager, various bug fixes, etc.
 56 * ==========================================================================
 57 */
 58 
 59 #include <binary.h>
 60 
 61 
 62 /*****************************************************************************
 63 *
 64 *   B_NewGlobal() returns a new binary search global.  Takes a key comparison
 65 *   function and the size to realloc the binary search list.  If you pass 0
 66 *   for AllocSize it will use the default value B_ALLOCSIZE * sizeof(B_List).  
 67 *   Returns NULL on failure.
 68 *
 69 *   B_DeleteGlobal() deletes the global.  Return 1 on success, 0 on failure. 
 70 *
 71 *****************************************************************************/
 72 
 73 NLM_EXTERN B_Global * B_NewGlobal(B_CompareFunc CompareFunc, Int4 AllocSize)
 74 {
 75     B_Global * pGlobal;
 76 
 77     if (CompareFunc == NULL) return NULL;
 78     pGlobal = (B_Global *) MemNew(sizeof(B_Global));
 79     if(pGlobal == NULL) return NULL;
 80 
 81 /*    pGlobal->RW = NlmRWinit(); */
 82     if(AllocSize == 0) pGlobal->AllocSize = B_ALLOCSIZE;
 83     else pGlobal->AllocSize = AllocSize;
 84     pGlobal->CompareFunc = CompareFunc;
 85     pGlobal->List = NULL;
 86     pGlobal->Size = 0;
 87     pGlobal->TrueSize = 0;
 88     pGlobal->Cursor = -1;
 89 
 90     return pGlobal;
 91 }
 92 
 93 NLM_EXTERN Int4 B_DeleteGlobal(B_Global *pGlobal)
 94 {
 95     if(pGlobal == NULL) return 0;
 96 
 97     MemFree(pGlobal->List);
 98 /*    NlmRWdestroy(pGlobal->RW); */
 99     MemFree(pGlobal);
100 
101     return 1;
102 }
103 
104 
105 /*****************************************************************************
106 *
107 *   Inserts a new entry into the List.  Returns the position.  The position
108 *   is not guaranteed between deletions and insertions
109 *
110 *   Automatically reallocates memory for List as List grows
111 *
112 *****************************************************************************/
113 
114 NLM_EXTERN Int4 B_Insert(B_Global *pGlobal, void *Key, void *Bag)
115 {
116     Int4 InsertPos;
117     Boolean NotFound, InsertBefore = TRUE;
118 
119     if(pGlobal == NULL || Key == NULL) return 0;
120 
121     if(pGlobal->Size !=0) {
122         InsertPos = B_GetFirst(pGlobal, Key, &NotFound);
123         if(InsertPos == INT4_MIN) return 0;
124         /* scan for insertion point */
125         if(InsertPos == B_GetSize(pGlobal)) InsertBefore = FALSE;
126         else if((*pGlobal->CompareFunc)(Key, pGlobal->List[InsertPos].Key) > 0)
127             InsertBefore = FALSE;
128     }
129     else InsertPos = 0;
130 
131     /* make the List bigger if necessary */
132     if(pGlobal->TrueSize == 0) {
133         pGlobal->TrueSize += pGlobal->AllocSize;
134         pGlobal->List = (B_List *)Nlm_MemNew((size_t)pGlobal->TrueSize * sizeof(B_List));
135         if(pGlobal->List == NULL) return -1;
136     }
137     else if (pGlobal->Size == pGlobal->TrueSize) {
138         pGlobal->TrueSize += pGlobal->AllocSize;
139         pGlobal->List = (B_List *)Nlm_MemMore((void *)pGlobal->List,
140             (size_t) pGlobal->TrueSize * sizeof(B_List));
141         if(pGlobal->List == NULL) return -1;
142     }
143     
144     if(InsertBefore) {
145         Nlm_MemMove(&pGlobal->List[InsertPos + 1], &pGlobal->List[InsertPos],
146             (size_t)(pGlobal->Size - InsertPos) * sizeof(B_List));
147         
148         pGlobal->List[InsertPos].Key = Key;
149         pGlobal->List[InsertPos].Bag = Bag;
150     }
151     else if(InsertPos == B_GetSize(pGlobal)) {
152         pGlobal->List[InsertPos].Key = Key;
153         pGlobal->List[InsertPos].Bag = Bag;
154     }
155     else {
156         Nlm_MemMove(&pGlobal->List[InsertPos + 1], &pGlobal->List[InsertPos],
157             (size_t)(pGlobal->Size - InsertPos) * sizeof(B_List));
158         
159         pGlobal->List[InsertPos + 1].Key = Key;
160         pGlobal->List[InsertPos + 1].Bag = Bag;
161     }
162 
163     pGlobal->Size++;
164 
165     return InsertPos;
166 }
167 
168 /*****************************************************************************
169 *
170 *   B_Get() Returns the position in the List associated with the key.
171 *   Returns INT4_MIN if no match or the list is empty.
172 *
173 *   B_GetFirst() does the same, but returns the first item in the List that
174 *   matches the Key.
175 *
176 *   B_GetBag() gets bag associated with the key.
177 *
178 *****************************************************************************/
179 
180 
181 NLM_EXTERN Int4 B_Get(B_Global *pGlobal, void *Key, Boolean *NotFound)
182 {
183     Int4 x, l, r;
184     Int4 CompareValue;
185 
186     if(pGlobal == NULL || Key == NULL) {
187         *NotFound = TRUE;
188         return INT4_MIN;
189     }
190 
191     *NotFound = FALSE;
192 
193     if(pGlobal->Cursor >= 0)
194         if ((*pGlobal->CompareFunc)(Key, pGlobal->List[pGlobal->Cursor].Key) == 0)
195             return pGlobal->Cursor;
196 
197     if(pGlobal->Size == 0) {
198         *NotFound = TRUE;
199         return 0;
200     }
201  
202     l = 0;
203     r = B_GetSize(pGlobal) - 1;
204 
205     while (TRUE) {
206         x = (l + r)/2;
207         CompareValue = (*pGlobal->CompareFunc)(Key, pGlobal->List[x].Key);
208         if (CompareValue == 0) {
209             pGlobal->Cursor = x;
210             return x;
211         }
212         if (r <= l) break;
213         if (CompareValue < 0) {
214             if (x > 0) r = x - 1;
215             else r = 0;
216         }
217         else {
218             if (x < B_GetSize(pGlobal) - 1) l = x + 1;
219             else l = B_GetSize(pGlobal) - 1;
220         }
221     }
222     *NotFound = TRUE;  /* not found */
223     return x;
224 }
225 
226 
227 NLM_EXTERN Int4 B_GetFirst(B_Global *pGlobal, void *Key, Boolean *NotFound)
228 {
229     Int4 i, j;
230 
231     i = B_Get(pGlobal, Key, NotFound);
232     if(B_GetSize(pGlobal) < 2) return i;
233 
234     if(*NotFound) {    
235         if( i == INT4_MIN) return i;
236         for(j = -1; j < 2; j++) {
237             if(j + i < 0 ) continue;
238             if(j + i >= B_GetSize(pGlobal)) break;
239             if((*pGlobal->CompareFunc)(Key, pGlobal->List[j+i].Key) < 0) break;
240         }
241         return j + i;
242     }
243     
244     if(i == 0) return i;
245     while((*pGlobal->CompareFunc)(pGlobal->List[i].Key, pGlobal->List[i-1].Key)
246         == 0 && i > 1) i--;
247 
248     return i;
249 }
250 
251 NLM_EXTERN void * B_GetBag(B_Global *pGlobal, void *Key)
252 {
253     Int4 i;
254     Boolean NotFound;
255 
256     i = B_Get(pGlobal, Key, &NotFound);
257     if(NotFound) return NULL;
258     else return pGlobal->List[i].Bag;
259 }
260 
261 
262
[ 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.