3 import "ArrayFactoredGrowth"
9 import "ArrayUtilities"
21 String result = new char[30 + 6 + 11 + 11];
22 sprintf(result, "BIloc { valid=%d, offset=%u, pos=%u }\n", valid, offset, pos);
27 public class BinaryIndex : Array
39 int (*Compare)(void * client, uint offset, typed_object data);
41 BIloc Find(typed_object data)
44 if(_count && data._class)
46 uint lo = 0, hi = _count - 1;
47 for( ; hi - lo >= threshold; )
49 uint tri = (hi - lo) / 3;
51 if(Compare(client, _[i], data) > 0)
56 if(Compare(client, _[i], data) < 0)
62 if(Compare(client, _[lo], data) <= 0)
64 if(Compare(client, _[hi], data) >= 0)
67 for(i = lo + 1; Compare(client, _[i], data) <= 0; i++);
69 if(Compare(client, _[i], data) == 0)
70 result.valid = true, result.offset = _[i];
74 if(Compare(client, _[hi], data) <= 0)
77 result.valid = true, result.pos = hi, result.offset = _[hi];
83 if(Compare(client, _[lo], data) == 0)
84 result.valid = true, result.offset = _[lo];
90 //void OnSerialize(IOChannel channel)
91 //void OnUnserialize(IOChannel channel)
94 public class StringBIArray : Array
96 // can simply implement multiple compare modes and allow nice switching using enum for method names
100 private BinaryIndex index { client = this, Compare = (void *)Compare };
101 int Compare(uint offset, typed_object data)
103 return strcmp(_[offset], (String)data);
105 BIloc Add(String item)
107 BIloc result = index.Find(item);
110 result.offset = _count;
112 _[result.offset] = item;
113 index.Insert(result.pos, 1);
117 BIloc Remove(String item)