/// Compare two views lexicographically (rows 0..N-1).
int c4_View::Compare(const c4_View &view_)const {
  if (_seq == view_._seq)
    return 0;

  int na = GetSize();
  int nb = view_.GetSize();
  int i;

  for (i = 0; i < na && i < nb; ++i)
    if (GetAt(i) != view_.GetAt(i))
      return GetAt(i) < view_.GetAt(i) ?  - 1:  + 1;

  return na == nb ? 0 : i < na ?  + 1:  - 1;
}

c4_View c4_GroupByViewer::GetTemplate()
{
  c4_View v = _keys.Clone();
  v.AddProperty(_result);

  return v;
}

int MkView::asIndex(c4_View &view, Tcl_Obj *obj_, bool mayExceed_) {
  int size = view.GetSize();
  int index;

  if (Tcl_GetIntFromObj(interp, obj_, &index) != TCL_OK) {
    const char *step = Tcl_GetStringFromObj(obj_, 0);
    if (step != 0 && strcmp(step, "end") == 0) {
      index = !mayExceed_ ? size - 1: size;
      Tcl_ResetResult(interp); // clear error
      _error = TCL_OK;
    } else {
      index =  - 1;
    }
  }

  if (mayExceed_) {
    if (index > size)
      Fail("view index is too large");
    else if (index < 0)
      Fail("view index is negative");
  } else if (index < 0 || index >= size)
    Fail("view index is out of range");

  return index;
}

void c4_Differ::ApplyDiff(int id_, c4_Column &col_)const {
  d4_assert(0 <= id_ && id_ < _diffs.GetSize());

  c4_View diff = pDiff(_diffs[id_]);
  t4_i32 offset = 0;

  for (int n = 0; n < diff.GetSize(); ++n) {
    c4_RowRef row(diff[n]);
    offset += pKeep(row);

    c4_Bytes data;
    pBytes(row).GetData(data);

    // the following code is a lot like c4_MemoRef::Modify
    const t4_i32 change = pResize(row);
    if (change < 0)
      col_.Shrink(offset,  - change);
    else if (change > 0)
      col_.Grow(offset, change);

    col_.StoreBytes(offset, data);
    offset += data.Size();
  }

  if (offset > col_.ColSize())
    col_.Shrink(offset, offset - col_.ColSize());
}

c4_Storage::c4_Storage(const c4_View &root_) {
  if (root_.Persist() != 0)
  // only restore if view was indeed persistent
    *(c4_View*)this = root_;
  else
  // if this was not possible, start with a fresh empty storage
    Initialize(*d4_new c4_Strategy, true, 0);
}

void c4_Differ::CreateDiff(int id_, c4_Column &col_) {
  _temp.SetSize(0);
#if 0
  t4_i32 offset = 0;
  t4_i32 savedOff = 0;
  t4_i32 savedLen = 0;

  c4_Strategy *strat = col_.Persist() != 0 ? &col_.Strategy(): 0;

  c4_ColIter iter(col_, 0, col_.ColSize());
  while (iter.Next()) {
    const t4_byte *p = iter.BufLoad();
    if (strat != 0 && strat->_mapStart != 0 && p >= strat->_mapStart && p -
      strat->_mapStart < strat->_dataSize) {
      t4_i32 nextOff = p - strat->_mapStart;
      if (savedLen == 0)
        savedOff = nextOff;
      if (nextOff == savedOff + savedLen) {
        savedLen += iter.BufLen();
        continue;
      }

      if (savedLen > 0)
        AddEntry(savedOff, savedLen, c4_Bytes());

      savedOff = nextOff;
      savedLen = iter.BufLen();
    } else {
      AddEntry(savedOff, savedLen, c4_Bytes(p, iter.BufLen()));
      savedLen = 0;
    }

    offset += iter.BufLen();
  }

  c4_View diff = pDiff(_diffs[id_]);
  if (_temp.GetSize() != diff.GetSize() || _temp != diff)
#else 
    c4_Bytes t1;
  const t4_byte *p = col_.FetchBytes(0, col_.ColSize(), t1, false);
  AddEntry(0, 0, c4_Bytes(p, col_.ColSize()));
#endif 
  pDiff(_diffs[id_]) = _temp;

  pOrig(_diffs[id_]) = col_.Position();
}

void c4_Differ::GetRoot(c4_Bytes &buffer_) {
  int last = _diffs.GetSize() - 1;
  if (last >= 0) {
    c4_Bytes temp;
    c4_View diff = pDiff(_diffs[last]);
    if (diff.GetSize() > 0)
      pBytes(diff[0]).GetData(buffer_);
  }
}

