examples/circular_list.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Licensed under the Apache License, Version 2.0 (the "License");
   4 # you may not use this file except in compliance with the License.
   5 # You may obtain a copy of the License at
   6 #
   7 #     http://www.apache.org/licenses/LICENSE-2.0
   8 #
   9 # Unless required by applicable law or agreed to in writing, software
  10 # distributed under the License is distributed on an "AS IS" BASIS,
  11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 # See the License for the specific language governing permissions and
  13 # limitations under the License.
  14
  15 # Implementation of circular lists
  16 # This example shows the usage of generics and somewhat a specialisation of collections.
  17 module circular_list
  18
  19 # Sequences of elements implemented with a double-linked circular list
  20 class CircularList[E]
  21         # Like standard Array or LinkedList, CircularList is a Sequence.
  22         super Sequence[E]
  23
  24         # NaiveCollection contains working (but inefficient) implementation of
  25         # the methods of Collection.
  26         super NaiveCollection[E]
  27
  28         # The first node of the list if any
  29         # The special case of an empty list is handled by a null node
  30         private var node: nullable CLNode[E] = null
  31
  32         redef fun iterator do return new CircularListIterator[E](self)
  33
  34         redef fun first do return self.node.item
  35
  36         redef fun push(e)
  37         do
  38                 var new_node = new CLNode[E](e)
  39                 var n = self.node
  40                 if n == null then
  41                         # the first node
  42                         self.node = new_node
  43                 else
  44                         # not the first one, so attach nodes correctly.
  45                         var old_last_node = n.prev
  46                         new_node.next = n
  47                         new_node.prev = old_last_node
  48                         old_last_node.next = new_node
  49                         n.prev = new_node
  50                 end
  51         end
  52
  53         redef fun pop
  54         do
  55                 var n = self.node
  56                 assert n != null
  57                 var prev = n.prev
  58                 if prev == n then
  59                         # the only node
  60                         self.node = null
  61                         return n.item
  62                 end
  63                 # not the only one do detach nodes correctly.
  64                 var prev_prev = prev.prev
  65                 n.prev = prev_prev
  66                 prev_prev.next = n
  67                 return prev.item
  68         end
  69
  70         redef fun unshift(e)
  71         do
  72                 # Circularity has benefits.
  73                 push(e)
  74                 self.node = self.node.prev
  75         end
  76
  77         redef fun shift
  78         do
  79                 # Circularity has benefits.
  80                 self.node = self.node.next
  81                 return self.pop
  82         end
  83
  84         # Move the first at the last position, the second at the first, etc.
  85         fun rotate
  86         do
  87                 var n = self.node
  88                 if n == null then return
  89                 self.node = n.next
  90         end
  91
  92         # Sort the list using the Josephus algorithm.
  93         fun josephus(step: Int)
  94         do
  95                 var res = new CircularList[E]
  96                 while not self.is_empty do
  97                         # count 'step'
  98                         for i in [1..step[ do self.rotate
  99                         # kill
 100                         var x = self.shift
 101                         res.add(x)
 102                 end
 103                 self.node = res.node
 104         end
 105 end
 106
 107 # Nodes of a CircularList
 108 private class CLNode[E]
 109         # The current item
 110         var item: E
 111
 112         # The next item in the circular list.
 113         # Because of circularity, there is always a next;
 114         # so by default let it be self
 115         var next: CLNode[E] = self
 116
 117         # The previous item in the circular list.
 118         # Coherence between next and previous nodes has to be maintained by the
 119         # circular list.
 120         var prev: CLNode[E] = self
 121 end
 122
 123 # An iterator of a CircularList.
 124 private class CircularListIterator[E]
 125         super IndexedIterator[E]
 126
 127         redef var index: Int
 128
 129         # The current node pointed.
 130         # Is null if the list is empty.
 131         var node: nullable CLNode[E]
 132
 133         # The list iterated.
 134         var list: CircularList[E]
 135
 136         redef fun is_ok
 137         do
 138                 # Empty lists are not OK.
 139                 # Pointing again the first node is not OK.
 140                 return self.node != null and (self.index == 0 or self.node != self.list.node)
 141         end
 142
 143         redef fun next
 144         do
 145                 self.node = self.node.next
 146                 self.index += 1
 147         end
 148
 149         redef fun item do return self.node.item
 150
 151         init(list: CircularList[E])
 152         do
 153                 self.node = list.node
 154                 self.list = list
 155                 self.index = 0
 156         end
 157 end
 158
 159 var i = new CircularList[Int]
 160 i.add_all([1, 2, 3, 4, 5, 6, 7])
 161 print i.first
 162 print i.join(":")
 163
 164 i.push(8)
 165 print i.shift
 166 print i.pop
 167 i.unshift(0)
 168 print i.join(":")
 169
 170 i.josephus(3)
 171 print i.join(":")