SCClassLibrary/Common/Collections/LinkedList.sc

   1 LinkedListNode {
   2         var <>prev, <>next, <>obj;
   3         // this class supports the LinkedList class
   4
   5         *new { arg item;
   6                 ^super.new.obj_(item)
   7         }
   8         remove {
   9                 if (prev.notNil, { prev.next_(next); });
  10                 if (next.notNil, { next.prev_(prev); });
  11                 next = prev = nil;
  12         }
  13 }
  14
  15 LinkedList : SequenceableCollection {
  16         var head, tail, <size = 0;
  17
  18
  19         copy {
  20                 var copy = LinkedList.new;
  21                 this.do {|item| copy.add(item) }
  22                 ^copy
  23         }
  24         species { ^this.class }
  25         do { arg function;
  26                 var i = 0;
  27                 var node = head;
  28                 while ({ node.notNil },{
  29                         function.value(node.obj, i);
  30                         node = node.next;
  31                         i = i + 1;
  32                 });
  33         }
  34         reverseDo { arg function;
  35                 var i = size - 1;
  36                 var node = tail;
  37                 while ({ node.notNil },{
  38                         function.value(node.obj, i);
  39                         node = node.prev;
  40                         i = i - 1;
  41                 });
  42         }
  43         addFirst { arg obj;
  44                 var node = LinkedListNode.new(obj);
  45                 if (head.notNil, {
  46                         node.next_(head);
  47                         head.prev_(node);
  48                 });
  49                 head = node;
  50                 if (tail.isNil, {
  51                         tail = node;
  52                 });
  53                 size = size + 1;
  54         }
  55         add { arg obj;
  56                 var node = LinkedListNode.new(obj);
  57                 if (tail.notNil, {
  58                         node.prev_(tail);
  59                         tail.next_(node);
  60                 });
  61                 tail = node;
  62                 if (head.isNil, {
  63                         head = node;
  64                 });
  65                 size = size + 1;
  66         }
  67         remove { arg obj;
  68                 var node = this.findNodeOfObj(obj);
  69                 if ( node.notNil, {
  70                         if (head == node, { head = node.next; });
  71                         if (tail == node, { tail = node.prev; });
  72                         node.remove;
  73                         size = size - 1;
  74                 });
  75         }
  76         pop {
  77                 var node;
  78                 if ( tail.notNil, {
  79                         node = tail;
  80                         tail = node.prev;
  81                         if (head == node, { head = nil; });
  82                         node.remove;
  83                         size = size - 1;
  84                         ^node.obj
  85                 },{
  86                         ^nil
  87                 });
  88
  89         }
  90         popFirst {
  91                 var node;
  92                 if ( head.notNil, {
  93                         node = head;
  94                         head = node.next;
  95                         if (tail == node, { tail = nil; });
  96                         node.remove;
  97                         size = size - 1;
  98                         ^node.obj
  99                 },{
 100                         ^nil
 101                 });
 102
 103         }
 104
 105         first { if (head.notNil, { ^head.obj },{ ^nil }) }
 106         last  { if (tail.notNil, { ^tail.obj },{ ^nil }) }
 107
 108         at { arg index;
 109                 var node = this.nodeAt(index);
 110                 if (node.notNil, {
 111                         ^node.obj
 112                 },{
 113                         ^nil
 114                 })
 115         }
 116         put { arg index, item;
 117                 var node = this.nodeAt(index);
 118                 if (node.notNil, {
 119                         node.obj_(item);
 120                 });
 121         }
 122         removeAt { arg index;
 123                 var node = this.nodeAt(index);
 124                 if (node.notNil, {
 125                         if (head == node, { head = node.next; });
 126                         if (tail == node, { tail = node.prev; });
 127                         node.remove;
 128                         size = size - 1;
 129                         ^node.obj
 130                 },{
 131                         ^nil
 132                 });
 133         }
 134         // private
 135         nodeAt { arg index;
 136                 var i = 0, node;
 137                 if ( index >= 0 and: { index < size }, {
 138                         if (index < (size - index), {
 139                                 node = head;
 140                                 while ({ i != index },{
 141                                         node = node.next;
 142                                         i = i + 1;
 143                                 });
 144                                 ^node
 145                         },{
 146                                 i = size - 1;
 147                                 node = tail;
 148                                 while ({ i != index },{
 149                                         node = node.prev;
 150                                         i = i - 1;
 151                                 });
 152                                 ^node
 153                         });
 154                 },{
 155                         this.indexOutOfRange;
 156                         ^nil
 157                 })
 158         }
 159
 160         findNodeOfObj { arg obj;
 161                 var node = head;
 162                 while ({ node.notNil },{
 163                         if (node.obj == obj, { ^node });
 164                         node = node.next;
 165                 });
 166                 ^nil
 167         }
 168 }