1 // Copyright (c) 2000 Matthias Clasen 2 // See the file COPYING for copying permission. 3 4 #include "splib.h" 5 #include "SubstTable.h" 6 #include <stdlib.h> 7 8 #ifdef SP_NAMESPACE 9 namespace SP_NAMESPACE { 10 #endif 11 12 SubstTable::SubstTable() 13 : isSorted_(1) 14 { 15 for (size_t i = 0; i < 256; i++) 16 lo_[i] = i; 17 } 18 19 void SubstTable::addSubst(Char from, Char to) 20 { 21 if (from < 256) 22 lo_[from] = to; 23 else { 24 for (size_t i = 0; i < map_.size(); i++) 25 if (map_[i].from == from) { 26 map_[i].to = to; 27 return; 28 } 29 if (from != to) { 30 isSorted_ = isSorted_ && (map_.size() == 0 || map_.back().from < from); 31 map_.push_back(Pair(from, to)); 32 } 33 } 34 } 35 36 Char SubstTable::at(Char t) const 37 { 38 if (!isSorted_) { 39 sort(); 40 #ifndef HAVE_MUTABLE 41 ((SubstTable *)this)-> 42 #endif 43 isSorted_ = 1; 44 } 45 size_t min = 0; 46 size_t max = map_.size() - 1; 47 if (map_.size() == 0 || t < map_[min].from || t > map_[max].from) 48 return t; 49 if (t == map_[min].from) 50 return map_[min].to; 51 if (t == map_[max].from) 52 return map_[max].to; 53 for(;;) { 54 size_t mid = (min + max) / 2; 55 if (mid == min || mid == max) 56 return t; 57 if (t == map_[mid].from) 58 return map_[mid].to; 59 if (t < map_[mid].from) 60 max = mid; 61 else 62 min = mid; 63 } 64 } 65 66 extern "C" { 67 68 static 69 int comparePairs(const void *p1, const void *p2) 70 { 71 return ((SubstTable::Pair *)p1)->from - ((SubstTable::Pair *)p2)->from; 72 } 73 74 } 75 76 void SubstTable::sort() const 77 { 78 qsort((void *)&map_[0], map_.size(), sizeof(map_[0]), comparePairs); 79 } 80 81 StringC SubstTable::inverse(Char c) const 82 { 83 StringC res; 84 bool cSeen = (c < 256); 85 for (size_t i = 0; i < 256; i++) 86 if (lo_[i] == c) 87 res += i; 88 for (size_t i = 0; i < map_.size(); i++) { 89 cSeen = cSeen || (map_[i].from == c); 90 if (map_[i].to == c) 91 res += map_[i].from; 92 } 93 if (!cSeen) 94 res += c; 95 return res; 96 } 97 98 void SubstTable::inverseTable(SubstTable &inverse) const 99 { 100 for (size_t i = 0; i < 256; i++) 101 inverse.lo_[i] = i; 102 inverse.map_.resize(0); 103 inverse.isSorted_ = 1; 104 for (size_t i = 0; i < 256; i++) 105 inverse.addSubst(lo_[i], i); 106 for (size_t i = 0; i < map_.size(); i++) 107 inverse.addSubst(map_[i].to, map_[i].from); 108 } 109 110 #ifdef SP_NAMESPACE 111 } 112 #endif 113