# encoding: utf-8

# name_tree.rb : Implements NameTree for PDF
#
# Copyright November 2008, Jamis Buck. All Rights Reserved.
#
# This is free software. Please see the LICENSE and COPYING files for details.
#
require 'prawn/literal_string'
require 'prawn/reference'

module Prawn
  module NameTree #:nodoc:
    class Node #:nodoc:
      attr_reader :children
      attr_reader :limit
      attr_reader :document
      attr_accessor :parent
      attr_accessor :ref

      def initialize(document, limit, parent=nil)
        @document = document
        @children = []
        @limit = limit
        @parent = parent
        @ref = nil
      end

      def empty?
        children.empty?
      end

      def size
        leaf? ? children.size : children.inject(0) { |sum, child| sum + child.size }
      end

      def leaf?
        children.empty? || children.first.is_a?(Value)
      end

      def add(name, value)
        self << Value.new(name, value)
      end

      def to_hash
        hash = {}

        hash[:Limits] = [least, greatest] if parent
        if leaf?
          hash[:Names] = children if leaf?
        else
          hash[:Kids] = children.map { |child| child.ref }
        end

        return hash
      end

      def least
        if leaf?
          children.first.name
        else
          children.first.least
        end
      end

      def greatest
        if leaf?
          children.last.name
        else
          children.last.greatest
        end
      end

      def <<(value)
        if children.empty?
          children << value
        elsif leaf?
          children.insert(insertion_point(value), value)
          split! if children.length > limit
        else
          fit = children.detect { |child| child >= value }
          fit << value
        end

        value
      end

      def >=(value)
        children.empty? || children.last >= value
      end

      def split!
        if parent
          parent.split(self)
        else
          left, right = new_node(self), new_node(self)
          split_children(self, left, right)
          children.replace([left, right])
        end
      end

      protected

        def split(node)
          new_child = new_node(self)
          split_children(node, node, new_child)
          index = children.index(node)
          children.insert(index+1, new_child)
          split! if children.length > limit
        end

      private

        def new_node(parent=nil)
          node = Node.new(document, limit, parent)
          node.ref = document.ref(node)
          return node
        end

        def split_children(node, left, right)
          half = (node.limit+1)/2

          left_children, right_children = node.children[0...half], node.children[half..-1]

          left.children.replace(left_children)
          right.children.replace(right_children)

          unless node.leaf?
            left_children.each { |child| child.parent = left }
            right_children.each { |child| child.parent = right }
          end
        end

        def insertion_point(value)
          children.each_with_index do |child, index|
            return index if child >= value
          end
          return children.length
        end
    end

    class Value #:nodoc:
      include Comparable

      attr_reader :name
      attr_reader :value

      def initialize(name, value)
        @name, @value = Prawn::LiteralString.new(name), value
      end

      def <=>(leaf)
        name <=> leaf.name
      end

      def inspect
        "#<Value: #{name.inspect} : #{value.inspect}>"
      end

      def to_s
        "#{name} : #{value}"
      end
    end
  end
end
