#! /local/bin/perl5 -w
# sjekkpart partition module

package partition;

$all = 'ALL';

# Fundamental access methods.

sub new {
    my ($class, $start, $size) = @_;
    my $self = {};

    $self->{"start"}->{$all} = $start;
    $self->{"size"}->{$all} = $size;
    bless $self;
}

sub add {
    my ($self, $part, $start, $size) = @_;
    $self->{"start"}->{$part} = $start;
    $self->{"size"}->{$part} = $size;
}

sub remove {
    my ($self, $part) = @_;
    if ($part eq $all) {
	undef $self;
    } else {
	undef $self->{"start"}->{$part};
	undef $self->{"size"}->{$part};
    }
}

sub list {
    my $self = shift;
    my @k = ();
    for (keys %{$self->{"start"}}) {
	push @k, $_ unless $_ eq $all;
    }
    return @k;
}

sub start {
    my ($self, $part) = @_;
    return $self->{"start"}->{$part};
}

sub size {
    my ($self, $part) = @_;
    return $self->{"size"}->{$part};
}

# Utility functions. Should treat structure as black box.

sub find_low {
    my ($self, $last_part) = @_;
    my ($found);

    $found = 0;

    for (sort {$self->start($a) <=> $self->start($b)} $self->list()) {
	return $_ unless defined $last_part;
	$found = 1, next if $_ eq $last_part;
	return $_ if $found;
    }
    undef;
}

sub complement {
    my ($self) = @_;
    my ($floor) = $self->start($all);
    my ($ceiling) = $self->size($all);
    local ($complement) = new partition ($floor, $ceiling);
    my ($i, $part);

    $i = 0;
    while (1) {
	$part = $self->find_low($part);
	last unless defined $part;
	if ($self->start($part) > $floor) {
	    $complement->add(++$i, $floor, $self->start($part) - $floor);
	}
	if ($self->start($part) + $self->size($part) > $floor) {
	    $floor = $self->start($part) + $self->size($part);
	}
    }
    if ($floor < $ceiling) {
	$complement->add(++$i, $floor, $ceiling - $floor);
    }
    return $complement;
}

sub overlap {
    my ($self) = @_;
    my ($overlap) = new partition ($self->start($all), $self->size($all));
    my ($part, $start, $size);

    while ($part = $self->find_low ($part)) {
	$start = $self->start($part);
	$end = $start + $self->size($part);
	
	for ($self->list()) {
	    my ($start2) = $self->start($_);
	    my ($end2) = $start2 + $self->size($_);

	    next if $_ eq $part;
	    if ($end >= $start2 && $end < $end2) {
		my ($ostart) = ($start > $start2) ? $start : $start2;
		next if $end == $ostart;
		$overlap->add("$part,$_", $ostart, $end - $ostart);
	    } elsif ($start < $start2 && $end >= $end2) {
		next if $end2 == $start2;
		$overlap->add("$part,$_", $start2, $end2 - $start2);
	    }
	}
    }
    return $overlap;
}

sub debug_dump {
    my ($self) = shift;
    for (keys %{$self->{"start"}}) {
	print $_, ": start ", $self->{"start"}->{$_},
	" size ", $self->{"size"}->{$_}, "\n";
    }
}

1;