Listing 13 Implementation for a self-adjusting lns class

//
// lns5.cpp - line number sequence
// implementation
//

#include <stdio.h>

#include "lns.h"

//
// lns_list
//
class lns_list : public lns::protocol
   {
public:
   lns_list();
   lns_list(unsigned n);
   ~lns_list();
   void print();
protected:
   struct node;
   node *first;
   };

struct lns_list::node
   {
   node(unsigned n);
   unsigned number;
   node *next;
   };

inline lns_list::node::node(unsigned n)
   :number(n), next(0)
   {
   }

//
// lns_list member definitions
//
inline lns_list::lns_list()
   {
   }

inline lns_list::lns_list(unsigned n)
   : first(new node(n))
   {
   }

lns_list::~lns_list()
   {
   node *p;
   while ((p = first) != 0)
      {
      first = first->next;
      delete p;
      }
   }

void lns_list::print()
   {
   node *p;
   for (p = first; p !=  0; p = p->next)
      printf(" %4d", p->number);
   }

//
// lns_small
//
class lns_small : public lns_list
   {
public:
   lns_small (unsigned n);
   protocol *add(unsigned n);
   void print();
private:
   enum { THRESHOLD =  5 };
   };

//
// lns_fast
//
class lns_fast : public lns_list
   {
public:
   lns_fast(node *fn,  node *ln);
   lns_fast(unsigned n);
   protocol *add(unsigned n);
   void print();
private:
   node *last;
   };

//
// lns_fast member definitions
//
inline lns_fast::lns_fast(node *fn, node *ln)
   {
   first = fn;
   last = ln;
   }

inline lns_fast::lns_fast(unsigned n)
   : lns_list(n)
   {
   last = firts;
   }

lns::protocol *lns_fast::add(unsigned n)
   {
   if (last->number != n)
      last = last->next = new node(n);
   return this;
   }

void lns_fast::print()
   {
   printf(" (f)");
   lns_list::print();
   }

//
// lns_small member definitions
//
inline lns_small::lns_small(unsigned n)
   : lns_list(n)
   {
   }

lns::protocol *lns_small::add(unsigned n)
   {
   int len = 1;
   node *p = first;
   for ( ; p->next != 0; p = p->next)
      ++len;
   if (p->number != n)
      {
      p = p->next = new node(n);
      if (++len > THRESHOLD)
         {
         lns_fast *q =
            new lns_fast(first, p);
         first = 0;
         return q;
         }
      }
   return this;
   }

void lns_small::print()
   {
   printf(" (s)");
   lns_list::print();
   }

//
// lns constructor
//
lns::lns(unsigned n)
   {
   pp = new lns_small(n);
   }

void lns::add(unsigned n)
   {
   protocol *np = pp->add(n);
   if (np != pp)
      {
      delete pp;
      pp = np;
      }
   }
lns::protocol::~protocol()
{ }

//End of File