c4_JoinViewer::c4_JoinViewer(c4_Sequence &seq_, const c4_View &keys_, const
  c4_View &view_, bool outer_): _parent(&seq_), _argView(view_.SortOn(keys_)) {
  // why not in GetTemplate, since we don't need to know this...
  _template = _parent.Clone();
  for (int l = 0; l < _argView.NumProperties(); ++l)
    _template.AddProperty(_argView.NthProperty(l));

  c4_View sorted = _parent.SortOn(keys_).Project(keys_);
  c4_View temp = _argView.Project(keys_);

  _base.SetSize(0, 5);
  _offset.SetSize(0, 5);

  int j = 0, n = 0;

  for (int i = 0; i < sorted.GetSize(); ++i) {
    int orig = _parent.GetIndexOf(sorted[i]);
    d4_assert(orig >= 0);

    if (i > 0 && sorted[i] == sorted[i - 1]) {
      // if last key was same, repeat the same join
      int last = _offset.GetSize() - n;
      for (int k = 0; k < n; ++k) {
        _base.Add(orig);
        _offset.Add(_offset.GetAt(last + k));
      }
    } else
     { // no, this is a new combination
      bool match = false;

      // advance until the temp view entry is >= this sorted entry
      while (j < temp.GetSize())
      if (sorted[i] <= temp[j]) {
        match = sorted[i] == temp[j];
        break;
      } else
        ++j;

      n = 0;

      if (match) {
        do {
          _base.Add(orig);
          _offset.Add(j);
          ++n;
        } while (++j < temp.GetSize() && temp[j] == temp[j - 1]);
      } else if (outer_) {
        // no match, add an entry anyway if this is an outer join
        _base.Add(orig);
        _offset.Add(~(t4_i32)0); // special null entry
        ++n;
      }
    }
  }
}

/// Insert copies of all rows of the specified view
void c4_View::InsertAt(int index_, const c4_View &view_) {
  int n = view_.GetSize();
  if (n > 0) {
    c4_Row empty;

    InsertAt(index_, empty, n);

    for (int i = 0; i < n; ++i)
      SetAt(index_ + i, view_[i]);
  }
}

static void ViewDisplay(const c4_View& v_, int l_ =0)
{
  c4_String types;
  bool hasData = false, hasSubs = false;

    // display header info and collect all data types
  printf("%*s VIEW %5d rows =", l_, "", v_.GetSize());
  for (int n = 0; n < v_.NumProperties(); ++n)
  {
    c4_Property prop = v_.NthProperty(n);
    char t = prop.Type();

    printf(" %s:%c", (const char*) prop.Name(), t);
    
    types += t;
  
    if (t == 'V')
      hasSubs = true;
    else
      hasData = true;
  }
  printf("\n");

  for (int j = 0; j < v_.GetSize(); ++j)
  {
    if (hasData)  // data properties are all shown on the same line
    {
      printf("%*s %4d:", l_, "", j);
      c4_RowRef r = v_[j];
      c4_Bytes data;

      for (int k = 0; k < types.GetLength(); ++k)
      {
        c4_Property p = v_.NthProperty(k);

        switch (types[k])
        {
        case 'I':
          printf(" %ld", (long) ((c4_IntProp&) p) (r));
          break;

#if !q4_TINY
        case 'F':
          printf(" %g", (double) ((c4_FloatProp&) p) (r));
          break;

        case 'D':
          printf(" %.12g", (double) ((c4_DoubleProp&) p) (r));
          break;
#endif

        case 'S':
          printf(" '%s'", (const char*) ((c4_StringProp&) p) (r));
          break;

        case 'M': // backward compatibility
        case 'B':
          (p (r)).GetData(data);
          printf(" (%db)", data.Size());
          break;

        default:
          if (types[k] != 'V')
            printf(" (%c?)", types[k]);
        }
      }

      printf("\n");
    }

    if (hasSubs)  // subviews are then shown, each as a separate block
    {
      for (int k = 0; k < types.GetLength(); ++k)
      {
        if (types[k] == 'V')
        {
          c4_Property prop = v_.NthProperty(k);

          printf("%*s %4d: subview '%s'\n", l_, "", j,
              (const char*) prop.Name());

          c4_ViewProp& vp = (c4_ViewProp&) prop;
          
          ViewDisplay(vp (v_[j]), l_ + 2);
        }
      }
    }
  }
}

