#ifdef HAVE_CONFIG_H
# include <config.h>
#endif
#include "landmark.hh"
#include <string.h>

//
// LANDMARK
//

Landmark::Landmark(PermString file)
  : _map(file ? new LandmarkMap(file) : 0), _cp(0)
{
}

String
Landmark::string() const
{
  unsigned l = line();
  String s = file() + ":";
  if (l != NO_LINE)
    s += String(l) + ":";
  return s;
}


//
// LANDMARKMAP :: LANDMASS
//

LandmarkMap::Landmass::Landmass(unsigned first_cp,
				PermString file, unsigned line)
  : _first_cp(first_cp), _last_cp(LAST_CP), _next(0), _n(1),
    _complex_tabs(0), _n_complex_tabs(0)
{
  _file[0] = file;
  _line[0] = line;
  _cp[0] = first_cp;
  _cp[1] = LAST_CP;
  _tabs[0] = 0;
}

LandmarkMap::Landmass::~Landmass()
{
  delete[] _complex_tabs;
}

int
LandmarkMap::Landmass::lineid(unsigned cp) const
{
  if (cp < _first_cp || cp >= _last_cp)
    return -1;
  
  int l = 0;
  int r = _n - 1;
  while (l <= r) {
    int m = (l + r) / 2;
    if (cp >= _cp[m] && cp < _cp[m+1])
      return m;
    else if (cp < _cp[m])
      r = m - 1;
    else
      l = m + 1;
  }
  
  return -1;
}

void
LandmarkMap::Landmass::mark_tab(unsigned cp)
{
  int lid = _n - 1;
  assert(!_next && cp >= _cp[lid]);

  /* How tabs are stored: For line `lid', _tabs[lid] is either
     0	- there are no tabs in the line
     >0	- there are _tabs[lid] at the beginning of the line, no tabs otherwise
     <0 - set k := -_tabs[lid] - 1. This is an offset into the _complex_tabs
          array. The elements beginning at _complex_tabs[k] are the offsets
	  from _cp[lid] which are tabs. Each line's complex tab information is
	  terminated by -1 in _complex_tabs. */

  // check for `common' case: tabs at beginning of line only
  if (_cp[lid] + _tabs[lid] == cp)
    _tabs[lid]++;
  
  else {
    // make sure _complex_tabs is big enough
    int cap = (_n_complex_tabs + 127) & ~127;
    int amt = (_tabs[lid] > 2 ? _tabs[lid] : 2);
    while (_n_complex_tabs + amt > cap) {
      cap += 128;
      short *new_complex_tabs = new short[cap];
      memcpy(new_complex_tabs, _complex_tabs, _n_complex_tabs * sizeof(short));
      delete[] _complex_tabs;
      _complex_tabs = new_complex_tabs;
    }
    
    // create the beginnings of a new block of complex tabs if necessary
    if (_tabs[lid] >= 0) {
      int old_tabs = _tabs[lid];
      _tabs[lid] = -_n_complex_tabs - 1;
      for (int i = 0; i < old_tabs; i++) {
	_complex_tabs[_n_complex_tabs] = i;
	_n_complex_tabs++;
      }
    } else
      _n_complex_tabs--;

    // actually set the tab for cp
    _complex_tabs[_n_complex_tabs] = cp - _cp[lid];
    _complex_tabs[_n_complex_tabs+1] = -1;
    _n_complex_tabs += 2;
  }
}

LandmarkMap::Landmass *
LandmarkMap::Landmass::finish_line(unsigned cp)
{
  assert(!_next);
  
  PermString next_file = _file[_n-1];
  unsigned next_line = _line[_n-1] + 1;
  if (next_line == 0) next_line = NO_LINE;
  
  _cp[_n] = cp;
  
  if (full()) {
    _last_cp = cp;
    _next = new Landmass(cp, next_file, next_line);
    return _next;
  } else {
    _file[_n] = next_file;
    _line[_n] = next_line;
    _tabs[_n] = 0;
    _cp[_n+1] = LAST_CP;
    _n++;
    return this;
  }
}

void
LandmarkMap::Landmass::change_lines(unsigned cp, PermString file,
				    unsigned line)
{
  int i = lineid(cp);
  if (i >= 0) {
    for (; i < _n; i++) {
      if (file) _file[i] = file;
      _line[i] = line;
      line++;
    }
    cp = _last_cp;
  }
  if (_next)
    _next->change_lines(cp, file, line);
}

int
LandmarkMap::Landmass::column(unsigned cp) const
{
  int i = lineid(cp);
  if (i < 0) return -1;
  
  int raw_col = cp - _cp[i];
  if (raw_col <= _tabs[i])
    return raw_col * 8;
  else if (_tabs[i] >= 0)
    return (raw_col - _tabs[i]) + _tabs[i] * 8;
  else {
    int tab = -_tabs[i] - 1;
    int column = 0;
    for (int p = 0; p < raw_col; p++)
      if (_complex_tabs[tab] == p) {
	column = (column & ~7) + 8;
	tab++;
      } else
	column++;
    return column;
  }
}


//
// LANDMARKMAP
//

LandmarkMap::LandmarkMap(PermString file)
  : _head(new Landmass(0, file, 1))
{
  _tail = _head;
}

LandmarkMap::~LandmarkMap()
{
  while (_head) {
    Landmass *n = _head->next();
    delete _head;
    _head = n;
  }
}

bool
LandmarkMap::find(unsigned cp, Landmass *&mass_out, int &index_out) const
{
  Landmass *mass = _head;
  while (mass && cp > mass->last_cp())
    mass = mass->next();
  if (!mass)
    return false;
  
  int index = mass->lineid(cp);
  if (index < 0)
    return false;
  else {
    mass_out = mass;
    index_out = index;
    return true;
  }
}

void
LandmarkMap::mark_tab(unsigned cp)
{
  _tail->mark_tab(cp);
}

void
LandmarkMap::change_lines(unsigned cp, PermString file, unsigned line)
{
  if (cp >= _tail->first_cp())
    _tail->change_lines(cp, file, line);
  else
    _head->change_lines(cp, file, line);
}

PermString
LandmarkMap::file(unsigned cp) const
{
  Landmass *mass; int index;
  if (find(cp, mass, index))
    return mass->file(index);
  else
    return PermString();
}

unsigned
LandmarkMap::line(unsigned cp) const
{
  Landmass *mass; int index;
  if (find(cp, mass, index))
    return mass->line(index);
  else
    return NO_LINE;
}

unsigned
LandmarkMap::column(unsigned cp) const
{
  Landmass *mass; int index;
  if (find(cp, mass, index))
    return mass->column(cp);
  else
    return NO_LINE;
}