/*
 * CDE - Common Desktop Environment
 *
 * Copyright (c) 1993-2012, The Open Group. All rights reserved.
 *
 * These libraries and programs are free software; you can
 * redistribute them and/or modify them under the terms of the GNU
 * Lesser General Public License as published by the Free Software
 * Foundation; either version 2 of the License, or (at your option)
 * any later version.
 *
 * These libraries and programs are distributed in the hope that
 * they will be useful, but WITHOUT ANY WARRANTY; without even the
 * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
 * PURPOSE. See the GNU Lesser General Public License for more
 * details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with these libraries and programs; if not, write
 * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
 * Floor, Boston, MA 02110-1301 USA
 */
/* $XConsortium: OffsetOrderedList.C /main/1 1996/07/29 16:59:05 cde-hp $ */
// Copyright (c) 1994 James Clark
// See the file COPYING for copying permission.

#include "splib.h"
#include "OffsetOrderedList.h"
#include "macros.h"

#ifdef SP_NAMESPACE
namespace SP_NAMESPACE {
#endif

OffsetOrderedList::OffsetOrderedList()
: blockUsed_(OffsetOrderedListBlock::size)
{
}

void OffsetOrderedList::append(Offset offset)
{
  // At any position in the list there's a current offset.
  // The offset is initially zero.
  // A byte of 255 says add 255 to the current offset.
  // A byte B < 255, says that there's an item in the list whose
  // offset is the current offset + B, and that B + 1 should be
  // added to the current offset.
  Offset curOffset = blocks_.size() > 0  ? blocks_.back()->offset : 0;
  ASSERT(offset >= curOffset);
  Offset count = offset - curOffset;
  while (count >= 255) {
    addByte(255);
    count -= 255;
  }
  addByte(count);
}

void OffsetOrderedList::addByte(unsigned char b)
{
  if (blockUsed_ >= OffsetOrderedListBlock::size) {
    blocks_.resize(blocks_.size() + 1);
    Owner<OffsetOrderedListBlock> &last = blocks_.back();
    last = new OffsetOrderedListBlock;
    if (blocks_.size() == 1) {
      last->nextIndex = 0;
      last->offset = 0;
    }
    else {
      OffsetOrderedListBlock &lastButOne = *blocks_[blocks_.size() - 2];
      last->nextIndex = lastButOne.nextIndex;
      last->offset = lastButOne.offset;
    }
    blockUsed_ = 0;
  }
  blocks_.back()->bytes[blockUsed_++] = b;
  if (b == 255)
    blocks_.back()->offset += 255;
  else {
    blocks_.back()->offset += b + 1;
    blocks_.back()->nextIndex += 1;
  }
}

// Find the last offset <= off.

Boolean OffsetOrderedList::findPreceding(Offset off,
					 size_t &foundIndex,
					 Offset &foundOffset) const
{
  // Invariant:
  // blocks with index < i have offset <= off
  // blocks with index >= lim have offset > off
  size_t i = 0;
  size_t lim = blocks_.size();
  // Most commonly we'll want to know the about positions near the end,
  // so optimize this case.
  if (lim > 0 && blocks_[lim - 1]->offset <= off)
    i = lim;
  else if (lim > 1 && blocks_[lim - 2]->offset <= off)
    i = lim - 1;
  else {
    // Do a binary search.
    while (i < lim) {
      size_t mid = i + (lim - i)/2;
      if (blocks_[mid]->offset > off)
	lim = mid;
      else
	i = mid + 1;
    }
  }
  if (i == blocks_.size()) {
    if (i == 0)
      return 0;
    foundIndex = blocks_.back()->nextIndex - 1;
    foundOffset = blocks_.back()->offset - 1;
    return 1;
  }
  // Note that an item with offset X can only occur in a block with offset > X
  // i is now the first block with offset > off
  Offset curOff = blocks_[i]->offset;
  size_t curIndex = blocks_[i]->nextIndex;
  const unsigned char *bytes = blocks_[i]->bytes;
  int j = (i == blocks_.size() - 1
	   ? blockUsed_ 
	   : int(OffsetOrderedListBlock::size));
  for (;;) {
    j--;
    if (bytes[j] != 255) {
      curIndex -= 1;
      curOff -= 1;
      if (curOff <= off)
	break;
    }
    curOff -= bytes[j];
    if (j == 0) {
      if (i == 0)
	return 0;
      i--;
      j = OffsetOrderedListBlock::size;
      curOff = blocks_[i]->offset;
      curIndex = blocks_[i]->nextIndex;
      bytes = blocks_[i]->bytes;
    }
  }
  foundIndex = curIndex;
  foundOffset = curOff;
  return 1;
}

#ifdef SP_NAMESPACE
}
#endif