3 import "ArrayUtilities"
7 define array = ((BinarySortedArrayImpl)this).a;
17 String result = new char[30 + 6 + 11];
18 sprintf(result, "BSloc { valid=%d, pos=%u }\n", valid, pos);
23 class BinarySortedArrayImpl
33 // do another class that uses a compare method or modify to use the compare method if it was provided
34 public class ArrayBinarySorted
54 int newsize = (value / _factor + 1) * _factor;
56 size = value ? newsize : 0;
60 get { return _count; }
71 array = renew array void * [value * sizeof(void *)];
76 array = new void * [value * sizeof(void *)];
82 property uint growingFactor { set { _factor = value; } get { return _factor; } }
87 memcpy(array, value, _size * sizeoftype);
94 void Insert(uint position, int n)
97 if(position < _count - 1)
98 MoveBytes(array + (position + n) * sizeoftype, array + position * sizeoftype, (_count - position - n) * sizeoftype);
104 void Remove(uint position, int n)
106 if(position + n - 1 < _count - 1)
107 MoveBytes(array + position * sizeoftype, array + (position + n) * sizeoftype, (_count - position - n) * sizeoftype);
110 BSloc Find(void * item)
115 uint lo = 0, hi = _count - 1;
116 for( ; hi - lo >= _threshold; )
118 uint tri = (hi - lo) / 3;
120 //if(Compare(client, _[i], item) > 0)
129 lo += tri, hi -= tri;
132 if(array[lo] <= item)
134 if(array[hi] >= item)
137 for(i = lo + 1; array[i] <= item; i++);
140 result.valid = true, result.pos = i;
144 if(array[hi] <= item)
145 ;//result.oldpos = hi + 1;
147 result.valid = true/*, result.oldpos = hi*/, result.pos = hi;
152 //result.oldpos = lo;
153 if(array[lo] == item)
154 result.valid = true, result.pos = lo;
162 public class StringBSArray : ArrayBinarySorted
164 type = class(String);
167 BSloc Add(String item)
169 BSloc result = Find(item);
172 Insert(result.pos, 1);
173 _[result.pos] = item;
177 BSloc Remove(String item)