void join(PQ<Item>&);  };-----  Item getmax()    { Item max; link x = head->next;      for (link t = x; t->next != head; t = t->next)        if (x->item < t->item) x = t;      max = x->item;       remove(x);       return max;    }  void change(handle x, Item v)    { x->key = v; }    void remove(handle x)    {      x->next->prev = x->prev;      x->prev->next = x->next;      delete x;    }    void join(PQ<Item>& p)    {      tail->prev->next = p.head->next;      p.head->next->prev = tail->prev;      head->prev = p.tail;       p.tail->next = head;      delete tail; delete p.head;      tail = p.tail;    }-----template <class Index>class PQ   {    private:      // Implementation-dependent code    public:      PQ(int);      int empty() const;      void insert(Index);      Index getmax();      void change(Index);      void remove(Index);  };-----template <class Index>class PQ   {    private:      int N; Index* pq; int* qp;      void exch(Index i, Index j)        { int t;          t = qp[i]; qp[i] = qp[j]; qp[j] = t;          pq[qp[i]] = i; pq[qp[j]] = j;        }    void fixUp(Index a[], int k);    void fixDown(Index a[], int k, int N);    public:      PQ(int maxN)        { pq = new Index[maxN+1];           qp = new int[maxN+1];  N = 0; }      int empty() const        { return N == 0; }      void insert(Index v)        { pq[++N] = v; qp[v] = N; fixUp(pq, N); }      Index getmax()        {           exch(pq[1], pq[N]);           fixDown(pq, 1, N-1);           return pq[N--];         }      void change(Index k)        { fixUp(pq, qp[k]); fixDown(pq, qp[k], N); }  };-----static link pair(link p, link q)  {    if (p->item < q->item)       { p->r = q->l; q->l = p; return q; }    else { q->r = p->l; p->l = q; return p; }  }-----handle insert(Item v)  { link t = new node(v), c = t;    for (int i = 0; i < maxBQsize; i++)      {        if (c == 0) break;        if (bq[i] == 0) { bq[i] = c; break; }        c = pair(c, bq[i]); bq[i] = 0;      }    return t;  }-----Item getmax()  { int i, max; Item v = 0;     link* temp = new link[maxBQsize];    for (i = 0, max = -1; i < maxBQsize; i++)      if (bq[i] != 0)         if ((max == -1) || (v < bq[i]->item))          { max = i; v = bq[max]->item; }    link x = bq[max]->l;     for (i = max; i < maxBQsize; i++) temp[i] = 0;     for (i = max ; i > 0; i--)      { temp[i-1] = x; x = x->r; temp[i-1]->r = 0; }    delete bq[max]; bq[max] = 0;    BQjoin(bq, temp);      delete temp;    return v;  }      -----static inline int test(int C, int B, int A)  { return 4*C + 2*B + 1*A; }static void BQjoin(link *a, link *b)  { link c = 0;    for (int i = 0; i < maxBQsize; i++)      switch(test(c != 0, b[i] != 0, a[i] != 0))        {          case 2: a[i] = b[i]; break;          case 3: c = pair(a[i], b[i]);                   a[i] = 0; break;          case 4: a[i] = c; c = 0; break;          case 5: c = pair(c, a[i]);                   a[i] = 0; break;          case 6:           case 7: c = pair(c, b[i]); break;        }  }----------CHAPTER 10. Radix Sorting-----template <class Item>void quicksortB(Item a[], int l, int r, int d)  { int i = l, j = r;    if (r <= l || d > bitsword) return;    while (j != i)      {         while (digit(a[i], d) == 0 && (i < j)) i++;        while (digit(a[j], d) == 1 && (j > i)) j--;        exch(a[i], a[j]);      }    if (digit(a[r], d) == 0) j++;    quicksortB(a, l, j-1, d+1);    quicksortB(a, j, r, d+1);  }template <class Item>void sort(Item a[], int l, int r)  { quicksortB(a, l, r, 0); }-----#define bin(A) l+count[A]template <class Item>void radixMSD(Item a[], int l, int r, int d)  { int i, j, count[R+1];     static Item aux[maxN];    if (d > bytesword) return;    if (r-l <= M) { insertion(a, l, r); return; }    for (j = 0; j < R; j++) count[j] = 0;    for (i = l; i <= r; i++)       count[digit(a[i], d) + 1]++;    for (j = 1; j < R; j++)       count[j] += count[j-1];    for (i = l; i <= r; i++)       aux[count[digit(a[i], d)]++] = a[i];    for (i = l; i <= r; i++) a[i] = aux[i-l];    radixMSD(a, l, bin(0)-1, d+1);    for (j = 0; j < R-1; j++)      radixMSD(a, bin(j), bin(j+1)-1, d+1);  }-----#define ch(A) digit(A, d)template <class Item>void quicksortX(Item a[], int l, int r, int d)  {     int i, j, k, p, q; int v;    if (r-l <= M) { insertion(a, l, r); return; }    v = ch(a[r]); i = l-1; j = r; p = l-1; q = r;    while (i < j)      {         while (ch(a[++i]) < v) ;        while (v < ch(a[--j])) if (j == l) break;        if (i > j) break;        exch(a[i], a[j]);        if (ch(a[i])==v) { p++; exch(a[p], a[i]); }        if (v==ch(a[j])) { q--; exch(a[j], a[q]); }      }    if (p == q)       { if (v != '\0') quicksortX(a, l, r, d+1);         return; }    if (ch(a[i]) < v) i++;    for (k = l; k <= p; k++, j--) exch(a[k], a[j]);    for (k = r; k >= q; k--, i++) exch(a[k], a[i]);    quicksortX(a, l, j, d);    if ((i == r) && (ch(a[i]) == v)) i++;    if (v != '\0') quicksortX(a, j+1, i-1, d+1);     quicksortX(a, i, r, d);   }-----template <class Item>void radixLSD(Item a[], int l, int r)  { static Item aux[maxN];    for (int d = bytesword-1; d >= 0; d--)      {        int i, j, count[R+1];         for (j = 0; j < R; j++) count[j] = 0;        for (i = l; i <= r; i++)           count[digit(a[i], d) + 1]++;        for (j = 1; j < R; j++)           count[j] += count[j-1];        for (i = l; i <= r; i++)           aux[count[digit(a[i], d)]++] = a[i];        for (i = l; i <= r; i++) a[i] = aux[i-l];      }  } ----------CHAPTER 11. Special-Purpose Sorts-----template <class Item>void shuffle(Item a[], int l, int r)  { int i, j, m = (l+r)/2;    static Item aux[maxN];    for (i = l, j = 0; i <= r; i+=2, j++)      { aux[i] = a[l+j]; aux[i+1] = a[m+1+j]; }    for (i = l; i <= r; i++) a[i] = aux[i];  }template <class Item>void unshuffle(Item a[], int l, int r)  { int i, j, m = (l+r)/2;    static Item aux[maxN];    for (i = l, j = 0; i <= r; i+=2, j++)      { aux[l+j] = a[i]; aux[m+1+j] = a[i+1]; }    for (i = l; i <= r; i++) a[i] = aux[i];  }-----template <class Item>void merge(Item a[], int l, int m, int r)  {     if (r == l+1) compexch(a[l], a[r]);    if (r < l+2) return;    unshuffle(a, l, r);    merge(a, l, (l+m)/2, m);     merge(a, m+1, (m+1+r)/2, r);    shuffle(a, l, r);    for (int i = l+1; i < r; i+=2)       compexch(a[i], a[i+1]);  }-----template <class Item>void merge(Item a[], int l, int m, int r)  { int N = r-l+1;  // assuming N/2 is m-l+1    for (int k = N/2; k > 0; k /= 2)      for (int j = k % (N/2); j+k < N; j += k+k)         for (int i = 0; i < k; i++)           compexch(a[l+j+i], a[l+j+i+k]);  }-----template <class Item>void batchersort(Item a[], int l, int r)  { int N = r-l+1;    for (int p = 1; p < N; p += p)      for (int k = p; k > 0; k /= 2)        for (int j = k%p; j+k < N; j += (k+k))           for (int i = 0; i < N-j-k; i++)             if ((j+i)/(p+p) == (j+i+k)/(p+p))               compexch(a[l+j+i], a[l+j+i+k]);  }--------------------CHAPTER 12. Symbol Tables and BSTs-----#include <stdlib.h>#include <iostream.h>static int maxKey = 1000;typedef int Key;class Item   {     private:      Key keyval;       float info;    public:      Item()         { keyval = maxKey; }       Key key()        { return keyval; }      int null()        { return keyval == maxKey; }      void rand()        { keyval = 1000*::rand()/RAND_MAX;             info = 1.0*::rand()/RAND_MAX; }        int scan(istream& is = cin)        { return (is >> keyval >> info) != 0; }      void show(ostream& os = cout)        { os << keyval << " " << info << endl; }   }; ostream& operator<<(ostream& os, Item& x)  { x.show(os); return os; }-----template <class Item, class Key>class ST   {    private:      // Implementation-dependent code    public:      ST(int);      int count();      Item search(Key) ;      void insert(Item);      void remove(Item);      Item select(int);      void show(ostream&);  };-----#include <iostream.h>#include <stdlib.h>#include "Item.cxx"#include "ST.cxx"int main(int argc, char *argv[])  { int N, maxN = atoi(argv[1]), sw = atoi(argv[2]);    ST<Item, Key> st(maxN);    for (N = 0; N < maxN; N++)      { Item v;         if (sw) v.rand(); else if (!v.scan()) break;        if (!(st.search(v.key())).null()) continue;        st.insert(v);       }    st.show(cout); cout << endl;    cout << N << " keys" << endl;    cout << st.count() << " distinct keys" << endl;  }-----template <class Item, class Key>class ST   {    private:      Item nullItem, *st;      int M;    public:      ST(int maxN)        { M = nullItem.key(); st = new Item[M]; }      int count()        { int N = 0;           for (int i = 0; i < M; i++)             if (!st[i].null()) N++;          return N;        }      void insert(Item x)        { st[x.key()] = x; }      Item search(Key v)        { return st[v]; }      void remove(Item x)        { st[x.key()] = nullItem; }      Item select(int k)        { for (int i = 0; i < M; i++)            if (!st[i].null())               if (k-- == 0) return st[i];          return nullItem;        }      void show(ostream& os)        { for (int i = 0; i < M; i++)            if (!st[i].null()) st[i].show(os); }  };-----template <class Item, class Key>class ST   {    private:      Item nullItem, *st;       int N;    public:      ST(int maxN)        { st = new Item[maxN+1]; N = 0; }      int count()        { return N; }      void insert(Item x)        { int i = N++; Key v = x.key();          while (i > 0 && v < st[i-1].key())            {  st[i] = st[i-1]; i--; }          st[i] = x;        }      Item search(Key v)        {          for (int i = 0; i < N; i++)            if (!(st[i].key() < v)) break;          if (v == st[i].key()) return st[i];          return nullItem;        }      Item select(int k)        { return st[k]; }      void show(ostream& os)        { int i = 0;           while (i < N) st[i++].show(os); }  };-----#include <stdlib.h>template <class Item, class Key>class ST   {    private:      Item nullItem;      struct node         { Item item; node* next;           node(Item x, node* t)            { item = x; next = t; }         };       typedef node *link;      int N;      link head;      Item searchR(link t, Key v)        { if (t == 0) return nullItem;          if (t->item.key() == v) return t->item;          return searchR(t->next, v);        }    public:      ST(int maxN)        { head = 0; N = 0; }      int count()        { return N; }      Item search(Key v)        { return searchR(head, v); }      void insert(Item x)        { head = new node(x, head); N++; }    };-----    private:      Item searchR(int l, int r, Key v)        { if (l > r) return nullItem;          int m = (l+r)/2;          if (v == st[m].key()) return st[m];          if (l == r) return nullItem;          if (v < st[m].key())                return searchR(l, m-1, v);          else return searchR(m+1, r, v);        }    public:      Item search(Key v)        { return searchR(0, N-1, v); }-----template <class Item, class Key>class ST   {    private:      struct node         { Item item; node *l, *r;          node(Item x)            { item = x; l = 0; r = 0; }         };       typedef node *link;      link head;      Item nullItem;      Item searchR(link h, Key v)        { if (h == 0) return nullItem;          Key t = h->item.key();          if (v == t) return h->item;          if (v < t) return searchR(h->l, v);                else return searchR(h->r, v);        }      void insertR(link& h, Item x)        { if (h == 0) { h = new node(x); return; }          if (x.key() < h->item.key())                insertR(h->l, x);          else insertR(h->r, x);        }    public:      ST(int maxN)        { head = 0; }      Item search(Key v)         { return searchR(head, v); }       void insert(Item x)        { insertR(head, x); }  };-----   private:      void showR(link h, ostream& os)        {           if (h == 0) return;          showR(h->l, os);          h->item.show(os);           showR(h->r, os);        }    public:      void show(ostream& os)        { showR(head, os); } -----void insert(Item x)  { Key v = x.key();    if (head == 0)       { head = new node(x); return; }    link p = head;    for (link q = p; q != 0; p = q ? q : p)      q = (v < q->item.key()) ? q->l : q->r;     if (v < p->item.key()) p->l = new node(x);                       else p->r = new node(x);  }-----#include <iostream.h>#include <fstream.h>#include "Item.cxx"#include "ST.cxx"static char text[maxN];int main(int argc, char *argv[])  { int N = 0; char t;    ifstream corpus; corpus.open(*++argv);    while (N < maxN && corpus.get(t)) text[N++] = t;     text[N] = 0;    ST<Item, Key> st(maxN);    for (int i = 0; i < N; i++) st.insert(&text[i]);    char query[maxQ]; Item x, v(query);    while (cin.getline(query, maxQ))      if ((x = st.search(v.key())).null())           cout << "not found: " << query << endl;      else cout <<  x-text << ": " << query << endl;  }-----void rotR(link& h)  { link x = h->l; h->l = x->r; x->r = h; h = x; }void rotL(link& h)  { link x = h->r; h->r = x->l; x->l = h; h = x; }-----private:  void insertT(link& h, Item x)    { if (h == 0) { h = new node(x); return; }      if (x.key() <  h->item.key())            { insertT(h->l, x); rotR(h); }      else { insertT(h->r, x); rotL(h); }    }public:  void insert(Item item)    { insertT(head, item); }-----private:  Item selectR(link h, int k)    { if (h == 0) return nullItem;      int t = (h->l == 0) ? 0: h->l->N;      if (t > k) return selectR(h->l, k);