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 # Example of an 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         # The first node of the list if any
  25         # The special case of an empty list is handled by a null node
  26         private var node: nullable CLNode[E] = null
  27
  28         redef fun iterator do return new CircularListIterator[E](self)
  29
  30         redef fun first do return self.node.item
  31
  32         redef fun push(e)
  33         do
  34                 var new_node = new CLNode[E](e)
  35                 var n = self.node
  36                 if n == null then
  37                         # the first node
  38                         self.node = new_node
  39                 else
  40                         # not the first one, so attach nodes correctly.
  41                         var old_last_node = n.prev
  42                         new_node.next = n
  43                         new_node.prev = old_last_node
  44                         old_last_node.next = new_node
  45                         n.prev = new_node
  46                 end
  47         end
  48
  49         redef fun pop
  50         do
  51                 var n = self.node
  52                 assert n != null
  53                 var prev = n.prev
  54                 if prev == n then
  55                         # the only node
  56                         self.node = null
  57                         return n.item
  58                 end
  59                 # not the only one do detach nodes correctly.
  60                 var prev_prev = prev.prev
  61                 n.prev = prev_prev
  62                 prev_prev.next = n
  63                 return prev.item
  64         end
  65
  66         redef fun unshift(e)
  67         do
  68                 # Circularity has benefits.
  69                 push(e)
  70                 self.node = self.node.prev
  71         end
  72
  73         redef fun shift
  74         do
  75                 # Circularity has benefits.
  76                 self.node = self.node.next
  77                 return self.pop
  78         end
  79
  80         # Move the first at the last position, the second at the first, etc.
  81         fun rotate
  82         do
  83                 var n = self.node
  84                 if n == null then return
  85                 self.node = n.next
  86         end
  87
  88         # Sort the list using the Josephus algorithm.
  89         fun josephus(step: Int)
  90         do
  91                 var res = new CircularList[E]
  92                 while not self.is_empty do
  93                         # count 'step'
  94                         for i in [1..step[ do self.rotate
  95                         # kill
  96                         var x = self.shift
  97                         res.add(x)
  98                 end
  99                 self.node = res.node
 100         end
 101 end
 102
 103 # Nodes of a CircularList
 104 private class CLNode[E]
 105         # The current item
 106         var item: E
 107
 108         # The next item in the circular list.
 109         # Because of circularity, there is always a next;
 110         # so by default let it be self
 111         var next: CLNode[E] = self
 112
 113         # The previous item in the circular list.
 114         # Coherence between next and previous nodes has to be maintained by the
 115         # circular list.
 116         var prev: CLNode[E] = self
 117 end
 118
 119 # An iterator of a CircularList.
 120 private class CircularListIterator[E]
 121         super IndexedIterator[E]
 122
 123         redef var index: Int = 0
 124
 125         # The current node pointed.
 126         # Is null if the list is empty.
 127         var node: nullable CLNode[E] is noinit
 128
 129         # The list iterated.
 130         var list: CircularList[E]
 131
 132         redef fun is_ok
 133         do
 134                 # Empty lists are not OK.
 135                 # Pointing again the first node is not OK.
 136                 return self.node != null and (self.index == 0 or self.node != self.list.node)
 137         end
 138
 139         redef fun next
 140         do
 141                 self.node = self.node.next
 142                 self.index += 1
 143         end
 144
 145         redef fun item do return self.node.item
 146
 147         init
 148         do
 149                 self.node = list.node
 150         end
 151 end
 152
 153 var i = new CircularList[Int]
 154 i.add_all([1, 2, 3, 4, 5, 6, 7])
 155 print i.first
 156 print i.join(":")
 157
 158 i.push(8)
 159 print i.shift
 160 print i.pop
 161 i.unshift(0)
 162 print i.join(":")
 163
 164 i.josephus(3)
 165 print i.join(":")