1# ex:ts=8 sw=4: 2# $OpenBSD: UList.pm,v 1.2 2014/04/20 17:34:26 zhuk Exp $ 3# 4# Copyright (c) 2013 Vadim Zhukov <zhuk@openbsd.org> 5# 6# Permission to use, copy, modify, and distribute this software for any 7# purpose with or without fee is hereby granted, provided that the above 8# copyright notice and this permission notice appear in all copies. 9# 10# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 11# WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 12# MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 13# ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 14# WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 15# ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 16# OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 17 18use strict; 19use warnings; 20use feature qw(say); 21 22# Hash that preserves order of adding items and avoids duplicates. 23# Also, some additional restrictions are applied to make sure 24# the usage of this list is straightforward. 25 26package LT::UList; 27require Tie::Array; 28 29our @ISA = qw(Tie::Array); 30 31sub _translate_num_key($$;$) { 32 if ($_[1] < 0) { 33 $_[1] = @{$_[0]} - (-$_[1]); 34 die "invalid index" if $_[1] < 1; 35 } else { 36 $_[1] += 1; 37 } 38 die "invalid index" if $_[1] - int($_[2] // 0) >= @{$_[0]}; 39} 40 41# Construct new UList and returnes reference to the array, 42# not to the tied object itself. 43sub new { 44 my $class = shift; 45 tie(my @a, $class, @_); 46 return \@a; 47} 48 49# Given we have successfully added N directories: 50# self->[0] = { directory => 1 } 51# self->[1 .. N] = directories in the order of addition, represented as 0..N-1 52 53sub TIEARRAY { 54 my $class = shift; 55 my $self = bless [ {} ], $class; 56 $self->PUSH(@_); 57 return $self; 58} 59 60# Unfortunately, exists() checks for the value being integer even in the 61# case we have EXISTS() outta there. So if you really need to check the 62# presence of particular item, call the method below on the reference 63# returned by tie() or tied() instead. 64sub exists { return exists $_[0]->[0]->{$_[1]}; } 65 66sub FETCHSIZE { return scalar(@{$_[0]}) - 1; } 67 68# not needed 69sub STORE { die "unimplemented and should not be used"; } 70sub DELETE { die "unimplemented and should not be used"; } 71sub EXTEND { } 72 73sub FETCH 74{ 75 my ($self, $key) = (shift, shift); 76 77 # ignore? 78 die "undef given instead of directory or index" unless defined $key; 79 80 $self->_translate_num_key($key); 81 return $self->[$key]; 82} 83 84sub STORESIZE 85{ 86 my ($self, $newsz) = (shift, shift() + 2); 87 my $sz = @$self; 88 89 if ($newsz > $sz) { 90 # XXX any better way to grow? 91 $self->[$newsz - 1] = undef; 92 } elsif ($newsz < $sz) { 93 $self->POP() for $newsz .. $sz - 1; 94 } 95} 96 97sub PUSH 98{ 99 my $self = shift; 100 for (@_) { 101 next if exists $self->[0]->{$_}; 102 $self->[0]->{$_} = @$self; 103 push(@$self, $_); 104 } 105} 106 107sub POP 108{ 109 my $self = shift; 110 return undef if @$self < 2; 111 my $key = pop @$self; 112 delete $self->[0]->{$key}; 113 return $key; 114} 115 116sub SHIFT 117{ 118 my $self = shift; 119 return undef if @$self < 2; 120 my $key = splice(@$self, 1, 1); 121 delete $self->[0]->{$key}; 122 return $key; 123} 124 125sub UNSHIFT 126{ 127 my $self = shift; 128 $self->SPLICE(0, 0, @_); 129} 130 131sub SPLICE 132{ 133 my $self = shift; 134 135 my $offset = shift // 0; 136 $self->_translate_num_key($offset, 1); 137 my $maxrm = @$self - $offset; 138 139 my $length = shift; 140 if (defined $length) { 141 $length = $maxrm - (-$length) if $length < 0; 142 $length = $maxrm if $length > $maxrm; 143 } else { 144 $length = $maxrm; 145 } 146 147 # do not ever dream of adding items here 148 my @ret = splice(@$self, $offset, $length); 149 150 for (@ret) { 151 delete $self->[0]->{$_}; 152 } 153 for ($offset .. scalar(@$self) - 1) { 154 $self->[0]->{$self->[$_]} -= $length; 155 } 156 157 return @ret unless scalar(@_); 158 159 if ($length == $maxrm) { 160 # simply add items to the end 161 $self->PUSH(@_); 162 return @ret; 163 } 164 165 my $newpos = $offset; 166 for (@_) { 167 my $index = $self->[0]->{$_}; 168 if (defined $index) { 169 if ($index < $offset) { 170 # skip current item totally 171 continue; 172 } elsif ($index == $offset) { 173 # skip adding but act as if added 174 $self->[0]->{$_} += $newpos - $offset; 175 $newpos++; 176 next; 177 } 178 splice(@$self, $index, 1); 179 } 180 splice(@$self, $newpos, 0, $_); 181 $self->[0]->{$_} = $newpos++; 182 } 183 for ($newpos .. scalar(@$self) - 1) { 184 $self->[0]->{$self->[$_]} += $newpos - $offset; 185 } 186 return @ret; 187} 188 189 190=head1 test 191package main; 192 193my $r = ['/path0', '/path1']; 194tie(@$r, 'LT::UList'); 195#push(@$r, '/path0'); 196#push(@$r, '/path1'); 197push(@$r, '/path2'); 198push(@$r, '/path3'); 199push(@$r, '/path4'); 200push(@$r, '/path3'); 201push(@$r, '/path1'); 202push(@$r, '/path5'); 203say "spliced: ".join(", ", splice(@$r, 2, 2, '/pathAdd1', '/pathAdd2', '/pathAdd1')); 204#say "a: ".join(", ", @a); 205say "r: ".join(", ", @$r); 206#say "r2: ".join(", ", @$r2); 207=cut 208