/*
    JPC: A x86 PC Hardware Emulator for a pure Java Virtual Machine
    Release Version 2.0

    A project from the Physics Dept, The University of Oxford

    Copyright (C) 2007 Isis Innovation Limited

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License version 2 as published by
    the Free Software Foundation.

    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, write to the Free Software Foundation, Inc.,
    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 
    Details (including contact information) can be found at: 

    www.physics.ox.ac.uk/jpc
*/

package org.jpc.emulator.memory.codeblock;

import java.util.*;
import org.jpc.emulator.memory.*;

public class MemoryTree extends AbstractMemory
{
    private long size;
    private Node root;
    private byte defaultValue;

    public MemoryTree(long size, int def)
    {
        this.defaultValue = (byte) def;
        root = new ConstantNode(defaultValue);
    }

    public boolean isCacheable()
    {
        return true;
    }

    abstract class Node
    {
        abstract byte getByte(int offset);
        
        abstract Node setByte(byte value, int offset);
    }

    class BranchNode extends Node
    {
        Node left, right;
        
        BranchNode(Node l, Node r)
        {
            left = l;
            right = r;
        }
        
        byte getByte(int offset)
        {
            if ((offset & 0x1) == 0)
                return left.getByte(offset >>> 1);
            else
                return right.getByte(offset >>> 1);
        }
        
        Node setByte(byte value, int offset)
        {
            if ((offset & 0x1) == 0)
                left = left.setByte(value, offset >>> 1);
            else
                right = right.setByte(value, offset >>> 1);

            if ((left instanceof ConstantNode) && (right instanceof ConstantNode))
            {
                ConstantNode cl = (ConstantNode) left;
                ConstantNode cr = (ConstantNode) right;
                if ((cl.value == cr.value) && (cl.value == defaultValue))
                    return cl;
            }
            
            return this;
        }
    }
    
    class ConstantNode extends Node
    {
        byte value;
        
        ConstantNode(byte value)
        {
            this.value = value;
        }
        
        byte getByte(int offset)
        {
            if (offset == 0)
                return value;
            else
                return defaultValue;
        }
        
        Node setByte(byte value, int offset)
        {
            if (offset == 0)
            {
                this.value = value;
                return this;
            }

            ConstantNode l = this;
            ConstantNode r = new ConstantNode(defaultValue);
            Node b = new BranchNode(l, r);
            
            b = b.setByte(value, offset);
            return b;
        }
    }

    public long getSize()
    {
        return size;
    }

    public byte getByte(int offset)
    {
        return root.getByte(offset);
    }

    public void setByte(int offset, byte data)
    {
        root = root.setByte(data, offset);
    }

    public CodeBlock queryCodeBlockAt(int offset)
    {
	return null;
    }

    public ProtectedModeCodeBlock getProtectedModeCodeBlockAt(int offset)
    {
	throw new IllegalStateException("Invalid Operation");
    }

    public RealModeCodeBlock getRealModeCodeBlockAt(int offset)
    {
	throw new IllegalStateException("Invalid Operation");
    }
}
