/* parc
 * Copyright (C) 2025 Ekaitz Zarraga <ekaitz@elenq.tech>
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

typedef struct
  {
    size_t len;
    size_t size;
    char *contents;
  }
text_buffer;

typedef struct _piece
  {
    text_buffer *buffer;
    size_t start;
    size_t length;
    struct _piece *next;
    struct _piece *prev;
  }
piece;

typedef struct _piece_buffer
  {
    size_t len;
    size_t size;
    struct _piece_buffer *next;
    piece *start;
  }
piece_buffer;

typedef struct _piece_table
  {
    text_buffer orig;
    text_buffer add;
    piece_buffer *pieces;
    piece *sentinel;
    piece *empty;
    size_t length;

    piece *cached;
    size_t cached_offset;
  }
piece_table;


void
text_buffer_init (text_buffer *tb)
{
  tb->len = 0;
  tb->size = 0;
  tb->contents = NULL;
}

void
text_buffer_append (text_buffer *tb, char c)
{
  size_t base_size = 1024;
  if (tb->size == 0)
    {
      tb->contents = malloc (sizeof(*tb->contents) * base_size);
      tb->size = base_size;
    }
  else if (tb->size == tb->len)
    {
      tb->contents = realloc (tb->contents, sizeof(*tb->contents) * tb->len*2);
    }
  tb->contents[tb->len++] = c;
}

char
text_buffer_index (text_buffer *tb, size_t pos)
{
  assert (pos < tb->len);
  return tb->contents[pos];
}

void
text_buffer_empty (text_buffer *tb)
{
  free (tb->contents);
  text_buffer_init (tb);
}

void
text_buffer_fill (text_buffer *tb, char *fill, size_t size)
{
  size_t i;
  tb->len = size;
  tb->size = size;
  free (tb->contents);
  tb->contents = malloc (sizeof (*tb->contents) * size);
  for (i=0; i<size; i++)
    {
      tb->contents[i] = fill[i];
    }
}

void
text_buffer_free (text_buffer *tb)
{
  free (tb->contents);
  text_buffer_init (tb);
}


piece_buffer *
piece_buffer_create (size_t size)
{
  piece_buffer *pb;
  size_t s = sizeof (piece_buffer) + sizeof (piece) * size;
  pb = malloc (s);
  memset (pb, 0, s);
  pb->start = (piece *)pb+1;
  return pb;
}

piece *
piece_buffer_bump (piece_buffer *pb)
{
  while (pb->next != NULL)
    {
      pb = pb->next;
    }

  if (pb->len == pb->size)
    {
      pb->next = piece_buffer_create (1024);
    }
  return &pb->start[pb->len++];
}

void
piece_buffer_destroy (piece_buffer *pb)
{
  piece_buffer *next;
  do
    {
      next = pb->next;
      free (pb);
      pb = next;
    }
  while (pb != NULL);
}



void
piece_table_piece_mark_empty (piece_table *pt, piece *p)
{
  p->next = pt->empty;
  pt->empty = p;
}

piece *
piece_table_piece_new (piece_table *pt)
{
  piece *p;
  if (pt->empty != NULL)
    {
      p = pt->empty;
      pt->empty = pt->empty->next;
      return p;
    }
  /* TODO: Resize if needed */
  return piece_buffer_bump (pt->pieces);
}


piece *
piece_table_piece_split(piece_table *pt, piece *p, size_t pos)
{
  /* Returns the first piece */
  piece *second;
  assert(pos < p->length);
  assert(p->buffer != NULL); /* Not a sentinel piece */
  assert(p->length != 0);    /* Not an empty piece (they should not exist) */
  if ( pos == 0 )
    {
      return p->prev;
    }
  second = piece_buffer_bump (pt->pieces);
  second->length = p->length - pos;
  p->length = pos;
  second->next = p->next;
  second->next->prev = second;
  p->next = second;
  second->prev = p;
  second->start = p->start + pos;
  second->buffer = p->buffer;
  return p;
}

void
piece_find_by_pos(piece_table *pt, size_t pos)
{
  piece *cur;
  assert(pos < pt->length);
  if ( pos >= pt->cached_offset )
    {
      /* Search forward */
      for ( cur = pt->cached; ; cur = cur->next )
        {
          if ( pt->cached_offset + cur->length > pos )
            {
              pt->cached = cur;
              assert(pt->cached != pt->sentinel);
              return;
            }
          pt->cached_offset += cur->length;
        }
    }
  else
    {
      /* Search backwards */
      for ( cur = pt->cached->prev; ; cur = cur->prev )
        {
          pt->cached_offset -= cur->length;
          if ( pt->cached_offset <= pos )
            {
              pt->cached = cur;
              assert(pt->cached != pt->sentinel);
              return;
            }
        }
    }
}


