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