Tag Archive for 'ProgrammingPearls'

  1  // ------------------------------------------------------------
  2  // Hyphnate tree
  3  //
  4  class Node;
  5
  6  bool hasChar(const char ch, const Node& n);
  7
  8  class Node {
  9  public:
 10     char ch;
 11     int pos; // position of hyphen from tail
 12     list<Node> children;
 13
 14     Node(char c, int p = -1) : ch(c), pos(p) {};
 15
 16     Node* add(const char c) {
 17        // XXX: linear search
 18        list<Node>::iterator found = find_if(
 19              children.begin(), children.end(),
 20              boost::bind( ptr_fun(hasChar), c, _1));
 21
 22        if (found == children.end()) { // not found
 23           // cout << "Node::add : " << c << endl;
 24           Node n(c);
 25           children.push_front(n);
 26           return &children.front();
 27        }
 28
 29        return &*found;
 30     }
 31
 32  }; // class Node
 33
 34  bool hasChar(const char ch, const Node& n) {
 35     return n.ch == ch;
 36  }
 37
 38
 39  Node root('c');
 40
 41  void addNode(string& pf) {
 42     Node *n = &root;
 43     int pos = -1;
 44     for (string::iterator i = pf.begin() + 1; i != pf.end(); i++) {
 45        if ('-' == *i) {
 46           pos = i - pf.begin() -1;
 47           continue;
 48        }
 49        n = n->add(*i);
 50     }
 51     n->pos = pos;
 52  }
 53
 54  string hyphenate(string& str) {
 55     Node *n = &root;
 56     string ret = str;
 57     int pos = -1;
 58
 59     for (string::reverse_iterator i = str.rbegin()+1; i != str.rend(); i++) {
 60        // cout << "HY: " << *i << endl;
 61        if (n->children.empty()) {
 62           // cout << "hyphenate : " << n->pos << endl;
 63           pos = n->pos;
 64           break;
 65        }
 66
 67        list<Node>::iterator found = find_if(
 68              n->children.begin(), n->children.end(),
 69              boost::bind( ptr_fun(hasChar), *i, _1));
 70        if (found == n->children.end()) { // not found
 71           if (n->pos != -1) {
 72              pos = n->pos;
 73              break;
 74           }
 75           cout << "hyphenate : not found" << endl;
 76           return "";
 77        }
 78
 79        n = &*found;
 80     }
 81
 82     cout << pos << " " << ret.size() << endl;
 83     // ret.resize(ret.length() + 1);
 84     ret.insert(ret.begin() + ret.length() - pos - 1, '-');
 85
 86     return ret;
 87  }
 88
 89  // ------------------------------------------------------------
 90  // utility
 91  //
 92  void showTree_rec(Node *n, int indent) {
 93     for(list<Node>::iterator i = n->children.begin();
 94           i != n->children.end();
 95           i++) {
 96        for (int j=0; j<indent; j++) {
 97           cout << " ";
 98        }
 99        cout << i->ch << " ";
100        if (i->children.empty() || i->pos != -1) {
101           cout << i->pos;
102        }
103        cout << endl;
104
105
106        showTree_rec(&*i, indent + 3);
107     }
108  }
109
110
111  void showTree() {
112     showTree_rec(&root, 0);
113  }
114
115  // ------------------------------------------------------------
116  // test
117  //
118  int main(int argc, char **argv) {
119     assert(argc == 2);
120
121     // build tree
122     string postfix;
123     ifstream ifs(argv[1]);
124     while (!ifs.eof()) {
125        ifs >> postfix;
126        addNode(postfix);
127     }
128
129     showTree();
130
131     // hyphenate
132     string input;
133     while (true) {
134        // read line
135        cin >> input;
136
137        if (cin.eof()) {
138           break;
139        }
140
141        cout << hyphenate(input) << endl;
142     }
143
144     return 0;
145  }

a
   i 1
   m 2
i
   a 1
   b 2
   d 1
   f 1
   h 1
   l 1
      c 3
      b 2
      l 2
   m 1
   n 1
      h 2
   t
      a 1
      c 2
      n 2
         a 2
      o 1
      y
         l 5
      p 2
      s 2
         i
            l
               a 5
      e 1
c

palistic
pa-listic

actic
ac-tic

mantic
man-tic

gigantic
gigan-tic

critic
hyphenate : not found