bool PyViewer::GetItem(int row_, int col_, c4_Bytes &buf_) {
  const c4_Property &prop = _template.NthProperty(col_);
  if (_byPos) {
    PWOSequence item(_data[row_]);
    PyRowRef::setFromPython(_tempRow, prop, item[col_]);
    return prop(_tempRow).GetData(buf_);
  }
  PyObject *item = _data[row_];
  if (PyInstance_Check(item)) {
    PyObject *attr = PyObject_GetAttrString(item, (char*)prop.Name());
    PyRowRef::setFromPython(_tempRow, prop, attr);
    return prop(_tempRow).GetData(buf_);
  }
  if (PyDict_Check(item)) {
    PyObject *attr = PyDict_GetItemString(item, (char*)prop.Name());
    PyRowRef::setFromPython(_tempRow, prop, attr);
    return prop(_tempRow).GetData(buf_);
  }
  if (_template.NumProperties() == 1) {
    PyRowRef::setFromPython(_tempRow, prop, _data[row_]);
    return prop(_tempRow).GetData(buf_);
  }
  Fail(PyExc_ValueError, "Object has no usable attributes");
  return false;
  // create a row with just this single property value
  // this detour handles dicts and objects, because makeRow does
  /*  c4_Row one;
  PyView v (prop); // nasty, stack-based temp to get at makeRow
  v.makeRow(one, _data[row_]);
  return prop (one).GetData(buf_); */
}

bool c4_RemapWithViewer::GetItem(int row_, int col_, c4_Bytes &buf_) {
  const c4_Property &map = _argView.NthProperty(0);
  d4_assert(map.Type() == 'I');

  row_ = ((const c4_IntProp &)map)(_argView[row_]);

  return _parent.GetItem(row_, col_, buf_);
}

void c4_Differ::AddEntry(t4_i32 off_, t4_i32 len_, const c4_Bytes &data_) {
  int n = _temp.GetSize();
  _temp.SetSize(n + 1);
  c4_RowRef r = _temp[n];

  pKeep(r) = (t4_i32)off_;
  pResize(r) = (t4_i32)len_;
  pBytes(r).SetData(data_);
}

void CResizer::Verify() {
  int i;

  A(_refSize == _unattached.GetSize());
  A(_refSize == _attached.GetSize());

  for (i = 0; i < _refSize; ++i) {
    A(_refData[i] == _prop(_unattached[i]));
    A(_refData[i] == _prop(_attached[i]));
  }
}

int CResizer::Del(int pos_, int cnt_) {
  A(pos_ + cnt_ <= _refSize);

  _refSize -= cnt_;
  memmove(_refData + pos_, _refData + pos_ + cnt_, _refSize - pos_);

  _unattached.RemoveAt(pos_, cnt_);
  _attached.RemoveAt(pos_, cnt_);

  Verify();

  return _refSize;
}

bool c4_SliceViewer::SetItem(int row_, int col_, const c4_Bytes& buf_)
{
  row_ = _first + _step * (_step > 0 ? row_ : row_ - GetSize() + 1);

  _parent.SetItem(row_, col_, buf_);
  return true;
}

int c4_SliceViewer::GetSize() {
  int n = _limit >= 0 ? _limit : _parent.GetSize();
  if (n < _first)
    n = _first;

  int k = _step < 0 ?  - _step: _step;
  return (n - _first + k - 1) / k;
}

bool c4_SliceViewer::InsertRows(int pos_, c4_Cursor value_, int count_) {
  if (_step != 1)
    return false;

  pos_ = _first + _step *(_step > 0 ? pos_ : pos_ - GetSize() + 1);
  if (_limit >= 0)
    _limit += count_;

  _parent.InsertAt(pos_,  *value_, count_);
  return true;
}

bool c4_GroupByViewer::GetItem(int row_, int col_, c4_Bytes& buf_)
{
  if (col_ < _keys.NumProperties())
    return _sorted.GetItem(_map.GetAt(row_), col_, buf_);

  d4_assert(col_ == _keys.NumProperties());
  
  t4_i32 count;
  switch (_result.Type())
  {
    case 'I': count = _map.GetAt(row_ + 1) - _map.GetAt(row_);
          buf_ = c4_Bytes (&count, sizeof count, true);
          break;
    case 'V': _temp = _sorted.Slice(_map.GetAt(row_), _map.GetAt(row_ + 1))
                .ProjectWithout(_keys);
          buf_ = c4_Bytes (&_temp, sizeof _temp, true);
          break;
    default:  d4_assert(0);
  }

  return true;
}

int CResizer::Ins(int pos_, int cnt_) {
  A(pos_ <= _refSize);
  A(_refSize + cnt_ < kMaxData);

  memmove(_refData + pos_ + cnt_, _refData + pos_, _refSize - pos_);
  _refSize += cnt_;

  c4_Row row;
  _unattached.InsertAt(pos_, row, cnt_);
  _attached.InsertAt(pos_, row, cnt_);

  for (int i = pos_; i < pos_ + cnt_; ++i) {
    _refData[i] = ++_seed;
    _prop(_unattached[i]) = _seed;
    _prop(_attached[i]) = _seed;

    if (_seed >= 123)
      _seed = 0;
  }

  Verify();

  return _refSize;
}