1 "

     2  COPYRIGHT (c) 2016 by eXept Software AG

     3               All Rights Reserved

     4 

     5  This software is furnished under a license and may be used

     6  only in accordance with the terms of that license and with the

     7  inclusion of the above copyright notice.   This software may not

     8  be provided or otherwise made available to, or used by, any

     9  other person.  No title to or ownership of the software is

    10  hereby transferred.

    11 "

    12 "{ Package: 'stx:libbasic2' }"

    13 

    14 "{ NameSpace: Smalltalk }"

    15 

    16 LinkedList subclass:#DoubleLinkedList

    17 	instanceVariableNames:''

    18 	classVariableNames:''

    19 	poolDictionaries:''

    20 	category:'Collections-Linked'

    21 !

    22 

    23 !DoubleLinkedList class methodsFor:'documentation'!

    24 

    25 copyright

    26 "

    27  COPYRIGHT (c) 2016 by eXept Software AG

    28               All Rights Reserved

    29 

    30  This software is furnished under a license and may be used

    31  only in accordance with the terms of that license and with the

    32  inclusion of the above copyright notice.   This software may not

    33  be provided or otherwise made available to, or used by, any

    34  other person.  No title to or ownership of the software is

    35  hereby transferred.

    36 "

    37 !

    38 

    39 examples

    40 "

    41                                                                         [exBegin]

    42     |l|

    43 

    44     l := DoubleLinkedList new.

    45     l addLast:'one'.

    46     l addLast:'two'.

    47     l addLast:'three'.

    48     l addLast:'four'.

    49     l inspect

    50                                                                         [exEnd]

    51 

    52 

    53                                                                         [exBegin]

    54     |l|

    55 

    56     l := LinkedList new.

    57     l addLast:(ValueDoubleLink new value:'one').

    58     l addLast:(ValueDoubleLink new value:'two').

    59     l addLast:(ValueDoubleLink new value:'three').

    60     l addLast:(ValueDoubleLink new value:'four').

    61     (l at:3) value inspect.        'slow operation for large lists'.

    62                                                                         [exEnd]

    63 

    64 

    65                                                                         [exBegin]

    66     |l link|

    67 

    68     l := LinkedList new.

    69     l addLast:(ValueDoubleLink new value:'one').

    70     l addLast:(ValueDoubleLink new value:'two').

    71     l addLast:(ValueDoubleLink new value:'three').

    72     l addLast:(ValueDoubleLink new value:'four').

    73     link := l removeFirst.

    74     l addLast:link.

    75     l inspect.

    76                                                                         [exEnd]

    77 "

    78 ! !

    79 

    80 !DoubleLinkedList methodsFor:'adding & removing'!

    81 

    82 add:aLinkOrAnyOtherObject

    83     "adds aLink to the end of the sequence. Returns aLink"

    84 

    85     |newLink|

    86 

    87     newLink := aLinkOrAnyOtherObject asDoubleLink.

    88 

    89     newLink nextLink:nil.

    90     newLink previousLink:lastLink.

    91     lastLink isNil ifTrue:[

    92         firstLink := newLink

    93     ] ifFalse: [

    94         lastLink nextLink:newLink

    95     ].

    96     lastLink := newLink.

    97     numberOfNodes := numberOfNodes + 1.

    98     ^ newLink

    99 

   100     "

   101      |l e1 e2|

   102      l := DoubleLinkedList new.

   103      e1 := l add:'one'.

   104      e2 := l add:'two'.

   105      self assert:(l firstLink == e1).

   106      self assert:(l lastLink == e2).

   107      self assert:(e1 nextLink == e2).

   108      self assert:(e2 nextLink isNil).

   109      self assert:(e1 previousLink isNil).

   110      self assert:(e2 previousLink == e1).

   111     "

   112 !

   113 

   114 add:aLinkOrAnyOtherObject after:aLinkOrValue

   115     |linkToAddAfter newLink this nextLink|

   116 

   117     aLinkOrValue asDoubleLink == aLinkOrValue ifTrue:[

   118         linkToAddAfter := aLinkOrValue

   119     ] ifFalse:[

   120         this := firstLink.

   121         [this notNil and:[this value ~~ aLinkOrAnyOtherObject]] whileTrue:[

   122             this := this nextLink

   123         ].

   124         this isNil ifTrue:[

   125             ^ self addLast:aLinkOrAnyOtherObject

   126         ].

   127         linkToAddAfter := this.

   128     ].

   129     newLink := aLinkOrAnyOtherObject asDoubleLink.

   130 

   131     newLink nextLink:(nextLink := linkToAddAfter nextLink).

   132     newLink previousLink:linkToAddAfter.

   133     linkToAddAfter nextLink:newLink.

   134     nextLink isNil ifTrue:[

   135         lastLink := newLink

   136     ] ifFalse:[

   137         nextLink previousLink:newLink.

   138     ].

   139     numberOfNodes := numberOfNodes + 1.

   140     ^ newLink

   141 

   142     "

   143      |l e1 e2 e3 e2_5 e4|

   144      l := DoubleLinkedList new.

   145      e1 := l add:'one'.

   146      e2 := l add:'two'.

   147      e3 := l add:'three'.

   148      self assert:(l firstLink == e1).

   149      self assert:(e1 nextLink == e2).

   150      self assert:(e2 nextLink == e3).

   151      self assert:(e3 nextLink isNil).

   152 

   153      self assert:(l lastLink == e3).

   154      self assert:(e3 previousLink == e2).

   155      self assert:(e2 previousLink == e1).

   156      self assert:(e1 previousLink isNil).

   157 

   158      e2_5 := l add:'twoPointFife' after:e2.

   159      self assert:(l firstLink == e1).

   160      self assert:(e1 nextLink == e2).

   161      self assert:(e2 nextLink == e2_5).

   162      self assert:(e2_5 nextLink == e3).

   163      self assert:(e3 nextLink isNil).

   164 

   165      self assert:(l lastLink == e3).

   166      self assert:(e3 previousLink == e2_5).

   167      self assert:(e2_5 previousLink == e2).

   168      self assert:(e2 previousLink == e1).

   169      self assert:(e1 previousLink isNil).

   170 

   171      e4 := l add:'four' after:e3.

   172      self assert:(l firstLink == e1).

   173      self assert:(e1 nextLink == e2).

   174      self assert:(e2 nextLink == e2_5).

   175      self assert:(e2_5 nextLink == e3).

   176      self assert:(e3 nextLink == e4).

   177      self assert:(e4 nextLink isNil).

   178 

   179      self assert:(l lastLink == e4).

   180      self assert:(e4 previousLink == e3).

   181      self assert:(e3 previousLink == e2_5).

   182      self assert:(e2_5 previousLink == e2).

   183      self assert:(e2 previousLink == e1).

   184      self assert:(e1 previousLink isNil).

   185     "

   186 !

   187 

   188 addFirst:aLinkOrAnyOtherObject

   189     "adds aLink to the beginning of the sequence. Returns aLink"

   190 

   191     |newLink|

   192 

   193     newLink := aLinkOrAnyOtherObject asDoubleLink.

   194 

   195     newLink nextLink:firstLink.

   196     firstLink isNil ifTrue:[

   197         lastLink := newLink

   198     ] ifFalse: [

   199         firstLink previousLink:newLink

   200     ].

   201     firstLink := newLink.

   202     numberOfNodes := numberOfNodes + 1.

   203     ^ newLink

   204 

   205     "

   206      |l e1 e0|

   207      l := DoubleLinkedList new.

   208      e1 := l add:'one'.

   209      e0 := l addFirst:'zero'.

   210      self assert:(l firstLink == e0).

   211      self assert:(l lastLink == e1).

   212      self assert:(e0 nextLink == e1).

   213      self assert:(e1 nextLink isNil).

   214      self assert:(e0 previousLink isNil).

   215      self assert:(e1 previousLink == e0).

   216     "

   217 !

   218 

   219 remove:aLinkOrValue ifAbsent:exceptionBlock

   220     "remove the argument, aLinkOrValue from the sequence and return it;

   221      if absent, evaluate the exceptionBlock."

   222 

   223     |linkToRemove this nextLink previousLink|

   224 

   225     aLinkOrValue asDoubleLink == aLinkOrValue ifTrue:[

   226         linkToRemove := aLinkOrValue

   227     ] ifFalse:[

   228         this := firstLink.

   229         [this notNil and:[this value ~= aLinkOrValue]] whileTrue:[

   230             this := this nextLink

   231         ].

   232         this isNil ifTrue:[

   233             ^ exceptionBlock value

   234         ].

   235         linkToRemove := this.

   236     ].

   237 

   238     nextLink := linkToRemove nextLink.

   239     previousLink := linkToRemove previousLink.

   240     nextLink notNil ifTrue:[

   241         nextLink previousLink:previousLink.

   242     ] ifFalse:[

   243         lastLink := previousLink

   244     ].

   245     previousLink notNil ifTrue:[

   246         previousLink nextLink:nextLink.

   247     ] ifFalse:[

   248         firstLink := nextLink

   249     ].

   250     numberOfNodes := numberOfNodes - 1.

   251     ^ linkToRemove

   252 

   253     "

   254      |l e1 e2 e3 e2_5 e4|

   255      l := DoubleLinkedList new.

   256      e1 := l add:'one'.

   257      e2 := l add:'two'.

   258      e3 := l add:'three'.

   259      self assert:(l firstLink == e1).

   260      self assert:(e1 nextLink == e2).

   261      self assert:(e2 nextLink == e3).

   262      self assert:(e3 nextLink isNil).

   263 

   264      self assert:(l lastLink == e3).

   265      self assert:(e3 previousLink == e2).

   266      self assert:(e2 previousLink == e1).

   267      self assert:(e1 previousLink isNil).

   268 

   269      l remove:'two'.

   270      self assert:(l firstLink == e1).

   271      self assert:(e1 nextLink == e3).

   272      self assert:(e3 nextLink isNil).

   273 

   274      self assert:(l lastLink == e3).

   275      self assert:(e3 previousLink == e1).

   276      self assert:(e1 previousLink isNil).

   277 

   278      l remove:'one'.

   279      self assert:(l firstLink == e3).

   280      self assert:(e3 nextLink isNil).

   281 

   282      self assert:(l lastLink == e3).

   283      self assert:(e3 previousLink isNil).

   284 

   285      l remove:'three'.

   286      self assert:(l size == 0).

   287     "

   288 !

   289 

   290 removeFirst

   291     "remove and return the first node from the sequence"

   292 

   293     |link|

   294 

   295     firstLink isNil ifTrue:[

   296         ^ self emptyCollectionError

   297     ].

   298     link := firstLink.

   299     firstLink := firstLink nextLink.

   300     firstLink isNil ifTrue:[

   301         lastLink := nil

   302     ] ifFalse:[ 

   303         firstLink previousLink:nil.

   304     ].        

   305     link nextLink:nil.

   306     link previousLink:nil.

   307     numberOfNodes := numberOfNodes - 1.

   308     ^ link

   309 

   310     "

   311      |l v1 v2 v3 e1 e2 e3 e2_5 e4|

   312 

   313      l := DoubleLinkedList new.

   314      e1 := l add:'one'.

   315      e2 := l add:'two'.

   316      e3 := l add:'three'.

   317      self assert:(l firstLink == e1).

   318      self assert:(e1 nextLink == e2).

   319      self assert:(e2 nextLink == e3).

   320      self assert:(e3 nextLink isNil).

   321 

   322      self assert:(l lastLink == e3).

   323      self assert:(e3 previousLink == e2).

   324      self assert:(e2 previousLink == e1).

   325      self assert:(e1 previousLink isNil).

   326 

   327      l removeFirst.

   328      self assert:(l firstLink == e2).

   329      self assert:(e2 nextLink == e3).

   330      self assert:(e3 nextLink isNil).

   331 

   332      self assert:(l lastLink == e3).

   333      self assert:(e3 previousLink == e2).

   334      self assert:(e2 previousLink isNil).

   335 

   336      l removeFirst.

   337      self assert:(l firstLink == e3).

   338      self assert:(e3 nextLink isNil).

   339 

   340      self assert:(l lastLink == e3).

   341      self assert:(e3 previousLink isNil).

   342 

   343      l removeFirst.

   344      self assert:(l size == 0).

   345     "

   346 !

   347 

   348 removeIdentical:aLinkOrValue ifAbsent:exceptionBlock

   349     "remove the argument, aLinkOrValue from the sequence and return it;

   350      if absent, evaluate the exceptionBlock."

   351 

   352     |linkToRemove this nextLink previousLink|

   353 

   354     aLinkOrValue asDoubleLink == aLinkOrValue ifTrue:[

   355         linkToRemove := aLinkOrValue

   356     ] ifFalse:[

   357         this := firstLink.

   358         [this notNil and:[this value ~~ aLinkOrValue]] whileTrue:[

   359             this := this nextLink

   360         ].

   361         this isNil ifTrue:[

   362             ^ exceptionBlock value

   363         ].

   364         linkToRemove := this.

   365     ].

   366 

   367     nextLink := linkToRemove nextLink.

   368     previousLink := linkToRemove previousLink.

   369     nextLink notNil ifTrue:[

   370         nextLink previousLink:previousLink.

   371     ] ifFalse:[

   372         lastLink := previousLink

   373     ].

   374     previousLink notNil ifTrue:[

   375         previousLink nextLink:nextLink.

   376     ] ifFalse:[

   377         firstLink := nextLink

   378     ].

   379     numberOfNodes := numberOfNodes - 1.

   380     ^ linkToRemove

   381 

   382     "

   383      |l v1 v2 v3 e1 e2 e3 e2_5 e4|

   384      l := DoubleLinkedList new.

   385      e1 := l add:(v1 := 'one').

   386      e2 := l add:(v2 := 'two').

   387      e3 := l add:(v3 := 'three').

   388      self assert:(l firstLink == e1).

   389      self assert:(e1 nextLink == e2).

   390      self assert:(e2 nextLink == e3).

   391      self assert:(e3 nextLink isNil).

   392 

   393      self assert:(l lastLink == e3).

   394      self assert:(e3 previousLink == e2).

   395      self assert:(e2 previousLink == e1).

   396      self assert:(e1 previousLink isNil).

   397 

   398      l removeIdentical:v2.

   399      self assert:(l firstLink == e1).

   400      self assert:(e1 nextLink == e3).

   401      self assert:(e3 nextLink isNil).

   402 

   403      self assert:(l lastLink == e3).

   404      self assert:(e3 previousLink == e1).

   405      self assert:(e1 previousLink isNil).

   406 

   407      l removeIdentical:v1.

   408      self assert:(l firstLink == e3).

   409      self assert:(e3 nextLink isNil).

   410 

   411      self assert:(l lastLink == e3).

   412      self assert:(e3 previousLink isNil).

   413 

   414      l removeIdentical:v3.

   415      self assert:(l size == 0).

   416     "

   417 !

   418 

   419 removeLast

   420     "remove and return the last node from the sequence"

   421 

   422     |link|

   423 

   424     lastLink isNil ifTrue:[

   425         ^ self emptyCollectionError

   426     ].

   427     link := lastLink.

   428     lastLink := lastLink previousLink.

   429     lastLink isNil ifTrue:[

   430         firstLink := nil

   431     ] ifFalse:[ 

   432         lastLink nextLink:nil.

   433     ].        

   434     link nextLink:nil.

   435     link previousLink:nil.

   436     numberOfNodes := numberOfNodes - 1.

   437     ^ link

   438 

   439     "

   440      |l v1 v2 v3 e1 e2 e3 e2_5 e4|

   441 

   442      l := DoubleLinkedList new.

   443      e1 := l add:'one'.

   444      e2 := l add:'two'.

   445      e3 := l add:'three'.

   446      self assert:(l firstLink == e1).

   447      self assert:(e1 nextLink == e2).

   448      self assert:(e2 nextLink == e3).

   449      self assert:(e3 nextLink isNil).

   450 

   451      self assert:(l lastLink == e3).

   452      self assert:(e3 previousLink == e2).

   453      self assert:(e2 previousLink == e1).

   454      self assert:(e1 previousLink isNil).

   455 

   456      l removeLast.

   457      self assert:(l firstLink == e1).

   458      self assert:(e1 nextLink == e2).

   459      self assert:(e2 nextLink isNil).

   460 

   461      self assert:(l lastLink == e2).

   462      self assert:(e2 previousLink == e1).

   463      self assert:(e1 previousLink isNil).

   464 

   465      l removeLast.

   466      self assert:(l firstLink == e1).

   467      self assert:(e1 nextLink isNil).

   468 

   469      self assert:(l lastLink == e1).

   470      self assert:(e1 previousLink isNil).

   471 

   472      l removeLast.

   473      self assert:(l size == 0).

   474     "

   475 ! !

   476 

   477 !DoubleLinkedList class methodsFor:'documentation'!

   478 

   479 version

   480     ^ '$Header$'

   481 !

   482 

   483 version_CVS

   484     ^ '$Header$'

   485 ! !

   486