void
piece_table_insert (piece_table *pt, size_t pos, char *in, size_t len)
{
  piece *start, *end, *new;
  size_t i;

  assert( pos <= pt->length );
  assert( len > 0 );

  for (i = 0; i<len; i++)
    {
      text_buffer_append (&pt->add, in[i]);
    }

  if ( pos == 0 )
    {
      start = pt->sentinel;
    }
  else if ( pos == pt->length )
    {
      start = pt->sentinel->prev;
      pt->cached_offset = pt->length - start->length;
      pt->cached = start;
    }
  else
    {
      piece_find_by_pos(pt, pos);
      start = piece_table_piece_split(pt, pt->cached, pos - pt->cached_offset);
    }
  end = start->next;

  /* Update cache;
   * If we insert before our cached piece, the offset is not up-to-date
   * anymore.
   */
  if ( pt->cached_offset >= pos )
    {
      pt->cached = pt->cached->prev;
      pt->cached_offset -= pt->cached->length;
    }

  /* Optimization!
   * Add in the end of the buffer, and the end of the piece: enlarge
   */
  if ( pt->add.len != 0 &&
       start->buffer == &pt->add &&
       pt->cached_offset + start->length == pos &&
       pt->add.len == start->start + start->length ) {
      pt->length += len;
      start->length += len;
      return;
  }


  /* Make a new piece and insert it */
  new = piece_buffer_bump(pt->pieces);
  new->buffer = &pt->add;
  new->start = pt->add.len - len;
  new->length = len;

  start->next = new;
  new->prev = start;
  new->next = end;
  end->prev = new;
  pt->length += len;
}

void
piece_table_delete(piece_table *pt, size_t pos, size_t len)
{
  piece *cur, *next, *start, *end;
  size_t off_start;
  assert( pos + len <= pt->length );
  assert( len > 0 );

  if ( pos == 0 )
    {
      start = pt->sentinel;
      off_start = 0;
    }
  else
    {
      piece_find_by_pos(pt, pos);
      off_start = pt->cached_offset;
      start = piece_table_piece_split(pt, pt->cached, pos - pt->cached_offset);
    }

  if ( pos + len == pt->length )
    {
      end = pt->sentinel;
    }
  else
    {
      piece_find_by_pos(pt, pos + len);
      end = piece_table_piece_split(pt, pt->cached, pos + len - pt->cached_offset)->next;
    }

  /* Update cache to before the start */
  if ( pt->cached_offset >= pos )
    {
      pt->cached = start;
      pt->cached_offset = off_start;
    }

  /* Free unneeded pieces */
  for ( cur = start->next; cur != end ; cur = next )
    {
      next = cur->next;
      /* Free the piece! */
      piece_table_piece_mark_empty (pt, cur);
    }

  start->next = end;
  end->prev = start;
  pt->length -= len;
}


piece_table *
piece_table_create (char *orig)
{
  piece *original;
  piece_table * pt = malloc (sizeof (*pt));
  size_t len = strlen(orig); /* obtain from the outside? */
  pt->length = len;

  /* Original buffer */
  text_buffer_init(&pt->orig);
  text_buffer_fill(&pt->orig, orig, len);

  /* Add buffer */
  text_buffer_init(&pt->add);

  pt->pieces = piece_buffer_create (1024);

  pt->sentinel = piece_buffer_bump (pt->pieces);
  original = piece_buffer_bump (pt->pieces);
  original->buffer = &pt->orig;
  original->start = 0;
  original->length = pt->length;
  original->next = pt->sentinel;
  original->prev = pt->sentinel;
  pt->sentinel->next = original;
  pt->sentinel->prev = original;

  pt->empty = NULL;
  pt->cached = original;
  pt->cached_offset = 0;
  return pt;
}

void
piece_table_destroy (piece_table *pt)
{
  text_buffer_free (&pt->orig);
  text_buffer_free (&pt->add);
  piece_buffer_destroy (pt->pieces);
  free (pt);
}

char
piece_table_index (piece_table *pt, size_t pos)
{
  assert(pos < pt->length);
  piece_find_by_pos(pt, pos);
  return text_buffer_index(pt->cached->buffer,
                           pt->cached->start + pos - pt->cached_offset);
}

void
piece_table_to_string (piece_table *pt, char *buf, size_t size)
{
  size_t i;
  if (pt->length < size)
    size = pt->length;
  for (i = 0; i < size; i++)
    {
      buf[i] = piece_table_index (pt, i);
    }
  buf[i] = '\0';
}

size_t
piece_table_length (piece_table *pt)
{
  return pt->length;
}